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


 

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

31287. Дослідження низькочастотних генераторів сигналів різної форми в пакеті Electronics Workbench 1.39 MB
  Розглянемо ряд найпоширеніших генераторів сигналів синусоїдальної прямокутної і трикутної форм із регульованими параметрами частота амплітуда тривалість імпульсів та з різними методами стабілізації параметрів вихідних коливань. Генератори синусоїдальних коливань Принцип роботи генераторів синусоїдальних коливань заснований на використанні в ланцюгах зворотного звязку ЗЗ фазозсуваючих чи резонансних елементів: моста Віна подвійного Т образного моста що зсуває RC ланцюгів і ін. Тому при використанні високоякісних RC елементів...
31288. Дослідження схем активних випрямлячів в пакеті Electronics Workbench 1.11 MB
  Робота подібних випрямлячів як правило заснована на тому що при одній полярності вхідна напруга з деяким масштабним коефіцієнтом подається на вихід а при іншій вихідна напруга підтримується рівною нулю однонапівперіодний випрямляч чи інвертованій вхідній напрузі двонапівперіодний випрямляч. Побудувати схеми випрямлячів в пакеті Electronics Workbench для контролю за вихідними параметрами необхідно до виходів випрямлячів підключити вольтметр та осцилограф. Для кожного з побудованих випрямлячів визначити його тип.
31289. Дослідження комбінаційних схем, реалізованих за методом декомпозиції 1.2 MB
  Знайти гарантовано мінімальний вираз для довільної функції можна лише перебравши всі варіанти різних способів групування в процесі мінімізації що реально лише для невеликої кількості аргументів. З точки зору підходів до спрощення логічних виразів функції з якими має справу схемотехнік доцільно розділити на три групи: функції невеликої кількості аргументів €œобєктивні€ функції багатьох аргументів €œсубєктивні€ функції багатьох аргументів. До першої групи відносять функції трьохпяти аргументів. Статистичний аналіз реальних схем...
31290. Дослідження схем синхронних та асинхронних цифрових автоматів з пам’яттю в пакеті Electronics Workbench 2.88 MB
  При моделюванні роботи синхронного автомата синхросерію слід подавати з генератора коливань обравши прямокутну форму імпульсів з параметрами близькими до вказаних на рис. Побудування логічних вентилів при синтезі синхронного автомата Якщо потрібно сформувати память автомата на Ттригерах не слід шукати їх в бібліотеці елементів так як їх фізично не існує необхідно побудувати Т тригер з JK тригера походячи з таблиці переходів. Часові діаграми роботи автомата слід скопіювати через буфер до редактора Paint або іншого графічного...
31291. Вивчення структури контролера КРВМ-2 та його засобів вводу-виводу 677.5 KB
  ЯПВВ - комірка програмованого вводу-виводу. Забезпечує зв’язок з зовнішніми об’єктами за будь-яким напрямком. До складу комірки входить мікросхема КР580ВВ55, порти якої з’єднані із зовнішніми приладами через шинні підсилювачі К589АП16, 2 шинних формувача КР580ВА86, мікросхеми К555ИД4 (здвоєний дешифратор 2 входи – 4 виходи), мікросхеми К155ТМ8 (4 D-тригери), К155ЛА3 (4 елементи 2І-НІ).
31292. Розрахунок генераторів пилкоподібної напруги 408 KB
  широко використовуються генератори пилкоподібної лінійнозмінної напруги. Часову діаграму пилкоподібної напруги наведено на рис.1 Часова діаграма пилкоподібної напруги Основними параметрами такої напруги є: тривалість робочого і зворотного ходу пилкоподібної напруги; період проходження імпульсів ; амплітуда імпульсів ; коефіцієнт нелінійності і коефіцієнт використання напруги джерела живлення .
31293. Розрахунок схем активних фільтрів 778 KB
  Апроксимація характеристик активних фільтрів зводиться до вибору таких коефіцієнтів цих поліномів що забезпечують найкраще в тому чи іншому значенні наближення до бажаних амплітудночастотної АЧХ чи фазочастотної характеристик фільтра.1 де відносна частота; частота зрізу; порядок фільтра. В фільтрі Чебишева апроксимуюча функція вибирається так щоб в смузі пропускання фільтра отримати відхилення його характеристики від ідеальної що не перевищує деякої заданої величини.2 де постійний коефіцієнт що визначає нерівномірність АЧХ...
31294. Мінімізація логічних функцій 449.5 KB
  Основна задача при побудові систем керування дискретними обєктами і процесами на основі логічних функцій: приведення логічних функцій керування до найбільш простого виду при якому система керування буде виконувати свої задачі. Для ручної мінімізації логічних функцій використовуються карти Карно і діаграми Вейча причому останні будують як розгорнення кубів на площині карти Карно.
31295. Тема: Синтез комбінаційних схем на мікросхемах середнього ступеня інтеграції Мета заняття:Закріпити отр. 1.08 MB
  Традиційно ця назва застосовується до вузлів робота яких не описується досить простим алгоритмом а задається таблицею відповідності входів і виходів.1 Якщо декодер має входів виходів і використовує всі можливі набори вхідних змінних то . Число входів і виходів декодера вказують таким чином: декодер 38 читається €œтри на вісім€ 416 410 неповний декодер. Мультиплексор це функціональний вузол що здійснює підключення комутацію одного з декількох входів даних до виходу.