Краткие сведения из теории

Регистры сдвига (сдвигающие регистры) являются одними из основных узлов аппаратуры передачи дискретных сообщений. Любой сдвигающий регистр, состоящий из n триггеров, есть запоминающее устройство, способное принимать 2 ⁿ различных состояний.

Если в регистр сдвига ввести обратные связи, каждая из которых формируется логической схемой, называемой схемой сложения по модулю два (или «ИСКЛЮЧАЮЩЕЕ ИЛИ»), то с помощью такого устройства можно построить генератор псевдослучайной последовательности или устройство деления одного многочлена на другой (кодирующие и декодирующие устройства).

Рассмотрим построение генератора псевдослучайной последовательности.

Случайной последовательностью называется последовательность из 1 и 0, в которой каждый элемент появляется в последовательности независимо от предыдущих символов. Случайные последовательности должны удовлетворять тестам на случайность:

уравновешенности, когда число 1 и 0 в последовательности равно;

корреляции, когда при почленном сравнении случайной последовательности с любым ее циклическим сдвигом число совпадающих символов равно числу несовпадающих символов;

вероятность появления каждого набора из m элементов для m<n (где n – длина последовательности) равна 2^{- m}.

Случайная последовательность не имеет ни начала, ни конца. Получить ее можно, подбрасывая монетку и рассматривая, какая сторона монетки выпадет. Если выпал “орел”, то записывается единица, если “решка”, то записывается ноль. На практике такие последовательности получить нельзя. Поэтому используют ограниченные (конечные) последовательности, которые обладали бы некоторыми свойствами случайных последовательностей. Такие последовательности называются псевдослучайными последовательностями (ПСП).

Получить ПСП можно с помощью регистра сдвига с логическими обратными связями. На простейшей схеме такого регистра (рис. 43) на один вход сумматора по модулю два подается сигнал с k -го разряда регистра, а на второй вход – сигнал с n -го разряда. Если в первый разряд регистра записать единицу, а в остальные нули, то под воздействием тактовых импульсов эта единица будет продвигаться по регистру. Когда k -й разряд примет состояние единицы, то на выходе сумматора появится единица, которая поступит на вход первого разряда и запишется в него. С этого момента в регистре сдвига будут продвигаться две единицы. Всякий раз, когда на входы сумматора по модулю два будут подаваться различные символы, в первый разряд регистра сдвига будет записана единица.

 

 

Рис. 43. Генератор псевдослучайной последовательности

 

Таким образом, под воздействием каждого тактового импульса разряды регистра сдвига принимают определенные состояния, причем последовательность этих состояний зависит от способа включения обратной связи. Общее число таких различных состояний равно 2 ⁿ -1, следовательно, период ПСП равен 2 ⁿ -1. ПСП можно снимать с выхода любого разряда регистра, в частности с последнего. Любая выходная последовательность, имеющая такой период, называется линейной последовательностью максимальной длины.

Регистр с логической обратной связью описывается характеристическим многочленом вида

F (x)= xⁿ+ A_{n- 1} x^{n- 1} +…+ A ₂ x ² + A ₁ x+ 1.

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

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

Таким образом, чтобы построить генератор ПСП, нужно знать неприводимый многочлен степени n. Если для данного
n известен неприводимый многочлен, то число элементов
обратной связи (сумматоров по модулю два) равно числу
ненулевых слагаемых многочлена минус два; а номера разря-
дов регистра, выходы которых подаются на входы сум-
маторов по модулю два, определяются из сопряженных многочленов.

Сопряженные многочлены вычисляют следующим образом:

в характеристическом многочлене производят замену переменных x=y^{- 1}:

1/ yⁿ + A_{n -1}/ y_{n -1}+…+ A ₂/ y ²+ A ₁/ y +1;

вновь полученный многочлен умножают на yⁿ:

(yⁿ / yⁿ) yⁿ + A_{n -1}(yⁿ / y_{n -1}) +…+ A ₂(yⁿ / y ²) + A ₁(yⁿ / y) + yⁿ =
=1+ A_{n -1} y +…+ A ₂ y^{n -2}+ A ₁ y + yⁿ.

Показатели степени переменной y сопряженного многочлена, у которых коэффициенты A_i не равны нулю, соответствуют номерам разрядов регистра, выходы которых подаются на сумматор по модулю два.

Для некоторых n неприводимые многочлены вычислены и сведены в таблицы. Некоторые из этих многочленов приведены в табл. 10.

 

 

Т а б л и ц а 10

Число разрядов n	Многочлен	Максимальная длина ПСП	Номера разрядов, выходы которых подаются на сумматор по модулю 2
	x 2+ x +1		1, 2
	x 3+ x +1 x 3+ x 2+1		2, 3 1, 3
	x 4+ x +1 x 4+ x 3+1		3, 4 1, 4
	x 5+ x 2+1 x 5+ x 3+1		3, 5 2, 5
	x 6+ x +1 x 6+ x 5+1		5, 6 1, 6
	x 7+ x +1 x 7+ x 6+1		6, 7 1, 7
	x 8+ x 4+ x 3+ x 2+1 x 8+ x 6+ x 5+ x 4+1		4, 5, 6, 8 2, 3, 4, 8

 

Рассмотрим построение генератора ПСП при n =4. В таблице найдем характеристический многочлен степени 4 – g (x)= x ⁴+ x +1.

Заменим переменную и найдем сопряженный многочлен:

1/ y ⁴+1/ y +1, y ⁴(1/ y ⁴+1/ y +1)=1+ y ³+ y ⁴.

Следовательно, регистр сдвига имеет четыре разряда. Число сумматоров по модулю два, включаемых в обратную связь, равно 3-2=1. Номера разрядов, выходы которых подаются на входы сумматора по модулю два, равны 3 и 4. Схема генератора ПСП приведена на рис. 44.

 

Рис. 44. Генератор ПСП для n =4

 

Если записать в первый разряд единицу, то под воздействием тактовых импульсов содержимое регистра будет меняться как в табл. 11.

Т а б л и ц а 11

Номер такта	Q 1	Q 2	Q 3	Q 4

 

Начиная с 16-го такта последовательность состояний регистра повторяется. ПСП можно снимать с выхода любого разряда регистра, а также с выхода схемы сложения по модулю два. Псевдослучайная последовательность, генерируемая данным устройством, имеет вид 000100110101111.

В данном случае эта последовательность получена с выхода четвертого разряда регистра сдвига (пятый столбец табл. 11).