Генератор потоков случайных событий Советский патент 1981 года по МПК G06F1/02 G07C15/00 

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

I

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

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

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

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

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

ментов ИЛИ, блок формирования первичных импульсных потоков и наборное поле 2.

Недостатком известного устройства является его сравнительная сложность из-за

наличия генераторов первичных импульсных потоков и больщого числа логических элементов, что, в частности, затрудняет выполнение таких устройств в виде интегральных микросхем. Наиболее близким к предлагаемому является генератор потоков случайных событий, который содержит (n-f 1) первичных источников случайного потока импульсов, соединенных с (п + 1)-ым формирователем импульсов, п из которых подключены через счетные триггеры и многовходовые элементы И к входам элемента ИЛИ, выход которого соединен с выходом устройства и входом генератора функций, выходы которого и выход (п + 1)-го формирователя импульсов также подключен к соответствующим входам многовходовых элементов И 3. Недостатком устройства является сложность из-за наличия (п + 1)-го источника потоков случайных импульсов, что, в частности, затрудняет реализацию генератора в интегральном исполнении на базе цифровых элементов. Цель изобретения - упрощение устройства генератора потоков случайных событий и повышение точности его работы. Для достижения поставленной цели в известный генератор импульсов, содержащий датчик импульсов, выход которого соединен с первым входом циклического регистра сдвига, первый выход которого соединен с первым входом многовходового элемента И, второй вход которого соединен с выходом равновероятностного элемента, а выход многовходового элемента И соединен с первым входом первого элемента ИЛИ, выход которого является первым выходом генератора, снабжен первым, вторым и третьим двухвходовыми и трехвходовыми элементами И, первым, вторым и третьим триггерами, вторым и третьим элементами ИЛИ, счетчиком и блоком выходных ключей, выход которого соединен с вторым выходом генератора, первый вход - с выходом первого элемента ИЛИ, а второй вход - с первым выходом счетчика, второй выход которого подключен к первым входам первого триггера и второго двухвходового элемента И, третий выход - к первым входам второго триггера, первого и третьего двух ходового элемента И и третьего элемента ИЛИ, а первый вход счетчика подключен к выходу датчика импульсов, к третьему входу многовходового элемента Ник первому входу трехвходового элемента И, второй вход которого соединен с вторым выходом циклического регистра сдвига, третий вход - с выходом равновероятностного элемента, а выход - с вторым входом первого триггера и первым входом второго элемента ИЛИ, выход которого подключен к первому входу датчика импульсов, а второй вход - к второму входу второго триггера и выходу многовходового элемента И, четвертый вход которого соединен с выходом первого триггера, а пятый вход - с выходом второго триггера, вторым входом второго двухвходового элемента И и вторым входом первого двухвходового элемента И, выход которого подключен к второму входу первого элемента ИЛИ, а выход второго двухвходового элемента И соединен с вторым входом третьего элемента ИЛИ, выход которого подключен к второму входу датчика импульсов, третий вход которого соединен с третьим выходом генератора и с выходом третьего двухвходового элемента И, второй вход которого подключен к выходу третьего триггера, второй вход которого соединен с первым выходом циклического регистра сдвига, а первый вход - с третьими входами первого и второго триггеров, вторцм входом счетчика, четвертым входом датчика импульсов и с первым входом генератора потоков случайных событий, второй вход которого подключен к второму входу циклического регистра сдвига. На чертеже изображена структурная схема предлагаемого устройства. Генератор содержит датчик 1 импульсов, циклический регистр 2 сдвига, многовходовый элемент И 3, первый элемент ИЛИ 4, равновероятностный элемент 5, блок 6 выходных ключей, счетчик 7, первый триггер 8, первый двухвходовой элемент И 9, второй триггер 10, трехвходовый элемент И 11, второй элемент ИЛИ 12, второй двухвходовый элемент И 13, третий элемент ИЛИ 14, третий триггер 15 и третий двухвходовый элемент И 16. Датчик 1 импульсов, циклический регистр 2 сдвига, многовходовый элемент И 3, первый элемент ИЛИ 4 и блок 6 выходных вентилей соединены последовательно, причем выход блока 6 выходных ключей соединен со вторым выходом генератора, а второй вход - с первым выходом счетЧика 7, второй выход которого подключен к первым входам первого триггера 8 и второго двухвходового элемента И 13, третий выход - к первым входам второго триггера 10, первого двухвходового элемента И 9 и третьего элемента ИЛИ 14, а первый вход - к выходу датчика 1 импульсов, к третьему входу многовходового элемента И 3 и к первому входу трехвходового элемента И 11, второй вход которого соединен с вторым выходом циклического регистра 2 сдвига, третий входс выходом равновероятностного элемента 5, а выход - с вторым входом первого триггера 8 и первым входом второго элемента ИЛИ 12, выход которого подключен к первому входу датчика 1 импульсов, а второй вход - к второму входу второго триггера 10 и выходу многовходового .элемента И 3, второй вход которого соединен с выходом равновероятностного элемента 5, четвертый вход - с выходом первого триггера 8, а пятый вход - с выходом второго триггера ю, вторым входом второго-двухвходового элемента И 13 и вторым входом первого двухвходового элемента И 9, выход которого подключен к второму входу первого элемента ИЛИ 14, а выход второго двухвходового элемента И 13 соединен с вторым входом третьего элемента ИЛИ 14, выход которого подключен к третьему выходу генератора и выходу третьего двухвходового элемента И 16, первый вход которого подключен к третьему выходу счетчика 7, а второй вход - к выходу третьего триггера 15, второй вход которого соединен с первым выходом циклического регистра 2 сдвига, а первый вход - с третьими входами первого триггера 8 и второго триггера 10, вторым входом счетчика 7, четвертым входом датчика -1 импульсов и с первым входом генератора потоков случайных событий, второй вход которого подключен к второму входу циклического регистра 2 сдвига, а первый выход - к выходу первого элемента ИЛИ 4.

Датчик 1 импульсов служит для обеспечения импульсного режима работы устройства. Циклический регистр 2 сдвига предназначен для хранения и выдачи по сигналу от датчика 1 импульсов кодов, управляющих прохождением импульсов либо через многоходовый элемент И 3, либо через трехвходовый элемент И 11. Многовходовый элемент И 3 обеспечивает управление прохождением импульсов с выхода датчика 1 импульсов на вход первого элемента ИЛИ 4, который служит для объединения импульсных потоков с выходом многовходового и первого двухвходового элементов И 3 и И 9. Блок выходных вентилей предназначен для выдачи по сигналу от первого элeмeнta ИЛИ 4 случайного числа на выход генератора потоков случайных событий. Счетчик 7 формирует случайное число, а также служит для организации управления режимом работы датчика 1 импульсов первый триггер 8 управляет прохождением импульсов через многовходовый элемент И 3. Первый двухвходовый элемент И 9 обеспечивает прохождение импульсов с третьего выхода счетчика 7 на вход первого элемента ИЛИ 4 при наличии разрешающего сигнала с выхода второго триггера 10, который управляет прохождением импульсов через многовходовый элемент И 3, первый двухвходовый элемент И 9 и второй двухвходовый элемент И 13. Трехвходовый элемент И 11 служит для организации управления режимом работы датчика 1 импульсов и задает состояние первого триггера 8. Второй элемент ИЛИ 12 предназначен для объединения импульсных потоков с выходом многовходового элемента И 3 и трехвходового элемента И 11 и заДания быстрого режима работы датчика 1 импульсов. Третий элемент ИЛИ 14 предназначен для объединения импульсных потоков с третьего выхода счетчика 7 и выхода второго двухвходового элемента И 13 и задания номинального режима работы датчика 1 импульсов. Третий триггер 15 предназначен для повышения достоверности работы устройства. Третий двухвходовый элемент

И 16 служит для повышения достоверности работы устройства.

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

В номинальном режиме работы импульс с выхода датчика 1 импульсов поступает на вход циклического регистра 2 сдвига, сигнал на выходе которого может принимать ,1 6(0,).

Если сигналы на первом выходе циклического регистра 2 сдвига и на выходе равновероятностного элемента 5 принимают значения «О, импульс с выхода датчика 1 импульсов не проходит ни через многовходовый элемент И 3, ни через трехвходовый элемент И 11. Следующий импульс приводит к появлению на выходе циклического регистра 2 сдвига нового сигналаа;,И€ (0,1).

Если сигнал на первом выходе циклического регистра 2 сдвига принимает значение «О, а на выходе равновероятностного элемента 5 устанавливается состояние «1, импульс с выхода датчика 1 импульсов проходит через трехвходовый элемент И 11, устанавливает первый триггер 8 в состояние, запрещающее прохождение импульсов через многовходовый элемент И 3, и через второй элемент ИЛИ 12 задает «быстрый режим работы датчика 1 импульсов, так как для дальнейшего проведения испытаний необходимо, чтобы на выходе циклического регистра 2 сдвига установилась следующая группа кодов ti+. В «быстром режиме работы, как и в номинальном режиме, на выходе циклического регистра 2 сдвига последовательно появляются коды dtj ,OLij4l

di. Однако прохождение импульса через многовходовый элемент И 3 на выход устройства невозможно, так как на четвертом входе многовходового элемента И 3 постоянно присутствует запрещающий сигнал с выхода первого триггера 8. В таком режиме генератор работает до тех пор, пока не выбираются все коды i-ой группы, т. е. все кодыа{. . .

Как в «быстром, так и в номинальном режимах работы импульсы с выхода датчика 1 импульсов поступают на первый вход счетчика 7. Когда в счетчике 7 зафиксируется число, равное количеству кодов в группе, на втором выходе счетчика 7 появляется сигнал, устанавливающий первый триггер 8 в состояние, разрешающее прохождение импульсов через многовходовый элемент И 3. Так как второй триггер 10 находится в разрешающем состоянии, то сигнал с второго выхода счетчика 7 проходит через второй двухвходовый элемент И 13 и элемент ИЛИ 14, поступает на второй вход датчика Д импульсов и задает номинальный режим его работы, после чего испытания продолжаются в номинальном режиме для (i + 1)-ой группы кодов, т. е. а.{.|...

Если сигналы на первом выходе циклического регистра 2 сдвига и на выходе равновероятностного элемента 5 принимают значения «1, импульс с выхода датчика 1 импульсов проходит через многовходовый элемент И 3 и первый элемент ИЛИ 4 в блок 6 выходных вентилей и на первый выход генератора. Появление импульса в блоке 6 выходных вентилей приводит к тому, что случайное число с первого выхода счетчика 7 (код старших разрядов) поступает на второй выход генератора потоков; случайных событий. Импульс с выхода многовходового элемента И 3 поступает также на второй вход второго триггера 10 и устанавливает его в состояние, запрещающее прохождение импульсов через многовходовый элемент И 3 и первый двухвходовый элемент И 9. Этот же импульс поступает на второй вход второго элемента ИЛИ 12, проходит через него и задает «быстрый режим работы датчика 1 импульсов. В таком режиме датчик 1 должен работать до тех пор, пока на выходе циклического регистра сдвига снова не устанавливается первый из начальной группы кодов о.,., . Это. обеспечивается тем, что, импульс, задающий номинальный режим работы, не может пройти со второго выхода счетчика 7 через второй двухвходовый элемент И 13, так как второй триггер 10 находится в состоянии запрета. Только когда в счетчике 7 зафиксируется число, соответствующее общему количеству кодов в группах, на третьем выходе счетчика 7 появляется импульс, задающий номинальный режим работы через третий элемент ИЛИ 14, и устанавливающий второй триггер 10 в разрещающее состояние. В случае, если до конца цикла импульс не появляется на выходе многовходового элемента И 3, то импульс с третьего выхода счетчика 7 проходит через первый двухвходовый эле.мент И 9 и первый элемент ИЛИ 4 в блок 6 выходных вентилей и на первый выход генератора, а случайное число с первого выхода счетчика 7 появляется па втором выходе генератора. Для повыщения достоверности работы устройство снабжено третьим триггером 15. Перед началом работы генератора на первый вход подается сигнал, устанавливающий счетчик 7, первый 8, второй 10 и третий 15 триггеры в исходное состояние, а датчик 1 импульсов - в состояние, позволяющее производить запись информации в циклический регистр 2 сдвига через второй вход генератора. В процессе функционирования сигналы с первого выхода циклического регистра 2 сдвига поступают на второй вход третьего триггера 15. При заранее известной совокупности кодов это позволяет ко.нтролировать исправность работы устройства, запи: сывая в последний разряд циклического регистра 2 сдвига ноль или единицу, дополняя всю кодовую последовательность, хранящуюся в этом регистре, до четной. Третий триггер 15 работает в счетном режиме и при нормальном функционировании циклического регистра 2 сдвига всегда устанавливается в одно и то же, например нулевое состояние, после чего, содержимое этого регистра при формировании случайной величи,цы сдвигается на длину регистра и снова занимает начальное размещение. Тогда при единичном состоянии третьего триггера 15 импульс с третьего выхода счетчика 7 (после окончания полного цикла сдвига) проходит черезтретий двухвходовый элемент И 16 и поступает на третий выход устройства и третий вход датчика 1 имрульсов. Этот сигнал останавливает ра датчика 1 импульсов и позволяет обеспечить быстрое обнаружение неисправности и восстановление информации в циклическом регистре 2 сдвига, что повыщает надежность и достоверность работы генератора, особенно с учетом слабо выраженной чувствительности случайных потоков событий к редким сбоям. При записи информации в циклический регистра 2 сдвига могут быть использова„ы различные способы кодирования. Так, например, будем считать, что коды А {af,aj,.,.,,c(} вычисляются по известной функции распределения ,..iPm} по формулеР . (1) Величины О.; представляются группой двоичных символов ai a,ai.i,.-.,ain.} (2) где величина О.- равна .rJ(3), Если код (2) считывать для участия в случайном испытании поэлементно, начиная со старщего разряда о. , затема|. (если испытание было неудачным) и т. д., то за счет последовательного появления сигналов di {ОД} на выходе циклического регистра 2 сдвига удается с помощью многовходового элемента И 3 и трехвходового элемента И 1 обеспечить правильную работу генератора с использованием единственного равновероятностного элемента, а это значительно упрощает техническую реализацию устройства, так как вероятностные выражении (3) формируются автоматически по условию последовательных испытаний. Технико-экономическая эффективность генератора потоков случайных событий определяется следующими факторами: а) упрощением логической структуры устройства, что позволяет применить в качестве элементов памяти и кодирования циклический (кольцевой) регистр сдвига и счетчик, и не включать, в отличие от известных устройств,, таким сложные блоки, как

блок управления и особенно, блок адресации;

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

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

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

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

второго двухвходового элемента И и вторым входом первого двухвходового элемента И, выход которого подключен к второму входу первого элемента ИЛИ, а выход второго двухвходового элемента И соединен с вторым входом третьего элемента ИЛИ, выход

которого подключен к второму входу датчика импульсов, третий вход которого соединен с третьим выходом генератора и с выходом третьего двухвходового элемента И второй вход которого подключен к выходу третьего триггера, второй вход которого соединен с первым выходом циклического регистра сдвига, а первый вход - с третьи ми входами первого и второго триггеров вторым входом счетчика, четвертым входом датчика импульсов и с первым входом генератора потоков случайных событий, второй вход которого подключен к второму входу циклического регистра сдвига. Источники информации, принятые во внимание при экспертизе 1.Авторское свидетельство СССР № 557481, кл. G 06 F 1/02, 1975. 2.Авторское свидетельство СССР № 341156, кл. G 06 F 1/02, 1970. 3.Авторское свидетельство СССР № 551653, кл. G 06 F 1/02, 1975 (прототип) .