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

(54) ГЕНЕРАТОР СЛУЧАЙНЫХ ЧИСЕЛ

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

Известно устройство, содержащее генератор шума, ключ, блок дифференцирования, анализатор знака и RS-триггер с установочными R и S входами. В генераторе напряжение шума через ключ и блок дифференцирования поступает на вход анализатора знака, поочередно формирующего сигналы на двух выходах. Выходные сигналы анализатора подаются на установочные входы триггера, переключая егослучайным образом в состояния логической 1 или О.

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

1 Недостатком генератора является

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

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

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

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

В этом устройстве случайные числа, вырабатываемые датчиком случайных чисел, распределенных по равно20мерному закону, сравниваются с числами узловых точек заданной функции распределения, определяется граница между возбужденными и невозбужденными частями выходов блока срав25нения и затем возбуждаются соответствующие выходные элементы выходного блока, определяющие в результате участок функции распределения, в пределс1Х которого оказалось в данный 30 момент времени случайное число, распределенное по равномерному закону. На выходе выходного блока получаются случайные числа,- соответствукядие заданной функции распределения. Однако числа, вырабатываемые датчиком случайных чисел, могут повторяться в некоторых смежных комбинациях, при этом также будут повторять ся случайные числа на )зыхрде устройс ва. Наиболее близким техническим реше нием к изобретению является генерато случайного процесса,содержащий управляемые датчики потоков случайных и мпульсов, количество которых равно числу состояний выходной цепи,группу элементов И, шифратор, регистр памяти, элемент. ИЛИ, блок задания длительности испытания, блок управления, регистр адреса и блоки памяти, причем каждый датчик потоков включает соединенные последовательно генератор случайных импульсов, вероятностный многополюсник с импульсами выходов, группу элементов Ии эле мент ИЛИ. . Работа генератора основана на проведении исследовательских случайных испытаний одновременного отпирания элементов И группы с последующей фиксацией номера элемента И группы, через -который прошёл первый с момента началаиспытания импульс датчиков потоков. Содержащаяся в генераторе обратная связь о выхода генератора на управляющие входы датчиков потоков через блок управления, регистр адреса и блоки памяти обеспечивает управление вероятностными : характеристиками выходных случайных чисел и исключает повторение чисел в смежных циклах. Таким образом,для устранения повторения- смежных чисел используется принцип, заключающийся в определении номера управляемого датчика случайных импульсов, сработавшего первым в данном цикле испытаний, и в выключении этого датчика в,последующем цикле формирования слу чайных чисел.,Для реализации такого принципа требуются управляемые датчики случайных импульсов и блоки памяти в количестве, равном числу допустимых выходных кодовых комбинаций, а также такие составляющие, как шифратор, блок управления и регистр адреса З. Недостатком генератора является сложность и невысокая надежность ь: вследствие применения большого числа управляемых датчиков случайных импул сов и блоков памяти, а также наличия таких составляющ11х, содержащих большое количество электррэлементрв, как шифратор, блок управления и регистр адреса. Цель изобретения - упрощение и повышение надежности генератора. Цель дootиj aeтcя тем, что в генератор случайныхчисел, содержащий генератор тактовых импульсов, генератор случайных.импульсов, блок элементов И, введены два элемента И-НЕ, элемент ИЛИ-НЕ, два счетчика, дешифратор и RS-триггер, R-вход которого является входом генератора, выход генератора тактовых импульсов соединен с первым входом первого элемента И-НЕ и с синхронизирующим входом дешифратора, выход которого соединен с S-входом К5-триггера,0выход которого соединен с вторым входом первого элемента И-НЕ, выход которого соединен с первым входом, элемента ИЛИ-НЕ и со счетным входом первого счетчика, кодовыйвыход которого соединен с информационным входом блока элементов И, выход KQ Tofspro является выходом генератора, вь1хЬд генератора случайных импульсов соединен с первым входом второго элемента И-НЕ, выход которого- соединен со вторым входом элемента ИЛИ-НЕ, выход.которого соединен со счетным, входом второго счетчика, кодовый выход которого соединен с информа- . ционным входом дешифратора,g -выход ЙЗ-триггера соединен со вторым входом второго элемента И-НЕ и с управляющим входом блока элементов И. Сущность работы генератора заключается в том., что в каждый период работы генератора сначала формируют вспомогательное случайное равновероятное число, которое может принимать все значения, например от О до А-1, а затем суммируют его, прибавляя при этом единицу, по модулю А+1, с выходным числом генератора, :сформированным в предшествующий период его работы, и результат суммирования выдают на выход, для чего в генератор введены два счетчика импульсов, дешифратор и RS-триггер с их связями. В результате генерируются случайно равновероятные числа, которые могут принимать все значения от О до А без повторения в смежных периодах. На чертеже представлена функциональная схема устройства. ГенераторJслучайных чисел содержит генератор 1 случайных импульсов, элементы 2 И-НЕ, 3 ИЛИ-НЕ, счетчик 4, дешифратор 5, RS-триггер 6, генератор 7 тактовых импульсов, элемент 8 И-НЕ, счетчик 9, блок 10 элементов И. Счетчик 4 осуществляет счет по модулю Л, счетчик 9 по модулю А4-1. Работа генератора случайных чисел заключается в,следующем. В исходном состоянии до поступления на вход генератора .импульса запуска RS-триггер 6 находится в первом состоянии, при котором эл.емент.

8 И-НЕ выключен, а элемент 2 И-НЕ и выходной коммутатор 10 включены. Импульсы генератора 7 на входы счетчиков 4 и 9 не поступают, счетчик 9 находится в статическом состоянии, и сигнал с выходов исех его разрядов в виде комбинации логических О и 1 кодирующий двоичные числа от О до определенного значения А, поступает через блок 10 элементов И на выход генератора.

Генератор 1 случайных импульсов непрерывно выдает последовательность импульсов со случайным периодом сле.дования. Элемент 2 И-НЕ сигналом, поступающим с RS-триггера 6, включен и импульсы с выхода генератора 1 че,jpe3 элементы 3 ИЛИ-НЕ и 2 И-НЕ постулают на счетный вход счетчика 4 импульсов, с помощью которого осуществляется подсчет числа слу- . чайных импульсов по модулю А. За ; достаточно большой интервал времени в счетчике 4 формируются коды случай ных равновероятных чисел, которые могут принимать все значения от О до А-1.

При поступлении импульса запуска триггер б переключается во второе состояние, при котором элемент 2 И-НЕ выключен, а элемент 8 И-НЕ включен, и счетные входы счетчиков 4 и 9 импульсов подключаются к выходу генератора 7 тактовых импульсов. Кроме того, при переключении триггера б на время формированИя в счетчике 9 очередной выходной кодовой комбинации выключается блок 10 элементов И. В счетчике 4 будет записан код двоичного случайного равновероятного числа в пределах от О до А-1.

Счетчики 4 и 9 импульсов могут изменять свои состояния при одинаковых, например отрицательных, перепадах их входных сигналов, причем на вход счетчика 9 тактовые импульсы поступают с выхода элемента 8 И-Н непосредственно, а на вход счетчика 4 - через элемент 3 ИЛИ-НЕ, поэтому счетчики срабатывают в разные полупериоды тактовы импульсов. В счетчик 9 записывается логическая 1 каждый раз при переключении триггера 6 после поступления запускающего импульса в первый полупериод тактовых импульсов.

Кроме того, на вход этого счетчика поступят счетные импульсы с генератора 7 тактовых импульсов, количество которых равно числу, записанному в счетчике 4 в момент прихода запускающего импульса, которое может быть в пределах от О до А-1. Для этого при установке в процессе счета тактовых импульсов нулевого кода в счетчике 4 в следующем полутакте с помощью дешифратора 5 нулевого кода, синхронизированного тактовБоми импульсами генератора 7, вырабатывается сигнёш во втором полутакте тактовых импульсов, переключающий RS-триггер б в первое состояние и прекращающий поступление счетных 5 импульсов на вход счетчика 9 импульсов.

Устройство переходит в исходное состояние.

Блок 10 включается, и новая кодо0 вая комбинация со счетчика 9 выдается на выход генератора. Таким обра.зом, новое число устанавливается на выходе генератора1 через некоторое время At Со,5 + аи)- Т после за5 пускающего импульса, где aj, - число, устанавливающееся в счетчике 4 при поступлении запускающего импульса в рассматриваег-ый п-период работы генератора (п 0, 1, 2,... , Т-пери01 од тактовых импульсов. Это новое .число равно сумме по модулю А-И числа, сформированного в предшествующий п - 1 период, которое может принимать все значения от О до А,

5 числа а, которое может принимать все значения от О до А-1, и 1. Поэтому вновь сформированное число не может быть равно предшествукяцему числу...

Q Действительно, эти смежные числа могут повториться, если к первому из них по модулю А+1 прибавить О или А+1, а так как в генераторе каждый раз добавляются случайные числа, принимающие значения только от 1 до А, то повторение смежных чисел исключается.

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

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

0 повторения в смежных периодах.

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

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

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

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

; Генератор случайных чисел, содер5 жащий генератор тактовых импульсов.

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

пульсов соединен с первым входбм второго элементаИ-НЕ, выход которого соединен с вторым входом элемента ИЛИ-НЕ, выход которого соединен со счетным входом второго счет5 чика, кодовый выход которого соединен с ин;$ормационным входом дешифратора, G-ВЫХОД RS-триггера соединен с вторым входом второго элемента И-НЕ и с управляющим входом бло10 ка элементов И.

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

3.Авторское свидетельство СССР 744532,кл.С Об F 7/58, 1978 (прото20 тип;.