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

Изобретение относится к вычислительной технике, предназначено для оценки качества потока равномерно распределенных случайных чисел и может быть использовано для повышения достоверности результатов вычислений при решении задач на ЭВМ методом вероятностного моделирования.

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

Известно, что в случайной последовательности из п двоичных цифр число 1 (или О) m с доверительной вероятностью 0,95 должно быть равно

m

0,5п ±0,5-1,96 гГ

или приближенно

m 0,5n ±- ЛГ

(Е.С.Венцель, Теория вероятностей. М.: Наука, 1969).

Число двоичных цифр п равно числу импульсов Опрос, по которым генератор вырабатывает О или 1. Поэтому, если иметь два счетчика, первый из которых подсчитывает число импульсов Опрос, а второй - число единиц в случайной последовательности, то можно вычитанием содержимого второго счетчика из уменьшенного в два раза содержимого первого счетчика определить их разность. Эта разность должна быть меньше п. Таким образом, старшие разряды сумматора должны всегда находиться в состоянии О (уменьшенное в два раза содержимое первого счетчика больше содержимого второго счетчика) или в состоянии 1 (уменьшенное в два раза содержимое первого счетчика меньше содержимого второго счетчика). Анализируя состояние старших разрядов сумматора, можно судить о правильности работы генератора случайных двоичных цифр. При конкретной реализации можно определить число разрядов в счетчиках и сумматоре. Например, если нужно контролировать генератор через каждые 500 тысяч случайных двоичных разрядов, то число разрядов счетчиков и сумматора должно быть не меньше 18. Число младших разрядов сумматора должно быть таким, чтобы на них пересчитать 707 единиц, т.е. равно 10. Контроль в этом случае

будет осуществляться за 8 старшими разрядами сумматора.

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

первый и второй счетчики, сумматор, первый и второй элементы И, группа элементов НЕ, элемент задержки, элемент ИЛИ-НЕ, элемент ИЛИ, первый вход которого является входом начального

5 запуска генератора и соединен с входами установки в ноль первого и второго счетчиков, сумматора и первого триггера, вход запуска генератора соединен с входом элемента задержки, вторым входом элемен0 та ИЛИ и счетным входом первого триггера, прямой выход которого соединен со счетным входом первого счетчика, разрядные выходы которого соединены с первым разрядным входом сумматора, второй разряд5 ный вход которого соединен с выходами элементов НЕ группы, входы которых соединены с разрядными выходами второго счетчика, счетный вход которого соединен с информационным выходом датчика случай0 ных цифр, выход элемента задержки соединен с входом синхронизации сумматора, единичные разрядные выходы старших разрядов которого соединены с входами первого элемента И, нулевые разрядные выходы

5 старших разрядов сумматора соединены с входами второго элемента И, выходы первого и второго элементов И соединены соответственно с первым и вторым входами элемента ИЛИ-НЕ, выход которого соеди0 нен .с входом установки в единицу второго

триггера, вход установки в ноль которого

соединен с выходом элемента ИЛИ, а выход

является выходом контроля генератора.

На чертеже представлена функциональ5 ная схема предложенного устройства.

Устройство содержит датчик случайных цифр 1, первый триггер 2, первый счетчик 3, второй счетчик 4, группу элементов НЕ 5, элемент задержки 6, сумматор 7, первый

0 элемент И 8, второй элемент И 9, элемент ИЛИ-НЕ 10, элемент ИЛИ 11, второй триггер 12, входы устройства 13 (запуск генератора) и 14 (начальный запуск генератора), выход схемы контроля 15 и ин5 формационный выход 16.

Предложенное устройство работает следующим образом,

При начальном запуске генератора по входу 14 устанавливаются в нулевое состояние первый триггер 2, первый 3 и второй 4

счетчики, сумматор 7 и через элемент ИЛИ 11 - второй триггер 12. Таким образом, схема готова к работе.

По импульсам запуска генератора по входу 13 на выходе датчика случайных цифр 1 вырабатываются уровни 1 или О случайного числа, которые поступают на выход устройства 16 и на вход второго счетчика единиц случайного числа 4, Единицы случайного числа подсчитываются на счетчике 4, Импульсы запуска генератора поступают также на первый триггер 2 и с его выхода - на вход первого счетчика 3, где и пересчитываются. Таким образом, на первом счетчике 3 имеется уменьшенное в два раза количество импульсов запуска генератора, а на счетчике 4 - количество единиц в случайной последовательности.

Импульсы запуска генератора через элемент задержки 6 поступают на вход син- хронизации сумматора 7. По этим импульсам происходит сложение содержимого первого счетчика 3 в прямом коде и содержимого второго счетчика 4 в обратном коде. Инвертирование содержимого второго счетчика 4 осуществляется на группе элементов НЕ 5.

В дальнейшем возможны три случая работы устройства,

Если содержимое счетчика 3 больше со- держимого счетчика 4 и их разрядность не превышает vn, то старшие разряды сумматора находятся в состоянии О. Высокие уровни с нулевых выходов старших разрядов сумматора поступают на вход первого элемента И 8. На выходе этого элемента будет высокий уровень, который поступает на первый вход элемента ИЛИ-НЕ 10. На второй элемент И 9 поступают низкие уровни с единичных выходов старших разрядов сумматора и на второй вход элемента ИЛИ- НЕ 10 поступает низкий уровень. На выходе элемента ИЛИ-НЕ 10 будет низкий уровень, и второй триггер 12 остается в состоянии нуля..

Если содержимое счетчика 3 меньше содержимого счетчика 4 и их разность не превышает Vn, то старшие разряды сумматора 7 находятся в состоянии 1. Тогда низкие уровни с нулевых выходов старших разря- дов сумматора поступают на первый элемент И 8, выход которого в виде низкого уровня поступает на первый вход элемента ИЛИ-НЕ 10. На втором входе элемента ИЛИ-НЕ 10 будет высокий уровень, так как на второй элемент И 9 поступают высокие уровни с единичных выходов старших разрядов сумматора. На выходе элемента ИЛИ-НЕ 10 будет также низкий уровень, и

второй триггер 12 останется в состоянии нуля.

Если же разность содержимого счетчика 3 и счегчика 4 больше м, то старшие разряды сумматора не будут все находиться в состоянии нуля или единицы. На выхЬдй- элементов 8 и 9 будут низкие уровни, а на выходе элемента ИЛИ-НЕ 10 будет высокий уровень, устанавливающий в единичное состояние второй триггер 12, высокий уровень с которого поступает на выход устройства 15, как признак того, что произошло отклонение от равновероятного закона. Однако единичные отклонения от равновероятного закона еще не говорят о плохой работе генератора, и формирование случайных цифр продолжается. Первый пришедший импульс запуска генератора через схему ИЛИ устанавливает в О второй триггер 12. В случае подключения данного генератора к ЭВМ в машине должна быть специальная программа, которая подсчитывает число отклонений от равномерного закона и,если частота их появления зайдет за пределы доверительной вероятности,, то на печатающее устройство ЭВМ выдается информация о неисправности генератора случайных двоичных цифр, а результаты решения задачи с использованием этих случайных цифр неверны.

Формула изобретения Генератор двоичных случайных цифр, содержащий датчик случайных цифр, вход запуска которого является входом запуска генератора, а информационный выход соединен с информационным выходом генератора, отличающийся тем, что, с целью расширения функциональных возможностей за счет фиксации частоты появления нулей и единиц в генерируемой последовательности цифр, в него введены первый и второй триггеры, первый и второй счетчики, сумматор, первый и второй элементы И, группа элементов НЕ, элемент задержки, элемент ИЛИ-НЕ, элемент ИЛИ, первый вход которого является входом начального запуска генератора и соединен с входами установки в О первого и второго счетчиков, сумматора и первого триггера, вход запуска генератора соединен с входом элемента задержки, вторым входом элемента ИЛИ и счетным входом первого триггера, прямой выход которого соединен со счетным входом первого счетчика, разрядные выходы которого соединены с первым разрядным входом сумматора, второй разрядный вход которого соединен с выходами элементов НЕ группы, входы которых соединены с разрядными выходами второго счетчика, счетный вход которого соединен с информационным выходом датчика случайных цифр, выход элемента задержки соединен с входом синхронизации сумматора, единичные разрядные выходы старших разрядов которого соединены с входами первого элемента И, нулевые разрядные выходы старших разрядов сумматорй соединены с входами

второго элемента И, выходы первого и второго элементов И соединены соответственно с первым и вторым входами элемента ИЛИ-НЕ, выход которого соединен с входом установки в 1 второго триггера, вход установки в О которого соединен с выходом элемента ИЛИ, а выход является выходом контроля генератора.

Изобретение относится к вычислительной технике. Цель изобретения - расширение Функциональных возможностей за счет фиксации частоты появления нулей и единиц в генерируемой последовательности цифр, что позволяет производить оператив-. ную оценку работоспособности генератора двоичных случайных цифр при использовании его для решения зйдач на ЭВМ. Генератор содержит датчик случайных цифр 1,. триггеры 2,12, счетчики 3,4, группу элементов НЕ 5, элемент задержки 6, элементы И 8, 9, сумматор 7, элемент ИЛИ-НЕ 10 и элемент ИЛИ 11. 1 Ил.