45494

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

Доклад

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

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

Русский

2013-11-17

75.5 KB

21 чел.

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

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

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

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

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

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


 

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

34682. Хімічні процеси в стратосфері 99.5 KB
  У стратосфері на висотах менше 50 км відбувається утворення озону за реакцією O2 O → O3 Нестабільна молекула озону в збудженому стані O3 перетворюється в стабільну молекулу озону в результаті реакції з так званою третьою часткою в якості якої виступають молекули кисню і азоту що містяться в повітрі в найбільшій кількості: O3 M → O3 M 107 кДж Швидкість утворення озону пропорційна добутку концентрацій що беруть участь у реакціях частинок. Таким чином існує максимум швидкості утворення озону який припадає на...
34683. Аерозоль і клімат 311.5 KB
  Оцінка прямого впливу аерозолів на радіаційний баланс дає досить широкі Schätzungen der direkten Wirkung von erosolen uf den Strhlungshushlt zeigen eine reltiv große Bndbreite und beruhen weitgehend uf Modellstudien die nicht nur für die vorindustrielle Zeit sondern uch für die Gegenwrt schwer zu verifizieren sind. Die Unsicherheiten beruhen zum einen druf dss selbst der ktuelle tmosphärische Gehlt einzelner erosolrten nicht genu feststeht zum nderen druf dss die Größenverteilung die chemische Zusmmensetzung die Mischung und die...
34684. Водяной пар в атмосфере и гидрологический цикл 44.5 KB
  В отличие от большинства других присутствующих в атмосфере газов содержание водяного пара может очень сильно меняться. По мере того как молекулы воды переходят в воздух давление пара в воздухе увеличивается. Если температура воздуха продолжает увеличиваться то для поддержания насыщенного состояния пара число молекул поступающих в воздух также должно увеличиваться если конечно жидкость еще имеется. Давление пара служит мерой для другой величины также выражающей количество пара содержащегося в воздухе и называемой абсолютной влажностью.
34685. Вплив атмосферної циркуляції на транспорт хімічних речовин 144.5 KB
  Розподіл та концентрація хімічних речовин у атмосфері залежить від особливостей переміщення повітряних мас яке обумовлене загальною циркуляцією атмосфери. Внаслідок цього є постійний річний обмін енергією від низьких до високих широт завдяки океанічним і повітряним течіям рис. Оскільки Земля найсильніше нагрівається на екваторі то потоки нагрітого екваторіального повітря піднімаються високо вгору набагато вище ніж повітря в інших широтах. Під час екваторіального підйому повітря повітряні маси із низьких і високих широт...
34686. ГЛОБАЛЬНІ ЗМІНИ ВМІСТУ ОЗОНУ В АТМОСФЕРІ ЗЕМЛІ 281 KB
  Аналіз накопичених за перші 10 – 15 років матеріалів спостережень показав що кількість озону в стратосфері зменшується і виникло припущення що причиною цього є виробнича діяльність людини. У заяві містилось перше попередження про зменшення кількості озону і пов’язаних у зв’язку з цим небезпечних наслідках. Зменшення кількості озону особливо помітне над холодним антарктичним континентом – так звані озонові дірки†було вперше помічено тут.
34687. Джерела формування аерозолів та їх розподіл в атмосфері 99.5 KB
  Класифікація аерозолів за походженням За умовами формування виділяють первинні і вторинні аерозолі. Первинні аерозолі вносяться в атмосферу завдяки диспергуванню матеріалу на поверхні Землі вітрова ерозія спалювання різних видів палива в промислових регіонах пожежі в тропічних лісах винесення морських аерозолів з поверхні морів та океанів космічний пил. Вторинні аерозолі утворюються в результаті хімічних перетворень газоподібних речовинпопередників в атмосфері.
34688. Проблема выбора. Альтернативные издержки и кривая производственных возможностей 30.32 KB
  Почему Для удовлетворения потребностей необходимы экономические блага которые создаются с помощью факторов производства а их количество ограниченно. Например не все земли пригодны для производства сельскохозяйственной продукции. Возникает проблема выбора: как распорядиться ограниченными факторами производства чтобы полнее удовлетворить свои потребности Отдавая предпочтение чемуто делая выбор мы одновременно от чегото отказываемся. Эти 1000 тракторов от которых пришлось отказаться правительству являются альтернативными...
34689. Спрос. Закон спроса. Кривая спроса. 184.21 KB
  Закон спроса. Кривая спроса. Спрос и величина спроса – это разные понятия. Величина спроса зависит от цены.
34690. Предложение. Закон предложения. Кривая предложения 17.42 KB
  Закон предложения. Кривая предложения. Предложение и величина предложения – это разные понятия. Величина предложения зависит от цены.