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

Илобр{ггенио (iTiioc irrcn к иычис.чп- Tfi.riTjiioH тпхинке. и мпжп няйти применение при статисл-ичег-ком мо.т.слитк - ваиии ita электронных пым11:глит(. машннах и при защита информации и пычнслнтельных сетях.

Цель иэобрете1 ия - упрощение 1Ч .и ратора.

ifa фиг. 1 прнпеде иа функциональ- ная схема генератора случай}1ых чисе на фиг, 2 и 3 - примеры конкретного выполнемия функциональных схем блока управления и KOMhiyTaTopa соотпет ственно; на фиг. 4 -- микропрограмма работы J . нератора случайных чисел,

Генератор случайных чмсел содержит перии гный источник 1 равномерно распреде,ггенных (случайных) чисел,, блок 2 памяти, регистр 3 памяти,,сум матер А, группу 5 элементов И, коммтатор 6,схему 7 сраянений, блок 8 управления 5 входы 9 и 10,, группу лы ходов 11..

Блок 8 управлвЕШЯ (фиг. 2) содер жит генератор 12 синхроимпульсов, элемент 13 И, группу триггеров 14 14 J элемент 15 НЕ, дешифратор 16., группу элементов И , группу элементов ИЛИ ., группу вхо- дов и группу выходов 20|-/ 0 Коммутатор (фиг„ .3) С(:),держит дешифратор 21, первую 22,22,вторую 23,-23,третью и четвертую 25,-25. группы элементов И, первую 26, -26,j и вторую 27 27 групппь входов(ВХОД 28 и rpvnny выходов 29, 29.

. этапе настройки генератора случайных чисел на воспроизведен1 е заданной функции распределения ГСх) функдия F(x) аппроксим.ируется отрезками прямой линии. При этом область существования функции pdO разбивается на равных участков а в каждую ячейку памяти генератора слггаиных чисел - зar OJП Яloтcя х- и

1

Лх .. Здесь X, - зн,пчепие аргумента функции F(x) в начале участк аппроксимации,, ii х. - длина 1 с:) участка aппpoкcи iaц lи, i O N-ljN емкость памяти генератора. В данном генераторе «сислу R становится в соответствие множество чисел

1

+ Rj .с требуемым законом распределения, где К., - равномерно распределенные на Hiri ov Ea.rie О, лх .слу- чайньи ; числа. Н рсзуап тате функция распредедтения . дрт 1;рпдстав;;ена в

су R

ныу.однпм слу4;uiHf,x чясеи не набором и-i N отд. льных точек х., принлдлгжаших H -i4ajry участка агп1роксимапии, а м ожеством точек X. К J,, имеющих заданное распределение. При этом кс5личество различных cJiyчайных чи сел, снимаемых с выхода генератора, будет определяться не емкостью памяти, а разрядЕюстью чисел X + R . ila фиг. 1 представлена функциональная схема генератора, формирующе1-о случайные числа с требуемым законом распределения, представленные в форме с фиксированной памяти внутри интернала -1, 1J. В блоке 2 памяти числа у.. хранятся в o6paTiiOM ходе, а накапливающий сумматор 4 операцию сложения Xj + Rj также осуществляет в обратном коде (при этом R всегда положительное число, а X. может быть как положительным, так и отрицательным).

Предлагаемый генератор случайных чисел работает в соответствии с микропрограммой, приведенной на фиг. 4.

Блок 8 управления формирует управляющие сигналы у,, j 1,5.По заднему фронту сигнала у , поступающего на синхровход генератора 1, вырабатывается очередное равномерно распределенное число. Под действием сигнала Yj происходит чтение из блока 2 памяти чисел, адрес которых задается П| старшими разрядами генератора 1 (разрядами числа R,),, По этому адресу R

и

в ячейке записано два числа 4X.,причем X. представлено .в

обратном ходе в форме с фиксированной запятой, а положительное нормализованное число iiX; К 2 . -в форме с плавающей запятой. Очевидно,- что Лх.| 1 . Под действием сигнала у прочитанное из блока 2 памяти число X, загшсывается в накапливающий сумматор 4, порядок р числа Дх. записывается в регистр 3, а мантиса М поступает на первую группу входов комбинациокной схемы 7 сравнения. Наконец, под действием сигнала у число, поступившее на вторую группу входов коммутатора 6, проходит через него на вторую группу входов сумматора 4, где и суммируется с X j ..

В схеме 7 сравнения под действием сигнала у происходит сравнение мантиссы М с р.авпомерно распределенным в интервале 0,1 случайным

313

числом Rj, снимаемым с П2 младших разрядов генератора 1. Если Rj М, то на выходе схемы 7 сравнения вырабатывается единичный сиг- нал Z, который поступает в блок 8 управления.Если R М, то Z 0. Сигнал Z, 1 говорит о том, что число R2 равномерно распределено в интервале О, М поскольку Rj ;с М причем 0,5 М 1, так как 1х,- - нормализованное число. В коммутаторе

6 число R, преобразуется в число 1

R, путем сдвига на р разрядов в сторону младших разрядов, где р - порядок числа Xj. В результате получается равномерно распределенное в интервале fO, лх случайное число Rj, которое суммируется в сумматоре 4с X. под действием сигна ла у. Таким образом, регистр 3,коммутатор 6 и схема 7 сравнения служат для получения чисел R , равномерно распределенных в указанном интервале.

Сумматор 4 имеет два управляющих входа V и V. . Под действием сигнала у , поступающего на вход V , происходит запись числа х. в регистр результата накапливающего сум- матора 4. Поскольку регистр результата сумматора 4 выполнен на двух ступенчатых триггерах, то число х. появится на выходах сумматора Д (на выходах регистра результата сумматора) в момент действия заднего фронта сигнала у, , Под действием сигнала у , поступающего на вход Vj,происходит суммирование числа х ., уже находящегося в сумматоре 4, с чис- лом R2 снимаемым с выходов коммутатора 6. В момент действия сигнала yj эта сумма пройдет через группу 5 -элементов И на выходы 11 генератора (сигнал Yj на микропрограм- ме не показан, поскольку у это есть сигнал у, который проходит на пятьш выход блока 8 управления не всегда, а только при переходе мик программного автомата из состояния а, в состояние . 2 и 4) .Таким образом, происходит формирование случайного числа с требуемьм законом распределения.

Рассмотрим теперь случай Zi 0. Сигнал Z. О указывает на то,что R, 7 М и, следовательно,число Rj вышло за пределы интервала О, х.- Поэтому это число Rj. не может быть

1

использовано для формирования очеред ного случайного числа с требуемым законом распределения,поскольку R не является равномерно распределенным числом в указанном интервале. В этом случае процедура формирования случайного числа с требуемым законом распределения начинается с самого начала, т.е. с выработки равномерно распределенного случайного числа генератором 1 под действием сигнала у (в микропрограмме на фиг. 4 в случае Z О устройство управления переходит из состояния aj в состояние а с выдачей сигнала у ) Далее опять происходит сравнение нового числа R с мантиссой М . Указанная процедура будет повторяться до тех пор, пока не выполнится условие Rj : М. В случае R М сигнал Z принимает единичное значение и предлагаемый генератор сформирует новое случайное число с требуемым законом распределения так как это было уже описано.Поскольку JX. является нормализованным числом, то мантисса этого числа лежит в диапазоне 0,5 М - . Считая, что среднее значение мантиссы М примерно равно 0,75, получим,что вероятность неблагоприятного события Ко М равна примерно 0,25, поскольку RJ равномерно распределено в интервале 0,1 . Поэтому в среднем только в одном случае из четырех будет выполняться условие Ri М, а в остальных трех случаях Rj М. Следовательно, количество неудачных попыток сформировать случайное иисло с требуемым законом распределения в среднем не будет превышать 25%, а поэтому быстродействие такого генератора будет достаточно высоким (в среднем на получение одного случайного числа требуется не более 2,5 тактов работы генератора). В известном устройстве для получения одного т-разрядного случайного числа требуется m тактов работы генератора,поскольку в каждом такте формируется только один разряд случайного числа с заданным законом распределения.

Рассмотрим теперь работу отдельных блоков предлагаемого генератора. На фиг. 2 приведена функциональная схема блока 8 управления. В этой схеме генератор 12 синхроимпульсов

91

элемент 13 И и триггер 1А образуют так называемую схему запуска „Триггер 14 устанавливается в единичное состояние а, состояние сигналом Пуск, поступающим на первый 19, .вход блока управления. В результате открывается элемент 13 И, синхроимпульсы с выхоа генератора 12 начинают проходить через элемент 13 И на синхровходы IQ триггеров 14., 14,1, 14, и дешифратора 16, и блок управления начинает свою работу.После поступления на вто-. рой вход 19, блока управления сигнаа оконча.чия работы Zj вырабатыва- 15 ется сигнал, сбрасывающий триггер 14j в нулевое состояние и блок уп авления прекращает свою работу.По сигналу Пуск также устанавливаются в исходное нулевое состояние триг- 2о геры I4j и 14 3 (состояние а на икропрограмме). у.

В схеме блока 8 управления тригеры 14 и 14, дешифратор 16,элеенты И 17 - 174, элементы ИЛИ 25 18, - 18 образуют схему управяющего автомата, интерпретируюего микропрограмму, приведенную

мата была п ка внутренни

00, состояни aj - 11, сос равляющий ав сической схе томата и син методике. Бл выходов. На ва управлени у., j 1,5, УЗ S У сним ющего автома да элемента 19, блока уп нал Пуск сигнал оконч тий вход 19 схемы 7

срав

(кроме у

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

на фиг. 4.Триггер 14. используется

, бло

для временного хранения сигнала поступающего на третий вход 19j ка 8 управления с выхода схемы 7 сравнения. Элемент 15 НЕ для получения инверсного значения сигнала Z. В зависимости от значений сигналов Z, nZ управляющий автомат формирует управляющие сигналы у s Уг Уа и У согласно микропрограмме, приведенной на фиг. 4. Элемент 17. И служит для получения сигнала у,, не показанного на микропрограмме и, следовательно, не формируемого . схемой управляющего автомата.ЛТо существу сигнал УС это сигнал у,.Однако з отличие от Уз сигнал у, формируется только при переходе управляющего, автомата из состояния а, в состояние а ,, т.е. когда получено очередное случайное число с требуемым законом распределения и необходимо выдать это число на выход генератора. Поэтому на второй вход элемента 17, И поступает сигнал у,, , а на первый вход - сигнал с третьего вьпсода дешифратора 16 (на третьем выходе дешифратора 16 единичный сигнал будет в том случае, когда управляющий автомат находится в состоянии a-j). При синтезе управляющего авто

состояние а, у.

6

мата была принята следующая кодировка внутренних состояний автомата:

состояние а, Q 5 о у.

5

представлено кодом 00, состояние а, - 01, состояние aj - 11, состояние а,,-- 10. Сам управляющий автомат построен по классической схеме микропрограммного ав-, томата и синтезирован по известной методике. Блок управления имеет пять выходов. На J-M выходе 20- устройства управления формируется сигнал у., j 1,5, причем сигналы у, у , УЗ S У снимают ся с выходов управляющего автомата,а сигнал yj - с выхода элемента 17j И. На первый вход 19, блока управления поступает сигнал Пуск, на второй вход 19j - сигнал окончания работы Z,a на третий вход 19j - сигнал Z, с выхода схемы 7

сравнения.Все сигналы ,

(кроме у),

а также

Z,, г

состояния

2 а

0

5

0

jg

0

5

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

На фиг. 3 приведен пример конкретного выполнения коммутатора 6 для случая 2-разрядного порядка р и четырехразрядного числа Rj. Порядок р с выходов регистра 3 поступает на первую группу входов коммутатора 6 (входы 26 и 26j), число Ri - на вторую группу входов (входы 27( - 274) управляющий сигнал у - на синхровход коммутатора (вход 28). Коммутатор имеет семь выходов 29J, i 1,7. В схеме коммутатора используется дешифратор 21 на четыре выхода и четыре группы двухвходовых элементов И, до1гускающих возможность монтажного объединения их выходов (например, элементы И с открытым коллектором, выходы которых можно объединять и через резистор подключать к источнику питания, либо другие типы элементов И, также позволяющие получать монтажное ИЛИ). Из приведенной функциональной схемы коммутатора видно,что при р о единичный сигнал будет только на первом выхо- . де дешифратора 21 и поэтому разряды числа Rj через пе{эвые элементы И каждый группы пройдут на первые четыре выхода коммутатора (вьпсоды 29, - , При р 1 единичный сигнал бу 13

дет на втором выходе дешифратора 21 и разряды числа Rj через вторые элементы И каждой группы пройдут на выходы 29}- 295 коммутатора,т.е. со сдвигом на один разряд. Аналогично при р 2 число RJ проходит на выходы коммутатора со сдвигом на два разряда, а При р 3 на три разряда в CTOporty младших разрядов. Та- КИМ образом, в коммутаторе осуществляется сдвиг числа R на р разрядов. Аналогично строится схема коммутатора и на большее число входов и выходов.

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

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

ГО соединен с первым входом второго

элемента И, выход которого соединен с первым входом первого элемента ИЛИ вьрсод которого соединен с единичным входом второго триггера, вьгход которого соединен с первым входом дешифратора, первый выход которого сое- ,динен с вторым входом первого элемента ИЛИ и с первым входом второго

5

5 Q Q .

0

5

5

1.8

элемента ИЛИ, выход которого соединен с синхронизирующим входом первичного источника равномерно распределенных случайных чисел, вторая ; группа выходов которого соединена с группой адресных входов блока памяти, вторая группа выходов которого соединена с входами соответствующих разрядов регистра памяти, а третья группа выходов блока памяти соединена с первой группой входов сумматора, вторая группа входов которого соединена с группой выходов коммутатора, а группа выходов сумматора соединена с первыми входами соответствующих элементов И группы, выходы которых являются выходами разрядов случайного числа генератора,выход второго элемента И соединен с первым в содом третьего элемента ИЛИ,второй вход которого подключен к второму выходу дешифратора и к единичному входу третьего, триггера, единичный выход которого соединен с вторым входом дешифратора, третий выход которого соединен с BTOPEJM входом второго элемента И и с первым входом третьего элемента И, второй вход которого соединен с входом элемента НЕ, а выход третьего элемента И соединен с нулевым входом первого триггера и с первым входом четвертого эле- мента ИЛИ, выход которого соединен с нулевым входом третьего триггера, четвертый выход дешифратора соединен с вторым входом второго элемента ИЛИ и с первыми входами четвертого и пятого элементов И, вторые входы которых подключены соответственно к единичному и нулевому выходам четвертого триггера, выход четвертого элемента И соединён с нулевыми входами второго и четвертого триггеров, с управляющим входом коммутатора и с , входом Суммирование сумматора,выход пятого элемента И соединен с вторым входом четвертого элемента ИЛИ, третий выход дешифратора соединен с первым входом шестого эле- мента- И, выход которого соединен с вторьгми входами элементов И группы, вых-од третьего элемента ИЛИ соединен с вторым входом шестого элемента И и с синхронизирующ1-1ми входами блока памяти, регистра памяти, сумматора, и схемы сравнения, выход которой соединен с единичным входом : четвертого триггера.

Редактор М.Келемеш

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

Техред М.Двдык Корректор С.Черни

Заказ 4920/47 Тираж 670Подписное,

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

по делам изобретений и открытий 113035, Москва, Ж-35, Раушская наб., д. 4/5

Производственно-полиграфическое предприятие, г. Ужгород, ул. Проектная, .4

сригЛ

Изобретение относится к вычислительной технике и может быть использовано при статистическом моде лировании. Цель изобретения - упрощение генератора. Генератор содержит первичный источник 1 равномерно распределенных случайных чисел,блок 2 памяти, регистр 3 памяти, сумматор 4, элементы И 5, коммутатор 6, схему 7 сравнения, блок 8 управле- НИН, 4 ил. ±fi /// (С .//л СЛ фиэЛ