Генератор последовательности случайных чисел Советский патент 1982 года по МПК G06F7/58 

(5) ГЕНЕРАТОР ПОСЛЕДОВАТЕЛЬНОСТИ СЛУЧАЙНЫХ ЧИСЕЛ

Изобретение относится к вычислительной технике и может быть использовано при моделировании случайных чисел и процессов. Известны способы генерирования последовательности случайных чисел, основанные на преобразовании сигнала первичного физического источника шума в случайную последовательность импульсов с последуюо4им пересчетом их числа за фиксированный интервал времени или же основанные на преобразовании сигнала источника шума за случайный интервал времени с последующим пересчетом импульсов детермированной последовательности за это случайный интервал времени tl3. Главный недостаток известных способов - изменение вероятностей появления символов в генерируемой последовательности случайных чисел из-з нестационарности статистических характеристик случайного процесса формируемого любым первичным физическим источником шума. Известно устройство, состоящее из последовательно соединенных генератора случайных напряжений, потенциального клапана, блока аналоговой памяти, ограничителя и схемы формирования 2. Известен также генератор случайных сигналов, содержасций генератор случайного напряжения, элемент И, два блока сравнения, блок суммирования и интегратор для устранения зависимости вероятности появления импульсов на выходе устройства от нестабильности статистических характеристик процесса, вырабатываемого генератором случайного напряжения, он имеет стабилизирующую обратную связь Наиболее близким к предлагаемому является генератор последовательности случайных чисел, содержащий последовательно соединенные источник шума, усилитель, формирователь, вен тиль запрета, триггер, вентиль опро са, генератор тактовых мипульсов, один из выходов которого подключен к второу входу вентиля запрета, дру гой выход - к второму входу вентиля опроса, а также интегрирующую схему в цепи обратной связи, вход которой подключен к выходу вентиля опроса, а выход - к входу источника шума С4 Параметры интегрирующей схемы выбраны таким образом, что при отклонении вероятности выдачи на выхо устройства единичных импульсов от значения 0,5 управляющее воздействие интегрирующей схемы на источник шума соответствующим образом изменяет ( увеличивает или уменьшает количество вырабатываемых единичных импульсов. Для устранения изменения вероятностей появления символов в генерируемой последовательности нестационарности за времени статистических характеристик случайного про цесса первичного физического источника шума используют различные виды коррекции. Коррекция осуществляется по результатам статистического анализа параметров вырабатываемой двоичной случайной последовательности, при этом не гарантируется исключение интервалов в генерируемой последовательности, на которых распре.деление вероятностей появления О отличается от равномерного вследствие инерционности корректирующей обратной связи, заключающейся в необходимости достаточно продолжительного анализа последовательности вырабатываемых импульсов для формирования корректирующего во действия. Достоверность результатов анализа определяется длиной анализируемой последовательности, что приводит к техническому противоречию увеличение продолжительности анализа с целью повышения достоверности его результатов влечет за собой уве личение вероятности появления некон тролируемых отрезков последовательности с неравномерным распределение вероятностей появления символов О и 1, уменьшение продолжительности анализа с целью повышения скорости получения его результатов за счет снижения достоверности приводит к существенной нестационарности форми руемой случайной последовательности, которая принимает колебательный характер. Цель изобретения - повышение статистических характеристик генерируемой случайной последовательности двоичных цифр, т.е. повышение точности генератора. Для достижения поставленной цели в генератор последовательности случайных чисел, содержащий генератор тактовых импульсов, триггер, источник шума, выход которого через формирователь импульсов соединен с первым входом элемента И, введены D-триггер и счетчик, счетный вход которого подключен к выходу элемента И, второй вход которого подключен к выходу генератора тактовых импульсов и счетному входу триггера, выход которого соединен с О-входом D-триггера, синхронизирующий вход которого подключен к выходу счетчика, а выход D-триг гера является выходом генератора. На чертеже приведена блок-схема генератора. Принцип работы генератора заключается в следующем. Рассмотрим регулярную двоичную последовательность символов вида ...010101..., каждый символ которой с вероятностью Rf. выбирается для формирования промежуточной случайной двоичной последовательности. Вероятности появления соответствующих символов промежуточной последовательности могут быть определены на основе ее представления марковским процессом с матрицей переходных вероятностей вида 00 01 э р -to лл где РОО вероятность того, что если некоторый из выбранных символов есть О, то и следующий выбранный за ним символ является .Р - вычисляется в соответствии с выражением ())p(), +pWpi -v pi M p 4 где P.-I-P. , а индексы при вероятностях указывают на порядковый номер выбранного (при Р4 )или не выJранного{при Р)символа относительно предыдущего выбранного символа исходной регулярной последовательности. Учитывая, что значения вероятно стей Р и Р не зависят от индекса выражение (2) представляет собой сумму членов бесконечно убывающей геометрической прогрессии, откуда . Аналогично имеем р - 4 1-Р.Р. И соответственно РОГ 10 Абсолютное значение разности д между значениями вероятностей Рд .Р определяется как Id| Pf 01 Н-1 - -I +Р4. И зависит от величины вероятности При формировании окончательной следовательности путем включения в нее каждого N-ro символа промежуточной последовательности матрица реходных вероятностей появления со ответствующих символов определяется путем М-кратного перемножения и ходной матрицы Л , т.е. 00 PI. Учитывая симметричность матрицы (1), значение |Д,ц|на М шага будет р но„ .N (5) Поскольку , имеем Bim , Н -«се откуда матрица предельных переходн вероятностей будет равна eim jl II 0.5 0.5 Н-ьс llO.J 0,5 Корреляционная функция случайно двоичной последовательности вычисляется по известному выражению R(K)M()(x.(XoX)-w(x),, которое для рассматриваемой промежуточной последовательности имеет вид R(K)P(X,(, -1) -(0,5Г. (6) Учитывая, что ptvvvbptv)-p(-t SpSt выражение (5 записывается в виде R{K)0, (О.З). с учетом (3) и С )для К-го элемента последовательности имеем 5( Р, (.).5, 1 и следовательно RIK)--(M) .0.s% ,1Д Г (в Учитывания, что окончательно выходная случайная двоичная последовательность формируется путем выбора каждого N-ro элемента из промежуточной случайной дпоичной последовательности, для выходной последовательности корреляционная функция имеет вид ад(о,5)1.н)«(,,л.- (5) Исходя из того, что число N выбирается таким образом, чтобы обеспечить требование ДМ |R (К7/1)|р} 0. Следовательно, описанный принцип обеспечивает генерирование последовательности равновероятных независимых двоичных символов. Задавая допустимое значение EzlAl, определяющее качество распределения вероятностей появления двоичных символов в выходной двоичной случайной последовательности, при известных значениях Р , можно рассчитать число N, показывающее какой по счету символ из промежуточной последовательности должен быть взят в качестве следующего разряда двоичного представления случайной величины. Число М определяется по формуле Знамения N, рассчитанные по цюрмуле (10J, для,некоторых значений Р и t представлены в таблице. T:::::: ::::I::: :I Го,01 0,001 I о. Продолжение таблицы Анализ результатов, представленных в таблице, показывает, что для обеспечения достаточно высокой равномерности распределения вероятностей случайных двоичных символов в выходной последовательности (iO,OOOl) при значительной нестационарности статистических характеристик исходного физического процесса (0,3 i P.i 0,7) достаточно иметь . Предлагаемый способ позволяет по лучить сколь угодно высокую равноме ность распределения вероятностей двоичной последовательности даже при предельных значениях флуктуации источ ика шума. Генератор содержит источник 1 шума, формирователь 2 импульсов, эл мент И 3f генератор 4 тактовых импульсов, триггер 5, счетчик 6, D-тр гер 7. Выход источника 1 шума соединен с входом формирователя 2, выполненного, например, в виде последовательно соединенных ограничителя по уровню и ждущего мультивибратора Выход формирователя 2 соединен с од ним из входов элемента И 3 Выход генератора k тактовых имупльсов сое динен со счетным входом триггера 5 и с вторым входом элемента И 3. элемента И 3 соединен с входом счетмика 6, который переводится до начала работы в исходное состояние (обнуляется и устанавливается коэффициент счета N, определяющий качес во формируемой последовательности). Выход счетчика 6 соединен с синхрон зирующим входом D-триггера 7, 0-вхо которого соединен с выходом счетног триггера 5. Устройство работает следующим образом. Сигнал с источника 1 шума поступает на формирователь 2, на выходе которого формируется случайная последовательность импульсов. Эти импульсы поступают на элемент И 3, на второй вход которого поступают импульсы тактовогс генератора . При совпадении во времени импульсов на входах элемента И 3 на его выходе вырабатывается сигнал, который поступает на вход счетчика 6. После поступления на вход счетчика N-ro по счету сигнала счетчик вырабатывает импульс разрешения выбора, KOTOрый поступает на синхронизирующий вход 0-триггера 7, на О-вход О-триггера 7 поступает детерминированная двоичная последовательность сигналов с выхода триггера 5 со счетным входом, на вход которого поступают тактовые импульсы с выхода генератора тактовых импульсов. При поступлении на синхронизирукмчий вход 0-триггера сигнала разрешения выбора D-триггер 7 принимает состояние, соответствукяцее состоянию триггера 5 На выходе D-триггера 7 формируется равновероятная двоичная последовательность. Предлагаемый генератор последавательности случайных чисел обладает существенными преимуществами по сравнению с известными ранее способами и устройствами, а именно неравномерность распределения вероятностей появления двоичных символов вырабатываемой случайной последовательности можно получить сколь угодНО малойJ принцип генерирования случайной двоичной последовательности предопределяет независимость ее статистических характеристик от изменения параметров физического источника случайного сигнала, в связи с чем исключается необходимость постоянного анализа Качества генерируемой последовательности, не требуется коррекция физического источника случайного сигнала или применение других известных способов повышения качества генерируемой случайной последовательности. Использование изобретения в вычислительной технике позволяет добиться высокого качества статистических характеристик стабильности их во времени, а также упрощение генератора случайной последовательности

из-за устранения необходимости применения стабилизируклцих элементов.

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

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

Генератор последовательности случайных чисел, содержащий генератор тактовых импульсов, триггер, источник шума, выход которого через (boo-fs мирователь импульсов соединен с первым входом элемента И, о т л и ч а ю щ и и с я тем, что, с целью повышения точности генератора, он содер жит О-триггер и счетчик, счетный вход 2в которого подключен к выходу элемента И, второй вход которого подключен к выходу генератора тактовых импульсов- и счетному входу триггера, выход которого соединен с О-входом D-триггера, синхронизирующий вход которого подключен к выходу счетчика, а выход О-триггера является выходом генератора.

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

Ц. Авторское свидетельство СССР W , кл.С Об F 15/36, 1970 (прототип).