Генератор случайных чисел
Изобретение относится к вычислительной технике и может быть использовано при статистическом моде лировании. Цель изобретения - упрощение генератора. Генератор содержит первичный источник 1 равномерно распределенных случайных чисел,блок 2 памяти, регистр 3 памяти, сумматор 4, элементы И 5, коммутатор 6, схему 7 сравнения, блок 8 управле- НИН, 4 ил. ±fi /// (С .//л СЛ фиэЛ
ф ф .7 РЕСПУБЛИН
„„SU„„1345191 (51) 4 G 06 F 7/58
ОПИСАНИЕ ИЗОБРЕТЕНИЯ
ГОСУДАРСТВЕННЫЙ НОМИТЕТ СССР
ПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТНРЫТИЙ
К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ (21) 4087392/24-24 (22) 29.05.86 (46) 15.10.87. Бюл. N 38 (72) В.M.ÒàðàñîB, В.М.Трусфус и А.У.Ярмухаметов (53) 681.325(088.8) (56) Авторское свидетельство СССР
Ф 378826, кл. G 06 F 7/58, 1971.
Авторское свидетельство СССР
М - 1008737, кл. С 06 F 7/58, 1981. (54) ГЕНЕРАТОР СЛУЧАИН61Х ЧИСЕЛ (57) Изобретение относится к вычислительной технике и может быть использовано при статистическом моде лировании. Цель изобретения — упрощение генератора. Генератор содержит первичный источник 1 равномерно распределенных случайных чисел, блок
2 памяти, регистр 3 памяти, сумматор 4, элементы И 5, коммутатор 6, схему 7 сравнения, блок 8 управле = ния, 4 ил.
И <обретеlift«эти<>сигея к вы (и< ill
T (..tl f I 1 t О Й т е х ! и к е If м (» ((е т l l а и т ! ! р и Г-! е
H (. f ! е I! р и с т (f т f (. т l f I (. (I«> Г м n) (."! l! р О ванин на электр<э!!!!1,>х вы п(слит< .!нных
<) машинах и при защи е информации в
BtIlI(ИСЛИТРЛЬ!(ЫХ СЕТЯХ, Цель изобретения — упроще>!ие генерат(эра.
Нл (1>иг, 1 приHÐÄ(lflа функцио(t(Illü 1Q ная схема генератора случ;юных чисел;
HB (1>HI". ? и 3 — примерь! конкретного выполнения функциональных схем блока управления и коммутатора соответственно; на фиг., — микропрограмма ll5 рабОты >,
Блок 8 управления (фиг. 2) содерэ)(ит генератор 12 синхроимпульсон, элемент 13 И группу триггеров 14
1 1„, элемент 15 НЕ, дешифрат<эр 16., группу элементов И 17, — 17, группу элементов ИХ1И 18, — 18, группу вхо- ЗО дов 19 — 19 и группу гыходов 20 -20 . ! 3 !>
Коммутатор (фиг. 3) (.<>Пе1эжит де шифратор 21, первую 22, -22„,нторук>
23 -23<,третью ?4„-?4 и четвеpтую
25,-25 группы элементов И, f(1(рр.y ю
3.э
26, -26 и вторую 27 -27, групппы v входов„ вход 28 и группу выходов 29,—
На этапе настройки генератора
СЛучайных чисел на воспроизведение (1О заданной функции расцред(.ления Г(х), функция Г(х) аппроксимируется отрезками прямой линии. При этом область су!цествона(!И>! функции E (х) разбива, п
e rc>f ffa 8=2 раннь(х участкОв, а н каждуf(> ячейк -f памя ти г< н е1эато>>а (.лу чайнь!х чисел — эа>(<ээ!!(Яются х и .
> ,) х .. Здесь х, — fl-..÷åíèå аргумента функции F(x) в lt;lчале i-го учас".-I(a аппроксимации,, d<х. — длина 1 гo 50 участка аппроксимац >и, i = О,N- :„ttl еГ!кость памяти ген Eр>ат01>а В да>! ном генераторе каэкэ(<яму числу R становит<
С Я Н С 0 О Т В Е Т С Т > ) ! (- !I f I f O >I< C C Т В О Ч И С (Л
x + R . с требуемым законом распре- г
1 г . - . . - 5, деления„ где, „ — ран><омерно распределенные на ицт !валс j(i, 71х,1 слу!>! распределен;!я (т предcTàff. ена н
l
ff, f>(>g>off и" 11 отд(>1>,н>>х точек х,, I
Il Plfll а>!!!(>I< v) IIIHX На «>!V К аж >(<Э Го Уна с кcl аццр<>I< симации, а и! Ож cтном точек
Г
;< R,, >!tact(>>!(fax зала!Гное распределе ие. 1!ри этом количество разли(них случайHMx чисел, снимаемых с выхода генератора, будет определяться не
Р мк ос тик> и а> !я ти а разряднОстьк) чи ( сел x + R . На фиг. l представле7 на функци<эн(>льна>! схема генератора, формирующего случайные числа с требуемым законом распределения, представленные в форме с фиксированной памяти внутри интервала (-1, 2Е.
В блоке 2 памяти числа х. хранятся
1 н обратьом ходе, а накапливающий сум< матор 4 операцию сложения х. + R7
1 также осуществляет н обратном коде
< (при этом Н всегда положительное число, а х. может быть как положи> тельным, так и отрицательным).
Предлагаемый генератор случайных чисел работает в соответствии с микропрограммой, приведенной на фиг. 4.
Блок 8 управления формирует управляющие сигналы у, j = 1,5.По задне< му фронту сигнала у, поступающего
1 на синхровход генератора 1, вырабатывается очередное ранномерно распределенное число. Под действием сигнала у„ происходит чтение из блока 2 памяти .èñåë, адрес которых задае гся и! старшими разрядами генератора 1 (разрядами числа R,)., По этому адресу R, в ячейке записано два числа х. и dx.,причем х, представлено в
1 1
1 обратном ходе в форме с фиксированной запятой, а положительное нормализованное число и х = 1" .2 — в е
I форме. с плавающей запятой. Очевидно,. что Лх с 1. Под действием сигнала у прочитанное из блока 2 памя3 ти число х. записывается в накапли1 нающий сумматор 4, порядок р числа ах. записывается в регистр 3, а
1 мантиса М поступает на первую группу входов комбинационной схемы 7 сравнения. Наконец, под действием
ci-гнала у число, поступившее на вторую группу нходон коммутатора 6, проходит через него на вторую группу входов сумматора 4, где и суммируется с х, В схеме 7 сравнения под действием сигнала у происходит сравнение мантиссы El c pllf>HOMepHo распределенным н интервале L 0,1) случайным
1345191 числом R, снимаемым с п младших разрядов генератора l. Если
R> c M, то на выходе схемы 7 сравнения вырабатывается единичный сиг5 нал Z, который поступает в блок 8
1 управления. Если R< ) М, то 21= О.
Сигнал Z, = 1 говорит о там, что число R> равномерно распределено в интервале (0, М) поскольку R2 < M 10 причем 0,5 « М с 1, так как (1х;— нормализованное число. В коммутаторе
6 число R преобразуется в число
R путем сдвига на р разрядов в сто( г рону младших разрядов, где р 15 порядок числа дх,. В результате получается равномерно распределенное в интервале (О, и х „. ) случайное
t число R, которое суммируется в сумматоре 4 с х . под действием сигна- 2р ла у . Таким образсм, регистр З,коммутатор 6 и схема 7 сравнения служат ( для получения чисел R<,равномерно распределенных в указанном интервале. 25
Сумматор 4 имеет два управляющих входа V„ V . Под действием сигнала у, поступающего на вход V происходит запись числа к. в реI гистр результата накапливающего сум- gp матора 4. Поскольку регистр результата сумматора 4 выполнен на двух ступенчатых триггерах, то число х.
1 появится на выходах сумматора 4 (на выходах регистра результата сумматора) в момент действия заднего фронта сигнала у . Под действием сигна3 ла у, поступающего на вход V<,происходит суммирование числа х, уже находящегося в сумматоре 4, с чис- 4О ( лом R, снимаемым с выходов коммутатора 6. В момент действия сигнала у- эта сумма пройдет через групТ пу 5 .элементов И на выходы 11 генератора (сигнал у на микропрограм- 45 ме не показан, поскольку у это есть сигнал у, который проходит на пятый выход блока 8 управления не всегда, а только при переходе микпрограммного автомата из состояния а в состояние а (фиг. 2 и 4).Таким образом, происходит формирование случайного числа с требуемым законом распределения.
Рассмотрим теперь случай Z1 = О.
Сигнал Е„.= О указывает на то,что
R ) M H, (e o Te 1Ho, H(0 R2 вышло за пределы интервала (0, л х.).
Поэтому это число R не может быть использовано для формирования очеред-. ного случайшога числа с требуемым законом распределения, поскольку R> не является равномерно распределенным числом в указанном интервале. В этом случае процедура формирования случайного числа с требуемым законом распределения начинается с самого начала, т.е. с выработки равномерно распределенного случайного числа генератором 1 под действием сигнала у (в микропрограмме на фиг. 4 в
1 случае Z = О устройство управле1 ния переходит из состояния а в состояние а с выдачей сигнала у ) .
1 "1
Далее опять происходит сравнение нового числа R с мантиссой М . Указанная процедура будет повторяться до тех пор, пока не выполнится условие Rq М. В случае R М сигнал Z„ принимает единичное значение и предлагаемый генератор сформирует новое случайное число с требуемым законом распределения так, как это было уже описано. Поскольку (1х является нормализованным чис1 лом, то мантисса этого числа лежит в диапазоне 0,5 М 1. Считая, что среднее значение мантиссы M примерно равно 0,75, получим,что вероятность неблагоприятного события
К > ) М равна примерно О, 25, поскольку R равномерно распределено в интервале (О, 1) . Поэтому в среднем только в одном случае из четырех будет выполняться условие
R > M, а в остальных трех случаях
R> < М. Следовательно, количества неудачных попыток сформировать случайное число с требуемым законом распределения в среднеи не будет превышать 25Х, а поэтому быстродействие такого генератора будет достаточно высоким (в среднем на получение одного случайного числа требуется не более 2,5 тактов работы генератора). В известном устройстве для получения одного m-разрядного случайного числа требуется m тактов работы генератора, поскольку в каждом такте формируется только один разряд случайного числа с заданным эаконом распределения.
Рассмотрим теперь работу отдельных блоков предлагаемого генератора. На фиг. 2 приведена функциональная схема блока 8 управления. В этой схеме генератор 12 синхроимпульсов, 5 134519 элемент 13 И и триггер i4 образуют так называемую схему запуска .,Триггер 14 устанавливается в единичное
It,tI состояние сигналом Пуск, поступа5 ющим на первый 19, вход блока управления. В результате открывается элемент 13 И, синхроимпульсы с выхода генератора 12 начинают проходить через элемент 13 И на синхровходы триггеров 14, 14 „ 14 и дешифратора 16, и блок управленйя начинает свою работу. После поступления на вто-, рой вход 19 блока управления сигнала оконча;1ия работы Е4 вырабатывается сигнал, сбрасывающий триггер
141 в нулевое состояние, и блок уп" равления прекращает свою работу.По сигналу Пуск также устанавливаются в исходное нулевое состояние триг- 20 геры 14 и t4 q (состояние а, на микропрограмме).
В схеме блока 8 управления триггеры 14 и 14, дешифратор 16,элементы И 17, — 174, элементы ИЛИ 25
18 - 18 образуют схему управ" ляющего автомата, интерпретирующего микропрограмму, приведенную на фиг, 4.Триггер 14 используется для временного хранения сигнала К,, поступающего на третий вход 195 блока 8 управления с выхода схемы 7 сравнения. Элемент 15 HE служит для получения инверсного значения сигнала Z . В зависимости от значений
35 сигналов Z и К управляющий автомат формирует уйравляющие сигналы у, у, у и у4 согласио микропрограмме,прйведенной на фиг. 4. Элемент
17 И служит для получения сигнала у5, не показанного на микропрограмме и, следовательно, не формируемого схемой управляющего автомата..По существу сигнал у это сигнал у .Од5 3 нако в отличие от у> сигнал у5 формируется только при переходе управляющего автомата из состояния а> в состояние а „ т.е. когда голучено очередное случайное число с требуемым законом распределения и необ-,.
60 ходимо выдать это число на выход генератора. Поэтому на второй вход элемента l75 И поступает сигнал: у, а на первый вход — сигнал с третьего выхода дешифратора 16 (на третьем выходе дешифратора 16 единичный сигнал будет в том случае. когда управ ляющий автомат находится в состоянии
a4). При синтезе управляющего анто6 мата была принята следующая кодировка внутренних состояний автомата: состояние а, представлено кодом
00, состояние а, †. О1, состояние а — 11, состояние a,, — — 10. Сам управляющий автомат построен по классической схеме микропрограммного автомата и синтезирован по известной методике. Блок управления имеет пять выходов. На j-м выходе 20 устройст-! ва управления формируется сигнал у, j = 1,5, причем сигналы у, у
1 у, у снимаются с выходов управляющего автомата,а сигнал у — с выхода элемента 17< И На первый вход
19, блока управления поступает сигнал "Пуск", на второй вход 19 сигнал окончания работы Z< а на третий вход 19 — сигнал Z, с выхода схемы 7 сравнения.Все сигналы Е,, Z< у. (кроме у ), а также состояния а
5 автомата указаны на микропрограмме., приведенной на фиг. 4. В схеме блока управления используются двухступечатые синхронные триггеры 14,-14 причем триггеры 14 и 14 имеют также асинхронные установочные входы.
На фиг. 3 приведен пример конкретного выполнения коммутатора 6 для случая 2-разрядного порядка р и четырехразрядного числа R>. Порядок р с выходов регистра 3 поступает На первую группу входов коммутатора 6 (входы 26, и 26 ), число
R q — на вторую группу входов (входы
27, — 27„ ), а управляющий сигнал у — на синхровход коммутатора (вход
28). Коммутатор имеет семь выходов
29;, i = 1,7. В схеме коммутатора используется дешифратор 2 1 на четыре выхода и четыре группы двухвходовых элементов N, допускающих возможность монтажного обьединеьия их выходов (например„ элементы И с открытым коллектором, выходы которых можно объединять и через резистор подключать к источнику питания, либо другие типы элементов И, также позволяющие получать монтажное ИЛИ). Иэ приведенной функциональной схемы коммутатора видно,что при р = 0 единичный сигнал будет только на первом выходе дешифратора 21 и поэтому разряды числа k> через первые элементы И каждый группы пройдут на первые четыре выхода коммутатора (выходы 29,—
29 4). При р = 1 единичный сигнал бу13ч519 дет va втором выходе дешифратора 21 и разряды числа R через вторые.элементы И каждой группы пройдут на выходы 29 — 29 коммутатора,т.е. со сдвигом на один разряд. Аналогично при р = 2 число R проходит на выходы коммутатора со сдвигом на дна разряда, а при р = 3 на три разряда в сторону младших раэрядон. Таким образом, в коммутаторе осуществляется сдвиг числа R< на р разря-. дов. Аналогично строится схема коммутатора и на большее число входов и выходов. l0
Формула изобретения ными входами второго и третьего триггерон и является входом "Пуск" генератора, входом "Стоп" которого является вход элемента НЕ, выход которого соединен с первым входом второго элемента И, выход которого соединен
50 с первым входом первого элемента ИЛИ, выход которого соединен с единичным входом второго . триггера, выход которого соединен с первым входом- дешифратора, первый выход которого сое. динен с вторым входом первого элемента ИЛИ и с первым входом второго
Генератор случайных чисел, содержащий первичный источник равномерно распределенных случайных чисел,первая группа выходов которого соединена с первой группой входов схемы сравнения и с первой группой информационных входов коммутатора, вторая группа информационных входов которого соединена с выходами разрядов ре- . гистра памяти, блок памяти, первая группа выходов которого соединена с второй группой входов схемы сравнения,группу элементов И, о т л ич аю шийся тем,что, с целью уп-.. рощения, он содержит сумматор и блок управления, содержащий шесть элементов И, четыре элемента ИЛИ, элемент НЕ, дешифратор, четыре триг35 гера и . генератор тактовых импульсов, выход которого соединен с первым входом первого элемента И и с синхронизирующим входом перного тригге-. ра, единичный выход которого соединен с вторым входом первого элемента И, выход которого соединен с синхронизирующими входами дешифратора, второго, третьего и четвертого триг- геров, единичный вход первого триггера объединен с установочными нуле4
1.
0 элемента ИЛИ, выход которого соединен с синхронизирующим входом первичного источника равномерно распределенных случайных чисел, вторая группа выходов которого соединена с группой адресных входов блока памя- ти,нторая группа выходов которого соединена с входами соответствующих разрядон регистра памяти, а третья группа выходов блока памяти соединена с первой группой нходов сумматора,вторая группа входов которого соединена с группой выходов коммутатора, а группа ныходов сумматора соединена с первыми входами соответствующих элементов И группы, выходы которых являются выходами разрядов случайного чйсла генератора, выход второго элемента И соединен с первым входом третьего элемента ИЛИ,второй вход которого подключен к второму выходу дешифратора и к единичному входу третьего триггера, единичный выход которого соединен с вторым входом дешифратора, третий выход которого соединен с вторым входом второго элемента И и с первым входом третьего элемента И, второй вход которого соединен с входом элемента НЕ, а выход третьего элемента И соединен с нулевым входом перного триггера и с первым входом четвертого элемента ИЛИ, выход которого соединен с нулевым входом третьего триггера, четвертый выход дешифратора соединен с вторым входом второго элемента ИЛИ и с первыми входами четвертого и пятого элементов И, вторые входы которых подключены соответственно к еди ничному и нулевому выходам четвертого триггера, выход четвертого элемента И соединен с нулевыми входами второго и четвертого триггеров, с управляющим входом коммутатора и с входом "Суммирование" сумматора,вы" ход пятого элемента И соединен с вторым входом четвертого элемента
HJIH, третий выход дешифратора соединен с первым входом шестого элемента. И, выход которого соединен с вторыми входами элементов И группы, выход третьего элемента ИЛИ соединен с вторым входом шестого элемента И и с синхронизирующими входами блока памяти, регистра памяти,. сум- матора.и схемы сравнения, выход которой соединен с единичным входом четвертого триггера.
1345191 Ii, 1
1 г
1 . р)
Г
1 (1 .)Я
L (" 1 1:Ф«»
Ф- — " j
t, .М» . (l
«/,, 1
Р
i У Гд
/ t
«ф » У:
«» У - 0 г
Г 6 .,Х.4/. (!
j"
1 3451 1 фОГ4
Составитель A.Kàðàñoâ
Техред М.Дидык
Редактор М.Келемеш
Корректор С.Черни
Заказ 4920/47 Тираж 670 Подписное
ВНИИПИ Государственного комитета СССР по делам изобретений и открытий
113035, Москва, Ж-35, Раушская наб., д. 4/5
Производственно-полиграфическое предприятие, r. Ужгород, ул. Проектная, 4
