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


 

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

73838. Технология изготовления втулок 80.5 KB
  Технологические задачи Отличительной технологической задачей является обеспечение концентричности наружных поверхностей с отверстием и перпендикулярности торцов к оси отверстия. Диаметры наружных поверхностей выполняют по h6 h7; отверстия по H7 реже по H8 для ответственных сопряжений по Н6.015 мм; перпендикулярность торцовых поверхностей к оси отверстия 02 мм на радиусе 100 мм при осевой нагрузке на торцы отклонение от перпендикулярности не должно превышать 002. Заготовками для втулок с диаметром отверстия до 20 мм служат...
73839. Технология изготовления корпусных деталей 1.63 MB
  Обрабатывают направляющие начерно резцами на продольнострогальных станках торцевыми фрезами и наборами фрез на продольнофрезерных станках. Обрабатывают начерно поверхности расположенные перпендикулярно направляющим на продольнофрезерных станках если станина по длине проходит между колонами станка; на горизонтальнорасточных станках фрезой или на торцефрезерных станках если станина длинная. Обрабатывают отверстия начерно на горизонтальнорасточных станках в приспособлении. Чистовую обработку лучше выполнять на продольнофрезерных...
73840. Процессы обработки деталей типа некруглые стержни 191.5 KB
  Технология изготовления рычагов. Характеристика рычагов К деталям класса рычагов относятся собственно рычаги тяги серьги вилки балансиры шатуны. Детали класса рычагов имеют два отверстия или больше оси которых расположены параллельно или под прямым углом.
73841. Процессы обработки деталей «круглые стержни» 58.5 KB
  В зависимости от типа производства операцию производят: в единичном производстве подрезку торцов и центрование выполняют на универсальных токарных станках последовательно за два установа; в серийном производстве подрезку торцов выполняют раздельно от центрования на продольнофрезерных или горизонтальнофрезерных станках а центрование на одностороннем или двустороннем центровальном станке. В зависимости от типа производства операцию выполняют: в единичном производстве на токарновинторезных станках; в мелкосерийном на...
73842. Технико-экономические показатели разрабатываемых ТП 72 KB
  На завершающим этапе разработки ТП проводят полную оценку вариантов путем сравнения себестоимости обработки заготовок отражающей затраты живого и овеществленного труда. Существует два основных метода определения себестоимости: бухгалтерский и метод прямого калькулирования поэлементный. Цеховые расходы при калькулировании себестоимости определяют в процентах от заработной платы основных рабочих цеха: тогда себестоимость текущие затраты можно выразить так: где ц – процент цеховых накладных расходов. Его можно использовать при приближенном...
73843. РОЗВИТОК СВІДОМОСТІ У ФІЛОГЕНЕЗІ 215 KB
  Сприймання – це відображення у свідомості людини цілісних предметів та явищ об’єктивного світу при їх безпосередньому впливі у дану мить на органи відчуттів. Його суттєва відмінність від відчуттів полягає в тому що в процесах сприймання формується образ цілісного предмету за допомогою відображення всієї сукупності його якостей. Однак образ сприймання не зводиться до простої суми відчуттів хоча й вносить їх до свого складу. Сприймання – результат діяльності системи аналізаторів.
73844. ПСИХІЧНІ ПРОЦЕСИ: ПАМ’ЯТЬ, УЯВА, МИСЛЕННЯ, УВАГА 84 KB
  Особливості пам’яті та уява. ІІ Пам’ять – форма психічного відображення яка заклечається в закріпленні збереженні і послідуючому відтворенні минулого досвіду. Пам’ять пов’язує минуле суб’єкта с його дійсністю і майбутнім і є найважливішою пізнавальною функцією яка лежить в основі розвитку і навчання.
73845. ЕМОЦІЙНО-ВОЛЬОВА СФЕРА ОСОБИСТОСТІ 112.5 KB
  Рису характеру розуміють як схильність до нервової поведінки яка склалася в силу наявності певних потреб мотивів чи інтересів мотиваційні риси або в силу наявності певних звичок установок сталевих особливостей поведінки. Окремі властивості характеру залежать одне від одного та тісно пов’язані між собою вони створюють цілісну організацію яку називають структурою характеру. В структурі характеру виділяють дві групи рис. Під рисою характеру розуміють ті чи інші особливості особистості людини які систематично проявляються в різних видах...
73846. Діяльність та особистість 148.5 KB
  Діяльність в житті людини: види структура предмет. ДІЯЛЬНІСТЬ – можна визначити як специфічний вид активності людини спрямований на пізнання і творче перетворення навколишнього світу включаючи самого себе й умови свого існування. Навчання являє собою прогресивне відтворення людини як свідомої особистості на основі засвоєння ним практичного та теоретичного досвіду людства. Особливе місце в житті людини займає ПРАЦЯ.