У. Питерсон - Коды, исправляющие ошибки (1267328), страница 44
Текст из файла (страница 44)
Предположим теперь, что й~ (Х) — неприводимый множитель степени А~ в разложении на множители многочлена й(Х). Пусть а — корень й,(Х). Тогда над полем 6г (д) элемент к и его степени могут бгять представлены в виде векторов с А~ компонентами. Очевидно, что каждый элемент последовательности (7.7) должен удовлетворять рекуррентному соотношению. В теории линейных Пример.
Пусть а — корень многочлена Хз + Х' + 1 над полем бЕ(2). Тогда элементы поля в расширении поля бг(2') могут быть представлены в виде вектор-столбцов из трех компонент, принадлежащих бр(2): 1001110 (1, а, ап, пз, а~, а~, а~)= 0100111 (7. 9) 0011101 Каждая строка этой матрицы удовлетворяет рекуррентному соотношению а, +а~+2+а,+,—— О, соответствующему многочлену й(Х) = Х~+ Хх+ 1, Рассмотрим теперь многочлен Ь(Х) = (Х+ 1) (Хз+ Х+ 1) = = Х'+ Ха+Ха+ 1 и соответствующее рекуррентное соотношение аг+ацд+а;+а+а~+~ — — О.
Если !1 — корень многочлена Х'-1-Х-)-1, го элементы (1, р, рз, !3', р4, йх, Р') удовлетворяют рекуррентиому соотношению. Поскольку единственный корень многочлена (Х+1) равен 1, то ему соответствует последовательность (1, 1, 1, 1, 1, 1, 1). Используя представление элементов бг"(2') с помощью многочле- пов по модулю Х'+ Х+ 1, найдем, что последовательные степени элемента р задают первые три строки матрицы М, а последняя строка составлена из степеней элемента 1: 1001011 0101110 0010111 11111! 1 (7.10) Таким образом, каждая строка матрицы М определяет решение, и совокупность всех решений совпадает с пространством строк матрицы М. С другой стороны, рассмотрим алгебру мпогочленов по модулю Х4+ Ха+ Хз+ 1, и пусть через 5 обозначен класс вычетов, содержагций Х, Тогда, поскольку 5'+ 5з-)-5з+ 1 = О, то (1, 5.
5х, 5з, Я 5х, 5') (довлетворяют рекуррентному соотношению. (Напомним, что 5 ие есть элемент поля.) Поэтому каждый элемент алгебры может дифференциальных уравнений это аналогично следующему утверждению: если комплекснозначная функция удовлетворяет уравнению с действительными коэффициентами, то и действительная, я мнимая части комплексного решения являются действительными решениями уравнения. быть представлен в виде вектора: 1=(Ц =(0001), Я=(Х) = — (О 0 1 0), у= (Хэ) =(О 100), сз (Хз) =(1000), У (Хз ( У ) 1) (1101) Зз=(Хз+Х+1) =(0111), У=(Хз+Х'+Х)=(1110), и, записывая классы вычетов 1, 5, Вз, Я', 34, Зз, 36 в виде вектор- столбцов, получаем матрицу 1000110 0100011 0 010111 0001101 Каждая строка этой матрицы является решением рекуррентного соотношения, и каждое решение принадлежит пространству строк этой матрицы.
Существует еще один подход к этим вопросам, основанный на понятии «поля частных» многочленов. Строгое изложение этого вопроса дано Цирлером (342) Приведем здесь только основную теорему и пример. Согласно теореме Цирлера, если некоторый многочлен !(Х) степени й — 1 или меньше формально делить «столбиком» на многочлен й*(Х) = НеХ" + Ь,Хь-' + ... +Лм то коэффициенты оказывающегося бесконечным рядом частного удовлетворяют рекуррентному соотношению 4Ф!+й;пг ~+ " +~ЬР~+»=0.
Пример. Пусть Ь*(Х) = 1+ Х+ Х". Тогда, проводя деление «столбиком», получаем 1/(1+Х+Х')= 1+Х+Л"'+ Х4+Х'+Х'+Х'+Хи+ ... и последовательность коэффициентов 1 1 ! 0 ! 0 0 1 1 1 0 1 0 0 согласуется с любой строкой матрицы (7З). Схемы, рассматриваемые в этом разделе и в разд. 7.2, аналогичны линейным фильтрам и системам с обратной связью. Онн являются по существу системами обработки дискретной информации, и единственное важное отличие их от обычных систем состоит в том, что используемые здесь величины являются элементами конечного поля, а в обычных системах — действительными чнс- лами. Методы преобразований, используемые для таких систем, применимы и здесь; соответствующие математические методы обсуждались в предыдущих разделах. Эти идеи развиваются далее в следующем разделе, где рассматриваются также методы синтеза генератора со сдвигом регистра с заданной или частично заданной выходной последовательностью.
Теорема 7.! дает достаточно информации для того, чтобы без труда осуществить синтез генератора, если задан только его период. 7.5. У-преобразования, передаточные функции и синтез В этом разделе показывается, что вход, выход и переходный отклик в схемах, описанных в равд. 7.2, могут быть охарактеризованы при помощи передаточной функции. Из изложенного в равд. 7.6 видно, что это справедливо и для произвольной линейной последовательной схемы.
Таким образом, любая линейная последовательная схема описывается передаточной функцией, и две различные схемы с одной и той же передаточной функцией внешне неразличимы, т. е. неразличимы, если заданы только их входы и выходы, а не внутренние состояния. Более того, показано, что при любом заданном отношении многочленов существует схема типа схемы, описанной в равд. 7.2, для которой это отношение является ее передаточной функцией, и, таким образом, проблема синтеза передаточных функций решена. В этом разделе решена также проблема нахождения передаточной функции для заданных импульсного и переходного откликов.
Последовательности входных или выходных символов обозначаются через ПО 11н 11м где аа — первый символ. (Некоторое неудобство связано с тем, что здесь индексы возрастают со временем, тогда как мы условились всегда записывать миогочлены начиная с коэффициентов при степенях высших порядков; однако любой другой способ обозначений также привел бы к некоторым, конечно, не слишком существенным трудностям.) Проще всего представлять результаты, используя понятие 2-греобразования последовательности: а (Р) = а, + а1Р + а202+ (7.!2) Эту запись можно рассматривать также как формальный степенной ряд или просто как способ обозначения последовательности, (В частности, вместо Р используется обозначение у.) После умножения последовательности иа Р получается та же самая последовательность, сдвинутая иа один символ: Ра(0)=аоР+а,Рз+ азРз+ ....
Поэтому Р можно рассматривать как оператор сдвига. При действиях с миогочлеиами умножение миогочлеиа иа Х эквивалентно сдвигу коэффициента иа один разряд, а умножение иа Х вЂ” ' равносильно сдвигу в противоположную сторону иа один разряд. Таким образом, в некотором смысле Р = Х вЂ ''). Прямой аиализ операции умножения, производимой с помоецью схем, изображенных на фиг. 7.2 и 7.3, показывает, что в каждой из этих схем связь между входной последовательностью а(0) и выходной последовательностью Ь(0) задается разиостиым уравиеиием Ь(0) = Ь„а(0)+ Ь,Ра (.Р)+ Ь„аР'а(Р)+ ...
... + Ь,Р'а (0) = Ь" (0) а (0), (7.13) где Ь*(Х) = Ь„+ Ь„,Х+ ... + ЬоХ" — миогочлеи, двойственный к миогочлеиу Ь(Х) = Ь„Х'+ Ь,,Х"-'+ ... + Ьо. (Предполагается, что во всех разрядах вначале содержатся нули.) Таким образом, в этих схемах проводится просто умножение входной последовательности иа Ь*(0).
Миогочлеи Ь*(Р) называется передаточной тйункз(пей для этих схем. Конечно, эти схемы были предназначены для умножения. Причина того, что в иих происходит умножение иа двойственный миогочлеи Ь*(0), заключается в том, что Р = Х-'. Аналогично для схемы, изображенной иа фиг. 7.4, входные последовательности а,(0) и ая(0) связаны с выходной последовательностью Ь(0) разиостпым уравнением Ь(0) = Ь" (0) пз (В)+ Ь'(О) а,(0).
(7.1 4) !7рииер. Пусть иа вход каждой из схем, изображеииых на фиг. 7.5, подается последовательность 1 1 О 1 О 1 1 1 О О 1 .... Формально перемножая преобразование входной последовательности п(0) ! + В+Рз ! Рз+ Ра+Рт+01о ( и передаточную функцию Ь*(Р) = 1+ Р + Р'+ Рз+ Ра, получаем а (0) Ь'(0) = ! + Р + Р'+ Р'+ ОР" + ...; это выражение так же, как и произведение, может быть вычислено по заданным символам входной последовательности. Оио равно преобразованию выходной последовательности схемы.
'! Здесь учитывается, что коэффициенты мвоточаенов от Х записаны в обратном порядке. — Орши. рад. Схема, изображенная на фиг. 7.6, предназначена для деления, причем деление могкпо производить даже дпя входных последовательностей бесконечной длины. Если преобразование входной последовательности разделить формально на многочлен д(й — ') = = Р-"д'(й), то результат этого деления равен преобразованию выходной последовательности. Аналогично схема, предназначенная для умножения многочленов на Й(Х) и последующего деления результата на а(Х), дает (если не учитывать возможную задержку) тот же самый результат, к которому приводят формальное умножение на Ь*(й) и деление на а*(й). Пример. Если вход схемы, показанной на фиг.
7.7, равен 101100100110 11...,товыходравеп00000011 1 0 О 1 1 1 .... Это можно проверить, прослеживая работу схемы, но можно получить и формальным делением преобразования входа а(й) = 1+ й'+ Рз+ Рв+ йэ+ Рм+ Рм+ Р'"+ ... на Р— ад*(й) = й — '(1+ Р+ й'+ й'+ йв). Сравните этот пример с примером, иллюстрируемым табл. 7.1, где та же самая входная последовательность использовалась в другом контексте. Работа схемы деления также описывается некоторым разностным уравнением. Это уравнение следующим образом может быть выведено из уравнения, которое описывает схему умножения. Схема умножения с двумя входами, изображенная на фиг.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
