Конечные поля. Том 1 - Лидл Р.
ISBN 5-03-000065-8
Скачать (прямая ссылка):
изучения свойств таких операций иа множестве линейных рекуррентных
последовательностей, как операции почленного сложения или умножения двух
последовательностей над произвольным конечным полем или операция
бинарного дополнения для последовательностей над полем F2-Мы рассмотрим
также задачу нахождения минимальных периодов последовательностей,
порожденных данным линейным рекуррентным соотношением. В § б представлены
некоторые детерминаптные критерии, характеризующие линейные рекуррентные
последовательности. Кроме того, в этом параграфе приводится алгоритм
Берлекэмпа-Мессн для вычисления минимального многочлена рекуррентной
последовательности.
§ 7 посвящен вопросам распределения элементов основного поля среди членов
линейной рекуррентной последовательности, Здесь основным инструментом
исследования является метод тригонометрических сумм.
§ 1. Регистры сдвига с обратной связью.
Свойства периодичности
Пусть к - натуральное число, а а, а0, аи ..., ак_л - заданные элементы
конечного поля F?. Последовательность s0, элементов поля Г?,
удовлетворяющая соотношению
^-lsn + fc-l Qk-'lSn+k-Z "f "1"' a0sn Ь at fl ~ О, С ¦ ¦
(8.1)
называется линейной рекуррентной последовательностью (k-го порядка) иад
пап ем F7. Первые члены s0, sly sh_ j однозначно определяют всю
последовательность и называются ее начальными значениями. Соотношение
вида (8.1) называется линейным ре куррентным соотношением (к-го порядка).
В старой литературе можно также встретить термин "разностное уравнение".
Мы будем называть линейное рекуррентное соотношение однородным, если а 0,
в противном случае линейное рекуррентное соотношение будет называться
неоднородным. Соответствующая рекуррентная последовательность sQy sly ...
будет называться однородной (или
496
Гл. 8, Линейные рекуррентные последовательности
4i:
неоднородной) линейной рекуррентной последовательностью над] полем Fg.
.
Линейные рекуррентные последовательности можно получать! с помощью
регистров сдвига с обратной связью. Это электронный переключательные
схемы специального вида, перерабатываюн информацию, заданную в форме
соответствующим образом пред*! ставленных элементов поля. Регистры сдвига
строятся из конструктивных элементов следующих четырех типов. Элементами!
первого.типа являются сумматоры. Сумматор имеет два вход|| и один выход.
Если на входе появляются два элемента поля то выходом является их сумма в
поле fg. Элементами второго тиф являются усилители. Усилитель имеет одни
вход и один выхо Если на вход поступает элемент поля f?, то на выходе
усилитед появляется его произведение на некоторый постоянный элеме нз
поля fg. Третьим типом конструктивного элемента являете: увеличитель,
который работает аналогично усилителю, но в отл чие от него прибавляет к
поступающему на вход элементу пек торый элемент поля fg. Элементом
четвертого типа являет элемент задержки (триггер). Он имеет одни вход и
один выхц а его работа регулируется внешними синхронизирующими часам
таким образом, что элемент поля fg, поступивший на вход в да| ный момент
времени, появляется в качестве выхода в следуют# момент времени (т, е. на
следующем такте работы). Мы не буд# здесь касаться технической реализации
описанных выше уе ройств. На рис. 8.1 показано, как эти элементы принято
изобр жать па схемах.
Сумматор
Уснпихвнь (умножает чл эжмект а)
Увеличитель (прибавляет элемент а)
Элемент задерз*яс&:} (ТрИП-ф)
Рис. 8.1
* <Оу.
:*АУ
щ
Регистр сдвнга с обратной связью строится путем соединений конечного
числа указанных выше конструктивных э в замкнутую цепь таким образом, что
никакие два выхода присоединяются друг к другу. На самом деле для
получений линейных рекуррентных последовательностей следует соединят^
элементы конструкции довольно специальным образом. Регистр сдвига с
обратной связью, вырабатывающий линейную рекуррентй ную
последовательность, удовлетворяющую соотношению {8.1)<| изображен на рис.
8.2.
В начале работы каждый элемент задержки Djt / - 0, 1, k- 1, содержит
некоторое начальное заполнение Sj. Если сч"Еу тать, что выполнение
арифметических операций и передача сипшф|
•INi.v
Л?
§ 1. Регистры сдвига с обратной связью
497
Рис. 8.2
,лоб по проводам происходят мгновенно, то на следующем такте работы
каждый элемент задержки Dj содержит заполнение sj+1. Продолжая этот
процесс, мы видим, что выходом регистра сдвига с обратной связью является
последовательность элементов st, .s.,, ..., получаемых в последовательные
моменты времени. Для большинства приложений' используются однородные
линейные рекуррентные последовательности; в этом случае увеличитель в
конструкции соответствующего регистра сдвига не требуется.
8.1. Пример. Для того чтобы в поле f5 получить линейную рекуррентную
последовательность, удовлетворяющую однородному линейному рекуррентному
соотношению ' *т& --
! 25n+4 + sn+i + 3sn> и ~~ 0, 1, . .можно использовать регистр сдвига с
обратной связью, изображенный на рис. 8.3. Так как а, а, - 0,
