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

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

Feedback with carry shift register (FCSR, сдвиговый регистр с обратной связью по переносу) — один из методов генерации псевдослучайных чисел.

В FCSR есть сдвиговый регистр, функция обратной связи и регистр переноса. Длина сдвигового регистра — количество битов. Когда нужно извлечь бит, все биты сдвигового регистра сдвигаются вправо на одну позицию. Новый крайний слева бит и новое значение регистра переноса определяются функцией остальных битов сдвигового регистра и регистра переноса (их биты складываются). Младший бит результата и становится новым крайним левым битом, а новым значением регистра переноса становится остальные биты результата (кроме младшего).

В отличие от LFSR, для FCSR существует задержка, прежде чем он перейдёт в циклический режим, то есть начнёт генерировать циклически повторяемую последовательность. В зависимости от выбранного начального состояния возможны 4 различных случая:

1. Начальное состояние может оказаться частью максимального периода.
2. Начальное состояние может перейти в последовательность максимального периода, после некоторой начальной задержки.
3. Начальное состояние может после начальной задержки породить последовательность нулей.
4. Начальное состояние может после начальной задержки породить последовательность единиц.