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

«ЛФСР» перенаправляется сюда. Чтобы узнать об аэропорте, использующем этот код ИКАО, см. Реймс – авиабаза Шампань .

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

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

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

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

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

LFSR Фибоначчи

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

Duration: 30 seconds.0:30

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

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

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

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

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

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

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

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

• Число нажатий четное .
• Набор отводов является взаимно простым ; т. е. не должно быть делителя, отличного от 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 <stdint.h>
unsigned lfsr_fib(void)
{
    uint16_t start_state = 0xACE1u;  /* Any nonzero start state will work. */
    uint16_t lfsr = start_state;
    uint16_t bit;                    /* Must be 16-bit to allow bit<<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) | (bit << 15);
        ++period;
    }
    while (lfsr != start_state);

    return period;
}

быстрая операция четности или 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
period = 0

while True:
    # taps: 16 15 13 4; feedback polynomial: x^16 + x^15 + x^13 + x^4 + 1
    bit = (lfsr ^ (lfsr >> 1) ^ (lfsr >> 3) ^ (lfsr >> 12)) & 1
    lfsr = (lfsr >> 1) | (bit << 15)
    period += 1
    if lfsr == start_state:
        print(period)
        break

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

Галуа ЛФСР

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

Названный в честь французского математика Эвариста Галуа , LFSR в конфигурации Галуа, который также известен как модульные внутренние XOR или LFSR «один-ко-многим» , представляет собой альтернативную структуру, которая может генерировать тот же выходной поток, что и обычный LFSR (но со смещением). во времени). В конфигурации Галуа, когда система тактируется, биты, не являющиеся отводами, сдвигаются на одну позицию вправо без изменений. С другой стороны, отводы подвергаются операции 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;  /* Any nonzero start state will work. */
    uint16_t lfsr = start_state;
    unsigned period = 0;

    do
    {
#ifndef LEFT
        unsigned lsb = lfsr & 1u;  /* Get LSB (i.e., the output bit). */
        lfsr >>= 1;                /* Shift register */
        if (lsb)                   /* If the output bit is 1, */
            lfsr ^= 0xB400u;       /*  apply toggle mask. */
#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; что может создавать более эффективный код на некоторых компиляторах. Кроме того, вариант со сдвигом влево может дать еще лучший код, поскольку старший бит является переносом от сложения 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;
    return lfsr;
}

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

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

Xorshift LFSR

Основная статья: Ксоршифт

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

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

#include <stdint.h>
unsigned lfsr_xorshift(void)
{
    uint16_t start_state = 0xACE1u;  /* Any nonzero start state will work. */
    uint16_t lfsr = start_state;
    unsigned period = 0;

    do
    {   // 7,9,13 triplet from http://www.retroprogramming.com/2017/07/xorshift-pseudorandom-numbers-in-z80.html
        lfsr ^= lfsr >> 7;
        lfsr ^= lfsr << 9;
        lfsr ^= lfsr >> 13;
        ++period;
    }
    while (lfsr != start_state);

    return period;
}

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

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

${\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}}$

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

${\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}}$

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

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

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

${\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 года. Число различных примитивных полиномов растет экспоненциально с длиной сдвигового регистра и может быть точно рассчитано с использованием функции тотента Эйлера. (последовательность A011260 в OEIS ).

Биты (n)	Полином обратной связи	Краны	Метчики ( шестнадцатеричные )	Период ( $2^{n}-1$)
2	$x^{2}+x+1$	11	0x3	3
3	$x^{3}+x^{2}+1$	110	0x6	7
4	$x^{4}+x^{3}+1$	1100	0xC	15
5	$x^{5}+x^{3}+1$	10100	0x14	31
6	$x^{6}+x^{5}+1$	110000	0x30	63
7	$x^{7}+x^{6}+1$	1100000	0x60	127
8	$x^{8}+x^{6}+x^{5}+x^{4}+1$	10111000	0xB8	255
9	$x^{9}+x^{5}+1$	100010000	0x110	511
10	$x^{10}+x^{7}+1$	1001000000	0x240	1,023
11	$x^{11}+x^{9}+1$	10100000000	0x500	2,047
12	$x^{12}+x^{11}+x^{10}+x^{4}+1$	111000001000	0xE08	4,095
13	$x^{13}+x^{12}+x^{11}+x^{8}+1$	1110010000000	0x1C80	8,191
14	$x^{14}+x^{13}+x^{12}+x^{2}+1$	11100000000010	0x3802	16,383
15	$x^{15}+x^{14}+1$	110000000000000	0x6000	32,767
16	$x^{16}+x^{15}+x^{13}+x^{4}+1$	1101000000001000	0xD008	65,535
17	$x^{17}+x^{14}+1$	10010000000000000	0x12000	131,071
18	$x^{18}+x^{11}+1$	100000010000000000	0x20400	262,143
19	$x^{19}+x^{18}+x^{17}+x^{14}+1$	1110010000000000000	0x72000	524,287
20	$x^{20}+x^{17}+1$	10010000000000000000	0x90000	1,048,575
21	$x^{21}+x^{19}+1$	101000000000000000000	0x140000	2,097,151
22	$x^{22}+x^{21}+1$	1100000000000000000000	0x300000	4,194,303
23	$x^{23}+x^{18}+1$	10000100000000000000000	0x420000	8,388,607
24	$x^{24}+x^{23}+x^{22}+x^{17}+1$	111000010000000000000000	0xE10000	16,777,215

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

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

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

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

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

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

См. также

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

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

• 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