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

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

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

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

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

Возьмите блок SHIFT4, соедините через XOR два его выходных бита (пара «бит 3 и бит 2» даёт последовательность максимальной длины для 4 бит) и подайте выход этого XOR на последовательный вход регистра сдвига вместо внешнего сигнала. Загрузите в регистр любое ненулевое значение — полностью нулевой LFSR так и останется нулевым навсегда, поскольку XOR нулей всегда даёт ноль.

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

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