Metod_B1.V.DV.19.02_09.03.01_04.06.2016_laby

В цепь обратной связи регистра включен сумматор по модулю 2. Матрица

функционирования имеет вид:

0 1 0			0 1
1 0		0	0	0
A 0 1 0			0	0
0	0 1 0			0
0	0 0 1 0

Схема данного ГПСЧ приведена на рис. 6.

Осуществим в условиях данного примера двухразрядный сдвиг, т.е. S=2.

Найдем матрицу А2 и составим схему генератора:

			0 1 0 0 1		0 1 0 0 1		1 0 0 1 0
			1 0 0 0 0		1 0 0 0 0		0 1 0 0 1
A	2	A A	0 1 0 0 0		0 1 0 0 0		1 0 0 0 0
			0 0 1 0 0		0 0 1 0 0		0 1 0 0 0
			0 0 0 1 0		0 0 0 1 0		0 0 1 0 0

Матрица А определяет структуру генератора следующим образом.

Если в i-й строке матрицы стоит две или более единицы, то это означает, что вход i-го разряда регистра соединен с выходом сумматора по mod 2, причем на входы этого сумматора подаются сигналы с выходов разрядов регистра, номера которых равны номерам столбцов i-й строки,

содержащих единицы. Если в i-той строке стоит одна единица, то это означает, что вход i-того разряда регистра соединен непосредственно с выходом k-того разряда, где k – номер столбца, в

котором стоит единица.

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

X1

X2

X3

D TT

D TT

D TT

D TT

ТИ

C

1

C 2

C 3

C 4

X4 X5

D TT

C 5

М2

Рис. 6. Схема пятиразрядного ГПСЧ с одноразрядным сдвигом за один такт

В итоге имеем схему 5-разрядного генератора с 2-разрядным сдвигом за один такт,

показанную на рис. 7.

В зависимости от среды использования ГПСЧ к нему предъявляются разные требования

(по независимости, случайности, равномерности, быстродействию и т.д.). В связи с этим требуется уметь строить и проверять различные схемы ГПСЧ. Поскольку проведение натурных опытов с разными схемами ГПСЧ трудоемко, целесообразно использовать программное средство, позволяющее строить и исследовать различные ГПСЧ на программных моделях. Для этих целей в лабораторной работе используется автоматизированная система подготовки и обработки статистической информации (АСПОСИ), которая представляет собой комплекс программных средств, позволяющих строить математические модели различных ГПСЧ и исследовать их характеристики.

Работая в диалоговом режиме с ПЭВМ, пользователь определяет структуру генератора,

т.е. некоторую исходную информацию: разрядность регистра сдвига (ГПСЧ), количество и номера подключенных в цепь обратной связи разрядов регистра, вид обратной связи,

разрядность и количество генерируемых чисел и др. Сгенерированные ПСЧ записываются в файл. Для запуска системы необходимо вызвать файл GENERATO.EXE.

		X1	X2	X3	X4	X5
D TT		D TT	D TT	D TT	D TT
C	1	C 2	C 3	C 4	C	5
ТИ
					М2
						1

М2

2

Рис. 7. Схема пятиразрядного ГПСЧ с двухразрядным сдвигом за один такт

Для оценки качества сгенерированных чисел используется программный комплекс «Автоматизированная система исследования статистической информации» ANALYZE.EXE,

работающий в интерактивном режиме.

Порядок выполнения работы

1.Изучить теоретический материал по данной теме.

2.Решить практическую задачу: в соответствии с произвольно выбранным вектором α,

определяющим структуру ГПСЧ, построить схему конкретного генератора с одноразрядным сдвигом за один такт.

Задав произвольное количество сдвигов S>2, определить матрицу многоразрядного сдвига и построить схему соответствующего ГПСЧ с многоразрядным сдвигом за один такт.

3.Пользуясь диалоговой автоматизированной системой GENERATO.EXE, убедиться в правильности вычисления (п.2) матрицы многоразрядного сдвига.

4.Пользуясь системой GENERATO.EXE, создать файл равномерно распределенных ПСЧ. Зафиксировать введенные данные в отчете по лабораторной работе.

Рекомендуется формировать не менее 1000 чисел; файл сопроводить расширением *.dat

и разместить его на диске b: .

5.Пользуясь автоматизированной системой обработки статистической информации ANALYZE.EXE, построить гистограмму статистического распределения для чисел из созданного в п.4 файла и по ней визуально оценить подтверждение гипотезы о равномерном распределении сгенерированных чисел.

6.Изменяя структуру ГПСЧ, повторить пп.4,5 несколько раз. Проанализировав визуально гистограммы, из всех вариантов выбрать ГПСЧ, для которого гистограмма наилучшим образом приближена к теоретическому виду. Запомните выбранную структуру ГПСЧ для последующих лабораторных работ; удалите с диска b: созданные Вами файлы с ПСЧ (с расширением *.dat).

7.Сделать вывод о влиянии структуры ГПСЧ на качество сгенерированных последовательностей.

8.Оформить и защитить отчет по лабораторной работе.

Лабораторная работа №4

Комбинированный генератор

Пусть заданы две периодические последовательности: последовательность {

xi

} целых

чисел

x	i

с максимальным периодом

m1

(

m1

– натуральное число,

m1

>2)

и

последовательность { y j } целых чисел y j с максимальным периодом m2 ( m2										– натуральное
число, m2 >2 ),			m1	не равно			m2 и числа m1 , m2	взаимно просты. Образуем целочисленную
последовательность { zk } чисел zk по правилу:
z	k	x	m	y	j	.			(1)
		i	1
Задача			– получить				последовательность	{	zk } на основе соотношения (1) с
максимальным периодом L, равным произведению								m m
								1	2 .

Для решения рассматриваемой задачи предложена структурная модель (СМ) комбинированного ГПСП в виде, представленном на рис. 1.

	xi
	1
C1	zk
	3

2	yj

C2

Рис. 1. Структурная модель СМ комбинированного генератора псевдослучайных

последовательностей

Обозначения: блок 1 – генератор 1 псевдослучайных целых неотрицательных чисел

xi

с

периодом m1 ;

блок 2 – генератор 2 псевдослучайных целых неотрицательных чисел y

j

с периодом

m2 ;

блок 3 – функциональный цифровой преобразователь (ФЦП), реализующий процедуру

(1);

c1

, c2 тактовые синхроимпульсы.

Модель СМ реализует следующий метод моделирования ПСП {

z

k

}:

Шаг 1. По синхроимпульсу

c

1

генераторы 1 и 2 формируют числа

x

i и

y j .

Шаг 2. По синхроимпульсу c2

ФЦП формирует число zk по соотношению (1).

При этом генератор 1 выполняет m2

периодов получения чисел

xi

с длиной каждого

периода m1 , а генератор 2 выполняет m1

периодов получения чисел

y j

с длиной каждого

периода

m

2 .

Порядок выполнения работы

1. Изучить теоретический материал по данной теме.

2. В соответствии с полученным заданием создать программный генератор ПСЧ.

3. Пользуясь собственным программным генератором (п.2), сформировать файл ПСЧ.

Определить программно статистические оценки математического ожидания и дисперсии для полученной последовательности.

Рекомендуется формировать не менее 1000 чисел; файл сопроводить	расширением
*.dat и разместить его на диске b.

4.Пользуясь автоматизированной системой обработки статистической информации ANALYZE.EXE, построить гистограмму статистического распределения для чисел из созданного в п.3 файла.

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

6.Оформить и защитить отчет по лабораторной работе.

Лабораторная работа №5

Вихрь Мерсенна

К таким генераторам относится генератор Мерсенна [9]. В этом генераторе используется принципиально другой подход к выбору модуля и множителей, основанный на числах Смита. Модулем конгруэнтного генератора служит простое число P, а множителем – его первообразный корень. Первообразным корнем простого числа P называется целое число N,

1<n<N, если наименьшая степень k, при которой верно сравнение	N	k	(mod P) 1, равна (P –

1). Количество первообразных корней равно количеству чисел, меньших значения (P – 1) и

взаимно простых с ним. При указанном выборе множителя обеспечивается максимальная длина периода, равная (P – 1).

Разработка генератора с заданными свойствами статистической многомерной равномерности требует:

поиска числа Смита;

поиска первообразных корней – претендентов на роль множителей генератора;

многомерного корреляционного анализа для отбора множителя, дающего последовательность наивысшего статистического качества.

Требуемый произвольный объем последовательности псевдослучайных чисел может обеспечить только система генераторов с различными модулями. При комбинировании нескольких генераторов ПСП период равен произведению периодов составляющих. Улучшаются и свойства равномерности последовательности.

В качестве одного из алгоритмов нелинейного преобразования элементов xi n-

разрядной информационной последовательности (16):

x=x1 x2 x3… xi… xm

(16)

(i 1,m)

длиной m под управлением ключевой n-разрядной последовательности (17):

γ= γ1 γ2 γ3… γi… γm

(17)

такой же длины и качественного генератора ПСП с числом состояний 2n можно предложить следующий в соответствии с рисунком 6 [1].

Рисунок 6 – Стохастическое преобразование информационной последовательности {xn}

Для каждого элемента xi повторяется нижеприведенная последовательность действий:

очередной элемент xi входной последовательности загружается в память генератора ПСП;

выполняется γi тактов работы генератора;

состояние генератора после γi тактов работы при начальном состоянии xi

объявляется результатом γi преобразования элемента xi.

После преобразования всех элементов исходной последовательности будет получена

результирующая последовательность (17):
y=y1 y2 y3… yi… ym	(17)
длиной m, для каждого элемента которой справедливо (18):

yi=R(xi, γi)

(18).

Данное преобразование может эффективно использоваться для решения различных

задач, связанных с защитой информации.

Порядок выполнения работы

1.Изучить теоретический материал по данной теме.

2.В соответствии с полученным заданием создать программный генератор ПСЧ.

3.Пользуясь собственным программным генератором (п.2), сформировать файл ПСЧ. Определить программно статистические оценки математического ожидания и

дисперсии для полученной последовательности.
Рекомендуется формировать не менее 1000 чисел; файл сопроводить	расширением
*.dat и разместить его на диске b.

4.Пользуясь автоматизированной системой обработки статистической информации ANALYZE.EXE, построить гистограмму статистического распределения для чисел из созданного в п.3 файла.

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

6.Оформить и защитить отчет по лабораторной работе.

Лабораторная работа №6

Двумерный тест

Распределение на плоскости Данный тест предназначен для определения зависимостей между элементами

исследуемой последовательности. На поле размером (2n	1) (2n 1) (n – разрядность чисел
исследуемой последовательности) наносятся точки с	координатами	(zk , zk 1 ) , где	zk	-

элементы исследуемой последовательности { zk }, k 1,(n 1) , n - длина последовательности

[7].

Рис. 8. Распределение на плоскости – результат хороший

Рис. 9. Распределение на плоскости – результат отрицательный Далее анализируется полученная картина. Если между элементами последовательности

отсутствуют зависимости, то точки на поле расположены хаотично (рис. 8). Если на поле присутствуют зависимости, наблюдаются «узоры» - последовательность не является случайной (рис. 9). Для последовательностей большой длины хорошим результатом является абсолютно черное поле.

Порядок выполнения работы

1.Изучить теоретический материал по данной теме.

2.Используя систему GENERATO.EXE. смоделировать работу генератора ПСЧ, основанного на регистре сдвига. В качестве исходных данных рекомендуется задать структуру ГПСЧ, отобранную по итогам лабораторного занятия №2.

Результат выполнения данного пункта – файл ПСЧ.

3.Используя программный ГПСЧ, созданный на лабораторном занятии №3, создать второй файл ПСЧ.

4.Применяя систему ANALYZE.EXE, проанализировать качество аппаратного и программного генераторов ПСЧ (по двум файлам чисел).

5.Проанализировав результаты исследований, сделать вывод о качестве созданных Вами аппаратного и программного ГПСЧ, отобрать лучший из них для дальнейшего применения в статистическом моделировании.

6.Удалить созданные Вами в процессе работы файлы данных.

7.Результаты исследований по двум файлам оформить в отчет по лабораторной

работе.

Замечание. Формируемые в п.2,3 файлы должны содержать не менее 5000-10000 чисел. Файлы рекомендуется создавать на диске b: и сопровождать расширением *.dat.

Лабораторная работа №7

Профиль линейной сложности

Понятие «линейная сложность» (ЛС) связано с понятием линейных рекуррентных последовательностей (ЛРП) над конечным полем [9]. Наименьшая степень характеристического многочлена ЛРП (степень минимального многочлена ЛРП) называется линейной сложностью ЛРП. ЛРП реализуется схемой регистра сдвига с линейной обратной связью (РСЛОС). Любая периодическая последовательность может рассматриваться как ЛРП. Линейная сложность ЛРП определяет минимальную длину РСЛОС, реализующего данную последовательность, задает минимальную степень характеристического многочлена и характеризует сложность ее

аналитического строения. Двоичные ЛРП с максимальным периодом T 2	n	1, где n - степень

характеристического многочлена, имеют ЛС, равную n. Малое значение ЛС (по сравнению с T)

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

Существует ряд приложений, широко использующих понятие ЛС.

1)В моделировании для исследования качества случайных чисел.

2)Для кодирования информации – алгоритм Берлекэмпа «решения ключевого уравнения над произвольным полем».

3)Для тестирования работоспособности цифровых схем. Данная методика производит генерирование тестов на основе синтеза линейного

регистра сдвига минимальной разрядности по заданной последовательности.