214
Рисунок 6.1 показывает степень-4 LFSR с c0 = c2 = 1 и c1 = c3 = 0.
С каждым тиком часов, LFSR выводит значение самого правого регистра s0.
Если начальное состояние LFSR
, первые n бит выходногопотока - ров-
но
.
Следующий выходной бит -
Если мы обозначим выходные биты y1, y2, . . ., где yi = s(i−1), тогда
В качестве примера, используя LFSR с Рисунка 6.1, если
начальное состоя-
ние (0, 0, 1, 1), тогда состояния на первые
несколько временных периодов
(0, 0, 1, 1)
(1, 0, 0, 1)
(1, 1, 0, 0)
(1, 1, 1, 0)
(1, 1, 1, 1)
и результат (который может быть считан из самой правой колонки выше) - это
поток битов 1, 1, 0, 0, 1, . . ..
Состояние LFSR содержит n бит; таким образом, LFSR может циклически
проходить максимум 2n возможных состояния перед повтором. Когда состоя-
ния повторяются, выходные биты повторяются, и это означает, что выходная
последовательность начнет повторяться после того, как будет сгенерировано
максимум 2n выходных битов. Максимальная длина LFSR проходит циклом
через все 2n − 1 ненулевые состояния перед повтором. (Обратите внимание,
что, если полностью нулевое состояние когда-либо реализуется, LFSR останет-
ся в таком состоянии навсегда, поэтому мы и исключили его.) Максимальной ли
длины LFSR или нет зависит только от коэффициентов обратной связи; если он
максимальной длины, тогда при инициализации в любое ненулевое состояние
он будет проходить через все 2n − 1 ненулевые состояния. Понятно, как ста-
новить коэффициенты обратной связи, чтобы получить максимальную длину
LFSR, хотя детали находятся за пределами данной книги.