LFSR-калькулятор - линейный регистр сдвига
Генерируйте псевдослучайные двоичные последовательности с линейным регистром сдвига и настраиваемыми taps обратной связи.
Введите длину регистра, начальное seed, позиции taps обратной связи, тип LFSR и число итераций, затем нажмите «Сгенерировать последовательность».
LFSR-калькулятор - линейный регистр сдвига
Генерируйте псевдослучайные двоичные последовательности с линейным регистром сдвига и настраиваемыми taps обратной связи.
Двоичная строка, представляющая начальное состояние (только 0 и 1)
Позиции taps через запятую, начиная с 1
Количество операций сдвига
Сгенерированная последовательность
Выходные биты:
000100110101111Период последовательности: 15
Максимальная длина: Да
Состояния регистра:
0: 1000
1: 0100
2: 0010
3: 1001
4: 1100
5: 0110
6: 1011
7: 0101
8: 1010
9: 1101
10: 1110
11: 1111
12: 0111
13: 0011
14: 0001
15: 1000
О LFSR-калькуляторе
Линейный регистр сдвига с обратной связью (LFSR) — это регистр сдвига, входной бит которого является линейной функцией (XOR) некоторых предыдущих битов состояния. На каждом такте регистр сдвигает все биты на одну позицию, новый входной бит вычисляется XOR-ом битов в определённых позициях, называемых taps обратной связи, а выходом становится бит, выдвинутый из регистра. Получающаяся двоичная последовательность выглядит случайной, но полностью детерминирована и повторяется с периодом, зависящим от длины регистра и выбора taps.
LFSR широко применяются в цифровой связи, криптографии, схемах встроенного самотестирования (BIST), системах расширенного спектра и генерации псевдослучайных чисел. Поскольку LFSR с n ступенями может выдать максимум 2ⁿ − 1 бит до повторения (состояние из всех нулей исключается), а максимальная последовательность может быть достигнута с помощью тщательно подобранных taps примитивного многочлена, LFSR являются эффективной аппаратной реализацией псевдослучайности.
Существует две распространённые архитектуры LFSR. В Fibonacci LFSR (внешняя обратная связь) бит обратной связи вычисляется из фиксированного набора taps и подаётся в левую ступень, а все остальные ступени сдвигаются вправо. Выход берётся с правой ступени. В Galois LFSR (внутренняя обратная связь) бит обратной связи XOR-ится напрямую в несколько промежуточных ступеней, а не возвращается только на вход. Galois LFSR быстрее в аппаратуре, потому что все XOR-операции выполняются параллельно, а не последовательно.
LFSR максимальной длины — то есть такой, который проходит все 2ⁿ − 1 ненулевых состояний до повторения, — требует примитивного многочлена в качестве многочлена обратной связи. Позиции taps соответствуют ненулевым коэффициентам этого многочлена. Для 4-битного LFSR с taps в позициях 4 и 3 примитивный многочлен равен x⁴ + x³ + 1, и LFSR проходит все 15 ненулевых состояний.
Этот калькулятор позволяет исследовать любые сочетания длины регистра, seed, позиций taps и типа LFSR. Вы можете проверить, дают ли выбранные taps последовательность максимальной длины, посмотрев на период в результатах — если период равен 2ⁿ − 1, taps образуют примитивный многочлен. Используйте приведённые примеры, чтобы увидеть известные конфигурации максимальной длины.
Области применения LFSR охватывают множество направлений. В Wi‑Fi и Bluetooth LFSR задают коды расширения для скачкообразной перестройки частоты и расширения спектра с прямой последовательностью. В хранении и связи схемы CRC (циклический контроль избыточности) реализуются как LFSR. В криптографических потоковых шифрах LFSR составляют базовый примитив (хотя современные шифры комбинируют несколько LFSR с нелинейными компонентами, чтобы противостоять линейному криптоанализу). При тестировании микросхем LFSR-основанный анализ сигнатур сжимает данные отклика теста в компактную сигнатуру.
Примеры LFSR
Распространённые конфигурации LFSR, демонстрирующие последовательности максимальной длины и разные размеры регистра.
| Конфигурация | Период | Описание |
|---|---|---|
| 4-bit, seed=1000, taps=[4,3], Fibonacci | 15 (максимальная) | Примитивный многочлен x⁴+x³+1. Проходит все 15 ненулевых 4-битных состояний. |
| 8-bit, seed=10110001, taps=[8,6,5,4], Fibonacci | 255 (максимальная) | Стандартный 8-битный Fibonacci LFSR, используемый в криптографии. |
| 5-bit, seed=10101, taps=[5,3], Galois | 31 (максимальная) | LFSR Galois с внутренней обратной связью и более быстрыми параллельными XOR-операциями. |
| 3-bit, seed=110, taps=[3,2], Fibonacci | 7 (максимальная) | Простой 3-битный LFSR — отлично подходит для обучения и изучения концепции. |
Как пользоваться LFSR-калькулятором
- Установите длину регистра в нужное число бит (например, 4 для 4-битного LFSR).
- Введите начальное seed в виде двоичной строки длиной, равной длине регистра (например, 1000). Избегайте состояния из одних нулей — оно блокирует LFSR.
- Введите taps обратной связи как позиции через запятую (например, 4, 3). Позиции taps считаются с 1 от левой ступени.
- Выберите тип LFSR: Fibonacci (внешняя обратная связь) или Galois (внутренняя обратная связь).
- Задайте число итераций и нажмите «Сгенерировать последовательность», чтобы увидеть выходной битовый поток и состояния регистра на каждом шаге.
FAQ по LFSR-калькулятору
Что такое LFSR максимальной длины?
LFSR максимальной длины проходит все 2ⁿ − 1 возможных ненулевых состояний до повторения. Для этого многочлен обратной связи (определяемый позициями taps) должен быть примитивным многочленом над GF(2). Для 4-битного LFSR максимальный период равен 15; для 8-битного — 255. Последовательности максимальной длины (m-sequences) обладают отличными псевдослучайными свойствами.
Почему исключается состояние из всех нулей?
Если все биты регистра равны нулю, XOR-обратная связь всегда даёт ноль, и регистр навсегда остаётся в состоянии всех нулей. Поэтому начальное seed не должно быть нулевым. По той же причине максимальный период равен 2ⁿ − 1, а не 2ⁿ.
В чём разница между Fibonacci и Galois LFSR?
В Fibonacci LFSR бит обратной связи получается XOR-ом всех позиций taps и подаётся в первую ступень; остальные ступени просто сдвигаются. В Galois LFSR бит обратной связи напрямую XOR-ится с несколькими промежуточными ступенями параллельно. Оба варианта дают одну и ту же последовательность (для эквивалентных многочленов), но Galois быстрее в аппаратуре, потому что XOR-операции выполняются параллельно.
Как выбрать правильные позиции taps?
Чтобы получить последовательность максимальной длины, позиции taps должны соответствовать примитивному многочлену над GF(2). Таблицы примитивных многочленов для распространённых длин регистров широко публикуются. Например, для n=4 примитивный многочлен x⁴+x³+1 даёт taps [4,3]; для n=8 многочлен x⁸+x⁶+x⁵+x⁴+1 даёт taps [8,6,5,4].
Являются ли последовательности LFSR действительно случайными?
Нет. Последовательности LFSR детерминированы и полностью предсказуемы по seed и позициям taps. Их называют псевдослучайными, потому что они проходят многие статистические тесты на случайность и выглядят случайными для наблюдателя, не знающего конфигурации. Для криптографического использования LFSR нужно сочетать с нелинейными компонентами, чтобы противостоять линейному криптоанализу.
Что такое CRC и как он связан с LFSR?
CRC (циклический избыточный контроль) — это код обнаружения ошибок, вычисляемый делением многочлена сообщения на порождающий многочлен над GF(2) с последующим добавлением остатка. Этот процесс деления эквивалентен пропусканию битов сообщения через LFSR, определённый порождающим многочленом. Стандартный CRC-32 использует конкретный 32-битный примитивный многочлен, а его аппаратная реализация — это 32-ступенчатый LFSR.