Регистр сдвига с линейной обратной связью - Linear-feedback shift register

"LFSR" перенаправляется сюда. Для аэропорта, использующего этот код ИКАО, см. Реймс - Авиабаза Шампань.

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

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

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

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

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

LFSR Фибоначчи

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

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

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

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

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

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

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

Воспроизвести медиа

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

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

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

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

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

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

# включить беззнаковый lfsr1(пустота){    uint16_t start_state = 0xACE1u;  / * Любое ненулевое начальное состояние будет работать. * /    uint16_t lfsr = start_state;    uint16_t немного;                    / * Должен быть 16-битным, чтобы разрешить бит << 15 позже в коде * /    беззнаковый период = 0;    делать    {   / * отводов: 16 14 13 11; полином обратной связи: x ^ 16 + x ^ 14 + x ^ 13 + x ^ 11 + 1 * /        немного = ((lfsr >> 0) ^ (lfsr >> 2) ^ (lfsr >> 3) ^ (lfsr >> 5)) / * & 1u * /;        lfsr = (lfsr >> 1) | (немного << 15);        ++период;    }    в то время как (lfsr != start_state);    вернуть период;}

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

немного = паритет(lfsr & 0x002Du);

или

немного = popcnt(lfsr & 0x002Du) / * & 1u * /;

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

lfsr = вращение((lfsr & ~1U) | (немного & 1U), 1);

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

немного ^= lfsr, немного &= 1U, немного ^= lfsr, lfsr = вращение(немного, 1);

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

Галуа LFSR

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

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

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

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

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

# включить беззнаковый lfsr2(пустота){    uint16_t start_state = 0xACE1u;  / * Любое ненулевое начальное состояние будет работать. * /    uint16_t lfsr = start_state;    беззнаковый период = 0;    делать    {#ifndef LEFT        беззнаковый lsb = lfsr & 1U;  / * Получить младший бит (т.е. выходной бит). * /        lfsr >>= 1;                /* Регистр сдвига */        если (lsb)                   / * Если выходной бит равен 1, * /            lfsr ^= 0xB400u;       / * применяем маску переключения. * /#else        беззнаковый msb = (int16_t) lfsr < 0;   / * Получить MSB (т.е. выходной бит). * /        lfsr <<= 1;                          /* Регистр сдвига */        если (msb)                             / * Если выходной бит равен 1, * /            lfsr ^= 0x002Du;                 / * применяем маску переключения. * /#endif        ++период;    }    в то время как (lfsr != start_state);    вернуть период;}

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

        если (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

Основная статья: Xorshift

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

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

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

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

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

${\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&\ddots &\vdots \\\vdots &\vdots &\ddots &\ddots &0\\0&0&\cdots &0&1\\c_{0}&c_{1}&\cdots &\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&\ddots &\vdots \\\vdots &\vdots &\ddots &\ddots &0\\0&0&\cdots &0&1\\c_{0}&c_{1}&\cdots &\cdots &c_{n-1}\end{pmatrix}}^{k}{\begin{pmatrix}a_{0}\\a_{1}\\a_{2}\\\vdots \\a_{n-1}\end{pmatrix}}}$

Матрица для соответствующей формы Галуа:

${\displaystyle {\begin{pmatrix}c_{0}&1&0&\cdots &0\\c_{1}&0&1&\ddots &\vdots \\\vdots &\vdots &\ddots &\ddots &0\\c_{n-2}&0&\cdots &0&1\\c_{n-1}&0&\cdots &\cdots &0\end{pmatrix}}}$

Для подходящей инициализации

${\displaystyle a'_{i}=\sum _{i=0}^{j}a_{i-j}c_{n-j},\ 0\leq i<n}$

верхний коэффициент вектора-столбца:

${\displaystyle {\begin{pmatrix}c_{0}&1&0&\cdots &0\\c_{1}&0&1&\ddots &\vdots \\\vdots &\vdots &\ddots &\ddots &0\\c_{n-2}&0&\cdots &0&1\\c_{n-1}&0&\cdots &\cdots &0\end{pmatrix}}^{k}{\begin{pmatrix}a'_{0}\\a'_{1}\\a'_{2}\\\vdots \\a'_{n-1}\end{pmatrix}}}$

дает срок а_k исходной последовательности.

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

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

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

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

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

• Единицы и нули встречаются в «пробегах». Выходной поток 1110010, например, состоит из четырех прогонов длиной 3, 2, 1, 1 по порядку. За один период максимального LFSR 2^п−1 происходят запуски (в приведенном выше примере 3-битный LFSR имеет 4 запуска). Ровно половина из этих прогонов имеют длину один бит, четверть - два бита, вплоть до одного цикла нулей. п - 1 бит и один запуск п биты длинные. Это распределение почти равно статистическому ожидаемое значение для действительно случайной последовательности. Однако вероятность найти именно это распределение в выборке действительно случайной последовательности довольно мала.^{[расплывчатый ]}.
• Потоки вывода LFSR детерминированный. Если текущее состояние и позиции элементов XOR в LFSR известны, следующее состояние может быть предсказано.^[7] Это невозможно с действительно случайными событиями. С LFSR максимальной длины намного проще вычислить следующее состояние, поскольку их количество легко ограничивается для каждой длины.
• Выходной поток обратимый; LFSR с зеркальными отводами будет циклически перебирать выходную последовательность в обратном порядке.
• Значение, состоящее только из нулей, появиться не может. Таким образом, LFSR длины п не может быть использован для генерации всех 2^п ценности.

Приложения

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

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

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

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

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

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

• Нелинейный сочетание нескольких биты из ЛФСР штат;
• Нелинейная комбинация выходных битов двух или более LFSR (см. Также: усадочный генератор ); или используя Эволюционный алгоритм ввести нелинейность.^[8]
• Нерегулярная синхронизация LFSR, как в генератор переменного шага.

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

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

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

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

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

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

Сигнатурный анализ

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

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

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

Основная статья: Скремблер

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

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

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

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

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

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

Другое использование

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

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

Смотрите также

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

использованная литература

1. Геремия, Патрик. «Вычисление с циклической проверкой избыточности: реализация с использованием TMS320C54x» (PDF). Инструменты Техаса. п. 6. Получено 16 октября, 2016.
2. Регистры сдвига с линейной обратной связью в устройствах Virtex
3. Пресс, Уильям; Теукольский, Саул; Веттерлинг, Уильям; Фланнери, Брайан (2007). Числовые рецепты: искусство научных вычислений, третье издание. Издательство Кембриджского университета. п. 386. ISBN  978-0-521-88407-5.
4. Марсалья, Джордж (Июль 2003 г.). "Xorshift RNGs". Журнал статистического программного обеспечения. 8 (14). Дои:10.18637 / jss.v008.i14.
5. Брент, Ричард П. (Август 2004 г.). «Заметка о генераторах случайных чисел Xorshift Марсаглии». Журнал статистического программного обеспечения. 11 (5). Дои:10.18637 / jss.v011.i05.
6. Кляйн, А. (2013). «Регистры сдвига с линейной обратной связью». Потоковые шифры. Лондон: Спрингер. С. 17–18. Дои:10.1007/978-1-4471-5079-4_2. ISBN  978-1-4471-5079-4.
7. http://www.xilinx.com/support/documentation/application_notes/xapp052.pdf
8. А. Пурханад, А. Садр, А. Кашанипур «Генерация высококачественных псевдослучайных чисел с помощью эволюционных методов», Конгресс IEEE по вычислительному интеллекту и безопасности, вып. 9, стр. 331-335, май 2008 г. [1]
9. Баркам, Элад; Бихам, Эли; Келлер, Натан (2008), «Мгновенный криптоанализ зашифрованной связи GSM с использованием только зашифрованного текста» (PDF), Журнал криптологии, 21 (3): 392–429, Дои:10.1007 / s00145-007-9001-y
10. Лу, Йи; Вилли Мейер; Серж Воденэ (2005). Атака условной корреляции: практическая атака на шифрование Bluetooth. Крипто 2005. Конспект лекций по информатике. 3621. Санта-Барбара, Калифорния, США. С. 97–117. CiteSeerX  10.1.1.323.9416. Дои:10.1007/11535218_7. ISBN  978-3-540-28114-6.
11. RFC 4086 раздел 6.1.3 «Традиционные псевдослучайные последовательности»
12. Мартинес Л.Х., Хуршид С., Редди С.М. Генерация LFSR для большого тестового покрытия и низких накладных расходов на оборудование. ИЭПП «Компьютеры и цифровые технологии». 2019 21 августа.Репозиторий UoL
13. Раздел 9.5 спецификации SATA, редакция 2.6
14. Hetzel, P. (16 марта 1988 г.). Распространение времени через низкочастотный передатчик DCF77 с использованием псевдослучайной фазовой манипуляции несущей (PDF). 2-й Европейский форум по частоте и времени. Невшатель. стр. 351–364. Получено 11 октября 2011.

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

• Регистры сдвига с линейной обратной связью на 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: генератор полиномов максимальной длины