EssayAI
Блог
Блог
Математика и алгоритмы

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

8 ноября 2026Время чтения: 8 минут
#регистр сдвига#линейная обратная связь#XOR#двоичная последовательность#период
Регистр сдвига с линейной обратной связью: принцип работы

Регистр сдвига с линейной обратной связью - устройство или алгоритм, которое хранит несколько битов и на каждом такте обновляет их по простому правилу. Часть битов сдвигается, а освободившуюся ячейку заполняет результат операции XOR над выбранными ячейками. Несмотря на простоту, регистр может проходить длинную последовательность состояний, прежде чем вернуться к началу.

В калькуляторе ниже выбран четырёхбитовый пример. Меняйте начальное состояние и номер такта: инструмент покажет выходной бит, обратную связь и период. Запись 1000 здесь означает четыре бита слева направо, а не число тысяча.

Из чего состоит регистр

Обозначим содержимое четырёх ячеек через (a,b,c,d)(a,b,c,d) слева направо. На каждом такте мы сначала считываем выход aa, затем одновременно заменяем состояние:

(a,b,c,d)⟼(b,c,d,a⊕b).(a,b,c,d)\longmapsto(b,c,d,a\oplus b).

Символ ⊕\oplus обозначает XOR, или сложение по модулю двух. Новое значение справа зависит от старых значений aa и bb; остальные три бита переходят на одну позицию влево. Обратной связью называют путь от выбранных ячеек, или отводов, к входу регистра. В этом примере отводы - первые две ячейки слева.

Четыре ячейки последовательно меняют состояние: обратная связь объединяет две левые позиции, а через 15 тактов возвращается 1000.

На схеме ячейки подписаны кириллическими буквами а, б, в, г; они соответствуют математическим обозначениям a,b,c,da,b,c,d в том же порядке. На видео показан весь цикл, начиная с 1000. Число тактов в конце снова становится нулём: это тот же момент следующего обхода. Схема задаёт один конкретный вариант регистра; в других источниках биты могут нумеровать справа, сдвигать в другую сторону или брать выход после такта. Для решения задачи всегда нужны эти соглашения, а не только список номеров отводов.

Один такт и операция XOR

Таблица XOR состоит из четырёх случаев: 0⊕0=00\oplus0=0, 0⊕1=10\oplus1=1, 1⊕0=11\oplus0=1, 1⊕1=01\oplus1=0. Результат равен единице, когда входы различны. Это не обычное сложение целых чисел: перенос в соседний разряд отсутствует.

Пусть регистр содержит 1000. Выход равен 1, а обратная связь - 1⊕0=11\oplus0=1. Три оставшихся бита сдвигаются влево, справа записывается 1, и новое состояние равно 0001. На следующем такте 0⊕0=00\oplus0=0, поэтому получается 0010. Ещё два перехода дают 0100 и 1001. Вычислять новую обратную связь уже после сдвига нельзя: тогда получится другая система.

ТактСостояние до сдвигаВыходНовое состояние
0100010001
1000100010
2001000100
3010001001

Подобную запись удобно вести как таблицу трассировки алгоритма: отдельные столбцы для старого состояния и результата не дают случайно использовать уже обновлённый бит. Если двоичная запись пока непривычна, сначала полезно разобрать перевод чисел в двоичную систему.

Почему последовательность повторяется

У регистра из nn битов всего 2n2^n состояний. Следующее состояние полностью определяется текущим: если какое-то состояние появилось снова, все последующие переходы повторятся. В общем случае до входа в цикл может быть начальный участок; для рассматриваемого правила каждый шаг обратим. Действительно, по новому состоянию (b,c,d,e)(b,c,d,e) восстанавливаются старые b,c,db,c,d и a=e⊕ba=e\oplus b. Поэтому каждый начальный набор сразу принадлежит циклу.

Для четырёх битов всего 16 состояний. Одно из них - 0000 - переходит само в себя. Из 1000, напротив, регистр проходит все 15 ненулевых состояний и на 15-м переходе возвращается к началу. Это можно проверить в калькуляторе или по схеме: индекс под каждым набором показывает число уже выполненных тактов.

Пятнадцать состояний регистра от 1000 до 1100 и возврат к началу после 15 тактов
Пятнадцать состояний регистра от 1000 до 1100 и возврат к началу после 15 тактов

Соответствующие выходные биты за период при нашем соглашении о считывании: 100010011010111100010011010111. Следующий бит снова равен 1. Если начать с другого ненулевого состояния того же цикла, порядок битов сдвинется по фазе, но период останется равным 15. Выбор 0000 даёт бесконечные нули и период 1.

Отводы, рекурсия и многочлен

Пусть sts_t - выходной бит в такт tt. За четыре такта новый бит, записанный справа, доходит до выхода. Для выбранной схемы поэтому справедлива рекурсия

st+4=st⊕st+1.s_{t+4}=s_t\oplus s_{t+1}.

Ей соответствует характеристический многочлен p(x)=x4+x+1p(x)=x^4+x+1 над полем F2\mathbb F_2. Его коэффициенты описывают именно эту рекурсию. В другой схеме, например при обратном порядке нумерации и противоположном сдвиге, запись связи между отводами и многочленом может выглядеть иначе. Перед переносом таблицы отводов следует проверить направление сдвига, расположение входа и способ считывания выхода. Производитель Analog Devices объясняет связь многочлена, разрядов и XOR на примере аппаратного генератора.

Многочлен x4+x+1x^4+x+1 примитивен над F2\mathbb F_2. Для соответствующего регистра это даёт максимально возможный период 24−1=152^4-1=15 при любом ненулевом старте. Примитивность сильнее неприводимости: одного отсутствия нетривиальных множителей для максимального периода недостаточно. Подробно отличие разобрано в статье о примитивном многочлене. Для произвольного набора отводов максимальный период обещать нельзя: у него могут возникнуть несколько более коротких циклов.

Откуда берётся предел периода

Для XOR-регистра нулевое состояние всегда замкнуто: XOR любых выбранных нулей равен нулю. Поэтому цикл, начатый с ненулевого состояния, не может содержать ноль и затем вернуться к ненулевому началу. В цикле остаётся не более 2n−12^n-1 разных состояний. Если эта граница достигается, последовательность называют последовательностью максимальной длины, или m-последовательностью.

Нулевая ловушка - свойство именно описанного линейного правила с XOR. В схемах с инверсией обратной связи неподвижным может стать другое состояние, поэтому ограничения стартового набора следует проверять для конкретной реализации. Период выходного потока тоже не всегда можно просто приравнять к числу состояний: в общем случае наблюдаемый один бит может повторяться чаще, чем внутреннее состояние. Для нашего примера выход имеет период 15; это видно по строке за цикл и можно проверить прямым сравнением её циклических сдвигов.

Проверка полным перебором работает для маленького регистра: сохраняйте состояния до первого повтора и измеряйте расстояние между одинаковыми записями. При большой разрядности перебор может быть дорогим; тогда используют свойства многочленов и разложение 2n−12^n-1 на множители. Подробнее о вычислениях с коэффициентами над полем рассказывает статья о неприводимых многочленах.

Как самостоятельно проверить период

Возьмите старт 1000 и записывайте каждое состояние до сдвига. Для каждой строки отдельно найдите XOR двух левых битов, отбросьте самый левый бит и приписывайте результат справа. При первом повторе остановитесь: сравнивать нужно все четыре позиции сразу, а не только выходной бит. Например, выход 0 встречается уже в состояниях 0001 и 0010, но эти состояния различны и продолжения у них тоже различаются.

В нашем примере последнее новое состояние перед возвратом - 1100. Его обратная связь равна 1⊕1=01\oplus1=0, поэтому следующим состоянием становится 1000. Считайте переходы между состояниями: от начального 1000 до его повторения их 15. Не добавляйте повторённую строку как шестнадцатое различное состояние. Если начальное состояние 0000, повтор произойдёт уже после одного перехода. Именно такой подсчёт использует инструмент: график показывает один полный период выходных битов, а ползунок такта позволяет увидеть его повторение.

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

Где применяют и чего ожидать от последовательности

Регистры используют для генерации тестовых последовательностей, скремблирования данных, моделирования помех и построения отдельных схем проверки ошибок. Они дешевы в аппаратуре: нужны ячейки памяти и несколько элементов XOR. Конкретные полином, начальное состояние, порядок битов и правило сброса задаются техническим стандартом или конструкцией системы. Даже одинаковый многочлен при разных соглашениях о записи не гарантирует одинаковый поток битов на выходе.

Последовательность выглядит нерегулярной, но регистр детерминирован: одинаковые состояние и правило всегда дают одинаковое продолжение. По наблюдаемым битам линейную рекурсию можно восстановить; поэтому отдельный LFSR не следует считать криптографически стойким генератором. Длинный период сам по себе не равен непредсказуемости. Для эксперимента сравните в калькуляторе старты 1000 и 0000, а затем два разных ненулевых старта: изменения на графике показывают фазу потока и нулевую ловушку.

Частые ошибки

  • Путать старое и новое состояние. Все правые части формулы вычисляются по битам до такта.
  • Считать XOR обычным сложением. В частности, 1⊕1=01\oplus1=0, а не 2.
  • Использовать нулевой старт для получения длинного XOR-цикла. Он навсегда оставляет регистр в 0000.
  • Ожидать период 2n−12^n-1 от любых отводов. Он зависит от правила обратной связи; максимальность нужно доказать или проверить.
  • Переносить номера отводов без соглашений. Направление сдвига, нумерация и момент считывания меняют интерпретацию схемы.

FAQ

Почему обратная связь называется линейной?

XOR - сложение в поле F2\mathbb F_2. Новый бит является линейной комбинацией старых битов с коэффициентами 0 или 1, а всё преобразование состояния линейно над этим полем.

Можно ли начать с любого ненулевого состояния?

Для выбранного примитивного многочлена да: все 15 ненулевых состояний лежат в одном цикле. Для других правил ненулевые состояния могут принадлежать разным циклам или иметь начальный участок до цикла.

Регистр выдаёт случайные биты?

Нет. Он выдаёт воспроизводимую псевдослучайную последовательность. Зная правило и состояние, можно точно вычислить следующие биты.

Коротко

Регистр с линейной обратной связью сдвигает биты и возвращает на вход их XOR. В примере (a,b,c,d)↦(b,c,d,a⊕b)(a,b,c,d)\mapsto(b,c,d,a\oplus b) старт 1000 даёт период 15, а 0000 неподвижен. Чтобы правильно найти последовательность, сначала зафиксируйте отводы, направление сдвига и момент считывания выхода.

Доверьте текст нейросети EssayAI

Открыть EssayAI

Бесплатно, на русском языке и без VPN

Читайте также

Абсолютная и относительная погрешность числа

Абсолютная и относительная погрешность числа

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

8 ноября 20268 минут
Абсолютная пропускная способность СМО: формула

Абсолютная пропускная способность СМО: формула

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

8 ноября 20268 минут
Алгоритм Флойда-Уоршелла: кратчайшие пути в графе

Алгоритм Флойда-Уоршелла: кратчайшие пути в графе

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

8 ноября 20268 минут
Алгоритм Хирхольцера: как найти эйлеров путь

Алгоритм Хирхольцера: как найти эйлеров путь

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

8 ноября 20268 минут
Алгоритм Хопкрофта-Карпа: паросочетание по фазам

Алгоритм Хопкрофта-Карпа: паросочетание по фазам

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

8 ноября 20268 минут
Анализ выживаемости Каплана-Мейера: пример расчёта

Анализ выживаемости Каплана-Мейера: пример расчёта

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

8 ноября 20268 минут