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

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

Linear feedback shift register (LFSR — линейный регистр сдвига с обратной связью) — один из методов генерации псевдослучайных чисел.

Сдвиговый регистр с обратной связью состоит из двух частей: сдвигового регистра и функции обратной связи. Сдвиговый регистр — последовательность битов. Длина сдвигового регистра — количество битов. Когда нужно извлечь бит, все биты сдвигового регистра сдвигаются вправо на одну позицию. Новый крайний слева бит определяется функцией остальных битов регистра. На выходе сдвигового регистра оказывается один, обычно младший, значащий бит. Период сдвигового регистра — длина получаемой последовательности до начала ее повторения.

Для LFSR функция обратной связи представляет собой сумму по модулю 2 (xor) некоторых битов регистра (эти биты называются отводной последовательностью).

LFSR может находиться в 2ⁿ − 1 внутренних состояниях, где n — длина сдвигового регистра. Если сдвиговый регистр заполнен нулями, то такое состояние будет порождать на выходе только нули (так как в качестве функции обратной связи используется xor), поэтому такое состояние бесполезно. Теоретически LFSR может генерировать последовательность с длиной 2ⁿ − 1 бит, так как длина последовательности совпадает с количеством внутренних состояний. LFSR будет проходить все внутренние состояния (иметь максимальный период) только при определённых отводных последовательностях — если многочлен, образованный из отводной последовательности и константы 1, является примитивным по модулю 2.

Степень многочлена — длина сдвигового регистра. Примитивный многочлен степени n — это неприводимый многочлен, который является делителем $x^{2^n-1}+1$, но не является делителем x^d + 1 для всех d, делящих 2ⁿ − 1.

Например, чтобы проверить будет ли LFSR с отводной последовательностью, состоящей из первого и четвертого битов, генерировать последовательность максимальной длины (15 для 4-битного регистра), нужно проверить, будет ли многочлен x⁴ + x + 1 примитивным.

См. также

• Cдвиговый регистр с обратной связью по переносу FCSR