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... при проверках будет считаться идеальным, что не совсем так


 

А также другие работы, которые могут Вас заинтересовать

22631. Закон руху матеріальних точок та твердого тіла 74 KB
  Запишемо другий закон Ньютона для матеріальної точки з даної системи: 1 де зовнішня сила що діє на іту м. Записавши 1 для кожної точки системи та просумувавши всі отриманні рівняння по і маємо: 2. Уведемо задає точкуцентр мас системи Центр мас рухається так ніби в ньому зосереджена вся маса системи. Повна кількість руху системи: = це математичне формулювання закону збереження імпульсу.
22632. Хвилі у пружному середовищі. Хвильове рівняння. Звукові хвилі 66 KB
  Хвилі у пружному середовищі. Звукові хвилі. Хвильовий процес характеризується фазовою швидкістю або швидкістю розповсюдження хвилі с груповою швидкістю або швидкістю розповсюдження хвильового пакету довжиною хвилі частотою або періодом коливань; між цими величинами існує простий звязок: . Довжина хвилі це відстань між частинками які коливаються з однаковою фазою.
22633. Рух ідеальної рідини. Рівняння Бернуллі 75 KB
  Рух ідеальної рідини. Ідеальна рідина внутрішнє тертя відсутнє сила тертя між окремими шарами рідини що тече рідина нестислива. Рівняння 1 для такої рідини має вигляд: Лінії потоку це лінії дотичні до яких в кожній точці співпадають за напрямом з вектором . При стаціонарному русі рідини її частинки при своєму русі не перетинають трубку потоку.
22634. Рух в’язкої рідини. Число Рейнольдса 39.5 KB
  Рух вязкої рідини. Розглянемо стаціонарну течію вязкої рідини в прямій горизонтальній трубі з постійним перерізом. Модуль сили внутрішнього тертя що прикладена до площини S яка лежить на границі між шарами:; або оскільки вісь z напрямлена вздовж радіусу η коефіцієнт вязкості залежить від природи і стану рідини. Виділимо з обєму рідини що тече циліндр радіусу r довжини l та запишемо умови його руху.
22635. Принцип найменшої дії та рівняння Лагранжа 80.5 KB
  Принцип найменшої дії та рівняння Лагранжа. функцією Лагранжа системи. Ці рівняння називаються рівняннями Лагранжа. Властивості функції Лагранжа: Якщо домножити функцію Лагранжа на деяку константу вигляд рівнянь руху не зміниться; Якщо система складається з двох не взаємодіючих частин A і B з функціями Лагранжа та то система описується функцією Лагранжа .
22636. Гамільтонова форма рівнянь руху класичної механіки 75.5 KB
  Тут величина являє собою енергію системи що виражена через координати і імпульси і називається функцією Гамільтона системи. Ці шукані рівняння в змінних і називаються рівняннями Гамільтона. Розглянемо повну похідну фції Гамільтона по часу . Підставимо сюди та з рівнянь Гамільтона.
22637. Основні положення і головні результати спеціальної теорії відносності 77 KB
  Ейнштейн побудував спеціальну теорію відносності на постулатах: фізичні закони формулюються однаково в усіх інерціальних системах відліку ІСВ; швидкість світла у вакуумі не залежить від руху джерела і є однаковою в усіх ІСВ. Якщо простір ізотропний і однорідний то виконується рівність де константа залежить від швидкості ІСВ. Для нерухомої другої ІСВ . Для оберненого перетворення перехід до першої ІСВ: .
22638. Основні закони термодинаміки. Статистичне означення ентропії 74.5 KB
  Функція що звязує тиск обєм і температуру фізично однорідної системи яка перебуває в термодинамічній рівновазі називається рівнянням стану. Другий закон ТД Не існує періодично діючого пристрою що виконував би роботу лише за рахунок відбору теплоти від одного і того ж джерела існує однозначна функція стану системи яка залишається постійною при адіабатичних процесах S. При рівноважних процессах зміна ентропії системи пов`язана з кількістю тепла що передається співвідношенням : Для адіабатичного циклічного процесу і тобто ...
22639. Розподіл Максвела та Больцмана. Їх експериментальна перевірка 121 KB
  Розподіл Максвела та Больцмана. Використаймо великий канонічний розподіл Гіббса де . Тобто можна відокремити де розподіл по швидкостям а розподіл по координатах. Розглянемо розподіл молекул по швидкостям.