Регистр сдвига с линейной обратной связью: принцип работы

Регистр сдвига с линейной обратной связью - устройство или алгоритм, которое хранит несколько битов и на каждом такте обновляет их по простому правилу. Часть битов сдвигается, а освободившуюся ячейку заполняет результат операции XOR над выбранными ячейками. Несмотря на простоту, регистр может проходить длинную последовательность состояний, прежде чем вернуться к началу.
В калькуляторе ниже выбран четырёхбитовый пример. Меняйте начальное состояние и номер такта: инструмент покажет выходной бит, обратную связь и период. Запись 1000 здесь означает четыре бита слева направо, а не число тысяча.
Из чего состоит регистр
Обозначим содержимое четырёх ячеек через слева направо. На каждом такте мы сначала считываем выход , затем одновременно заменяем состояние:
Символ обозначает XOR, или сложение по модулю двух. Новое значение справа зависит от старых значений и ; остальные три бита переходят на одну позицию влево. Обратной связью называют путь от выбранных ячеек, или отводов, к входу регистра. В этом примере отводы - первые две ячейки слева.
На схеме ячейки подписаны кириллическими буквами а, б, в, г; они соответствуют математическим обозначениям в том же порядке. На видео показан весь цикл, начиная с 1000. Число тактов в конце снова становится нулём: это тот же момент следующего обхода. Схема задаёт один конкретный вариант регистра; в других источниках биты могут нумеровать справа, сдвигать в другую сторону или брать выход после такта. Для решения задачи всегда нужны эти соглашения, а не только список номеров отводов.
Один такт и операция XOR
Таблица XOR состоит из четырёх случаев: , , , . Результат равен единице, когда входы различны. Это не обычное сложение целых чисел: перенос в соседний разряд отсутствует.
Пусть регистр содержит 1000. Выход равен 1, а обратная связь - . Три оставшихся бита сдвигаются влево, справа записывается 1, и новое состояние равно 0001. На следующем такте , поэтому получается 0010. Ещё два перехода дают 0100 и 1001. Вычислять новую обратную связь уже после сдвига нельзя: тогда получится другая система.
| Такт | Состояние до сдвига | Выход | Новое состояние |
|---|---|---|---|
| 0 | 1000 | 1 | 0001 |
| 1 | 0001 | 0 | 0010 |
| 2 | 0010 | 0 | 0100 |
| 3 | 0100 | 0 | 1001 |
Подобную запись удобно вести как таблицу трассировки алгоритма: отдельные столбцы для старого состояния и результата не дают случайно использовать уже обновлённый бит. Если двоичная запись пока непривычна, сначала полезно разобрать перевод чисел в двоичную систему.
Почему последовательность повторяется
У регистра из битов всего состояний. Следующее состояние полностью определяется текущим: если какое-то состояние появилось снова, все последующие переходы повторятся. В общем случае до входа в цикл может быть начальный участок; для рассматриваемого правила каждый шаг обратим. Действительно, по новому состоянию восстанавливаются старые и . Поэтому каждый начальный набор сразу принадлежит циклу.
Для четырёх битов всего 16 состояний. Одно из них - 0000 - переходит само в себя. Из 1000, напротив, регистр проходит все 15 ненулевых состояний и на 15-м переходе возвращается к началу. Это можно проверить в калькуляторе или по схеме: индекс под каждым набором показывает число уже выполненных тактов.

Соответствующие выходные биты за период при нашем соглашении о считывании: . Следующий бит снова равен 1. Если начать с другого ненулевого состояния того же цикла, порядок битов сдвинется по фазе, но период останется равным 15. Выбор 0000 даёт бесконечные нули и период 1.
Отводы, рекурсия и многочлен
Пусть - выходной бит в такт . За четыре такта новый бит, записанный справа, доходит до выхода. Для выбранной схемы поэтому справедлива рекурсия
Ей соответствует характеристический многочлен над полем . Его коэффициенты описывают именно эту рекурсию. В другой схеме, например при обратном порядке нумерации и противоположном сдвиге, запись связи между отводами и многочленом может выглядеть иначе. Перед переносом таблицы отводов следует проверить направление сдвига, расположение входа и способ считывания выхода. Производитель Analog Devices объясняет связь многочлена, разрядов и XOR на примере аппаратного генератора.
Многочлен примитивен над . Для соответствующего регистра это даёт максимально возможный период при любом ненулевом старте. Примитивность сильнее неприводимости: одного отсутствия нетривиальных множителей для максимального периода недостаточно. Подробно отличие разобрано в статье о примитивном многочлене. Для произвольного набора отводов максимальный период обещать нельзя: у него могут возникнуть несколько более коротких циклов.
Откуда берётся предел периода
Для XOR-регистра нулевое состояние всегда замкнуто: XOR любых выбранных нулей равен нулю. Поэтому цикл, начатый с ненулевого состояния, не может содержать ноль и затем вернуться к ненулевому началу. В цикле остаётся не более разных состояний. Если эта граница достигается, последовательность называют последовательностью максимальной длины, или m-последовательностью.
Нулевая ловушка - свойство именно описанного линейного правила с XOR. В схемах с инверсией обратной связи неподвижным может стать другое состояние, поэтому ограничения стартового набора следует проверять для конкретной реализации. Период выходного потока тоже не всегда можно просто приравнять к числу состояний: в общем случае наблюдаемый один бит может повторяться чаще, чем внутреннее состояние. Для нашего примера выход имеет период 15; это видно по строке за цикл и можно проверить прямым сравнением её циклических сдвигов.
Проверка полным перебором работает для маленького регистра: сохраняйте состояния до первого повтора и измеряйте расстояние между одинаковыми записями. При большой разрядности перебор может быть дорогим; тогда используют свойства многочленов и разложение на множители. Подробнее о вычислениях с коэффициентами над полем рассказывает статья о неприводимых многочленах.
Как самостоятельно проверить период
Возьмите старт 1000 и записывайте каждое состояние до сдвига. Для каждой строки отдельно найдите XOR двух левых битов, отбросьте самый левый бит и приписывайте результат справа. При первом повторе остановитесь: сравнивать нужно все четыре позиции сразу, а не только выходной бит. Например, выход 0 встречается уже в состояниях 0001 и 0010, но эти состояния различны и продолжения у них тоже различаются.
В нашем примере последнее новое состояние перед возвратом - 1100. Его обратная связь равна , поэтому следующим состоянием становится 1000. Считайте переходы между состояниями: от начального 1000 до его повторения их 15. Не добавляйте повторённую строку как шестнадцатое различное состояние. Если начальное состояние 0000, повтор произойдёт уже после одного перехода. Именно такой подсчёт использует инструмент: график показывает один полный период выходных битов, а ползунок такта позволяет увидеть его повторение.
В более общей задаче первое повторившееся состояние не обязано совпадать с начальным. Тогда период измеряют от первого появления повторённого набора до следующего, исключая предшествующие переходы. Для нашего обратимого преобразования такого начального участка нет, но для регистра с другим правилом этот шаг проверки важен.
Где применяют и чего ожидать от последовательности
Регистры используют для генерации тестовых последовательностей, скремблирования данных, моделирования помех и построения отдельных схем проверки ошибок. Они дешевы в аппаратуре: нужны ячейки памяти и несколько элементов XOR. Конкретные полином, начальное состояние, порядок битов и правило сброса задаются техническим стандартом или конструкцией системы. Даже одинаковый многочлен при разных соглашениях о записи не гарантирует одинаковый поток битов на выходе.
Последовательность выглядит нерегулярной, но регистр детерминирован: одинаковые состояние и правило всегда дают одинаковое продолжение. По наблюдаемым битам линейную рекурсию можно восстановить; поэтому отдельный LFSR не следует считать криптографически стойким генератором. Длинный период сам по себе не равен непредсказуемости. Для эксперимента сравните в калькуляторе старты 1000 и 0000, а затем два разных ненулевых старта: изменения на графике показывают фазу потока и нулевую ловушку.
Частые ошибки
- Путать старое и новое состояние. Все правые части формулы вычисляются по битам до такта.
- Считать XOR обычным сложением. В частности, , а не 2.
- Использовать нулевой старт для получения длинного XOR-цикла. Он навсегда оставляет регистр в 0000.
- Ожидать период от любых отводов. Он зависит от правила обратной связи; максимальность нужно доказать или проверить.
- Переносить номера отводов без соглашений. Направление сдвига, нумерация и момент считывания меняют интерпретацию схемы.
FAQ
Почему обратная связь называется линейной?
XOR - сложение в поле . Новый бит является линейной комбинацией старых битов с коэффициентами 0 или 1, а всё преобразование состояния линейно над этим полем.
Можно ли начать с любого ненулевого состояния?
Для выбранного примитивного многочлена да: все 15 ненулевых состояний лежат в одном цикле. Для других правил ненулевые состояния могут принадлежать разным циклам или иметь начальный участок до цикла.
Регистр выдаёт случайные биты?
Нет. Он выдаёт воспроизводимую псевдослучайную последовательность. Зная правило и состояние, можно точно вычислить следующие биты.
Коротко
Регистр с линейной обратной связью сдвигает биты и возвращает на вход их XOR. В примере старт 1000 даёт период 15, а 0000 неподвижен. Чтобы правильно найти последовательность, сначала зафиксируйте отводы, направление сдвига и момент считывания выхода.
Читайте также

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

Абсолютная пропускная способность СМО: формула
Как найти абсолютную пропускную способность СМО через интенсивность потока и вероятность отказа: формула, пример расчёта и отличие от относительной способности.

Алгоритм Флойда-Уоршелла: кратчайшие пути в графе
Алгоритм Флойда-Уоршелла на примере: как получить матрицу кратчайших путей для всех пар вершин, восстановить маршрут и вовремя обнаружить отрицательный цикл.

Алгоритм Хирхольцера: как найти эйлеров путь
Алгоритм Хирхольцера строит эйлеров путь или цикл в графе. Разбираем условия существования, работу стека, пример с двумя циклами и сложность алгоритма.

Алгоритм Хопкрофта-Карпа: паросочетание по фазам
Алгоритм Хопкрофта-Карпа находит максимальное паросочетание в двудольном графе. Разбираем поиск кратчайших цепей, BFS и DFS, пример двух фаз и оценку сложности.

Анализ выживаемости Каплана-Мейера: пример расчёта
Анализ выживаемости Каплана-Мейера: как построить ступенчатую кривую, учесть цензурирование, рассчитать медиану и правильно прочитать результат на примере.