Введение

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

В вычислительной технике линейный регистр сдвига с обратной связью (LFSR) — это регистр сдвига, входной бит которого является линейной функцией его предыдущего состояния. Наиболее часто используемой линейной функцией отдельных битов является исключающее ИЛИ (XOR). Таким образом, LFSR чаще всего представляет собой регистр сдвига, входной бит которого управляется XOR некоторых битов общего значения регистра сдвига. Начальное значение LFSR называется начальным значением (seed), и поскольку работа регистра детерминирована, последовательность значений, генерируемых регистром, полностью определяется его текущим (или предыдущим) состоянием. Аналогично, поскольку регистр имеет конечное число возможных состояний, он неизбежно должен войти в повторяющийся цикл. Однако LFSR с хорошо выбранной функцией обратной связи может генерировать последовательность битов, которая выглядит случайной и имеет очень длинный цикл. Области применения LFSR включают генерацию псевдослучайных чисел, псевдошумовых последовательностей, быстрых цифровых счетчиков и отбеливающих последовательностей. Как аппаратные, так и программные реализации LFSR широко распространены. Математические основы циклического избыточного кода (CRC), используемого для быстрой проверки на ошибки передачи, тесно связаны с математикой LFSR. В целом, арифметика, лежащая в основе LFSR, делает их очень элегантным объектом для изучения и реализации, позволяя создавать относительно сложную логику из простых строительных блоков. Однако следует также учитывать и другие методы, которые могут быть менее элегантными, но при этом более производительными.

Небинарный Galois LFSR

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

Свойства потока вывода

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

Приложения

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/XNOR с параллельным входным битом номер ноль и "отводами". Вход каждого последующего триггера комбинируется по XOR/XNOR с выходом предыдущего триггера и соответствующим параллельным входным битом. Следовательно, следующее состояние MISR зависит от нескольких предыдущих состояний, а не только от текущего. Поэтому MISR всегда будет генерировать одну и ту же эталонную сигнатуру при одинаковой входной последовательности. В современных разработках предлагается использовать триггеры с установкой и сбросом в качестве "отводов" LFSR. Это позволяет системе BIST оптимизировать использование памяти, поскольку триггеры с установкой и сбросом могут сохранять начальное значение (seed) для генерации всего потока битов из LFSR. Однако это требует изменений в архитектуре BIST и является вариантом для конкретных применений.

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

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