EWB

Исследование генератора псевдослучайной чисел (Лабораторная работа)

 

Цель работы: исследовать генератор псевдослучайной последовательности.

 

Теория

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

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

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

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

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

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

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

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

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

 

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

 

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

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

F(x)= xn+ An-1xn-1 +…+ A2x2 + A1x+1.

 

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

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

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

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

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

 

1/yn+An-1/yn-1+…+A2/y2+A1/y+1;

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

 

(yn /yn)yn + An-1(yn /yn-1) +…+ A2(yn /y2) + A1(yn /y) + yn=
=1+ An-1y +…+
A2yn-2+ A1y + yn.

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

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

 

Таблица. Многочлены

Число
разрядов
n

Многочлен

Максимальная

длина ПСП

Номера разрядов, выходы которых подаются на сумматор по модулю 2

2

x2+x+1

3

1, 2

3

x3+x+1

x3+x2+1

7

7

2, 3

1, 3

4

x4+x+1

x4+x3+1

15

15

3, 4

1, 4

5

x5+x2+1

x5+x3+1

31

31

3, 5

2, 5

6

x6+x+1

x6+x5+1

63

63

5, 6

1, 6

7

x7+x+1

x7+x6+1

127

127

6, 7

1, 7

8

x8+x4+x3+x2+1

x8+x6+x5+x4+1

255

255

4, 5, 6, 8

2, 3, 4, 8

 

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

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

1/y4+1/y+1, y4(1/y4+1/y+1)=1+y3+y4.

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

 

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

 

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

Т а б л и ц а 11

Номер такта

Q1

Q2

Q3

Q4

1

1

0

0

0

2

0

1

0

0

3

0

0

1

0

4

1

0

0

1

5

1

1

0

0

6

0

1

1

0

7

1

0

1

1

8

0

1

0

1

9

1

0

1

0

10

1

1

0

1

11

1

1

1

0

12

1

1

1

1

13

0

1

1

1

14

0

0

1

1

15

0

0

0

1

16

1

0

0

0

 

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

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

 

Последовательность выполнение работы

Исследование генератора ПСП для n=4

1.     Нарисовать схему генератора ПСП для n=4. Поместить на схему функциональный генератор (Function Generator) и осциллограф (Oscilloscope).

На этой схеме логический элемент «4И-НЕ» введен для автоматической записи единицы в первый разряд регистра, если в момент включения питания все триггеры регистра сдвига установятся в состояние ноль.

2.     Открыть окно функционального генератора и установить частоту (1 кГц) и вид генерируемого сигнала (прямоугольные импульсы).

 

Рис. Схема четырехразрядного генератора ПСП

 

3.     Запустить процесс моделирования, нажав кнопку  на панели инструментов, и в появившемся меню выбрать команду Run.

4.     Щелкнуть по иконке осциллографа, чтобы открыть окно осциллографа, и зарисовать осциллограмму.

 

Описание осциллографа (Oscilloscope)

Работа осциллографа основывается на применении электронно-лучевой трубки (ЭЛТ), содержащей катод, излучающий поток (луч) электронов за счет термоэмиссии, модулятор для управления интенсивностью этого потока, систему его фокусировки, отклоняющую систему в виде двух пар пластин, и экран из кристалликов люминофора, которые под действием падающего на них потока электронов высвечивают траекторию движения электронного луча в пространстве, определяемую потенциалами на пластинах отклоняющей системы. Горизонтальные пластины этой системы называются Y-каналом, вертикальные –
X-каналом.

На пластины Y-канала подается исследуемый сигнал после его усиления и масштабирования вертикальным Y-усилителем. Для одновременного наблюдения n сигналов используют n усилителей, выходные сигналы которых с помощью аналоговых коммутаторов поочередно подаются на вход усилителя мощности Y-канала.

На пластины X-канала подается пилообразный сигнал развертки, длительность (период) которого с помощью системы синхронизации поддерживается равным или кратным периоду исследуемого сигнала в одном из Y-каналов, что позволяет получить устойчивое, а не хаотично «бегающее» изображение контролируемого сигнала.

Осциллограф имеет два канала (Channel) A и B с раздельной установкой чувствительности в диапазоне от 10 мкВ/дел (µV/Div) до 5 кВ/дел (kV/Div) и регулировкой смещения по вертикали (Y POS).

 

Рис. Лицевая панель осциллографа

 

На панелях Channel A и Channel B с помощью кнопок выбирается режим по входу. Режим АС предназначен для наблюдения только сигналов переменного тока. В режиме «0» входной зажим замыкается на землю. В режиме DC (включен по умолчанию) можно наблюдать сигналы как постоянного, так и переменного тока. С правой стороны от кнопки DC расположен входной зажим канала.

На этих панелях в окне Scale устанавливается величина развертки, а в окне Y position – величина смещения относительно оси Х.

На панели Timebase с помощью кнопок Y/T, Add, B/A, A/B выбирается режим развертки. В режиме Y/T (обычный режим, включен по умолчанию) устанавливается следующий режим развертки: по вертикали – напряжение сигнала, по горизонтали – время; в режиме Add – сигналы обоих каналов накладываются друг на друга; в режиме B/A: по вертикали – сигнал канала В, по горизонтали – сигнал канала А; в режиме А/В: по вертикали – сигнал канала А, по горизонтали – сигнал канала В.

В режиме Y/T длительность развертки (Timebase) может быть задана в диапазоне от 0,1 нс/дел (ns/div) до 1 с/дел (s/div) с возможностью установки смещения в тех же единицах по горизонтали, т.е. по оси Х (X POS).

В режиме Y/T можно установить ждущий режим в поле Trigger. В строке Edge – режим запуска по переднему (кнопка ) или по заднему (кнопка ) фронту запускающего сигнала. В окне Lever (уровень) устанавливается уровень запускающего сигнала.

В этом поле с помощью кнопок Auto, А, В или Ext ждущий режим запускается от каналов А или В, от канала А, от канала В или от внешнего источника, подключаемого к находящемуся на этой панели зажиму, соответственно.

С помощью кнопки Revere можно инвертировать изображение, кнопки Save можно записать данные в файл.

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

Исследование генератора ПСП для n=5 и g(x)=x5+x3+1

1.     Нарисовать схему генератора ПСП для n=5 и g (x) = x5 + x3 + 1.

2.     Запустить процесс моделирования, нажав кнопку  на панели инструментов, и в появившемся меню выбрать команду Run.

3.     Щелкнуть по иконке осциллографа, чтобы открыть окно осциллографа, и зарисовать осциллограмму.

Исследование генератора ПСП для n=5 и g(x)=x5+x4+1

1.     Нарисовать схему генератора ПСП для n=5 и g (x) = x5 + x4 + 1.

2.     Запустить процесс моделирования, нажав кнопку  на панели инструментов, и в появившемся меню выбрать команду Run.

3.     Щелкнуть по иконке осциллографа, чтобы открыть окно осциллографа, и зарисовать осциллограмму.

 
Содержание отчета

Отчет должен включать:

1) название пункта работы,

2) исследуемую схему,

3) результат моделирования: все различные состояния разрядов регистра и полученную ПСП.