LINEAR FEEDBACK SHIFT REGISTERS



Hadamard matrix family catalogue and on-line algorithms

© Nickolay A. Balonin, 20.10.2015


Мультивибраторы на транзисторах, – увлечение детства, для семидесятых. Пищалки и свистелки, продолжение глиняных свистулек. У них есть продолжение, в виде закольцованных обратными связями регистров, создающих колебания в GF(2).

Сдвиговые регистры, обладающие помимо обратной связи с выхода, еще обратными связями, называют линейными сдвиговыми регистрами LFSR или регистрами Фибоначчи. Последовательное соединение сдвиговых регистров называется регистром Галуа.



Регистры Фибонначи и Галуа


Моделирование регистров Фибоначчи несложно в рамках рекурсии: Xk=FXk–1, k=1, 2, 3, ... где F – фробениусова матрица, элементы вектора состояния определены в конечном поле GF(2). Нормальная форма модели оперирует нижней строчкой f матрицы Фробениуса, содержащей s коэффициентов обратных связей.

F=
0
I
 f[0] 
 f[1] ... f[s–1] 


Собственно сдвиговый регистр, это регистр с f=[1, 0,..., 0, 0]. Положения единичек обратной связи называются не битами, а тэйпами (taps). Обратная связь может быть инвертирующей, роль единицы играет логическое отрицание. Задав вектор начального состояния, мы будем наблюдать на выходе (первый элемент вектора состояния) его последовательное воспроизведение.

Вектор состояния сдвигового регистра образует малый период генерируемых колебаний. Добавлением обратных связей (т.е. изменением элементов f) можно увеличить период воспроизводимой последовательности до числа Мерсенна 2s–1, s – размер регистра, поэтому регистр Фибоначчи можно назвать также регистром Мерсенна или твистером Мерсенна.

Полиномы с коэффициентами из f, обеспечивающими максимальный период, называются примитивными. Для регистра длины два полином имеет вид x2+x+1, число единичек при степенях (тэйпов) – четное. Любой регистр имеет парный, противопоставленный, с номерами тэйпов s–k: [32, 7, 3, 2, 0] сопряжен с [32, 30, 29, 25, 0].

Регистр Галуа оперирует, очевидно, блочной фробениусовой формой матрицы, количество и параметры фробениусовых блоков разнообразят его поведение.

Значения векторов состояния регистра образуют систему чисел, подобную привычным в практике программирования числовым системам. Матрица Мерсенна порядка 2s–1, если у нее отрезать полосу, высоты s, столбцы полосы можно считать бинарными кодами абстрактных чисел, эти числа образуют "псевдо-случайную" последовательность длиною в размер матрицы. Это и есть твистер Мерсенна.

PENDULUMS IN GF(2) | PSEUDO-NOISE MATRICES | ТВИСТЕР МЕРСЕННА

Rambler's Top100