Генератор последовательности случайных чисел

 

Г. П. Чубатов, А. В. Король, В. Н. Коротков, В. И. Чепрунова и В. В. Титов (72) А В%эры взебретеяия (71) Заявитель (54) ГЕНЕРАТОР ЛОСЛЕДОВАТЕЛЬНОСТИ СЛУЧАЙНЫХ

ЧИСЕЛ

Изобретение относится к вычислительной технике и может быть исполь« ! эовано при моделировании случайных чисел и процессов.

Известны способы генерирования последовательности случайных чисел, основанные на преобразовании сигнала первичного физического источника шума в случайную последовательность импульсов с последующим пересчетом их числа за фиксированный интервал времени или же основанные на преобразовании сигнала источника шума за случайный интервал времени с последующим пересчетом импульсов детермированной последовательности эа этот случайный интервал времени 0 3.

Главный недостаток известных способов - изменение вероятностей появления символов в генерируемой последовательности случайных чисел из-за нестационарности статистических характеристик случайного процесса фор2

;мируемого любым первичным физическим источником шума.

Известно устройство, состоящее из последовательно соединенных генератора случайных напряжений, потен5 циального клапана, блока аналоговой памяти, ограничителя и схемы формирования (2).

Известен также генератор случайных сигналов, содержащий генератор случайного напряжения, элемент И, два блока сравнения, блок суммирования и интегратор для устранения за" висимости вероятности появления им пульсов на выходе устройства от нестабильности статистических характеристик процесса, вырабатываемого генератором случайного напряжения, он имеет стабилизирующую обратную связь зв (3 3.

Наиболее близким к предлагаемому является генератор последовательности случайных чисел, содержащий последовательно соединенные источник з 94 шума, усилитель, формирователь, вентиль запрета, триггер, вентиль опроса, генератор тактовых мипульсов, один из выходов которого подключен к второу входу вентиля запрета, другой выход — к второму входу вентиля опроса, а также интегрирующую схему в цепи обратной связи, вход которой подключен к выходу вентиля опроса, а выход - к входу источника шума (4 3.

Параметры интегрирующей схемы выбраны таким образом, что при отклонении вероятности выдачи на выходе устройства единичных импульсов от значения 0,5 управляющее воздействие интегрирующей схемы на источник шума соответствующим образом изменяет (увеличивает или уменьшает количество вырабатываемых единичных импульсов.

Для устранения изменения вероятностей появления символов в генерируемой последовательности из-за нестационарности во времени статисти-ческих характеристик случайного процесса первичного физического источника шума используют различные виды коррекции. Коррекция осуществляется по результатам статистического анализа параметров вырабатываемой двоичной случайной последовательности, при этом не гарантируется исключение интервалов в генерируемой последовательности, на которых распре.деление вероятностей появления "0" и "1", отличается от равномерного вследствие инерционности корректирующей обратной связи, заключающейся в необходимости достаточно продолжительного анализа последовательности вырабатываемых импульсов для формирования корректирующего воздействия.

Достоверность результатов анализа определяется длиной анализируемой последовательности, что приводит к техническому противоречиюувеличение продолжительности анализа с целью повышения достоверности

его результатов влечет за собой увеличение вероятности появления неконтролируемых отрезков последовательности с неравномерным распределением вероятностей появления символов "0" и "1", уменьшение продолжительности анализа с целью повышения скорости получения его результатов за счет снижения достоверности приводит к существенной нестационарности форми0156 4 руемой случайной последовательности, которая принимает колебательный характер.

Цель изобретения - повышение статистических характеристик генерируемой случайной последовательности двоичных цифр, т.е. повышение точности генератора.

Для достижения поставленной цели

10 в генератор последовательности случайных чисел, содериащий генератор тактовых импульсов, триггер, источник шума, выход которого через формирователь импульсов соединен с первым входом элемента И, введены 0-триггер и счетчик, счетный вход которого подключен к выходу элемента И, второй вход которого подключен к выходу генератора тактовых импульсов и счетному входу триггера, выход которого соединен с 0-входом 0-триггера, синхронизирующий вход которого подключен к выходу счетчика, а выход 0-триг гера является выходом генератора.

На чертеже приведена блок-схема генератора.

Принцип работы генератора заключается в следующем. Рассмотрим регулярную двоичную последовательность символов вида ...01010 1..., каждый символ которой с вероятностью Р выбирается для формирования промежуточной случайной двоичной последовательности. Вероятности появзз, ления соответствующих символов про межуточной последовательности могут быть определены на основе ее представления марковским процессом с матрицей переходных вероятностей вида

ОО О4

10 М где Р о- вероятность того, что если некоторый из выбранных символов есть

45 "0", то и следующий выбранный за ним символ является "0";.P - вычисляется в соответствии с выражением р р(1)р(М р(4}р(1)р(3)р(4) р(Цр(Ордер(4)рф)р(6) (Я ) где Р =-1-Р+, а индексы при вероятностях указывают на порядковый номер выбранного (при Р )или не вы,55 ранного(при P )символа относительно предыдущего выбранного символа исходной регулярной последовательности, 5 940

Учитывая, что значения вероятностей P и Р+ не зависят от индекса, выражение (? ) представляет собой сумму членов бесконечно убывающей геометрической прогрессии, откуда

Р Р

po . оо РР

Аналогично имеем р Р 1О

Р«=

)-P Р и соответственно

Ро„= Р10 = 1-Р „(3)

Абсолютное значение разности д

35 между значениями вероятностей Ро и ,Р1 определяется как

11

1й) = Ра„- P„ --- „, (4) и зависит от величины вероятности Р

При формировании окончательной последовательности путем включения в

Щ нее каждого N-ro символа промежуточной последовательности матрица переходных вероятностей появления соответствующих символов определяет- . ся путем Й-кратного перемножения ис2S ходной матрицы Л, т.е.

Й

00 6.»

10 11,й = Jf s (Й) Учитывая симметричность матрицы (1), значение )ЬЙ)на Й вага будет равно д )» fg$ . (5) зз

Поскольку 1Ы (1, имеем

Ь1Р Я l=O, Я -все откуда матрица предельных переходных 4в вероятностей будет равна е- Й- I 0»5 0,5 ф-(рр 10)5 0,5

Корреляционная функция случайной двоичной последовательности вычис- 45 . ляется ho известному выражению

)))(»)=м((» -х)(х„-х))=м(х х„)-м(х»),.

) которое для рассматриваемой промежуточной последовательности имеет у» вид й(К)=Р(Хк=1 Хо 1) -(0,5) . (6)

Учитывая, что

Р(»„ 4/хов1)оР(»о= ) P(»»=<)=OSP„,(1) выражение (5 ) записывается в виде

) (К)=0,5PI„ - (0,5)

С учетом (3 ) и (4)для К-го элемента последовательности имеем

156 6 к

Р(=0,5 (1- b„)=0,5 (- j 0Д

1 и следовательно к -Р " к

К(К)=(-1) — -0,S К=О, )Л)--- (8)

1+Р

Я(х)-(О») +4)»" "- - )","К-О,., (»)

Исходя из того, что число N выбирается таким образом, чтобы обеспечить М требование дЯ / ФО, имеем

1 Р- °

)R (К,1))р О.

Следовательно, описанный принцип обеспечивает генерирование последовательности равновероятных независимых двоичных символов.

Задавая допустимое значение E=)h), определяющее качество распределения вероятностей появления двоичных символов.в выходной двоичной случайной последовательности, при известных значениях Р, можно рассчитать число

Й, показывающее какой по счету символ из промежуточной последовательно-. сти должен быть взят в качестве следующего разряда двоичного представления случайной величины.

Число Й определяется по формуле е е

К С - (10)

Значения Й, рассчитаннь)е по ())u)»муле (10}, для некоторых значений Р и 6 представлены в таблице.

1 1

0,01 0,001

0,0001

030 8 12 15

035 7 10 13

0,40 6

0,45 I0

0,50 5

Учитывания, что окончательно выходная случайная двоичная последовательность формируется путем выбора каждого М-го элемента из промежуточной случайной двоичной последовательности, для выходной последовательности корреляционная функция имеет вид

940156

Сигнал с источника 1 шума поступает на формирователь 2, на выходе которого формируется случайная последовательность импульсов. Эти импульсы постулают на элемент И 3, на второй вход которого поступают импульсы тактового генератора 4.

При совпадении во времени импульсов на входах элемента И 3 на его в выходе вырабатывается сигнал, который поступает на вход счетчика 6. После поступления на вход счетчика М-го по счету сигнала счетчик вырабатывает имлульс разрешения выбора, который поступает на синхрониэирующий вход О-триггера 7, на 0-вход 0-триггера 7 поступает детерминированная двоичная последовательность сигналов с выхода триггера 5 со счетным входом, на вход которого лоступают тактовые импульсы с выхода генератора 4 тактовых импульсов.

Продолжение таблицы

0,55 4

0,60 4

0,65 3 0,70 3

15 бв

0,01 0,001 0,0001

Рнализ результатов, представленных в таблице, показывает, что для обеспечения достаточно высокой равномерности распределения вероятностей случайных двоичных символов в выходной лоследоеательности

®40,0001) при значительной нестационарности статистических характеристик исходного физического процесса (0,3 < P» 0,7) достат иметь И=15.

Предлагаемый способ дозволяет получить сколь угодно высокую равномерность распределения вероятностей двоичной лоследовательности даже при. предельных значениях флуктуаций источника шума.

Генератор содержит источник шума, формирователь 2 импульсов, элемент И 3, генератор 4 тактовых имлульсов, триггер 5, счетчик 6, 0-триг35 гер 7.

Выход источника 1 шума соединен с входом формирователя 2, вылолненного, например, в виде последовательно соединенных ограничителя по уровню и ждущего мультивибратора, Выход формирователя 2 соединен с одним из входов элемента И 3. Выход генератора 4 тактовых имупльсов соединен со счетным входом триггера 5

45 и с вторым входом элемента И 3. Выход элемента И 3 соединен с входом счетчика 6, который переводится до начала работы в исходное состояние (обнуляется и устанавливается коэффициент счета N, определяющий качество формируемой последовательности).

Выход счетчика 6 соединен с синхронизирующим входом 0-триггера 7, 0-вход которого соединен с выходом счетного 55 триггера 5.

Устройство работает следующим образом.

При поступлении на синхронизирующий вход О-триггера сигнала разрешения выбора 0-триггер 7 принимает состояние, соответствуецее со" стояние триггера 5. На выходе D-триг. гера 7 формируется равновероятная двоичная последовательность.

Предлагаемый генератор последо= вательности случайных чисел обладает существенными преимуществами по сравнению с известными ранее способами и устройствами, а именно неравномерность распределения вероятностей появления двоичных символов вырабатываемой случайной последовательности можно получить сколь угодно малой принцип генерирования случайной двоичной последовательности 1тредопределяет .независимость ее статистических характеристик от изменения параметров физического источника случайного сигнала, в связи с чем исключается необходимость постоянного анализа качества генерируемой последовательности, не требуется коррекция физического источника случайного сигнала или применение других известных способов повышения качества генерируемой случайной последовательности.

Использование изобретения в вычислительной технике позволяет добиться высокого качества статистических характеристик стабильности их во времени, а также упрощение генератора случайной последовательности

56 10 та И, второй вход которого подключен к выходу генератора тактовых импульсов и счетному входу триггера, выход которого соединен с 0-входом

О-триггера, синхронизирующий вход которого подключен к выходу счетчика, а выход 0-триггера является выходом генератора.

Источники инФормации, в принятые во внимание при экспертизе

1. Свердлин А. Некоторые вопросы образования случайных чисел в

ЦЕИ, ЛВИКА им. А. ф. MoeaNcxoro, Л., 196, с. 46.

2. Авторское свидетельство СССР

И 351210, кл. 6 06 F 1/02, 1971.

3. Авторское свидетельство СССР

И 510706, кл. 6 06 Р 1/02, 1973.

4. Авторское свидетельство CCCP

И 348991, кл.G 06 F 15/36, 1970 (прототип), 9 9401 из-за устранения необходимости применения стабилизирующих элементов.

Кроме того, существенно повышается точность и достоверность моделирования и полученных на его 5 основе результатов решений вычислительных задач.

Формула изобретения

Генератор последовательности случайных чисел, содержащий генератор тактовых импульсов, триггер, источник шума, выход которого через Фоо-1% мирователь импульсов соединен с первым входом элемента И, о т л и ч а— ю шийся тем, что, с целью повышения точности генератора, он содер жит 0-триггер и счетчик, счетный вход в которого подключен к выходу элемен1

Заказ 4668/70 Тираж 731 Подписное

ВНИИПИ Государственного комитета СССР по делам изобретений и открытий

113035, Москва, Ж-35, Раушская наб., д. 4/5

Филиал ППП "Патент", г. Ужгород, ул. Проектная, 4

Составитель Я. Карасов

Редактор С. Крупенина Техред E.Õàðèòîí÷èêÊîððåêòîð В. Бутяга