45494

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

Доклад

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

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

Русский

2013-11-17

75.5 KB

25 чел.

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

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

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

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

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

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


 

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

39204. Семья как социальный институт, ее исторические типы, функции 16.11 KB
  Специфика социологического изучения семьи заключается в том, что семья рассматривается как особый социальный институт, выполняющий одну из самых важных функций общества - воспроизводство его членов и осущестляющий их первичную социализацию.
39205. Основы истории и философии науки 181.35 KB
  Основы истории и философии наукИ Часть 1. Основы философии науки: лекционно курс Учебнометодическое пособие для аспирантов очной и заочной форм обучения СОКРАЩЕННЫЙ ВАРИАНТ Содержание Пояснительная записка. Курс лекций: Основы философии науки. ОБЩИЕ ПРОБЛЕМЫ ФИЛОСОФИИ НАУКИ.
39206. РЕКОМЕНДАЦИИ ПО ОФОРМЛЕНИЮ СТУДЕНЧЕСКИХ РАБОТ СОЦИАЛЬНО-ЭКОНОМИЧЕСКОГО НАПРАВЛЕНИЯ 264.5 KB
  При выполнении работы выбирается шрифт Times New Roman размером № 14 интервал 15. Опечатки описки и графические неточности обнаруженные в процессе выполнения работы допускается исправлять закрашиванием белым штрихом и аккуратным нанесением на том месте исправленного текста черной пастой гелем. Все подписи на титульном листе следует выполнять строчными буквами название темы работы прописными буквами размер шрифта 14. ПОСТРОЕНИЕ РАБОТЫ Текст работы разделяют на разделы и подразделы.
39207. Право собственности 753 KB
  Кроме того в регулируемых маркетинговым законодательством отношения могут участвовать Российская Федерация субъекты Российской Федерации и муниципальные образования.;6 маркетинговые союзы и ассоциации например Ассоциация распространителей финансовоэкономической информации;7 органы власти осуществляющие функции государственного регулирования маркетинговой деятельности например Министерство Российской Федерации по антимонопольной политике и поддержке предпринимательства Госстандарт России. Кроме того в регулируемых маркетинговым...
39208. Прохождение практики в Филиале Центрального АКБ «Инвестбанк» (ОАО) 195 KB
  В том числе клиентам предлагается большой выбор кредитных программ разнообразные формы денежных переводов как в рублях так и в иностранной валюте обслуживание банковских карт международных платежных систем а также варианты срочных валютных депозитов операции на валютном рынке и на рынке ценных бумаг. Кредитование при недостатке средств на расчетном счете овердрафт это особая форма краткосрочного кредита при котором Инвестбанк осуществляет оплату платежных документов клиента сверх средств имеющихся на его расчетном счете в пределах...
39211. Влияние кризиса на банковскую систему 94.5 KB
  Первая половина 2008 года привнесла достаточно много новых факторов влияющих на казахстанский банковский сектор которые складываются в новые доминанты развития финансовой системы Казахстана. Если рассматривать финансовые аспекты среди тенденций преобладающих в тот момент времени можно выделить: резкое сокращение темпов роста банковской системы; существенное ухудшение качества активов; снижение доходности казахстанских банков. Динамика данных по первой десятке крупнейших казахстанских банков представляющих 928 активов...
39212. Посткризисные проблемы формирования банковских ресурсов 60 KB
  Если рассматривать финансовые аспекты среди тенденций преобладающих в последнее время можно выделить: сокращение темпов роста банковской системы; ухудшение качества активов. В результате завершения реструктуризации внешних обязательств казахстанских банков объем собственного капитала банковской системы вернулся к своему прежнему положительному уровню. Однако ухудшающее качество ссудного портфеля со своей стороны продолжает увеличивать нагрузку на собственный капитал банков что требует проведения дальнейшей капитализации банковской...