Генератор потоков случайных событий

 

ОПИСАНИЕ

ИЗОБРЕТЕН ИЯ

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

Союз Советриии

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

Республик (ii) 824178 (61) Дополнительное к авт. свид-ву— (22) Заявлено 20.06.79 (21) 2787511/18-24 (51) М. Кл.з

G 06 F 1/02 б 07 С 15/00 (53) УДК 681,325 с присоединением заявки №вЂ”

Гооударстееилмк комитет (23) Приоритет—

Опубликовано 23.04.81. Бюллетень № 15

Дата опубликования описания 04.05.81

IIo делам иаобретеиий и открытий (088.8) Э. А. Бвквиович, М. A. Орлов и Л. А. Смч риовв,.""., (Минский радиотехнический институ г" : = .:. .. (72) Авторы изобретения (71) Заявитель (54) ГЕНЕРАТОР ПОТОКОВ СЛУЧАЙНЫХ СОБЫТИЙ

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

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

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

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

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

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

824178

10

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

И к входам элемента ИЛИ, выход которого соединен с выходом устройства и входом генератора функций, выходы которого и выход (и + 1)-ro формирователя импульсов также подключен к соответствующим входам многовходовых элементов И (31.

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

Цель изобретения — упрощение устройства генератора потоков случайных со бытий и повышение точности его работы.

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

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

25 зо

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

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

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

Генератор содержит датчик 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, а пятый вход — с выходом второго триггера

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

И 16, первый вход которого подключен к третьему выходу счетчика 7, а второй вход— к выходу третьего триггера 15, второй вход которого соединен с первым выходом циклического регистра 2 сдвига, а первый вход— с третьими входами первого триггера 8 и второго триггера 10, вторым входом счетчика 7, четвертым входом датчика -1 импульсов и с первым входом генератора потоков случайных событий, второй вход которого подключен к второму входу циклического регистра 2 сдвига, а первый выход— к выходу первого элемента ИЛИ 4.

Датчик 1 импульсов служит для обеспечения импульсного режима работы устройства. Циклический регистр 2 сдвига предназначен для хранения и выдачи по сигналу от датчика 1 импульсов кодов, управляющих прохождением импульсов либо через многоходовый элемент И 3, либо через трехвходовый элемент И 11. Многовходовый элемент И 3 обеспечивает управление прохождением импульсов с выхода датчика 1 импульсов на вход первого элемента ИЛИ 4, который служит для объединения импульсных потоков с выходом многовходового и первого двухвходового элементов И 3 и И 9.

Блок выходных вентилей предназначен для выдачи по сигналу от первого элемента ИЛИ

4 случайного числа на выход генератора потоков случайных событий. Счетчик 7 формирует случайное число, а также служит для организации управления режимом работы датчика 1 импульсов первый триггер 8 управляет прохождением импульсов через многовходовый элемент И 3. Первый двухвходовый элемент И 9 обеспечивает прохождение импульсов с третьего выхода счетчика 7 на вход первого элемента ИЛИ 4 при наличии разрешающего сигнала с выхода второго триггера 10, который управляет прохождением импульсов через многовходовый элемент И 3, первый двухвходовый элемент

И 9 и второй двухвходовый элемент И 13.

Трехвходовый элемент И 11 служит для организации управления режимом работы датчика 1 импульсов и задает состояние первого триггера 8. Второй элемент ИЛИ 12 предназначен для объединения импульсных потоков с выходом многовходового элемента

И 3 и трехвходового элемента И 11 и за1 ания быстрого режима работы датчика 1 импульсов. Третий элемент ИЛИ 14 предназначен для объединения импульсных потоков с третьего выхода счетчика 7 и выхода второго двухвходового элемента И 13 и задания номинального режима работы датчика

1 импульсов. Третий триггер 15 предназначен для повышения достоверности работы устройства. Третий двухвходовый элемент

5 ! о

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

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

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

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

Если сигнал на первом выходе циклического регистра 2 сдвига принимает значение

«О», а на выходе равновероятностного элемента 5 устанавливается состояние «1», импульс с выхода датчика 1 импульсов проходит через трехвходовый элемент И 11, устанавливает первый триггер 8 в состояние, запрещающее прохождение импульсов через многовходовый элемент И 3, и через второй элемент ИЛИ 12 задает «быстрый» режим работы датчика 1 импульсов, так как для дальнейшего проведения испытаний необходимо, чтобы на выходе циклического регистра 2 сдвига установилась следующая группа кодов Ф;+ . В «быстром» режиме разо боты, как и в номинальном режиме, на выходе циклического регистра 2 сдвига последовательно появляются коды a„>,äö+

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

40 коды а.„.ц

Как в «быстром», так и в номинальном режимах работы импульсы с выхода датчика 1 импульсов поступают на первый вход счетчика 7. Когда в счетчике 7 зафиксируется число, равное количеству кодов в группе, 45 на втором выходе счетчика 7 появляется сигнал, устанавливающий первый триггер

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

3. Так как второй триггер 10 находится в разрешающем состоянии, то сигнал с второго выхода счетчика 7 проходит ерез второй двухвходовый элемент И 13 и третий элемент ИЛИ 14, поступает на второй вход датчика импульсов и задает номинальный режим его работы, после чего испытания продолжаются в номинальном режиме для (i + 1)-ой группы кодов, т. е. а. +, Если сигналы на первом выходе циклического регистра 2 сдвига и на выходе рав824178!

Импульс с выхода многовходового элемента И 3 поступает также на второй вход!

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

6 выходных вентилей и на первый выход генератора. Появление импульса в блоке 6 выходных вентилей приводит к тому, что случайное число с первого выхода счетчика 7 (код старших разрядов) поступает на второй выход генератора потоков. случайных событий. второго триггера 10 и устанавливает его в состояние, запрещающее прохождение импульсов через многовходовый элемент И 3 и первый двухвходовый элемент И 9. Этот же импульс поступает на второй вход второго элемента ИЛИ 12, проходит через него и задает «быстрый» режим работы датчика

1 импульсов. В таком режиме датчик 1 должен работать до тех пор, пока на выходе циклического регистра сдвига снова не устанавливается первый из начальной группы кодов a« . Это . обеспечивается тем, что, импульс, задающий номинальный режим работы, не может пройти со второго выхода счетчика 7 через второй двухвходовый элемент И 13, так как второй триггер 10 находится в состоянии запрета.

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

ИЛИ 14, и устанавливающий второй триггер !О в разрешающее состояние.

В случае, если до конца цикла импульс не появляется на выходе многовходового элемента И 3, то импульс с третьего выхода счетчика 7 проходит через первый двухвходовый элемент И 9 и первый элемент ИЛИ 4 в блок 6 выходных вентилей и на первый выход генератора, а случайное число с первого выхода счетчика 7 появляется на втором выходе генератора.

Для повышения достоверности работы устройство снабжено третьим триггером 15:

Перед началом работы генератора на первый вход подается сигнал, устанавливающий счетчик 7, первый 8, второй 10 и третий !5 триггеры в исходное состояние, а датчик 1 импульсов — в состояние, позволяющее производить запись информации в циклический регистр 2 сдвига через второй вход генератора.

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

50 няя всю кодовую последовательность, хранящуюся в этом регистре, до четной.

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

Тогда при единичном состоянии третьего триггера 15 импульс с третьего выхода счетчика 7 (после окончания полного цикла сдвига) проходит через третий двухвходовый элемент И 16 и поступает на третий выход устройства и третий вход датчика 1 им(!ульсов. Этот сигнал останавливает работу датчика 1 импульсов и позволяет обеспечить быстрое обнаружение неисправности и восстановление информации в циклическом регистре 2 сдвига, что повышает надежность и достоверность работы генератора, особенно с учетом слабо выраженной чувствительности случайных потоков событий к редким сбоям.

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

Так, например, будем считать, что коды

А = а„а,.„, а„, вычисляются по известной функции распределения Р=Я,Р,..., P по формуле (1)

Величины Q.; представляются группой двоичных символов

< = Ь и < ii " .а2 ) (2) где величина Q.„ равна а;=Х,а; р. (3)

Если код (2) считывать для участия в случайном испытании поэлементно, начиная со старшего разряда a„, затем, ;, (если испытание было неудачйым) и т. д., то за счет последовательного появления сигналов а.„" 1- $0,<$ на выходе циклического регистра 2 сдвига удается с помощью многовходового элемента И 3 и трехвходового элемента И 11 обеспечить правильную работу генератора с использованием единственного равновероятностного элемента, а это значительно упрощает техническую реализацию устройства, так как вероятностные веса 2 в выражении (3) формируются автоматически по условию последовательных испытаний.

Технико-экономическая эффективность генератора потоков случайных событий определяется следующими факторами: а) упрощением логической структуры устройства, что позволяет применить в качестве элементов памяти и кодирования циклический (кольцевой) регистр сдвига и счетчик, и не включ! ть, в отличие от известных устройств, таким сложные блоки, как

824178

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

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

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

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

20 .5

З0

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

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

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

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

1. Авторское свидетельство СССР № 557481, кл. G 06 F 1/02, 1975.

2. Авторское свидетельство СССР № 341156, кл. G 06 F 1/02, 1970.

3. Авторское свидетельство СССР № 551653, кл. G 06 F 1/02, 1975 (прототип).

824178

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

Редактор А. Шишкина Техред А. Бойкас Корректор Ю. Макаренко

Заказ 2111/70 Тираж Т45 Подлнсное

ВНИИПИ Государственного комитета СССР но делам изобретений и открытий

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

Филиал ППП «Патент», г. Ужгород, ул. Проектная,, 4