Генератор случайной последовательности

 

ГЕНЕРАТОР CJmiAEHOfi ПОСЛЕДОВАТЕЛЬНОСТИ , содержащий датчик слу. чайного напряжения, выход которого соединен с первым входом сумматора, второй вход которого через цифроаналоговый преобразователь подключен к выходу вычитателя, вход уменьшаемого которого является информационным входом генератора, выход сумматора соединен с D-входом первого D-триггера , С-вход которого является входом Опрос генератора, а выход первого D-триггера соединен с первым входом первого элемента И, выход которого является выходом генератора, отличающийся тем, что, с целью повыщения точности, в него введены три элемента задержки, элемент ШШ, три элемента И, регистр памяти, мультиплексор , два счетчика, счетньй триггер и второй В-т-риггер, выход которого соединен с вторым входом первого элемента И, выход первого D-триггера соединен с первым входом второго элемента И, выход которого соединен с первым входом третьего элемента И, выход которого соединен со счетным входом первого счетчика, информационный выход которого соединен с первьм информационным входом мультиплексора, выход которого соединен с входом регистра памяти, выход которого соединен с входом вычитаемого вычитателя, вход уменьшаемого которого объединен с вторым информационным входом мультиплексора, первый управляющий вход которого объединен с входом Сброс второго счетчика, с первым входом элемента ИЛИ, с установочным входом второго D-триггера и является входом Установка генератора , вход Опрос которого через первый элемент задержки соединен с вторым входом второго элемента И и непосредственно соединен с первым входом четвертого элемента И, выход которого соединен со счетным входом второго счетчика, выход переполнения которого соединен с С-входом счетного триггера, инверсный выход которо D го соединен с вторыми входами третьеЧ -v| го и четвертого элементов И и с С-входом второго D-триггера, D-вход которого подключен к шине Логическая единица, выход элемента ИЛИ соединен с входом Сброс первого счеТчика и с установочным входом Учетного триггера, единичный выход которого соединен с входом второго элемента задержки, выход которого соединен с вторым управляющим входом Мультиплексора и с входом третьего элемента задержки, выход которого соединен с вторым входом элемента ИЛИ.

747 А

ОЮ:. 01) С 06 F 7/58

Г:

ОПИСАНИЕ ИЗОБРЕТЕНИЯ

H aeXoimOvV cs amnWXsv

ГОСУДАРСТВЕННИЙ НОМИТЕТ СССР

ПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТНРЫТИЙ (21) 3573476/18-24 (22) 06.04.83 (46) 23.08.84. Бюл. И 31. (72) Е.Я.Семенюк (53) 681.325(088.8) (56) I. Авторское свидетельство СССР

Ф 688905, кл. С 06 F 7/58, 1977.

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

В 463962, кл. G 06 F 7/58, 1972.

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

У 510706, кл. С 06 F 7/58, 1974.

4 ° Авторское свидетельство СССР

Р 687456, кл. G 06 F 7/58, 1977.

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

9 447707, кл. С 06 F 7/58, 1972 (прототип). (54)(57) ГЕНЕРАТОР СЛУЧАЙНОЙ ПОСЛЕДОВАТЕЛЬНОСТИ, содержащий датчик случайного напряжения, выход которого соединен с первым входом сумматора, второй вход которого через цифроаналоговый преобразователь подключен к выходу вычитателя,. вход уменьшаемого которого является информационным .входом генератора, выход сумматора соединен с D-входом первого D-триггера, С-вход которого является входом

"Опрос" генератора, а выход первого

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

0-триггера соединен с первым входом второго элемента И, выход которого соединен с первым входом третьего элемента И, выход которого соединен со счетным входом первого счетчика, информационный выход которого соединен с первым информационным входом мультиплексора, выход которого соединен с входом регистра памяти, выход которого соединен с входом вычитаемого вычитателя, вход уменьшаемого которого объединен с вторым информационным входом мультиплексора, первый управляющий вход которого объединен с входом "Сброс" второго счетчика, с первым входом элемента ИЛИ, с установочным входом второго D-триггера и является входом "Установка" генератора, вход "Опрос" которого через первый элемент задержки соединен с вторым входом второго элемента И и непосредственно соединен с первым

С входом четвертого элемента И, выход которого соединен со счетным входом второго счетчика, выход переполнения которого соединен с С-входом счетного триггера, инверсный выход которого соединен с вторыми входами третье1 го и четвертого элементов И и с С-входом второго D-триггера, D-вход рф которого подключен к шине "Логическая а,) единица", выход элемента ИЛИ соединен с входом "Сброс" первого счетчика и с установочным входом счетного триггера, единичный выход которого ф соединен с входом второго элемента задержки, выход которого соединен с вторым управляющим входом Мультиплексора и с входом третьего элемен-. та задержки, выход которого соединен с вторым входом элемента ИЛИ.

1109

Указанный генератор имеет достаточное для практических целей быстро- 50 действие, но обладает повьппенной чувствительностью к изменению параметров шумового сигнала (главным образом его медианного значения). Поэтому разбаланс. появления "О",и "1" 55 в генераторах указанного класса обцчно больше, чем в других, что требу.ет введения в конструкцию генерато1

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

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

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

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

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

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

747 ров аппаратурных средств его компенсации.

Известен также генератор случайI ных двоичных цифр, содержащий источники формирования первичного случайного напряжения и блок суммирования по модулю два, D-триггеры, D-входы которых соединены с выходами источников формирования первичного случайно. го напряжения соЬтветственно, выходы триггеров соединены с входами блока суммирования по модулю два, а синхронизационные входы D-триггеров соединены между собой и подключены к входу "Опрос" генератора.

В указанном устройстве применение

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

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

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

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

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

1109747

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

10 генератора, выход сумматора соединен с D-входом первого D-триггера, С-вход которого является входом "Опрос" генератора, а выход первого D-триггера соединен с первым входом первого

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

20 соединен с вторым входом первого элемента И, выход первого D-триггера соединен с первым входом второго элемента И, выход которого соединен

25 с первым входом третьего элемента И, . выход которого соединен со счетным входом первого счетчика, информационный выход которого соединен с первым информационным входом мультиплек сора, выход которого соединен с входом регистра памяти, выход которого соединен со входом вычитаемого вычитателя, вход уменьшаемого которо. го объединен с вторым информационным входом мультиплексора, первый управ- 35 ляющий вход которого объединен с входом "Сброс" второго счетчика, с первым входом элемента ИЛИ, с установочным входом второго D-триггера и является входом "Установка 1 генератора, вход "Опрос" которого через первый элемент задержки соединен с вторым входом второго элемента И и непосредственно соединен с первым входом четвертого элемента И, выход которого 45 соединен со счетным входом второго счетчика, выход переполнения которого соединен с С-входом счетного триггера, инверсный выход которого соединен с вторыми входами третьего и 50 четвертого элементов И и с С-входом второго D-триггера, D-вход которого подключен к шине "Логическая единица", выход элемента ИЛИ соединен с входом

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

На фиг. 1 приведена блок-схема генератора; на фиг. 2 — схема блока определения отношения частот.

Генератор содержит сумматор датчик 2 случайного напряжения, цифроаналоговый преобразователь 3, вычитатель 4 с информационным входом 5 уменьшаемого, блок 6 определения отношения частот, D-триггер 7 с входом 8 "Опрос", элемент И 9, выход 10, элемент И 1 1, элемент 12 задержки, блок 6 и элементы 11 и 12 образуют блок 13 текущих вероятностей, который содержит вход 14 "Установка", элемент ИЛИ 15, триггер 16, счетчик 17, мультиплексор 18, элементы 19 и 20 .задержки, счетный триггер 2 1, элементы И 22 и 23, счетчик 24, регистр 25 памяти с выходом 26,вход 27 мультиплексора 18, входы 28 и 29 элементов И 22 и 23, выход 30 D-триггера 16.

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

В режиме подготовки с входа 5 на первые информационные входы вычитателя 4 и блока 6 поступает цифровой код нормативного значения вероятности появления выходного сигнала генератора, после .чего на вход 14 воз" действует импульсный сигнал установки в исходное состояние, который устанавливает в нулевое состояние триггеры 16, 21 и суммирующие счетчики 17 и 24, а также воздействует на первый управляющий вход мультиплексора 18. При этом. с инверсного выхода счетного триггера 21 на вторые входы элементов И 22 и 23 поступает сигнал логической "1", а присутствующий на входе 27 код нормативного значения вероятности появления выходного сигнала генератора фиксируется в регистре 25 и через информационный выход 26 поступает на второй вход вычитателя 4. Поскольку при работе генератора в режиме подготовки на оба входа вычитателя 4 поступают коды одного и того же числа, на его выходе образуется код нулевого состояния, который преобразуется цифроаналоговым преобразователем 3 в нулевой аналоговый сигнал

1 1109747 и поступает на второй вход сумматора 1 ° При этом шумовой аналоговый сигнал с выхода датчика 2 случайного напряжения поступает на первый вход сумматора 1, с выхода которого без 5 каких-либо изменений поступает на

D-вход первого D-триггера 7.

В моменты поступления на вход 8 положительных перепадов импульсов опроса генератора первый D-триггер 7 принимает состояние "0" или "1" в зависимости от соотношения в указанные моменты времени значений напряжения на его D-входе и напряжения порога срабатывания первого D-триггера 7 по входу 9 . .В случае установления первого D-триггера 7 данным импульсом опроса в состояние логической "1" сигнал этого состояния с прямого выхода первого 0-триггера 7 поступает 20 на первый вход элемента И 11, где стробируется тем же импульсом опроса, поступившим через элемент 12 задержки на второй вход элемента И 11,и переводится в импульсный сигнал наличия

"1" на выходе первого О-триггера 7.

Импульсные сигналы наличия "1" на выходе первого D-триггера 7 с выхода элемента И 11 поступают на второй вход блока 6, на третий вход которо30 го поступают импульсы опроса генератора. При этом .импульсные сигналы наличия "1" на выходе первого П-триггера 7 проходят через первый вход 28 элемента И 22 и накапливаются в счет-З чике 24 появления случайных сигналов генератора, а импульсы опроса генератора, которые представляют собой сигналы наличия как "0", так и "1", на выходе D-триггера 7, проходят че40 рез первый вход 29 элемента И 23 и накапливаются в счетчике 17. В момент переполнения счетчика 17 перепад напряжения на выходе его старшего разряда устанавливает счетчный триг- 45 гер 21 в состояние логической "1".

На инверсном выходе счетного триггера 21 появляется сигнал логического "0", который блокирует прохождение импульсных сигналов через элементы И 22 и 23 по входам 28, 29 и фиксирует состояния счетчиков 17 и 24.

На этом цикл измерения текущей вероятности .появления логической "1" на выходе первого В-триггера 7 заканчи-Б вается, во всех разрядах счетчика 17 фиксируются логические "0", а в счет-. чике 24 появления случайных сигналов генератора фиксируется цифровой код текущей вероятности появления логической "1" на выходе первого

D-триггера 7 при отсутствии коррек тирующего воздействия на втором вхо- . де блока 1 суммирования.

Точность получения кода текущей вероятности появления логической " 1" на выходе первого D-триггера 7 непосредственно Зависит от объема статистической выборки, на которой она вычисляется, и определяется разрядностью счетчика 17. Напряжение логи11 1 I ческои 1 с прямого выхода. счетного триггера 2 1 через интервал времени, определяемый элементом 20 задержки, поступает на вход элемента 19 задержки, а также воздействует на второй управляющий вход мультиплексора 18. В результате этого воздействия содержимое счетчика 24 появления случайных сигналов генератора поступает в регистр 25, с выхода 26 которого цифровой код текущей вероятности появления логической"1" на выходе первого D-триггера 7 поступает на второй вход вычитателя 4, на выходе которого образуется цнфровой код разности нормативного и текущего значений вероятности появления логической "t" на выходе первого

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

Если разность между нормативным и текущим значениями вероятности появления логической "1" на выходе первого D-триггера 7 равна "0", аналоговый сигнал на втором входе блока 1 суммирования отсутствует и сигнал с датчика 2 случайного напряжения передается на D-вход первого D-триггера 7 без изменений. Если текущее значение вероятности появления. логи11 1! ческои 1 на выходе первого D-триггера 7 ниже нормативного значения вероятности его появления, вычитатель 4 вырабатывает положительное значение. цифрового корректирующего сигнала, которое в,аналоговой форме суммируется в блоке 1 суммирования с сигналом датчика 2 случайного напряжения.и повышает медианное значение последнего относительно порогового значения напряжения на D-вхо1109747 де первого D-триггера 7. Текущая вероятность появления логической "1" на выходе первого D-триггера 7 при этом увеличивается. Если текущее значение вероятности появления логичес- 5 кой "1" на выходе первого D-триггера 7 превышает нормативное значение вероятности его появления, вычитатель 4 формирует отрицательное значение цифрового корректирующего сигнала, которое понижает медианное значение сигнала датчика 2 случайного напряжения относительно порогового значения напряжения на D-входе первого D-триггера 7, чем вызывает снижение вероятности появления сигнала логической "I" на выходе первого

D-триггера 7.

После воздействия управляющего сигнала на второй управляющий вход мультиплексора 18 через интервал вре-. мени, определяемый элементом 19 задержки, с выхода последнего на второй вход элемента ИЛИ 15 поступает сигнал логической "1". На выходе элемен-2 та ИЛИ 15 появляется сигнал, который переводит в состояние логического "0" все разряды счетчика 24 и счетный триггер 21, на инверсном выходе кото рого появляется сигнал логической "1". зо

При этом сигнал логической "1" на инверсном выходе счетного триггера 21 разблокирует прохождение импульсных сигналов через элементы И 22 и 23 по входам 28 и 29 соответственно и одновременно с этим переводит второй D-триггер .16 в состояние логической "1". Сигнал этого состояния с выхода 30 второго D-триггера 16 воздействует на второй вход элемен- 4р та И 9 и открывает прохождение сигналов логической "1" с выхода первого D-триггера 7 на выход 10 генератора. Подготовительный режим работы генератора на этом заканчиваетея и 4 сменяется режимом генерации случайной последовательности двоичных цифр., который отличается от подготовительного режима отсутствием импульсов установки в исходное состояние íà. вхо ц де 14 установки в исходное состояние.

В результате этого второй D-триггер. 16 в течение всего режима генерации находится в состоянии логической " 1", а с его выхода 30 на второй вхбд элемента И 9 постоянно поступает управляющий сигнал, который обеспечивает прохождение случайной последоваi тельности двоичных цифр с выхода первого триггера 7 на выход 10 генератора. Информационный вход 27 и первый управляющий вход мультиплексора 18 не используются, а счетный триггер 21 и счетчики 17 и 24 автоматически принимают необходимые для нормальной работы блока 6 состояния. При этом измерение текущих значений вероятнос! тн появления логической "1" на. выходе 10 генератора происходит отдельными циклами, каждый из которых начинается с заполнения импульсами наличия логической "1" на выходе первого D-триггера 7 и импульсами опроса генератора счетчиков 24 и 17соответственно, а завершается выдачей результата измерения с информационных выходов счетчика 24 в регистр 25 и последующим обнулением счетного триггера 21 и счетчика 24.

Элементы 19 и 20 задержки включены в схему блока 6 с целью более четкого разделения во времени процесса фиксации текущего результата измерения в счетчике 24, процесса его занесения в регистр 25, момента завершения переходного процесса на D-вхо.де первого D-триггера 7 после поступления очередного корректирующего воздействия на второй вход блока 1 суммирования и момента начала последующего цикла измерения °

В течение каждого из циклов измерения текущего значения вероятности появления логической "1" на выходе 10 генератора на второй вход блока 1 суммирования воздействует аналоговый корректирующий сигнал, соответствующий зафиксированному в регистре 25 цифровому значению предшествующего результата измерения. Поскольку значение корректирующего сигнала стабилизирующей обратной связи генератора вырабатывается непосредственно на основе сигнала датчика 13 вероятности появления выходного сигнала, цифровое значение которого не зависит от амплитудных и временных характеристик первичного шумового и управляющих сигналов, качество работы предлагаемого устройства полностьн> не зависит от частоты и скважности управляющих импульсов, а также от статистических распределений амплитудных и временных характеристик первичного случайного сигнала датчика 2 случайного напряжения.: Для правильной

9 1109747 10 работй датч3иса 13.вероятности появле- должно быть больше времени срабатыния выхо@вого сигнала генератора вания первого D-триггера 7 по его время задераки элемента 12 задержки тактируемому входу.

1109747

Фиа2

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

Редактор А.Мотыль Техред М.Кузьма Корректор Е.Сирохман

Заказ 6085/34 Тираж 699 .. Подписное

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

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

Филиал ППП "Патент", r.Óæãîðîä, ул.Проектная, 4