45494

Методы построения датчиков случайных чисел

Доклад

Коммуникация, связь, радиоэлектроника и цифровые приборы

Генератор случайных чисел ГСЧ Основа метода МонтеКарло ГСЧ равномерно распределенных в интервале 01. Такая последовательность чисел должна обладать математическим ожиданием и дисперсией Если окажется что случайные числа должны быть распределены в другом интервале то преобразование имеет вид: ГСЧ ррb x:= b r Пример: x:= 313r r:=0 x:=3r:=1 x:=10r:=0. ГСЧ порождает случайный поток событий с равномерным законом распределения. ГСЧ делятся на: физические; табличные; алгоритмические.

Русский

2013-11-17

75.5 KB

22 чел.

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

На  этапе исследования и проектирования систем при построении и реализации моделей (имитационных или аналитических) широко используется метод статических испытаний

Монте-Карло, который базируется на использовании случайных чисел, т.е.

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

Генератор случайных чисел (ГСЧ)

Основа метода Монте-Карло - ГСЧ, равномерно распределенных в интервале (0,1). Такая последовательность чисел должна обладать математическим ожиданием и дисперсией

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

ГСЧ рр(a,b)

x:= a + (b-a) r

Пример:

x:= -3+13r

r:=0     x:=-3
r:=1     x:=10
r:=0.8  x:=7.4

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

ГСЧ порождает случайный поток событий с равномерным законом распределения. При одном обращении выпадает одно случайное число.

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

Следует запомнить, что генерация произвольного случайного числа состоит из двух этапов:
1. генерация нормализованного случайного числа (равномерно распределенного от 0 до 1);
2. преобразование случайного числа в произвольный закон распределения.

ГСЧ делятся на:
- физические;
- табличные;
- алгоритмические.

1. Физические ГСЧ

- монета ("орел" - 1, "решка" - 0)

- игральные кости
- вращающийся барабан, разделенный на сектора, со стрелкой
- аппаратурный генератор шума (ГШ). В качестве ГШ используют шумящее тепловое устройство, например транзистор.

2. Табличные ГСЧ

таблица

 

0 r 1

7

1

8

0

. . .

0,718

3

4

6

0

 

0,346

6

4

1

2

 

0,641

. . .

 

. . .

< P>Случайные цифры

 

Случайные числа равномерно распределенные от 0 до 1

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

Недостатки метода: для хранения большого количества цифр требуется много памяти.

3. Алгоритмические ГСЧ

Эти числа всегда квазислучайные (то есть следующее сгенерированное число зависит от предыдущего)
r = f(r
i-1)

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

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

1. Метод серединных квадратов

Имеется четырехзначное число

Возводим его в квадрат

Из a1 берется середина и записывается в a0, далее процедура повторяется.

Недостатки:

- если число получится 0, то датчик вырождается;

- для качества генератора важно - какое взято начальное значение;

- датчик будет повторять последовательность через 2n шагов (24 для нашего случая).

2. Метод серединных произведений

Умножая a0 на a1 из полученного результата берем середину и умножаем ее на a1 и так далее.

3. Метод перемешивания

ц.с. на 1/4 P означает циклический сдвиг на 1/4 регистра вправо или влево.

Берется начальное число, из него образуется еще 2 с помощью циклического сдвига на 1/4 регистра вправо или влево.

4. Мультипликативный метод

ai+1 = mod(k ai + b, M)

MOD(a,z) - операция, возвращающая остаток от деления первого аргумента на второй. Для качественного генератора требуется подобрать подходящие коэффициенты k, b, M и

начальное число случайной последовательности. Например, известен ГСЧ, дающий 7

миллионов случайных чисел с

параметрами
k = 1220703125
b = 7
M = 2
31 - 1 = 0.1111...
a
0 = 7

Проверка качества работы датчика

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

Проверки осуществляются:

- на равномерность,
- на статическую независимость.

1) Проверки на равномерность распределения

a). ГСЧ должен выдавать значение статистических параметров близко к следующим:

(мат. ожидание)

(дисперсия)

(среднеквадратичное отклонение)

б). частотный тест (выясняет, сколько чисел попало в интервал):

(mr sr) = (0.5 0.2887) 0.57
(то есть 58% должно попадать в интервал (m
r sr) )
(0 0.5) (0.5 1) - сколько чисел попало в интервал от 0 до 0.5, столько же и в интервал от 0.5 до 1.

в). проверка по критерию

f(r) - плотность вероятности
ni - число точек, попавших в i-ый интервал
Pi - теоретическая вероятность попадания чисел в i-ый интервал
Pi = 1/k
n
1 + n2 + ... + nk = N

где k - количество интервалов

Процедура проверки:

1. Запускают ГСЧ (N раз).
2. Разбивают диапазон от 0 до 1 на k интервалов.
3. Определяют количество случайных чисел, попавших в каждый интервал n
i , i = (1 k).
4. Вычисляют по формуле.
5. Формируется вывод: удовлетворяет датчик по качеству или нет сравнением полученного экспериментально значения с теоретическим по таблице:

N-1 \ V

0.99

0.98

. . .

0.01

2

0.02

0.03

. . .

13.8

3

 

. . .

 

4

 

. . .

 

 

 

 

. . .

 

V - доверительная вероятность
(N-1) - количество экспериментов

Для этого:

5.1. Входим в таблицу (строка = количество экспериментов)
5.2. Столбец определяем сами, задавшись доверительной вероятностью (насколько ГСЧ должен удовлетворять требованиям равномерного распределения)
5.3. Находим в таблице
5.4. Если <, то датчик не удовлетворяет требованию равномерного распределения, если неравенство обратное - удовлетворяет.

2) Проверки на статистическую независимость

a). проверка на частоту появления цифры в последовательности


P
j - теоретическая вероятность выпадения цифры
P
j = 0.1

b). Проверка появления серий из одинаковых цифр

nl - серия длины l
l = (1 m)

В примере обнаружены
n
2 - 2 серии длиной в 2,
n
3 - 1 серия длиной в 3.

Вероятность появления серий длиной в l равна: Pl = 9*10-1 (теоретическая). Реальная подсчитывается по формуле:
.

датчик проверяется многократно, но несмотря на это проверки не обладают свойством

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

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