LFSR: детерминированная случайность

Компьютер — честная машина: та же программа на тех же входах даёт тот же ответ. Откуда тогда в процессоре берётся «случайное» число для броска кубика? В курсе за него отвечает LFSR — сдвиговый регистр с обратной связью (Linear Feedback Shift Register). Секрет в том, что его числа только выглядят случайными. Такая случайность называется псевдослучайностью, и у неё есть точная формула.

Сдвиг с одной добавкой

Восемь триггеров образуют байт состояния. На каждом такте весь байт сдвигается на один разряд: старший бит уходит наружу, остальные переезжают влево, а на освободившееся место встаёт новый бит. Вся хитрость — в том, как он считается: берутся значения нескольких разрядов регистра (в нашем LFSR — биты 7, 5, 4 и 3) и складываются по модулю 2, то есть через вентиль XOR. Этот бит и дописывается в хвост.

Со стороны поведение выглядит бессистемно: регистр скачет по значениям без видимого порядка. Но каждый шаг строго определён текущим состоянием — никакой случайности внутри нет.

Проверим руками

Стартовое состояние LFSR в курсе — 156 (0x9C, биты 10011100). Считаем новый бит: из отводов единицы стоят в битах 7, 4 и 3, а бит 5 — ноль; 1⊕0⊕1⊕1 = 1. Сдвигаем влево и дописываем 1 — получаем 57 (0x39). Следующий шаг: 115, затем 230, 204, 152… Последовательность не поддаётся глазу — и при этом воспроизводится до последнего бита: соберите схему заново с той же затравкой, и числа пойдут те же самые.

Период 255 и запрещённый ноль

Наш полином x⁸ + x⁶ + x⁵ + x⁴ + 1 — максимально длинный для 8 бит: регистр по очереди проходит все 255 ненулевых состояний и лишь потом возвращается к затравке. Период равен 255 — отсюда и «случайность»: до первого повторения пройдёт больше двухсот тактов.

Одно состояние из 256 недостижимо — ноль. Из нулевого регистра новый бит всегда получается нулём, и схема застревает навсегда. Поэтому LFSR никогда не инициализируют нулём: затравка 156 заведомо рабочая.

Где это в курсе

На двадцать шестом уровне LFSR подключается к шине данных как третье устройство: читается через порт 250 (0xFA, на адресной шине — 0x1A). В финальной «Змейке» тот же регистр расставляет еду. Полезное свойство для игры: последовательность одна и та же при каждом запуске — поведение воспроизводимо и отлаживается, хотя игрок «случая» не заметит.

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