Линейные сдвиговые регистры с обратной связью

Простейшим видом функции обратной связи является линейная функция, например, сумма по модулю 2 содержимого определенных разрядов. Такой регистр называется сдвиговым регистром с линейной обратной связью (Linear Feedback Shift Register, сокращенно LFSR). В общем случае линейная функция обратной связи задается формулой . Здесь ck = 1, если k-й разряд используется в функции обратной связи, и ck = 0 в противном случае. Символ Å обозначает сложение по модулю 2 (исключающее ИЛИ).

Для примера рассмотрим LFSR с функцией обратной связи (см. рисунок).

Если начальным состоянием регистра является 1111, то в последующих тактах он будет принимать следующий ряд состояний: 1111, 0111, 1011, 0101, 1010, 1101, 0110, 0011, 1001, 0100, 0010, 0001, 1000, 1100, 1110, 1111, …

Выходная последовательность формируется из младшего (крайнего правого) разряда регистра. Она будет выглядеть следующим образом: 1 1 1 1 0 1 0 1 1 0 0 1 0 0 0 1. Видно, что генерируемая битовая последовательность целиком определяется начальным состоянием регистра и функцией обратной связи. Поскольку число всевозможных состояний регистра конечно (оно равно 2L), то, рано или поздно, ключевая последовательность начнёт повторяться. Максимальная длина неповторяющейся части ключевой последовательности называется ее периодом T. Период зависит от функции обратной связи. Максимально возможный период равен Tmax = 2L-1 (регистр принимает все возможные состояния, кроме 0000...0). Выходная последовательность LFSR, обладающего максимальным периодом, называется М-последовательностью.

Чтобы выяснить условия, при которых LFSR будет обладать максимальным периодом, функции обратной связи ставят в соответствие характеристический полином . Так, регистру, приведенному выше в качестве примера, соответствует полином . Теоретический анализ показывает, что LFSR будет обладать максимальным периодом тогда и только тогда, когда полином P(x) является примитивным. Ниже приведены некоторые примитивные полиномы, рекомендованные к применению на практике. В таблице указаны степени переменной x в записи полинома. Например, запись (31, 3) соответствует полиному .

P(x) P(x) P(x)
(39, 16, 23, 35) (38, 5, 6, 27) (32, 2, 7, 16)
(30, 6, 4, 1) (31, 6) (31, 7)
(31, 13) (31, 25, 23, 8) (33, 13)
(35, 2) (47, 5) (48, 9, 7, 4)
(47, 11, 24, 32) (46, 18, 31, 40) (53, 6, 2, 1)
(55, 24) (57, 7) (58, 19)
(59, 7, 4, 2) (41, 27, 31, 32) (61, 5, 2, 1)
(42, 30, 31, 34) (51, 15, 24, 46) (50, 17, 31, 34)



Изначально LFSR были разработаны для аппаратной реализации в виде набора цифровых схем. Программные реализации LFSR обычно проигрывают по скорости аппаратным. Для увеличения быстродействия состояние регистра выгодно хранить в виде целого L-разрядного числа, отдельные биты которого соответствуют двоичным разрядам регистра. Тогда для доступа к отдельным битам используются поразрядные операции (сдвиг, маскирование и т.д.).


6755153008672972.html
6755199304128450.html
    PR.RU™