Р. Лидл, Г. Нидеррайтер - Конечные поля. Т. 1 (1988) (1127099), страница 109

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 109)

Практический интерес представляет случай, когда члены последовательности, линейным образом зависят от фиксированного числа предыдущих членов. Такие последовательности называются линейными' рекуррентными последовательностями. Они применяются в теори кодирования (см.

гл, 9), а также в различных областях электро. ники. Для большинства приложений в качестве основного пол выбирается поле Г.„однако теория рекуррентных последователь-', ностей может быть развита для произвольного конечного поля' В 9 1 мы покажем, как можно технически осуществить полу-", чение линейных рекуррентных последовательностей с помощь ' переключательных схем специального вида, называемых реги" страми сдвига с обратной связью. Здесь же мы обсудим основныв периодические свойства таких последовательностей. В 5 2 вво'' дится понятие импульсной функции, т.

е. последовательностиэ порожденной импульсом. Зги функции представляют как теоре тическнй, так и практический интерес. Так, с нх помощью полу;, чаются дальнейшие результаты о периодических свойствах ре; курреитных последовательностей. Исследование периодичности; ведется также с использованием так называемых характеристи-' ческих многочленов линейных рекуррентных последовательностей.' С помощью характеристических многочленов можно также полу:, чить явные формулы для членов линейной рекуррентной после-, довательности.

В этом же параграфе определяются последова-! тельности максимального периода. К теории линейных рекуррентных последовательностей можно:, подойти как через линейную алгебру, так и через теорию идеалов" или теорию формальных степенных рядов. В 9 3 представлен: подход, основанный на понятии формального степенного ряда,~ 495 9 ц Регистры сдвига с обратной связью 11а этой основе в следующем параграфе вводится минимальный ипогочлен линейной рекуррентной последовательности. Понятие минимального миогочлена очень важно для теории линейных рекчрреитных последовательностей, так как порядок минимального многочлена определяет минимальный период соответствующей последовательности В Ь 5 мы будем исследовать множества, состоящие из всех последовательностей, удовлетворяющих данному линейному реьурреитному соотношению.

Полученные орн этом результаты ока,ываются полезными для изучения свойств таких операций на множестве линейных рекуррентных последовательностей, как операции почленного сложения или умножения двух последовательностей над произвольным конечным полем или операция бинарного дополнения для последовательностей над полем Чы рассмотрим также задачу нахождения минимальных периодов ио«ледовательностей, порожденных данным линейным рекуррентиым соотношением.

В $ 6 представлены некоторые детерминантные критерии, характеризующие линейные рекуррентные последовательности. Кроме того, в этом параграфе приводится алгоритм Всрлекэмпа — Месси для вычисления минимального многочлена рекуррентной последовательности. 9? посвящен вопросам распределения элементов основного поля «реди членов линейной рекуррентной последовательности. Здесь основным инструментом исследования является метод тригонометрических сумм. $ 1. Регистры сдвига с обратной связью. Свойства периодичности Пусть й — натуральное число, а а, а,, а„ ..., аи, — заданные з~емеиты конечного поля Гч. Последовательность з„ з,,...

элементов поля Гч, удовлетворяющая соотношению зи„„= а,,з„„, +ад,з„,д з-~ + поз„) а, и = О, 1, ..., (8.1) называется линейной рекуррентной последовательностью (и-го порядка) над полем Ки. Первые члены ди з,, ..., и„, однозначно определяют всю последовательность и называются ее начальными значениями. Соотношение вида (8.1) называется линейным рекрррентным соотношением (и-го порядка). В старой литературе можно также встретить термин «разностное уравнение» Мы будем называть линейное рекуррентное соотношение однородным, если О, в противном случае линейное рекуррентное соотношение оудет называться неоднородным.

Соответствующая рекуррентная последовательность з„з„... будет называться однородной (или 498 Гл. 8, Линейные ренуррентные последовательности неоднородной) линейной ренуррентной туоследовательностьуо над" полем Линейные рекуррентные последовательности можно получать: с помощью регистров сс)виги с обратной связью. Это электронны переключательные схемы специального вида, перерабатывающие, информацию, заданную в форме соответствующим образом пред;у ставленных элементов поля. Регистры сдвига строятся из кон.' структивпых элементов следующих четырех типов. Элемептамц первого типа являются сумматоры.

Сумматор имеет два входа; н один выход. Если на входе поЯвлЯютсЯ два элемента полЯ вял то выходом нвляется их сумма в поле Гв Элементами второго ти являются усилители. Усилитель имеет один вход и один выхо Если на вход поступает элемент поля Г», то на выходе уснлител' появляется его произведение на некоторый постоянный элеме из поля К,. Третьим типом конструктивного элемента являето увеличитель, который работает аналогично усилителю, но в отл чие от него прибавляет к поступающему на вход элементу нек торый элемент поля Кд.

Элементом четвертого типа являет элемент зидержки (триггер). Он имеет один вход и один вых а его работа регулируется внешними синхронизирующими часа таким образом, что элемент поля К„, поступивший на вход в да ный момент времени, появляется в качестве выхода в следующв момент времени (т. е. на следующем такте работы). Мы не буде здесь касаться технической реализации описанных выше у ройств. На рис. 8,1 показано, как эти элементы принято изобр ' жать на схемах.

оо «лункау су. пот Рнс. 8Л Регистр сдвига с обратной связью строится путем соединеия," конечного числа указанных выше конструктивных элегнентоу»;, В ЗаМКНутуЮ ЦЕПЬ таКИМ ОбраЗОМ, ЧтО НИКаКИЕ даа ВЫХОда Иет присоединяются друг к другу, На самом деле для получения линейных рекуррентных последовательностей следует соединять элементы конструкции довольно специальным образом. Регистр сдвига с обратной связью, вырабатывающий линейную рекуррент."1 ную последовательность, удовлетворяющую соотношению (8.1)у! изображен на рис. 8.2. В начале работы каждый элемент задержки Оуь 1 = О, 1, й — 1, содержит некоторое начальное заполнение в;.

Если счи-, тать, что выполнение арифметических операций и передача сигна,.'у 497 4 Н Регистры сдвига с обратной связью Рьз Рют Рил Рз Рис. В.2 Ра Рис. 8.3 8.2. Пример. Рассмотрим однородное линейное рекуррентное соотношение зп т Яие4 1 диез 1 лей 1 п над полем гз. Соответствующий этому рекуррентному соотношению регистр сдвига с обратной связью изображен на рис. 8.4. Рис. 8.4 лов по проводам происходят мгновенно, то на следующем такте работы каждый элемент задержки 07 СОДЕРжит заполнение зз„. Продолжая этот процесс, мы видим, что выходом регистра сдвига с обратной связью является последовательность элементов з„э„ з,„, .., получаемых в последовательные момен.гы времени.

Для большинства приложений' используются однородные линейные рекуррентные последовательности; в этом случае увеличитель в конструкции соответствующего регистра сдвига не требуется. 8.1. Пример. Для того чтобы в поле Гь получить линейную рекуррентную последовательность, удовлетворяющую однородному линейному рекуррентному соотношению з„„= э„„ь+ + 2з„,4+ а„,-, 'Зз„, и = О, 1, ..., можно использовать регистр сдвига с обратной связью, изображенный на рнс. 8.3. Так как ае =- аз =- О, ссютветствующие соединения не нужны.

П 498 Гл. 8. Линейные рекуррснтные носледонательоостн Так как в поле Еа умножение на константу или сохраняет м жимое (при умножении на !), или обращает его в нуль (при ум женин на О), то в этом случае узел, соответствующий усилител не требуется. Его функции исполняет простое наличие соедин тельного проводника или его отсутствие.

Таким образом, регнс сдвига с обратной связью, вырабатывающий бинарную одиар ' ную линейную рекуррентную последовательность, может б ', сконструирован с использованием лишь элементов задерж сумматоров и соединяющих проводников. Пусть в„з, — линейная рекуррентная последовательи к-го порядка над полем Кч, удовлетворяющая соотношенц" (8.!). Как уже было отмечено, эту последовательность мо получить с помощью регистра сдвига с обратной связью, изобр' женного на рис.

8.2. Если и — целое неотрицательное числ то через и тактов работы эчемент задержки 0;, ) -:= О, ), ..., й— будет содержать заполнение з„„. Таким образом, вектор а„', .= (зн, з„„„..., з„,н,) естественно назвать вектором и-го сос ния линейной рекуррентной последовательности (илн внутренн состоянием регистра сдвига с обратной связью на п-м работы). Вектор состояния за = (зь зы ..., вл,) называется тором начального состояния. Характерной особенностью линейных рекуррентных после ' вательностей над конечным полем является то, что такие п довательности с некоторого момента (после, возможно, иере парного поведения в начале) проявляют свою периодическу' природу (т.

е. опи периодичны в смысле определения 8.3, с ниже). Прежде чем перейти к детальному изучению этого свойс рекуррентиых последовательностей, введем соответствующую т минологию и приведем несколько общих утверждений, каса' щихся периодических последовательностей. 8.3. Определение. Пусть 5 — произвольное непустое мк, жество, н пусть з,, з,, ... — последовательность элементов множества 3. Если существуют целые числа г) 0 и и, такие, что з„,„= эн для всех п ~ п„, то последовательность ' з,, ...

называется периодической последовагпельностью, а г— риодом указанной последовательности. Наименьший из в возможных периодов периодической последовательности иаз вается лтнимальным периодом последовательности. 8.4 Лемма. )таждый период периодической последовательн дегигпся на ее минимальный период. Доказательство. Пусть г — произвольный период периодич ской последовательности з„в,, ..., и пусть г, — ее минимальи период.

Из этого следует, что з„„=- з„для всех и ) па, а з„„, = з„для всех и ~ и, при соответствующем выборе и, и и,. Если' 4 П Регистры сдвига с обратной связно 499 не делится на г„то, применяя алгоритм деления целых чисел, представим г в виде г = тг, + 1, где т» 1, 0 < 1 < г,. Тогда для всех п» гпах (п„п,) получаем ВЛ = ВН+Г = ЗН+МО+Г = Вн+ Ов — О г,-~-» = ' ' = 8»ен о~куда следует, что 1 также является периодом последовательности з,, вы .... Это противоречит тому, что г, — минимальный период последовательности.

Характеристики

Список файлов книги