Генератор случайных чисел

Генератор случайных чисел

Иллюстрации

Показать все

Реферат

 

ОП ИСАНИЕ

ИЗОБРЕТЕНИЯ

К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ

Союз Советских

Социалистических

Республик

Опубликовано 230183. Бюллетень HP 3

Р М К з

G 06 Р 7/58

Государственный комитет

СССР по делам изобретений и открытий (53) УДК 681. 325 (088.8) Дата опубликования описания 23.01.83 (72) Авторы изобретения

Н.Н.Егоров и В.К.Моисеев (71) Заявитель (54) ГЕНЕРАТОР СЛУЧАЙНЫХ ЧИСЕЛ

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

Известно устройство, содержащее генератор шума, ключ, блок дифференцирования, анализатор э нака и BS-триг- гер с установочными В и Б входами.

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

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

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

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

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

r пределенное по равномерному закону. !

На выходе выходного блока получаются; случайные числа; соответствующие заданнойй функции распределения.

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

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

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

Работа генератора основана на проведении исследовательских случайных испытаний одновременного отпирания элементов И группы с последующей фиксацией номера элемента И группы, через который прошел первый с момента начала испытания импульс датчиков потоков. Содержащаяся в генераторе обратная связь о выхода генератора на управляющие входы датчиков потоков через блок управления, 350 регистр адреса и блоки памяти обеспечивает управление вероятностными характеристиками выходных случайных чисел и исключает повторение чисел в смежных циклах. Таким образом,для 4Q устранения повторения смежных чисел используется принцип, заключающийся в определении номера управляемого датчика случайных импульсов, сработавшего первым в данном цикле испытаний, и в выключении этого датчика в.последующем цикле формирования случайных чисел. Для реализации такого принципа требуются управляемые датчйки случайных импульсов и блоки памяти в количестве, равном числу допустимых выходных кодовых комбинаций, а также такие составляющие, как шифратор, блок управления и регистр адреса (3).

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

Цель. изобретения †. упрощение и повышение надежности генератора. 65

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

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

ЙЯ-триггера соединенсо вторым входом второго элемента И-НЕ и с управляющим входом блока элементов И.

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

A+1, с выходным числом генератора, .сформированным в предшествующий период его работы, и результат суммирования выдают на выход, для чего в генератор введены два счетчика импульсов, дешифратор и RS-триггер с их связями.

В результате генерируются случайно равновероятные числа, которые Ivloгут принимать все значения от 0 до

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

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

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

4, дешифратор 5, RS-триггер б, генератор 7 тактовых импульсов, элемент 8 И-НЕ, счетчик 9, блок 10 элементов И. Счетчик 4 осуществляет счет по модулю А, счетчик 9 по модулю A+1.

Работа генератора случайных чисел заключается в следующем.

B исходном состоянии до поступления на вход генератора .импульса эаПуска RS-триггер б находится в первом состоянии, при котором элемент

991422

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

8 И-НЕ выключен, а элемент 2 И-ИЕ

H выходной коммутатор 10 включены.

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

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

4 импульсов, с помощью которого осуществляется подсчет числа случайных импульсов по модулю A. За достаточно большой интервал времени в счетчике 4 формируются коды случай. ных равновероятных чисел, которые могут принимать все значения от О до А-1.

При поступлении импульса запуска триггер 6 переключается во второе состояние, при котором элемент

2 И-НЕ выключен, а элемент 8 И-НЕ включен, и счетные входы счетчиков

4 и 9 импульсов подключаются к выходу генератора 7 тактовых импульсов.

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

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

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

Для этого при установке в процессе счета тактовых импульсов нулевого кода в счетчике 4 в следующем полутак е с помощью дешифратора 5 нулевого кода, синхронизированного тактовыми импульсами генератора 7,-вырабатывается сигнал во втором полутакте тактовых импульсов, переключающий ВБ-триггер 6 в первое состояние и прекращающий поступление счетных

5 импульсов на вход счетчика 9 импульсов.

Устройство переходит в исходное состояние. . Блок 10 включается, и новая кодо10 вая комбинация со счетчика 9 выдается на выход генератора. Таким образом, новое число устанавливается на выходе генератора через некоторое время at = (0,5 + à g).. Т после за 5 пускающего импульса, где а - число, устанавливающееся в счетчике 4 при поступлении запускающего импульса в рассматриваеьый и-период работы ге:нератора (и = О, 1, 2,..., Т-пери)од тактовых импульсов. Это новое ,число равно сумме по модулю A+1 числа, сформированного в предшествую щий и — 1 период, которое может принимать все значения от О до А, числа а, которое может принимать все значения от О до A-1, и 1 ° Поэтому вновь сформированное число не может быть равно предшествующему числу.

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

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

Ф

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

Экспериментальная проверка генератора случайных чисел подтвердила правильность найденного технического решения. Расчеты, проведенные сов местно с отделом надежности предприятия — заявителя для случая формирования 6 различных двоичных комбинаций, дали следукщий результат: надежность повьыается не менее чем в

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

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

ixoP

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

Редактор С. Патрушева ТехредТ.Фанта Корректор A. дзятко

Тираж 704 . Подписное

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

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

Эаказ 135/67

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

И-HE элемент ИЛИ.-НЕ, два счетчика, дешифратор и RS-триггер,. R-вход которого является входом генератора, выход генератора тактовых импульсов соединен с первым входом первого элемента И-НЕ с синхронизирующим входом дешифратора, выход которого соединен с S-. âõîäîì RS-триггера, g -выход. которого соединен с вторым входом первого элемента И-НЕ, выход которого соединен с первым входом элемента ИЛИ-НЕ и со счетным входом первого счетчика, кодовый выход которого соединен с информационным входом блока элементов И, выход которого является выходом генератора, выход генератора случайных им--, пульсов соединен с первым вход6м второго элемента И-НЕ, выход которого соединен с вторым входом элемента ИЛИ-НЕ, выход которого соединен со счетным входом второго счетчика, кодовый выход которого соединен с информационным входом дешифратора, 8-выход RS"òðèããåðà соединен с вторым входом второго элемента И-НЕ и с управляющим входом бло10 ка элементов И.

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

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

jg 9 697990, кл. G 06 F 7/58, 1978.

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

Р 744533, кл. G 06 F 7/58, 1978.

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

0744532,кл.С 06 F 7/58, 1978 (прото20 тип)»