Гпсч с источником энтропии или гсч

Наравне с существующей необходимостью генерировать легко воспроизводимые последовательности случайных чисел, также существует необходимость генерировать абсолютно случайные числа. Такие генераторы называются генераторами случайных чисел (ГСЧ — англ. random number generator, RNG). Такие генераторы чаще всего строятся из комбинации ГПСЧ и внешнего источника энтропии (и именно такую комбинацию теперь и принято понимать под ГСЧ). Под источником энтропии понимают некоторые устройства (счетчики) случайных событий.

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

В персональных компьютерах авторы программных ГСЧ используют гораздо более быстрые источники энтропии, такие, как шум звуковой карты или счётчик тактов процессора. Сбор энтропии является наиболее уязвимым местом ГСЧ. Эта проблема до сих пор полностью не разрешена во многих устройствах (например, смарт-картах). Многие ГСЧ используют традиционные испытанные, хотя и медленные, методы сбора энтропии вроде измерения реакции пользователя (движение мыши и т.п.), как, например, в PGP и Yarrow, или взаимодействия между потоками, как, например, в Java secure random.

Пример простейшего ГСЧ с источником энтропии

Если в качестве источника энтропии использовать текущее время, то для получения натурального числа от 0 до N достаточно вычислить остаток от деления текущего времени в миллисекундах на число N+1. Недостатком этого ГСЧ является то, что в течение одной миллисекунды он выдает одно и то же число.

Примеры ГСЧ и источников энтропии приведены в таблице 3.1

Таблица 3.1. – ГСЧ и источники энтропии

Источник ГСП	Источник энтропии	ГПСЧ
/dev/random в UNIX/Linux	Счётчик тактов процессора	LFSR, с хешированием выхода через SHA-1
Yarrow от Брюса Шнайера	Традиционные методы	AES-256 и SHA-1 маленького внутреннего состояния
Microsoft CryptoAPI	Текущее время, размер жёсткого диска, размер свободной памяти, номер процесса и NETBIOS-имя компьютера	MD5-хеш внутреннего состояния размером в 128 бит
Java SecureRandom	Взаимодействие между потоками	SHA-1-хеш внутреннего состояния (1024 бит)
Chaos от Ruptor	Счётчик тактов процессора	Хеширование 4096-битового внутреннего состояния на основе нелинейного варианта Marsaglia-генератора
RRAND от Ruptor [5]	Счётчик тактов процессора	Зашифровывание внутреннего состояния поточным шифром EnRUPT в authenticated encryption режиме (aeRUPT)

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

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

1) с показательным законом распределения:

, где и – гауссовские случайные процессы с нулевым средним и единичной дисперсией;

2) с нормальным (гаусовским) законом распределения:

, где и – случайные процессы с равномерным распределением в диапазоне [0,1];

3) с рэлеевским законом распределения:

, где и – гауссовские случайные процессы с нулевым средним и единичной дисперсией;

4) с распределением Вейбулла:

, где , и – случайный процесс с равномерным распределением в диапазоне [0,1].

 

Порядок выполнения:

1. Выполнить имитацию вероятностных распределений четырех видов согласно варианта, используя ГСЧ с равномерным распределением в диапазоне [0, 1].

а) построить временные ряды;

б) произвести анализ статистических характеристик случайных процессов (найти математическое ожидание и дисперсию сигналов);

2. Выполнить имитацию смеси трех сигналов:

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

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

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

г) сложить все четыре случайных сигнала согласно варианта;

д) найти математическое ожидание сигнала для случаев (а) – (г);

е) найти дисперсию общего для случаев (а) – (г);

3. Вывести временные ряды полученных сигналов в виде графиков и табличных массивов данных.

Варианты заданий

Вари-ант	Виды законов распределений случайных сигналов
Показа- тельный	Нормальный	Рэлеев- ский	Вейбула	Периодический сигнал
	+	+, m=2;s=1	–	+	синусоидальный
	+	+, m=0;s=2	+	–	косинусоидальный
	–	+, m=5;s=4	+	+	ступеньчатый
		+, m=3;s=2,5	–		П-образный
	+	+, m=7;s=3	+	–	из равносторонних треугольников, имеющих общую точку соприкосновения
	+	+, m=10;s=7	–	+	из полукругов
	+	+, m=4;s=3	+	–	пила в виде прямоугольных трапеций
	+	+, m=0;s=3	–	+	пила в виде прямоугольных треугольников с гипотенузой справа
	–	+, m=5;s=7	+	+	пила из парабол и прямых линий
	–	+, m=2,5;s=2	+	+	сигнал из косинусоиды по модулю
	–	+, m=2;s=1,8	+	+	сигнал из равнобедренных треугольников, перекрывающих друг друга (холмы)
	+	+, m=3;s=1,5	–	+	пила в виде прямоугольных треугольников с гипотенузой слева
	+	+, m=0;s=3	+	–	сигнал “хоккейная клюшка”
	–	+, m=5;s=4	+	+	сигнал в виде отдельных отрезков под углом 45° (слеш)
	+	+, m=3;s=2,8	+	–	S-образный сигнал
	–	+, m=0;s=5	+	+	Сигнал из накладывающихся друг на друга перевернутых восьмерок
	+	+, m=7;s=4,5	–	+	сигнал из равнобедренных трапеций
	+	+, m=0;s=5	+	–	X-образный сигнал (сигнал “ромбики”)
	–	+, m=7;s=3	+	+	Сигнал растянутой спирали
	+	+, m=2;s=1	–	+	Сигнал “перекрывающиеся кольца”

 

Контрольные вопросы:

1. Какими способами можно получить случайный процесс с экспоненциальным распределением?

2. Какими способами можно получить случайный процесс с рэлеевским распределением?

3. Как можно оценить математическое ожидание и дисперсию случайной величины по соответствующим графикам плотности распределения вероятностей?

4. Какова связь между средним квадратом и дисперсией случайной величины?

5. Каким образом можно найти математическое ожидание случайной величины, зная её плотность распределения вероятностей?

6. Каким образом можно найти средний квадрат случайной величины, зная её плотность распределения вероятностей?

7. Как определить по графику плотности распределения вероятностей вероятность попадания случайной величины в заданный промежуток её значений?

8. Какие реальные случайные процессы имеют нормальное (гауссово) распределение, рэлеевское распределение, равномерное распределение, распределение Пуассона?

9. Каковы основные характеристики генератора случайных чисел в ЭВМ: закон распределения, интервал изменения случайных чисел?

10. В чем заключается центральная предельная теорема теории вероятностей?

11. Каковы характерные особенности модели белого шума?

 

1.2 Рекомендуемая литература

1. Е.И. Гурский Теория вероятностей с элементами математической статистики: уч. пос. для вузов / Е.И. Гурский. – М.: Вс. шк., 1971. – 328 с.

2. Дж. Купер. Вероятностные методы анализа сигналов и систем / Дж. Купер, К. Макгиллем; пер. с англ. В.Т. Горяинова. – М.: Мир, 1989. – 376 с.

3. В.П. Бакалов. Цифровое моделирование случайных процессов / В.П. Бакалов. – М.: Сайнс-пресс, 2002. – 88 с. – (Серия «Конспекты лекций по радиотехническим дисциплинам»; вып. 4).

4. Боровиков В. STATISTICA для профессионалов. СПб.: Питер. 2001. – 655 с.

5. Гультяев А.К. Matlab 5.2. Имитационное моделирование в среде Windows: практическое пособие.

Приложение А. – Основные сведения по генераторам случайных чисел

В основе метода Монте-Карло лежит генерация случайных чисел, которые должны быть равномерно распределены в интервале (0; 1).

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

Математическое ожидание m_r и дисперсия D_r такой последовательности, состоящей из n случайных чисел r_i, должны быть следующими (если это действительно равномерно распределенные случайные числа в интервале от 0 до 1):

Если пользователю потребуется, чтобы случайное число x находилось в интервале (a; b), отличном от (0; 1), нужно воспользоваться формулой x = a + (b – a) · r, где r —

случайное число из интервала (0; 1). Законность данного преобразования демонстрируется на рисунке А.1.

Рис. А.1. Схема перевода числа из интервала (0; 1) в интервал (a; b)

 

Теперь x – случайное число, равномерно распределенное в диапазоне от a до b.

За эталон генератора случайных чисел (ГСЧ) принят такой генератор, который порождает последовательность случайных чисел с равномерным законом распределения в интервале (0; 1). За одно обращение данный генератор возвращает одно случайное число. Если наблюдать такой ГСЧ достаточно длительное время, то окажется, что, например, в каждый из десяти интервалов (0; 0.1), (0.1; 0.2), (0.2; 0.3), …, (0.9; 1) попадет практически одинаковое количество случайных чисел – то есть они будут распределены равномерно по всему интервалу (0; 1). Если изобразить на графике k = 10 интервалов и частоты N_i попаданий в них, то получится экспериментальная кривая плотности распределения случайных чисел (см. рис. А.2 ).

 

 

Рис. А.2. Частотная диаграмма выпадения случайных чисел,
порождаемых реальным генератором

 

Заметим, что в идеале кривая плотности распределения случайных чисел выглядела бы так, как показано на рисунке А.3. То есть в идеальном случае в каждый интервал попадает одинаковое число точек: N_i = N / k, где N – общее число точек, k – количество интервалов, i = 1, …, k.

Функциональные преобразования для имитации случайных процессов

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

Нормальное распределение моделируется следующими способами: