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

Простейшим видом функции обратной связи является линейная функция, например, сумма по модулю 2 содержимого определенных разрядов. Такой регистр называется сдвиговым регистром с линейной обратной связью (Linear Feedback Shift Register, сокращенно LFSR). В общем случае линейная функция обратной связи задается формулой . Здесь c_k = 1, если k -й разряд используется в функции обратной связи, и c_k = 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. Видно, что генерируемая битовая последовательность целиком определяется начальным состоянием регистра и функцией обратной связи. Поскольку число всевозможных состояний регистра конечно (оно равно 2 ^L), то, рано или поздно, ключевая последовательность начнёт повторяться. Максимальная длина неповторяющейся части ключевой последовательности называется ее периодом T. Период зависит от функции обратной связи. Максимально возможный период равен T _max = 2 ^L -1 (регистр принимает все возможные состояния, кроме 0000...0). Выходная последовательность LFSR, обладающего максимальным периодом, называется М-последовательностью.

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

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