Регистр сдвига, питающий сам себя

Обычному регистру сдвига нужен внешний последовательный вход. Регистр сдвига с линейной обратной связью (LFSR) вместо этого вычисляет этот вход сам, беря XOR от фиксированного подмножества собственных битов регистра (их называют «отводами») и подавая результат обратно на первую ступень.

Почему обратная связь через XOR даёт длинные последовательности

Поскольку обратная связь через XOR линейна, регистр проходит длинную последовательность различных состояний, прежде чем повториться — при удачно выбранных отводах N-битный LFSR посещает все 2^N−1 ненулевых состояний ровно по одному разу, прежде чем вернуться к исходному значению, — так называемую последовательность максимальной длины. Выход выглядит статистически как шум, хотя вся схема целиком детерминированная последовательностная логика.

Собираем такой регистр из SHIFT4 в Boolflow

Возьмите блок SHIFT4, соедините через XOR два его выходных бита (пара старших ступеней, Q2 и Q3, даёт последовательность максимальной длины для 4 бит) и подайте выход этого XOR на последовательный вход регистра сдвига вместо внешнего сигнала. Есть одна тонкость: регистры в Boolflow включаются в состоянии 0000, а обычный XOR-LFSR застрял бы в нём навсегда, поскольку XOR нулей всегда даёт ноль. Поставьте вместо него вентиль XNOR — состояние-ловушка переезжает в 1111, 0000 становится обычным состоянием, и регистр проходит 15 из своих 16 значений.

Где это применяется

Та же самая структура, что генерирует псевдослучайные тестовые последовательности для встроенного самотестирования микросхем, вычисляет и контрольные суммы CRC для обнаружения ошибок передачи — CRC это просто LFSR, прогнанный по битам сообщения вместо собственной свободно бегущей обратной связи. Соберите такой регистр в редакторе схем, переключайте CLOCK и наблюдайте, как 4-битный выход проходит 15 разных значений, прежде чем повториться.