Сдвиговый регистр с линейной обратной связью
В вычислениях регистр сдвига с линейной обратной связью ( LFSR ) — это регистр сдвига , входной бит которого является линейной функцией его предыдущего состояния.
Наиболее часто используемая линейная функция отдельных битов — исключающее ИЛИ (XOR). Таким образом, LFSR чаще всего является регистром сдвига, входной бит которого управляется XOR некоторых битов общего значения регистра сдвига.
Начальное значение LFSR называется начальным значением, и поскольку операция регистра является детерминированной, поток значений, создаваемых регистром, полностью определяется его текущим (или предыдущим) состоянием. Точно так же, поскольку регистр имеет конечное число возможных состояний, в конечном итоге он должен войти в повторяющийся цикл. Однако LFSR с хорошо подобранной функцией обратной связи может создать последовательность битов, которая выглядит случайной и имеет очень длинный цикл .
Приложения LFSR включают генерацию псевдослучайных чисел , псевдошумовых последовательностей , быстрых цифровых счетчиков и отбеливающих последовательностей . Как аппаратные, так и программные реализации LFSR являются общими.
Математика проверки циклическим избыточным кодом , используемая для обеспечения быстрой проверки ошибок передачи, тесно связана с LFSR. [1] В целом, арифметика, стоящая за LFSR, делает их очень элегантными объектами для изучения и реализации. Можно создать относительно сложную логику с помощью простых строительных блоков. Однако следует рассмотреть и другие методы, менее элегантные, но более эффективные.
Позиции битов, влияющие на следующее состояние, называются ответвлениями. На схеме отводы [16,14,13,11]. Самый правый бит LFSR называется выходным битом. Отводы последовательно объединяются XOR с выходным битом, а затем возвращаются обратно в самый левый бит. Последовательность битов в крайнем правом положении называется выходным потоком.
