Конечные поля. Том 1 - Лидл Р.
ISBN 5-03-000065-8
Скачать (прямая ссылка):
соответствующие соединения не нужны, ?
8,2. Пример. Рассмотрим однородное линейное рекуррентное соотношение
*^71+7 ~ 3 ^п+2 ~Т~ /1 - 0, 1, . . ¦,
над полем Соответствующий этому рекуррентному соотношению регистр сдвига
с обратной связью изображен на рис. 8.4.
498 Гл, 8, Линейные рекуррентные последовательности
iW HWtfM II I
Так как в поле Т2 умножение на константу или сохраняет м|: жимое (при
умножении на 1), или обращает его в нуль (при уш| женин на 0), то в этом
случае узел, соответствующий усилите^? не требуется. Его функции
исполняет простое наличие соедий' тельного проводника или его отсутствие.
Таким образом, реги сдвига с обратной связью, вырабатывающий бинарную
однор; ную линейную рекуррентную последовательность, может бьС.
сконструирован с использованием лишь элементов задержй сумматоров и
соединяющих проводников.
Пусть %, slt ... - линейная рекуррентная последовательно^ k-ro порядка
над полем fq, удовлетворяющая соотношен4|?" (8.1). Как уже было отмечено,
эту последовательность можз^ получить с помощью регистра сдвига с
обратной связью, изобф| жеиного на рис. 8.2. Если п - целое
неотрицательное чис"С то через п тактов работы элемент задержки Djf j -
0,1, ..., к - ;; будет содержать заполнение sn+j. Таким образом, вектор
sn:'f ~ (sn, sft+1, sn+fc_!) естественно назвать вектором п~го состри,
ния линейной рекуррентной последовательности (или внутрентщ состоянием
регистра сдвига с обратной связью на п-м тощ| работы). Вектор состояния
sfl - (s{), slt s&"[) называется тором начального состояния. у?
Характерной особенностью линейных рекуррентных после$| вательностей над
конечным полем является то, что такие noesjfc дователыюсти с некоторого
момента (после, возможно, нерезв" лярного поведения в начале) проявляют
свою периодически природу (т. е. они периодичны в смысле определения 8.3,
сг ниже). Прежде чем перейти к детальному изучению этого crohct
рекуррентных последовательностей, введем соответствующую мннологию и
приведем несколько общих утверждении, каса^Г щихся периодических
последовательностей. I
" Ъ
8.3. Определение. Пусть S - произвольное непустое жество, и пусть % slt
... - последовательность элементов | множества X. Если существуют целые
числа г > 0 н > такие, что sn+r - для всех п г- л0- то последовательность
{Щ sb ... называется периодической последовательностьюt а г - ш риодом
указанной последовательности. Наименьший из вЩ возможных периодов
периодической последовательности назф вается минимальным периодом
последовательности.
8.4 Лемма. Каждый период периодической последовательное; делится на ее
минимальный период.
Доказательство. Пусть г - произвольный пернод периодич* ской
последовательности So, sb ..., и пусть гг -г ее минимально пернод. Из
этого следует, что sn.hr --- sn для всех п ^ п0, a зл+Г| ^ =* sn для всех
п > при соответствующем выборе п0 и пх. ЕслК
§ 1. Регистры сдвига с обратной связью
499
не делится на rlt то, применяя алгоритм деления целых чисел, представим г
в виде г = тгх + U где т ^ 1, 0 < i < rt. Тогда для всех п ^ шах (л0, гц)
получаем
sn ~ (r)л+г " 5"4шТ-Н " 5л-г {т-1) rt+t = ¦ ¦ ¦ =
откуда следует, что t также является периодом последовательности So, slt
... . Это противоречит тому, что гх- минимальный период
последовательности. ?
8.5. Определение. Периодическая последовательность
slt ... с минимальным периодом г называется чисто периодической, если
равенствоsn+r ~ sn выполняется для всех п ~ О, I, ... .
Следующее условие, которое нногда встречается в литературе, эквивалентно
определению чисто периодической последовательности.
8.6. Лемма. Последовательность s0, sb ... является чисто периодической
тогда и только тогда, когда существует целое число г > 0, такое, что sn+r
- sn для всех п = 0, 1, ... .
Доказательство. Необходимость приведенного условия очевидна. Далее, если
условие выполняется, то s0, %, ... является периодической
последовательностью и, следовательно, имеет минимальный период г1( причем
равенство sn+Ti - sn справедливо для всех п ^ щ и некоторого п0 С IN.
Пусть теперь п - произвольное целое неотрицательное число, н выберем
такое целое ш яй, для которого т = я (mod г). Тогда sn+ri - sm+Tl
=
= sm = sn, откуда вытекает, что последовательность s0, sx, ...
является чисто периодической в смысле определения 8.5. ?
Пусть s0, slt ... - периодическая последовательность, а г - ее
минимальный период. Наименьшее неотрицательное целое число па, такое, что
s^r - sn для всех п ^ п0, называется пред-периодом этой
последовательности. Периодическая последовательность является чисто
периодической, если ее предпериод равен 0.
Вернемся теперь к линейным рекуррентным последовательностям над конечными
полями и установим основные результаты 0 свойствах периодичности у
таких последовательностей.
8-7. Теорема. Пусть - произвольное конечное тле, a k -
некоторое натуральное число. Тогда каждая линейная рекуррентная
последовательность k-го порядка над полем F? является периодической. При
