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

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

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

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

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

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

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

LFSR Фибоначчи

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

31-битный регистр сдвига Фибоначчи с линейной обратной связью и отводами в позициях 28 и 31, что обеспечивает максимальный цикл и период на этой скорости почти 6,7 года.

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

• LFSR максимальной длины создает m-последовательность (т. е. она циклически проходит через все возможные 2 ^m  - 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.}$

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

LFSR имеет максимальную длину тогда и только тогда, когда соответствующий полином обратной связи примитивен над полем Галуа GF(2). ^{[3] [4]} Это означает, что необходимы (но недостаточны) следующие условия:

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

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

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

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

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

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

• bit = parity(lfsr & 0x002Du);или эквивалентно
• bit = popcnt(lfsr & 0x002Du) /* & 1u */;. ( & 1uПревращает popcnt в настоящую функцию четности, но последующий битовый сдвиг bit << 15делает старшие биты нерелевантными.)

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

• lfsr = rotateright((lfsr & ~1u) | (bit & 1u), 1);или эквивалентно
• lfsr = rotateright(((bit ^ lfsr) & 1u) ^ lfsr, 1);

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

Пример на Python

Пример реализации аналогичного (16-битных отводов в [16,15,13,4]) Фибоначчи LFSR на Python будет выглядеть так:

start_state  =  1  <<  15  |  1 lfsr  =  период start_state = 0  while  True :  # Taps: 16 15 13 4; полином обратной связи: x^16 + x^15 + x^13 + x^4 + 1  бит  =  ( lfsr  ^  ( lfsr  >>  1 )  ^  ( lfsr  >>  3 )  ^  ( lfsr  >>  12 ))  &  1  lfsr  =  ( лфср  >>  1 )  |  ( бит  <<  15 )  период  +=  1,  если  lfsr  ==  start_state :  печать ( период )  перерыв

Если используется регистр из 16 бит, а отвод xor на четвертом, 13, 15 и шестнадцатом битах устанавливает максимальную длину последовательности.

Галуа ЛФСР

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

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

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

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

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

#include <stdint.h> unsigned lfsr_galois ( 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 ; /* Получаем старший бит (т.е. выходной бит). */ lfsr <<= 1 ; /* Регистр сдвига */ if ( msb ) /* Если выходной бит равен 1, */ lfsr ^= 0x002Du ; /* применяем маску переключения. */ #endif ++ период ; } while ( lfsr != start_state );                                             период возврата ; } 

Ветвь также может быть написана так, что может создавать более эффективный код на некоторых компиляторах. Кроме того, вариант со сдвигом влево может дать еще лучший код, поскольку старший бит представляет собой перенос в результате сложения самого себя.if (lsb) lfsr ^= 0xB400u;lfsr ^= (-lsb) & 0xB400u;lfsr

Параллельные вычисления Галуа LFSR

Биты состояния и результирующие биты также можно комбинировать и вычислять параллельно. Следующая функция вычисляет следующие 64 бита, используя 63-битный полином x⁶³ + x⁶² + 1:

#include <stdint.h> uint64_t prsg63 ( uint64_t lfsr ) { lfsr = lfsr << 32 | ( lfsr << 1 ^ lfsr << 2 ) >> 32 ; lfsr = lfsr << 32 | ( lfsr << 1 ^ lfsr << 2 ) >> 32 ; вернуть лфср ; }                           

Небинарный Галуа LFSR

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

Xorshift LFSR

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

Ниже приведен пример кода C для 16-битного Xorshift LFSR с максимальным периодом, использующего триплет 7,9,13 от Джона Меткалфа: ^[8]

#include <stdint.h> unsigned lfsr_xorshift ( void ) { uint16_t start_state = 0xACE1u ; /* Любое ненулевое начальное состояние будет работать. */ uint16_t lfsr = start_state ; беззнаковый период = 0 ;                do { // тройка 7,9,13 из http://www.retroprogramming.com/2017/07/xorshift-pseudorandom-numbers-in-z80.html lfsr ^= lfsr >> 7 ; lfsr ^= lfsr << 9 ; lfsr ^= lfsr >> 13 ; ++ период ; } while ( lfsr != start_state );                        период возврата ; } 

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

Двоичные LFSR конфигураций Фибоначчи и Галуа могут быть выражены как линейные функции с использованием матриц в (см. GF(2) ). ^[9] Используя сопутствующую матрицу характеристического полинома LFSR и обозначая начальное число как вектор-столбец , состояние регистра в конфигурации Фибоначчи после шагов определяется выражением ${\displaystyle \mathbb {F} _{2}}$ ${\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}}}$

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

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

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

В следующей таблице перечислены примеры полиномов обратной связи максимальной длины ( примитивных полиномов ) для длин сдвиговых регистров до 24. Формализм для LFSR максимальной длины был разработан Соломоном В. Голомбом в его книге 1967 года. ^[10] Число различных примитивных полиномов растет экспоненциально с длиной регистра сдвига и может быть точно рассчитано с использованием функции тотента Эйлера ^[11] (последовательность A011260 в OEIS ).

Xilinx опубликовал расширенный список счетчиков отводов до 168 бит. Таблицы полиномов максимальной длины доступны по адресу http://users.ece.cmu.edu/~koopman/lfsr/ и могут быть созданы проектом https://github.com/hayguen/mlpolygen.

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

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

Приложения

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

Использование в качестве счетчиков

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

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

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

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

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

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

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

Использование в тестировании цепей

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 всегда будет генерировать одну и ту же золотую подпись, учитывая, что входная последовательность каждый раз одинакова. В недавних приложениях ^[17] в качестве «отводов» 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 (множественный доступ с кодовым разделением каналов)
• «Быстрый» Ethernet 100BASE-T2 шифрует биты с помощью LFSR.
• 1000BASE-T Ethernet , наиболее распространенная форма Gigabit Ethernet, шифрует биты с помощью LFSR.
• PCI Экспресс
• САТА ^[18]
• Последовательный SCSI (SAS/SPL)
• USB 3.0
• IEEE 802.11a шифрует биты с помощью LFSR.
• Уровень связи Bluetooth с низким энергопотреблением использует LFSR (так называемое отбеливание).
• Системы спутниковой навигации, такие как GPS и ГЛОНАСС . Все современные системы используют выходы LFSR для генерации некоторых или всех своих кодов ранжирования (в качестве чипового кода для CDMA или DSSS) или для модуляции несущей без данных (например, кода дальности GPS L2 CL). ГЛОНАСС также использует множественный доступ с частотным разделением каналов в сочетании с DSSS.

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

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

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

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

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

Рекомендации

1. Джеремия, Патрик. «Вычисление проверки циклического избыточного кода: реализация с использованием TMS320C54x» (PDF) . Инструменты Техаса. п. 6 . Проверено 16 октября 2016 г.
2. Регистры сдвига с линейной обратной связью в устройствах Virtex
3. Нежный, Джеймс Э. (2003). Генерация случайных чисел и методы Монте-Карло (2-е изд.). Нью-Йорк: Спрингер. п. 38. ISBN 0-387-00178-6. ОСЛК  51534945.
4. Таусворт, Роберт К. (апрель 1965 г.). «Случайные числа, генерируемые линейной рекуррентностью по модулю два» (PDF) . Математика вычислений . 19 (90): 201–209. doi : 10.1090/S0025-5718-1965-0184406-1. S2CID  120804149.
5. Пресс, Уильям; Теукольский, Саул; Веттерлинг, Уильям; Фланнери, Брайан (2007). Численные рецепты: искусство научных вычислений, третье издание . Издательство Кембриджского университета . п. 386. ИСБН 978-0-521-88407-5.
6. Марсалья, Джордж (июль 2003 г.). «Xorshift ГСЧ». Журнал статистического программного обеспечения . 8 (14). дои : 10.18637/jss.v008.i14 .
7. Брент, Ричард П. (август 2004 г.). «Заметка о генераторах случайных чисел Xorshift Марсальи». Журнал статистического программного обеспечения . 11 (5). дои : 10.18637/jss.v011.i05 . hdl : 1885/34049 .
8. Меткалф, Джон (22 июля 2017 г.). «16-битные псевдослучайные числа Xorshift в сборке Z80». Ретро-программирование . Проверено 5 января 2022 г.
9. Кляйн, А. (2013). «Регистры сдвига с линейной обратной связью». Потоковые шифры . Лондон: Спрингер. стр. 17–18. дои : 10.1007/978-1-4471-5079-4_2. ISBN 978-1-4471-5079-4.
10. Голомб, Соломон В. (1967). Последовательности сдвиговых регистров . Лагуна-Хиллз, Калифорния: Aegean Park Press. ISBN 978-0894120480.
11. Вайсштейн, Эрик В. «Примитивный полином». mathworld.wolfram.com . Проверено 27 апреля 2021 г.
12. http://www.xilinx.com/support/documentation/application_notes/xapp052.pdf ^{[ пустой URL-адрес PDF ]}
13. А. Порганад, А. Садр, А. Кашанипур «Генерация высококачественных псевдослучайных чисел с использованием эволюционных методов», Конгресс IEEE по вычислительному интеллекту и безопасности, том. 9, стр. 331-335, май 2008 г. [1]
14. Баркам, Элад; Бихам, Эли; Келлер, Натан (2008), «Мгновенный криптоанализ зашифрованной связи GSM, содержащий только зашифрованный текст» (PDF) , Journal of Cryptology , 21 (3): 392–429, doi : 10.1007/s00145-007-9001-y, S2CID  459117, заархивировано из оригинала (PDF) 25 января 2020 г. , получено 15 сентября 2019 г.
15. Лу, Йи; Вилли Мейер; Серж Водене (2005). «Атака с условной корреляцией: практическая атака на шифрование Bluetooth». Достижения в криптологии – CRYPTO 2005. Конспекты лекций по информатике. Том. 3621. Санта-Барбара, Калифорния, США. стр. 97–117. CiteSeerX 10.1.1.323.9416 . дои : 10.1007/11535218_7. ISBN  978-3-540-28114-6. {{cite book}}: |journal=игнорируется ( помощь )CS1 maint: location missing publisher (link)
16. RFC 4086, раздел 6.1.3 «Традиционные псевдослучайные последовательности»
17. Мартинес Л.Х., Хуршид С., Редди С.М. Генерация LFSR для высокого охвата тестов и низких затрат на оборудование. IET Компьютеры и цифровая техника. 21 августа 2019 г. Репозиторий UoL
18. Раздел 9.5 спецификации SATA, версия 2.6.
19. Хетцель, П. (16 марта 1988 г.). Распространение по времени через НЧ-передатчик DCF77 с использованием псевдослучайной фазовой манипуляции несущей (PDF) . 2-й Европейский форум по частоте и времени. Невшатель. стр. 351–364 . Проверено 11 октября 2011 г.

дальнейшее чтение

• http://www.xilinx.com/support/documentation/application_notes/xapp052.pdf
• https://web.archive.org/web/20161007061934/http://courses.cse.tamu.edu/csce680/walker/lfsr_table.pdf
• http://users.ece.cmu.edu/~koopman/lfsr/index.html — Таблицы полиномов обратной связи максимальной длины для 2–64 бит.
• https://github.com/hayguen/mlpolygen — Код для генерации полиномов обратной связи максимальной длины

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

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

• LFSR и внутренняя генерация случайности: заметки NKS