FSR (Feedback Shift Register)

Материал из Национальной библиотеки им. Н. Э. Баумана
Последнее изменение этой страницы: 14:01, 12 июня 2016.

Шаблон:Проверка-

FSR - Feedback Shift Register(Регистр сдвига с обратной связью) - стандартный способ генерирования потока битов основан на использовании регистра сдвига с обратной связью. Это микросхема с ячейками памяти, в каждой из которых записан один бит информации. Множество таких ячеек и образует регистр. На каждом шаге содержимое нескольких заранее определенных ячеек, которые называются отводами, пропускается через функцию обратной связи. А ее значение записывается в самую левую ячейку регистра, сдвигая все остальные его биты на одну позицию вправо. Самый крайний справа, «вытолкнутый» из регистра, бит — выход регистра сдвига на данном шаге. В качестве функций обратной связи желательно брать нелинейные функции. Однако это сложно осуществить на практике, и поэтому пользуются регистром сдвига с линейной обратной связью или, сокращенно, РСЛОС, функция обратной связи в котором линейна. Этот регистр устроен так же, как и общий, описанный выше. Но в качестве функции обратной связи берется логическая операция XOR исключающего ИЛИ.

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

Для РСЛОС функция обратной связи представляет собой сумму по модулю 2(XOR) некоторых битов регистра - отводов.

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

  • содержимое ячейки формирует часть выходной последовательности;
  • содержимое -й ячейки перемещается в ячейку для любого
  • новое содержимое ячейки определяется битом обратной связи, который вычисляется сложением по модулю с определёнными коэффициентами битов ячеек .
Файл:LFSR1.PNG
Регистр сдвига с линейной обратной связью

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

  • на первом шаге:
  • на втором шаге:
  • на -м шаге:


Свойства выдаваемой РСЛОС последовательности тесно связаны со свойствами ассоциированного многочлена над полем . Его ненулевые коэффициенты называются отводами, как и соответствующие ячейки регистра, поставляющие значения аргументов функции обратной связи.

Периодичность FSR

Так как существует разных ненулевых состояний регистра, то период последовательности, генерируемой РСЛОС при любом ненулевом начальном состоянии, не превышает . При этом период зависит от ассоциированного многочлена:

  • если старший коэффициент ассоциированного многочлена равен нулю, то периодичная часть генерируемой последовательности может проявляться не сразу;
  • если , то соответствующая последовательность называется неособой. Такая последовательность начинается со своей периодичной части. Наиболее интересны неособые последовательности, соответствующие многочленам со следующими дополнительными свойствами:
    • если неприводим, то при любом ненулевом начальном состоянии регистра период генерируемой последовательности равен наименьшему числу , при котором многочлен делит . Как следствие, период последовательности будет делить число ;
    • если примитивен (то есть, является делителем , но не является делителем для всех d, делящих ), то любое ненулевое начальное состояние регистра дает последовательность с максимально возможным периодом . Например, РСЛОС с отводной последовательностью, состоящей из первого и четвёртого битов имеет максимальный период тогда и только тогда, когда ассоциированный многочлен является примитивным.

Сингулярность FSR

TemplateDifinitionIcon.svg Определение « Определение - сингулярность FSR»
FSR называется несингулярным несингулярным, если соответствующий ему граф состояний не имеет подходов. Иначе говоря, FSR несингулярен, если в каждое внутреннее состояние можно за один такт работы перейти только из одного внутреннего состояния состояния, т.е. нет двух таких состояний, из которых за один такт работы можно перейти в одно и то же состояние состояние. В противном случае FSR называется сингулярным.

Критерии несингулярности FSR для поля F2

TemplateTheoremIcon.svg Теорема Теорема о несингулярности FSR
Для того того, чтобы FSR над полем был несингулярным, достаточно, чтобы функция обратной связи имела вид:

В случае FSR над полем условие является необходимым и достаточным.
Доказательство
См. далее


Доказательство

В случае случае, когда функция обратной связи является линейной (над произвольным полем), условие является необходимым и достаточным условием несингулярности. Внутренние состояния FSR длины L над полем описывается L-мерными векторами }}

Для того, чтобы FSR из состояния перешел в состояние необходимо и достаточно, чтобы . Два разных состояния и переходящие в одно и то же состояние должны иметь вид и и при этом должно выполняться

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

Пусть Докажем необходимость условия . Если FSR несингулярен, то для любой пары состояний и должно выполняться неравенство

Учитывая то, что и векторы, и функции рассматриваются над полем и полагая , получаем: и . Обозначим тогда при этом равенство выполняется при любых Таким образом получаем: следовательно имеет вид .

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

Если бы , то для любой пары состояний и указанного вида в было бы равенство, то есть FSR был бы сингулярным. Таким образом, и, следовательно, функция обратной связи имеет вид