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

ФЕДЕРАЛЬНОЕ ГОСУДАРСТВЕННОЕ БЮДЖЕТНОЕ ОБРАЗОВАТЕЛЬНОЕ УЧРЕЖДЕНИЕ ВЫСШЕГО ОБРАЗОВАНИЯ

«КАЗАНСКИЙ НАЦИОНАЛЬНЫЙ ИССЛЕДОВАТЕЛЬСКИЙ ТЕХНИЧЕСКИЙ УНИВЕРСИТЕТ им. А.Н. ТУПОЛЕВА-КАИ»

Чистопольский филиал «Восток» Кафедра компьютерных и телекоммуникационных систем

Методические указания

по выполнению лабораторных работ

по учебной дисциплине

«Генераторы случайных и псевдослучайных последовательностей»

Индекс по учебному плану: Б1.В.ДВ.19.02

Направление подготовки: 09.03.01 Информатика и вычислительная

техника

Квалификация: Бакалавр

Профиль подготовки: Интегрированные автоматизированные

информационные системы

Вид профессиональной деятельности: научно-исследовательская,

проектно-конструкторская, проектно-технологическая

Рекомендованы УМК ЧФ «Восток» КНИТУ-КАИ

Чистополь

2016 г.

разрядов в двоичном представлении L не должна иметь регулярного вида, например,

Конгруэнтные процедуры – не единственный источник ПСЧ. Некоторые известные методы рассмотрены в /1, 2, 3/.

Помимо создания пользовательских процедур получения требуемых чисел, имеется еще одна возможность формирования ПСЧ программным способом – использование стандартного программного обеспечения.

Так, например, в языке Turbo Pascal обращение к стандартному программному датчику ПСЧ осуществляется с помощью функции RANDOM:

function RANDOM (N: WORD);

Функция возвращает одно целочисленное равномерно распределенное число в интервале

(0, N). В случае вызова функции без параметра N возвращается одно вещественное число,

равномерно распределенное в интервале (0,1).

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

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

В данном примере программный датчик реализован в виде функции RND на языке Turbo Pascal, которая при каждом обращении возвращает одно РРПСЧ в интервале (0,1),

сформированное мультипликативным методом.

В примере используются следующие значения констант:

L=5169, x0=7533, k=2q=216=65536.

FUNCTION RND: REAL;

{ х – глобальная переменная типа word} begin

x:=L*x; { т.к. k – целая степень числа 2, то операция (L*x) mod k сводится к выделению q младших разрядов числа L*x }

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

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

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

Генератор на основе линейных регистров сдвига

Цель работы: изучение основных способов формирования последовательностей равномерно распределенных чисел; создание файла чисел, формируемых моделью генератора псевдослучайных чисел регистровой структуры.

При реализации статистического моделирования на ЭВМ наиболее часто используются последовательности равномерно распределенных чисел. Они представляют собой некоторое количество чисел, имитирующих выборку равномерно распределенных чисел с заданными параметрами (например, А и В – нижняя и верхняя границы интервала равномерной функции распределения на рис. 4).

При заданных значениях А и В математическое ожидание М и дисперсия D

определяются следующим образом: М = (А+В) / 2; D = (В-А)2 / 12.

Рис. 4. График функции плотности равномерного закона распределения

Широкое распространение находят как случайные числа, так и псевдослучайные. В

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

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

Если получена последовательность y1,y2,…,yn, равномерно распределенных в интервале

(C, D), то для перехода к последовательностям x1,x2,…,xn из интервала (А, В) применяется следующая формула:

При C=0 и D=1 получаем: xi=(В - А)*yi + А.

При С=0 и D=М, где М – целое число, получаем

xi B A yi A M

На практике используются три основных способа генерирования случайных чисел:

табличный (файловый), программный и аппаратный (физический).

Табличный способ Если сформированные каким-либо способом случайные и псевдослучайные числа

оформить в виде таблицы (массива) и записать их во внешнюю (магнитные диски или ленты)

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

Достоинства метода:

-имеется возможность воспроизведения последовательностей;

-требуется лишь однократная проверка чисел.

Недостатки метода:

-запас чисел ограничен;

-тратится много времени на обращение к внешней памяти;

-характеристики случайных воздействий трудно изменить в ходе моделирования.

Программный способ

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

ГПСЧ состоит из m-разрядного регистра сдвига R1,R2,…, Rm и набора комбинационных схем КС1,КС2 ,…,КСm в цепи обратной связи. Двоичные псевдослучайные символы x1, x2,…, xm

формируются на выходах R1,R2,…, Rm. Регистр сдвига кроме функции хранения предшествующих m символов последовательности x1, x2,…, xm выполняет также их сдвиг в последующем такте, при этом вход Ri формируется схемой КСi. На вход схемы КСi подаются сигнал с выхода Ri при αi=1 и сигнал с КСi+1(i 1,m 1), на вход КСm подаются сигнал с выхода

Rm при αm=1 и внешний сигнал α0(α0=0 или 1). Если αi=0, то сигнал с выхода Ri не подается на вход схемы КСi.

Пусть КС представляют собой сумматоры по модулю 2, α0=0. Тогда состояние схемы

(рис. 5) в момент времени t+1 описывается следующей системой уравнений:

Полученные уравнения можно записать в матричном виде:

X(t+1)=A X(t), где

Зная матрицу А и состояние выходов регистра R1,R2,…, Rm в момент времени t (т.е.

вектор-столбец Х(t)), можно определить состояние регистра в (t+S)-й момент времени,

воспользовавшись преобразованием:

X(t+S)=ASX(t).

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

последовательности равна 2n-1. Однако в зависимости от структуры обратной связи и от исходного состояния регистра сдвига она может быть иной (в частности, даже единичной).

Циклические свойства ГПСЧ определяются характеристическим многочленом матрицы

А:

которым является определитель матрицы ||А+хЕ||, где Е – единичная матрица.

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

связаны с понятиями приводимости и примитивности многочлена вида (1). Если φ(х) степени m

не делится ни на какой другой многочлен от х меньшей степени, то такой многочлен называется неприводимым. Примитивность φ(х) означает, что он не является сомножителем многочлена xS+1 для любого S<(2m-1).

Доказано, что если φ(х) неприводим и примитивен, то генерируется последовательность,

имеющая максимальный период Т=2m-1. В других случаях Т<(2m-1).

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

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

Если съем информации производится в каждом такте, то числа будут коррелированны

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

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

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

S – разрядный сдвиг за один такт будет реализован, если в качестве матрицы функционирования схемы взять матрицу Аs (S>1) вместо матрицы А, соответствующей регистру с одноразрядным сдвигом.

Рассмотрим пример многоразрядного сдвига для пятиразрядного генератора (m=5).