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

редактировать

Тип сдвигового регистра в вычислениях

В вычислениях, a регистр сдвига с линейной обратной связью (LFSR ) является регистром сдвига, входной бит которого является линейной функцией своего предыдущего состояния.

Наиболее часто используемой линейной функцией отдельных битов является исключающее ИЛИ (XOR). Таким образом, LFSR чаще всего представляет собой регистр сдвига, входной бит которого управляется операцией XOR некоторых битов общего значения регистра сдвига.

Начальное значение LFSR называется начальным значением, и поскольку операция регистра является детерминированной, поток значений, создаваемых регистром, полностью определяется его текущим (или предыдущим) состоянием. Точно так же, поскольку регистр имеет конечное число возможных состояний, он в конечном итоге должен войти в повторяющийся цикл. Однако LFSR с хорошо выбранной функцией обратной связи может создавать последовательность битов, которая кажется случайной и имеет очень длинный цикл.

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

Математика циклического контроля избыточности, используемая для обеспечения быстрой проверки на наличие ошибок передачи, тесно связана с математикой LFSR.

Содержание

1 LFSR Фибоначчи
2 LFSR Галуа
- 2.1 Недвоичные LFSR Галуа
3 LFSR Xorshift
4 Матричные формы
5 Некоторые полиномы для максимальных LFSR
6 Свойства выходного потока
7 Приложения
- 7.1 Использование в качестве счетчиков
- 7.2 Использование в криптографии
- 7.3 Использование при тестировании цепей
  - 7.3.1 Генерация тестового шаблона
  - 7.3.2 Анализ сигнатур
- 7.4 Использование в цифровом вещании и связи
  - 7.4.1 Скремблирование
  - 7.4.2 Другое использование
8 См. Также
9 Ссылки
10 Внешние ссылки

LFSR Фибоначчи

16-битный Fibonacci LFSR. Показанные числа отводов обратной связи соответствуют примитивному полиному в таблице, поэтому регистр циклически перебирает максимальное количество из 65535 состояний, исключая состояние «все нули». Показанное состояние 0xACE1 (шестнадцатеричное ) будет сопровождаться 0x5670.

Позиции битов, которые влияют на следующее состояние, называются ответвлениями. На схеме отводы [16,14,13,11]. Самый правый бит LFSR называется выходным битом. Отводы подвергаются операции XOR последовательно с выходным битом, а затем возвращаются в крайний левый бит. Последовательность битов в крайнем правом положении называется потоком вывода.

Биты в состоянии LFSR, которые влияют на вход, называются ответвлениями.
LFSR максимальной длины создает m-последовательность (т. Е. Циклически перебирает все возможные 2-1 состояний в регистре сдвига, кроме состояния, в котором все биты равны нулю), если он не содержит все нули, и в этом случае он никогда не изменится.
В качестве альтернативы обратной связи на основе XOR в LFSR можно также используйте XNOR. Эта функция является аффинным отображением , а не строго линейным отображением, но она приводит к эквивалентному полиномиальному счетчику, состояние которого является дополнением к состоянию LFSR. Состояние со всеми единицами недопустимо при использовании обратной связи XNOR, так же как состояние со всеми нулями недопустимо при использовании XOR. Это состояние считается недопустимым, потому что в этом состоянии счетчик останется заблокированным. Этот метод может быть полезным в аппаратных LFSR, использующих триггеры, которые запускаются в нулевом состоянии, поскольку он не запускается в состоянии блокировки, что означает, что регистр не нужно заполнять, чтобы начать работу.

Последовательность чисел, сгенерированных LFSR или его аналогом XNOR, можно рассматривать как двоичную систему счисления так же, как и код Грея или естественный двоичный код.

Расположение отводов для обратной связи в LFSR может быть выражено в арифметике с конечным полем как полином mod 2. Это означает, что коэффициенты полинома должны быть 1 или 0. Это называется полиномом обратной связи или обратным характеристическим полиномом. Например, если ответвления находятся в 16-м, 14-м, 13-м и 11-м битах (как показано), полином обратной связи будет

x 16 + x 14 + x 13 + x 11 + 1. {\ displaystyle x ^ {16 } + x ^ {14} + x ^ {13} + x ^ {11} +1.}

{\ displaystyle x ^ {16 } + x ^ {14} + x ^ {13} + x ^ {11} +1.}

«Единица» в полиноме не соответствует нажатию - она соответствует вводу первого бита ( т.е. x, что эквивалентно 1). Степени членов представляют собой отведенные биты, считая слева. Первый и последний биты всегда подключены как входной и выходной ответвители соответственно.

Воспроизведение мультимедиа 31-битный регистр сдвига с линейной обратной связью Фибоначчи с отводами в положениях 28 и 31, что дает ему максимальный цикл и период при такой скорости почти 6,7 лет. Схема использует 4x74HC565N для регистров сдвига, 74HC86N для XOR и инвертора и таймер LMC555 для тактовых импульсов.

LFSR имеет максимальную длину тогда и только тогда, когда соответствующий полином обратной связи примитивный. Это означает, что следующие условия являются необходимыми (но недостаточными):

Количество ответвлений равно , даже.
Набор ответвлений взаимно заполнен по множеству ; то есть не должно быть никакого делителя, кроме 1, общего для всех ответвлений.

Таблицы примитивных многочленов, из которых могут быть построены LFSR максимальной длины, приведены ниже и в ссылках.

Для данной длины LFSR может быть более одной последовательности ответвлений максимальной длины. Кроме того, как только одна последовательность отводов максимальной длины будет найдена, автоматически следует другая. Если последовательность ответвлений в n-битном LFSR равна [n, A, B, C, 0], где 0 соответствует члену x = 1, тогда соответствующая «зеркальная» последовательность будет [n, n - C, n - B, n - A, 0]. Таким образом, последовательность ответвлений [32, 22, 2, 1, 0] имеет аналог [32, 31, 30, 10, 0]. Оба дают последовательность максимальной длины.

Пример в C приведен ниже:

# include unsigned lfsr1 (void) {uint16_t start_state = 0xACE1u; / * Любое ненулевое начальное состояние будет работать. * / uint16_t lfsr = start_state; uint16_t bit; / * Должен быть 16-битным, чтобы разрешить бит <<15 later in the code */ unsigned period = 0; do { /* taps: 16 14 13 11; feedback polynomial: x^16 + x^14 + x^13 + x^11 + 1 */ bit = ((lfsr>>0) ^ (lfsr>>2) ^ (lfsr>>3) ^ (lfsr>>5)) / * 1u * /; lfsr = (lfsr>>1) | (бит << 15); ++period; } while (lfsr != start_state); return period; }

Если доступна операция быстрой четности или popcount, бит обратной связи может быть вычислен более эффективно как скалярное произведение регистра с характеристический полином:

бит = четность (lfsr 0x002Du);

или

бит = popcnt (lfsr 0x002Du) / * 1u * /;

. Если доступна операция поворота, новое состояние может быть вычислено более эффективно как

lfsr = rotateright ((lfsr ~ 1u) | (bit 1u), 1);

или эквивалентный

bit ^ = lfsr, bit = 1u, bit ^ = lfsr, lfsr = rotateright (bit, 1);

Эта конфигурация LFSR также известна как стандартный, многие-к-одному или внешние шлюзы XOR . Альтернативная конфигурация Галуа описана в следующем разделе.

LFSR Галуа

16-битный LFSR Галуа. Приведенные выше номера регистров соответствуют тому же примитивному полиному, что и пример Фибоначчи, но подсчитываются в обратном порядке. в направлении сдвига. Этот регистр также проходит через максимальное количество из 65535 состояний, исключая в состоянии все нули. За показанным шестнадцатеричным состоянием ACE1 будет следовать шестнадцатеричный код E270.

Названный в честь французского математика Эвариста Галуа, LFSR в конфигурации Галуа, также известный как модульный, внутренние операции XOR или LFSR «один ко многим» - это альтернативная структура, которая может генерировать тот же выходной поток, что и обычный LFSR (но со смещением во времени). В конфигурации Галуа, когда система синхронизируется, биты, которые не являются ответвлениями, смещаются на одну позицию вправо без изменений. С другой стороны, ответвления подвергаются операции XOR с выходным битом, прежде чем они будут сохранены в следующей позиции. Новый выходной бит - это следующий входной бит. В результате, когда выходной бит равен нулю, все биты в регистре смещаются вправо без изменений, а входной бит становится нулевым. Когда выходной бит равен единице, все биты в позициях отводов меняются местами (если они равны 0, они становятся 1, а если они равны 1, они становятся 0), а затем весь регистр сдвигается вправо и входной бит становится 1.

Для генерации того же выходного потока порядок ответвлений является эквивалентом (см. выше) порядка для обычного LFSR, в противном случае поток будет обратным. Обратите внимание, что внутреннее состояние LFSR не обязательно одно и то же. Показанный регистр Галуа имеет тот же выходной поток, что и регистр Фибоначчи в первой секции. Между потоками существует временное смещение, поэтому для получения одного и того же вывода в каждом цикле потребуется другая начальная точка.

LFSR Галуа не объединяют каждое нажатие для создания нового ввода (XOR выполняется внутри LFSR, и никакие элементы XOR не запускаются последовательно, поэтому время распространения сокращается до одного XOR, а не всей цепочки), таким образом, можно вычислять каждое нажатие параллельно, увеличивая скорость выполнения.
В программной реализации LFSR форма Галуа более эффективна, поскольку операции XOR могут быть реализованы словом за один раз: только выходной бит должен проверяться индивидуально.

Ниже приведен пример кода C для 16-битного примера LFSR Галуа с максимальным периодом на рисунке:

# include беззнаковый lfsr2 (void) {uint16_t start_state = 0xACE1u; / * Любое ненулевое начальное состояние будет работать. * / uint16_t lfsr = start_state; беззнаковый период = 0; do {#ifndef LEFT unsigned lsb = lfsr 1u; / * Получить младший бит (т.е. выходной бит). * / lfsr>>= 1; / * Регистр сдвига * / if (lsb) / * Если выходной бит равен 1, * / lfsr ^ = 0xB400u; / * применяем маску переключения. * / #else unsigned msb = (int16_t) lfsr < 0; /* Get MSB (i.e., the output bit). */ lfsr <<= 1; /* Shift register */ if (msb) /* If the output bit is 1, */ lfsr ^= 0x002Du; /* apply toggle mask. */ #endif ++period; } while (lfsr != start_state); return period; }

Обратите внимание, что

if (lsb) lfsr ^ = 0xB400u;

также можно записать как

lfsr ^ = (-lsb) 0xB400u;

что может дать более эффективный код на некоторых компиляторах; вариант со сдвигом влево может дать еще лучший код: msb - это перенос от добавления lfsrк самому себе.

Недвоичный LFSR Галуа

Двоичные LFSR Галуа, подобные показанным выше, могут быть обобщены на любой q-ичный алфавит {0, 1,..., q - 1} (например, для двоичного кода q = 2, а алфавит - это просто {0, 1}). В этом случае компонент исключающее ИЛИ обобщается до сложения по модулю -q (обратите внимание, что XOR - это сложение по модулю 2), а бит обратной связи (выходной бит) умножается (по модулю-q) на q -арное значение, которое постоянно для каждой конкретной точки отвода. Обратите внимание, что это также обобщение двоичного случая, когда обратная связь умножается либо на 0 (нет обратной связи, то есть нет касания), либо на 1 (обратная связь присутствует). При соответствующей конфигурации отвода такие LFSR могут использоваться для генерации полей Галуа для произвольных простых значений q.

Xorshift LFSR

Как показано Джорджем Марсалья и дополнительно проанализировано Ричардом П. Брентом, регистры сдвига с линейной обратной связью могут быть эффективно реализованы с помощью XOR и операции Shift.

Ниже приведен пример кода C для 16-битного Xorshift LFSR с максимальным периодом:

# include unsigned lfsr3 (void) {uint16_t start_state = 0xACE1u; / * Любое ненулевое начальное состояние будет работать. * / uint16_t lfsr = start_state; беззнаковый период = 0; сделать {lfsr ^ = lfsr>>7; lfsr ^ = lfsr << 9; lfsr ^= lfsr>>13; ++ период; } while (lfsr! = начальное_состояние); период возврата; }

Матричные формы

Двоичные LFSR конфигураций Фибоначчи и Галуа могут быть выражены как линейные функции с использованием матриц в $F 2 {\ displaystyle \ mathbb {F} _ {2}}$ $\ mathbb {F} _ {2}$ (см. GF (2) ). Использование сопутствующей матрицы характеристического полинома LFSR и обозначение начального числа как вектора-столбца $(a 0, a 1,…, an - 1) T {\ displaystyle (a_ {0}, a_ {1}, \ dots, a_ {n-1}) ^ {\ mathrm {T}}}$ ${\ displaystyle (a_ {0}, a_ {1}, \ dots, a_ {n-1}) ^ { \ mathrm {T}}}$ , состояние регистра в конфигурации Фибоначчи после $k {\ displaystyle k}$ $k$ шаги задаются как

(akak + 1 ak + 2 ⋮ ak + n - 1) = (0 1 0 ⋯ 0 0 0 1 ⋯ 0 ⋮ ⋮ ⋮ ⋮ c 0 c 1 c 2 ⋯ cn - 1) (ak - 1 akak + 1 ⋮ ak + n - 2) = (0 1 0 ⋯ 0 0 0 1 ⋯ 0 ⋮ ⋮ ⋮ ⋱ ⋮ c 0 c 1 c 2 ⋯ cn - 1) k (a 0 a 1 a 2 ⋮ an - 1) {\ displaystyle {\ begin {pmatrix} a_ {k} \\ a_ {k + 1} \\ a_ {k + 2} \\\ vdots \\ a_ {k + n -1} \ end {pmatrix}} = {\ begin {pmatrix} 0 1 0 \ cdots 0 \\ 0 0 1 \ cdots 0 \\\ vdots \ vdots \ vdots \ ddots \ vdots \\ c_ {0} c_ { 1} c_ {2} \ cdots c_ {n-1} \ end {pmatrix}} {\ begin {pmatrix} a_ {k-1} \\ a_ {k} \\ a_ {k + 1} \\\ vdots \\ a_ {k + n-2} \ end {pmatrix}} = {\ begin {pmatrix} 0 1 0 \ cdots 0 \\ 0 0 1 \ cdots 0 \\\ vdots \ vdots \ vdots \ ddots \ vdots \\ c_ {0} c_ {1} c_ {2} \ cdots c_ {n-1} \ end {pmatrix} } ^ {k} {\ begin {pmatrix} a_ {0} \\ a_ {1} \\ a_ {2} \\\ vdots \\ a_ {n-1} \ end {pmatrix}}}

{\ displaystyle {\ begin {pmatrix} a_ {k} \ \ a_ {k + 1} \\ a_ {k + 2} \\\ vdots \\ a_ {k + n-1} \ end {pmatrix}} = {\ begin {pmatrix} 0 1 0 \ cdots 0 \\ 0 0 1 \ cdots 0 \\\ vdots \ vdots \ vdots \ ddots \ vdots \\ c_ {0} c_ {1} c_ {2} \ cdots c_ {n-1} \ end {pmatrix}} {\ begin {pmat rix} a_ {k-1} \\ a_ {k} \\ a_ {k + 1} \\\ vdots \\ a_ {k + n-2} \ end {pmatrix}} = {\ begin {pmatrix} 0 1 0 \ cdots 0 \\ 0 0 1 \ cdots 0 \\\ vdots \ vdots \ vdots \ ddots \ vdots \\ c_ {0} c_ {1} c_ {2} \ cdots c_ {n-1} \ end {pmatrix}} ^ {k} {\ begin {pmatrix} a_ {0} \\ a_ {1} \\ a_ {2} \\\ vdots \\ a_ {n-1} \ end {pmatrix}}}

Для форму Галуа, имеем

(akak + 1 ak + 2 ⋮ ak + n - 1) = (c 0 1 0 ⋯ 0 c 1 0 1 ⋯ 0 ⋮ ⋮ ⋮ ⋱ cn - 1 0 0 ⋯ 0) (ak - 1 akak + 1 ⋮ ak + n - 2) = (c 0 1 0 ⋯ 0 c 1 0 1 ⋯ 0 ⋮ ⋮ ⋮ cn - 1 0 0 ⋯ 0) k (a 0 a 1 a 2 ⋮ ан - 1) {\ displaystyle {\ begin {pmatrix} a_ {k} \\ a_ {k + 1} \\ a_ {k + 2} \\\ vdots \\ a_ {k + n-1} \ end { pmatrix}} = {\ begin {pmatrix} c_ {0} 1 0 \ cdots 0 \\ c_ {1} 0 1 \ cdots 0 \\\ vdots \ vdots \ vdots \ ddots \ vdots \\ c_ {n- 1} 0 0 \ cdots 0 \ end {pmatrix}} {\ begin {pmatrix} a_ {k-1} \\ a_ {k} \\ a_ {k + 1} \\\ vdots \\ a_ {k + n- 2} \ end {pmatrix}} = {\ begin {pmatrix} c_ {0} 1 0 \ cdots 0 \\ c_ {1} 0 1 \ cdots 0 \\\ vdots \ vdots \ vdots \ ddots \ vdots \ \ c_ {n-1} 0 0 \ cdots 0 \ end {pmatrix}} ^ {k} {\ begin {pmatrix} a_ {0} \\ a_ {1} \\ a_ {2} \\\ vdots \\ a_ {n-1} \ end {pmatrix}}}

{\ displaystyle {\ begin {pmatrix} a_ {k} \\ a_ {k + 1} \\ a_ {k + 2 } \\\ vdots \\ a_ {k + n-1} \ end {pmatrix}} = {\ begin {pmatrix} c_ {0} 1 0 \ cdots 0 \\ c_ {1} 0 1 \ cdots 0 \\\ vdots \ vdots \ vdots \ ddots \ vdots \\ c_ {n-1} 0 0 \ cdots 0 \ end {pmatrix}} {\ begin {pmatrix} a_ {k-1} \\ a_ {k} \\ a_ {k + 1} \\\ vdots \\ a_ {k + n-2} \ end {pmatrix}} = {\ begin {pmatrix} c_ {0} 1 0 \ cdots 0 \\ c_ {1} 0 1 \ cdots 0 \\\ vdots \ vdots \ vdots \ ddots \ vdots \\ c_ {n-1} 0 0 \ cdots 0 \ end {pmatrix}} ^ {k} {\ begin {pmatrix} a_ {0} \ \ a_ {1} \\ a_ {2} \\\ vdots \\ a_ {n-1} \ end {pmatrix}}}

Эти формы естественным образом обобщаются на произвольные поля.

Некоторые полиномы для максимальных LFSR

В следующей таблице перечислены полиномы максимальной длины для длин регистра сдвига до 24. Обратите внимание, что для любого заданного сдвига может существовать более одного полинома максимальной длины. длина регистра. Список альтернативных многочленов максимальной длины для длин регистра сдвига 4–32 (при превышении которых становится невозможным их сохранение или передача) можно найти здесь: http://www.ece.cmu.edu/~koopman /lfsr/index.html.

Биты (n)	Полином обратной связи	Период ( $2 n - 1 {\ displaystyle 2 ^ {n} -1}$ $2 ^ {n} -1$ )
2	$x 2 + x + 1 {\ displaystyle x ^ {2} + x + 1}$ $x ^ {2} + x + 1$	3
3	$x 3 + x 2 + 1 {\ displaystyle x ^ {3} + x ^ {2} +1}$ $x ^ {3} + x ^ {2} +1$	7
4	$x 4 + x 3 + 1 {\ displaystyle x ^ {4} + x ^ {3} +1}$ $x ^ {4} + x ^ {3} +1$	15
5	$x 5 + x 3 + 1 {\ displaystyle x ^ {5} + x ^ {3 } +1}$ $x ^ {{5}} + x ^ {{3}} + 1$	31
6	$x 6 + x 5 + 1 {\ displaystyle x ^ {6} + x ^ {5} +1}$ $x ^ {{6}} + x ^ {{5} } +1$	63
7	$x 7 + x 6 + 1 { \ displaystyle x ^ {7} + x ^ {6} +1}$ $x ^ {{7}} + x ^ {{6}} + 1$	127
8	$x 8 + x 6 + x 5 + x 4 + 1 {\ displaystyle x ^ {8} + x ^ {6} + x ^ {5} + x ^ {4} +1}$ $x ^ {{8}} + x ^ {{6}} + x ^ {{5 }} + x ^ {{4}} + 1$	255
9	$x 9 + x 5 + 1 {\ displaystyle x ^ {9} + x ^ {5} +1}$ $x ^ {{9}} + x ^ {{5}} + 1$	511
10	$x 10 + x 7 + 1 {\ displaystyle x ^ {10} + x ^ {7} +1}$ $x ^ {{10}} + x ^ {{7}} + 1$	1,023
11	$x 11 + x 9 + 1 { \ displaystyle x ^ {11} + x ^ {9} +1}$ $x ^ {{11}} + x ^ {{9}} + 1$	2,047
12	$x 12 + x 11 + x 10 + x 4 + 1 {\ displaystyle x ^ {12} + x ^ {11} + x ^ {10} + x ^ {4} +1}$ $x ^ {{12}} + x ^ {{11}} + x ^ {{10 }} + x ^ {{4}} + 1$	4,095
13	$x 13 + x 12 + x 11 + x 8 + 1 {\ displaystyle x ^ {13} + x ^ {12} + x ^ {11} + x ^ {8} +1}$ $x ^ {{13}} + x ^ {{12}} + x ^ {{11}} + x ^ {{8}} + 1$	8,191
14	$x 14 + x 13 + x 12 + x 2 + 1 {\ displaystyle x ^ {14} + x ^ {13} + x ^ {12} + x ^ {2} +1}$ $x ^ {{14}} + x ^ {{13}} + x ^ {{12}} + x ^ {{2}} + 1$	16,383
15	$x 15 + x 14 + 1 {\ displaystyle x ^ {15} + x ^ {14} +1}$ $x ^ {{15}} + x ^ {{14}} + 1$	32,767
16	$x 16 + x 15 + x 13 + x 4 + 1 {\ displaystyle x ^ {16} + x ^ {15} + x ^ {13} + x ^ {4} +1}$ ${\ displaystyle x ^ {16} + x ^ {15} + x ^ {13} + x ^ {4} +1}$	65 535
17	$x 17 + x 14 + 1 {\ displaystyle x ^ {17} + x ^ {14} +1}$ $x ^ {{17}} + x ^ {{14}} + 1$	131,071
18	$x 18 + x 11 + 1 {\ displaystyle x ^ {18} + x ^ {11} +1}$ $x ^ { {18}} + x ^ {{11}} + 1$	262,143
19	$x 19 + x 18 + x 17 + x 14 + 1 {\ displaystyle x ^ {19} + x ^ { 18} + x ^ {17} + x ^ {14} +1}$ $x ^ {{19}} + x ^ {{18}} + x ^ {{17}} + x ^ {{14}} + 1$	524,287
20	$x 20 + x 17 + 1 {\ displaystyle x ^ {20} + x ^ {17} + 1}$ ${\ displaystyle x ^ {20} + x ^ {17} +1}$	1 048 575
21	$x 21 + x 19 + 1 {\ displaystyle x ^ {21} + x ^ {19} +1}$ ${\ displaystyle x ^ {21} + x ^ {19} +1}$	2 097 151
22	$x 22 + x 21 + 1 {\ displaystyle x ^ {22} + x ^ {21} +1}$ ${\ displaystyle x ^ {22} + x ^ {21} +1}$	4,194,303
23	$x 23 + x 18 + 1 {\ displaystyle x ^ {23} + x ^ {18} +1}$ ${\ displaystyle x ^ { 23} + x ^ {18} +1}$	8,388,607
24	$x 24 + x 23 + x 22 + x 17 + 1 {\ displaystyle x ^ {24} + x ^ {23} + x ^ {22} + x ^ {17} +1}$ ${\ displaystyle x ^ {24} + x ^ {23} + x ^ {22} + x ^ {17} +1 }$	16,777,215
3–168	[2]
2–786,. 1024,. 2048,. 4096	[3]

Свойства выходного потока

Единицы и нули встречаются в "прогонах". Выходной поток 1110010, например, состоит из четырех прогонов длиной 3, 2, 1, 1 по порядку. За один период максимального LFSR происходит 2 прогона (в приведенном выше примере 3-битный LFSR имеет 4 прогона). Ровно половина этих прогонов имеет длину один бит, четверть - длину двух бита, до одной серии нулей длиной n - 1 бит и одиночной серии единиц длиной n бит. Это распределение почти равно статистическому математическому ожиданию для действительно случайной последовательности. Однако вероятность обнаружения именно этого распределения в выборке действительно случайной последовательности довольно мала.
Выходные потоки LFSR детерминированы. Если текущее состояние и позиции элементов XOR в LFSR известны, следующее состояние может быть предсказано. Это невозможно с действительно случайными событиями. С LFSR максимальной длины гораздо проще вычислить следующее состояние, поскольку их количество легко ограничивается для каждой длины.
Выходной поток обратим; LFSR с зеркальными отводами будет циклически перебирать выходную последовательность в обратном порядке.
Значение, состоящее из всех нулей, не может отображаться. Таким образом, LFSR длины n не может использоваться для генерации всех двух значений.

Приложения

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

Используется как счетчик

Повторяющаяся последовательность состояний LFSR позволяет используется как тактовый делитель или как счетчик, когда приемлема недвоичная последовательность, как это часто бывает, когда компьютерный индекс или места кадрирования должны быть машиночитаемыми. LFSR счетчики имеют более простую логику обратной связи, чем естественные двоичные счетчики или счетчики кода Грея, и поэтому могут работать с более высокими тактовыми частотами. Однако необходимо гарантировать, что LFSR никогда не перейдет в состояние «все нули», например, предварительно установив его при запуске в любое другое состояние в последовательности. Таблица примитивных полиномов показывает, как LFSR могут быть расположены в форме Фибоначчи или Галуа, чтобы дать максимальные периоды. Можно получить любой другой период, добавив к LFSR, который имеет более длинный период, некоторую логику, которая сокращает последовательность, пропуская некоторые состояния.

Использование в криптографии

LFSR долгое время использовались в качестве генераторов псевдослучайных чисел для использования в потоковых шифрах (особенно в военных криптография ), благодаря простоте построения из простых электромеханических или электронных схем, длинных периодов и очень однородных распределено выходных потоков. Однако LFSR - это линейная система, приводящая к довольно простому криптоанализу. Например, учитывая участок известного открытого текста и соответствующий зашифрованный текст, злоумышленник может перехватить и восстановить участок выходного потока LFSR, используемый в описанной системе, и из этого участка выходного потока может построить LFSR минимальный размер, который имитирует предполагаемый приемник с использованием алгоритма Берлекампа-Месси. Затем этот LFSR может быть передан перехваченному фрагменту выходного потока для восстановления оставшегося открытого текста.

Для уменьшения этой проблемы в потоковых шифрах на основе LFSR используются три общих метода:

Нелинейная комбинация нескольких бит из состояния LFSR ;
Нелинейная комбинация выходных битов двух или более LFSR (см. Также: генератор сжатия ); или с использованием эволюционного алгоритма для введения нелинейности.
Нерегулярная синхронизация LFSR, как в генераторе переменного шага.

Важные потоковые шифры на основе LFSR включают A5 / 1 и A5 / 2, используемые в сотовых телефонах GSM, E0, используемые в Bluetooth, и термоусадочный генератор. Шифр A5 / 2 был взломан, и как A5 / 1, так и E0 имеют серьезные недостатки.

Регистр сдвига с линейной обратной связью тесно связан с линейными конгруэнтными генераторами.

Использование в тестировании схем

LFSR используются в тестировании схем для генерации тестовых шаблонов (для исчерпывающего тестирования, псевдослучайного тестирования или псевдо-исчерпывающего тестирования) и для сигнатурного анализа.

Генерация тестового шаблона

Полные LFSR обычно используются в качестве генераторов шаблонов для исчерпывающего тестирования, поскольку они охватывают все возможные входы для схемы с n входами. LFSR максимальной длины и взвешенные LFSR широко используются в качестве генераторов псевдослучайных тестовых шаблонов для приложений псевдослучайного тестирования.

Анализ сигнатур

В методах встроенного самотестирования (BIST) сохранение всех выходных сигналов схемы на микросхеме невозможно, но выход схемы может быть сжат сформировать подпись, которая позже будет сравнена с золотой подписью (хорошей схемы) для обнаружения неисправностей. Поскольку это сжатие происходит с потерями, всегда существует вероятность того, что неисправный вывод также генерирует ту же сигнатуру, что и золотая подпись, и ошибки не могут быть обнаружены. Это состояние называется маскированием ошибок или псевдонимом. BIST реализуется с помощью регистра подписи с несколькими входами (MISR или MSR), который является типом LFSR. Стандартный LFSR имеет один вентиль XOR или XNOR, где вход элемента соединен с несколькими «ответвлениями», а выход соединен со входом первого триггера. MISR имеет ту же структуру, но вход в каждый триггер подается через вентиль XOR / XNOR. Например, 4-битный MISR имеет 4-битный параллельный выход и 4-битный параллельный вход. Входом первого триггера является XOR / XNORd с нулевым битом параллельного входа и «отводами». Каждый второй вход триггера является XOR / XNORd с предыдущим выходом триггера и соответствующим битом параллельного входа. Следовательно, следующее состояние MISR зависит от нескольких последних состояний, а не только от текущего состояния. Следовательно, MISR всегда будет генерировать одну и ту же золотую подпись, учитывая, что входная последовательность каждый раз одинакова. Недавние приложения предлагают триггеры установки-сброса в качестве «ответвлений» LFSR. Это позволяет системе BIST оптимизировать хранение, поскольку триггеры установки-сброса могут сохранять начальное начальное значение для генерации всего потока битов из LFSR. Тем не менее, это требует изменений в архитектуре BIST, это опция для конкретных приложений.

Используется в цифровом вещании и связи

Скремблирование

Для предотвращения коротких повторяющихся последовательностей (например, серий 0 или 1) от формирования спектральных линий, которые могут усложнить отслеживание символов на приемник или мешает другим передачам, последовательность битов данных комбинируется с выходом регистра линейной обратной связи перед модуляцией и передачей. Это скремблирование удаляется в приемнике после демодуляции. Когда LFSR работает с той же скоростью передачи, что и передаваемый поток символов, этот метод упоминается как скремблирование. Когда LFSR работает значительно быстрее, чем поток символов, последовательность битов, сгенерированная LFSR, называется чиповым кодом. Чип-код объединяется с данными с использованием эксклюзивного доступа или перед передачей с использованием двоичной фазовой манипуляции или аналогичного метода модуляции. Результирующий сигнал имеет более широкую полосу пропускания, чем данные, и поэтому это метод связи с расширенным спектром. Когда используется только для свойства расширенного спектра, этот метод называется расширенный спектр прямой последовательности ; когда используется для различения нескольких сигналов, передаваемых в одном и том же канале одновременно и на одной частоте, это называется множественный доступ с кодовым разделением.

Ни одну из схем не следует путать с шифрованием или шифрованием ; скремблирование и распространение с помощью LFSR не защищают информацию от подслушивания. Вместо этого они используются для создания эквивалентных потоков, обладающих удобными техническими характеристиками, обеспечивающими надежную и эффективную модуляцию и демодуляцию.

Системы цифрового вещания, использующие регистры с линейной обратной связью:

Стандарты ATSC (система передачи цифрового телевидения - Северная Америка)
DAB (Цифровое аудиовещание система - для радио)
DVB-T (система передачи цифрового телевидения - Европа, Австралия, часть Азии)
NICAM (цифровая аудиосистема для телевидения)

Другие системы цифровой связи, использующие LFSR:

Бизнес-сервис INTELSAT (IBS)
Промежуточная скорость передачи данных (IDR)
HDMI 2.0
SDI (передача через последовательный цифровой интерфейс)
Передача данных по PSTN (согласно рекомендациям ITU-T серии V)
CDMA (множественный доступ с кодовым разделением каналов) сотовая телефония
100BASE-T2 " fast "Ethernet скремблирует биты, используя LFSR
1000BASE-T Ethernet, наиболее распространенную форму Gigabit Ethernet, скремблирует биты, используя LFSR
PCI Express
SATA
Serial connected SCSI" (SAS / SPL)
USB 3.0
IEEE 802.11a скремблирует биты с помощью LFSR
Bluetoo Канальный уровень с низким энергопотреблением использует LFSR (называемый отбеливающим)
Спутниковые навигационные системы, такие как GPS и ГЛОНАСС. Все современные системы используют выходы LFSR для генерации некоторых или всех своих кодов ранжирования (в качестве чипового кода для CDMA или DSSS) или для модуляции несущей без данных (например, код ранжирования GPS L2 CL). ГЛОНАСС также использует множественный доступ с частотным разделением в сочетании с DSSS.

Другое применение

LFSR также используются в системах радиопомех для генерации псевдослучайного шума для повысить уровень шума целевой системы связи.

Немецкий сигнал времени DCF77, в дополнение к амплитудной манипуляции, использует фазовую манипуляцию, управляемую 9-ступенчатым LFSR для повышения точности времени приема и устойчивость потока данных в присутствии шума.

См. также

Вертушка
Мерсенна твистер
Последовательность максимальной длины
Аналоговый регистр сдвига с обратной связью
NLFSR, Регистр сдвига нелинейной обратной связи
Счетчик звонков
Псевдослучайная двоичная последовательность

Ссылки

Внешние ссылки

Регистры сдвига линейной обратной связи на Wayback Machine (заархивировано 1 октября 2018 г.) - Теория и реализация LFSR, последовательности максимальной длины и подробные таблицы обратной связи для длин от 7 до 16 777 215 (от 3 до 24 этапов) и частичные таблицы для длин до 4 294 967 295 (от 25 до 32 этапов).
Рекомендация O.151 Международного союза электросвязи (август 1992 г.)
Таблица максимальной длины LFSR длиной от 2 до 67.
Процедура генерации псевдослучайных чисел для микропроцессора MAX765x
http://www.ece.ualberta.ca/~elliott/ee552/studentAppNotes/1999f/Drivers_Ed/lfsr.html
http://www.quadibloc.com/crypto/co040801. htm
Простое объяснение LFSR для инженеров
Условия обратной связи
Общая теория LFSR
Реализация LFSR в VHDL.
Простое кодирование VHDL для LFSR Галуа и Фибоначчи.
mlpolygen: Максимальный Генератор полиномов длины