45494

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

Доклад

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

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

Русский

2013-11-17

75.5 KB

26 чел.

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

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

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

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

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

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


 

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

21345. Устойчивость систем автоматического управления 1.15 MB
  Оценить устойчивость системы можно в результате исследования ее математической модели то есть решить соответствующую систему дифференциальных уравнений. Для разомкнутой системы математическая модель в операторной форме: или где оператор дифференцирования. Для замкнутой системы: или .
21346. Свойства систем автоматического управления 975.5 KB
  Системы характеризуются: запасом устойчивости областями устойчивости притяжения качеством регулирования и другими характеристиками. Структурная устойчивость неустойчивость Это такое свойство замкнутой системы при наличии которого она не может быть сделана устойчивой ни при каких изменениях параметров. Годограф Найквиста для данной системы изображен на Рис. Устойчивость этой системы определяется значениями параметров и .
21347. Теория автоматического управления 720 KB
  Постановка задачи автоматического управления. Типовые звенья систем автоматического управления все виды математических моделей построение частотных характеристик: Идеальное и реальное усилительные идеальное и реальное дифференцирующие идеальное формирующее идеальное интегрирующее звено второго порядка апериодическое колебательное консервативное минимально фазовые звенья. Устойчивость систем автоматического управления: Анализ устойчивости САУ по корням характеристического уравнения Алгебраический критерий устойчивости Гурвица.
21348. Минимально фазовые и неминимально фазовые звенья 1.64 MB
  Если в передаточной функции произвести замену то получаем называемое частотной характеристикой звена частотный коэффициент передачи звена. Общая фаза выходного сигнала звена будет складываться из частичных фаз определяемых каждым двучленом числителя и знаменателя. Если хотя бы один из корней звена расположен справа то такое звено не минимально фазовое звено.
21349. Порядок эксплуатации станции. Подготовка к работе 34.71 KB
  Подготовка станции помех к работе заключается в подготовке к работе основных устройств и блоков изделия. Перед включением, проверьте надежность и правильность подключения заземления, состояние и надежность подключения кабелей питания.
21350. Назначение, состав, основные технические характеристики, устройство АСП Р-934Б 34.13 KB
  Состав станции Станция размещается на гусеничном тягаче МТ ЛБУ. Время реакции станции с момента выхода в эфир подавляемого РЭС до момента создания ему дежурной помехи при работе по 20 предварительно заданным частотам в пределах одной литеры не более 20 мкс при работе по неизвестным частотам в пределах 20 МГц не более 800 мкс. Служебная связь в станции обеспечивается с помощью радиостанции Р173. Экипаж станции 3 человека.
21351. Автоматизированная станция помех Р-934УМ 73.5 KB
  Предназначена для обнаружения анализа пеленгования источников радиоизлучений ИРИ и создания помех линиям УКВ радиосвязи системам сотовой и транковой связи а также системам телевидения.1 Станция помех Р934УМ может работать автономно в сопряженной паре однотипной АСП в качестве ведущей или ведомой а также под управлением пункта управления Р330КМА. В отличие от станции помех Р934У в АСП Р934УМ установлена более совершенная быстродействующая аппаратура управления и разведки позволяющая определять пеленги на источники...
21352. Назначение, состав, основные тактико-технические характеристики, общее устройство и принцип работы АПУ Р-330К 255.44 KB
  АПУ обеспечивает: сбор обработку хранение информации об обнаруженных ИРИ; автоматическое целераспределение целей с учётом системы приоритетов. У1М ПУ тактический в этом режиме по каналам телекодовой связи ПУ осуществляет сбор информации от АСП об обнаруженных ИРИ ее обработку и передачу на вышестоящий ПУ а также приём результатов целераспределения от вышестоящего ПУ и её распределение на подчинённые АСП. ПУ У1М обеспечивает: Автоматизированный ввод в ЭВМ информации поступающей от У2М и станций помех частота вид передачи...
21353. Устройство и принцип работы АПУ Р 330К 1.31 MB
  Сюда вводится режим работы ПУ номера исправных направлений связи дата количество выявленных радиосетей и обнаруженных ИРИ КВ УКВ и радиорелейном диапазонах АСП радиорелейного диапазона сопряженные с данными ПУ не разработаны но информация о них в ПУ введена количество выявленных УС номер этапа работы и время до начала следующего этапа; Е2 поле диагностических сообщений о сбоях в системе; Е3 поле набора команд и сообщений об ошибках в наборе; Е4 поле набора параметров и сообщений об ошибках в наборе; Е5 поле отображения...