Генератор случайных чисел

(51) 4 С ССРРЫТИЙ ИЗОБРЕТЕНИЯ ПИС К АВТОРСКОМУ СВИДЕТЕЛЬСТВ Трусфу льство ССС /58, 1971. ство СССР 7/58, 1981 Рф ф ф .) РЕСПУБЛИН ГОСУДАРСТВЕННЫЙ НОМИТ ПО ДЕЛАМ ИЗОБРЕТЕНИЙ И(54) ГЕНЕРАТОР СЛУЧАЙНЫХ ЧИСЕЛ(57) Изобретение относится к вычислительной технике и может быть использовано при статистическом модлировании. Цель изобретения - упрощение генератора. Генератор содержит первичный источник 1 равномернораспределенных случайных чисел, блок2 памяти, регистр 3 памяти, сумматор 4, элементы И 5, коммутатор 6,схему 7 сравнения, блок 8 управле-ния, 4 ил.Изс)бретенп тпс итсл к пыи п 1 т 11 ьп ОЙ тех 1 пк е 11 мож. т 11 д йт 11)1 мепеппе при стдтпстпче 11 молелпрснации па электр)пи),х вы июлит .нных)машинах и при защите информации ввычислительных сс.тяэс,Цель изобретения - упрощение юепердтора,11 д фию, 1 приведена функционалная схема юецердторд случдпцых чисел;на Фию, 2 и 3 - примерь коцкретцоюовыполнения функциональных схем блока управления и коммутатора соответственно; на фию. , - ми)сОпроюрдм)я 5работы .цРрдтоэа случайных писец,Генератор сэ)уч 1 пых чсеп ссще)жит первичный источникрднцомерцораспредетепцых (случдйцых) чиселблок 2 памяти, регистр 3 пдмятисум с)мдтор 4, группу 5 элементов И, коммутатор 6,схему 7 сравнения, блок 8управления, входы 9 и 10 юруппу вь 1 ходов 11.Блок 8 управления (фию. 2) содержит генератор 12 сицхроимпульсон,элемент 13 И юруппу триггеров 14111, элемент 15 НЕ, де 1)и)рдтэр 6,группу элементов И 17, - 17 , группуэлементов ИЛИ 18,-18 , группу вха- ЗО;ээ26, -267 и вторую 27 -27, юрупппы5входонвход 28 и группу выходов 29 в97На этапе настройки генератораспучайцых чисел нд воспроизведение Озаданной функции рдспредс.ления Г(х),функция Г(х) яппроксимируется Отэезкдми прямой лицин. При этом областьсуцествонаки 51 функции )(х) рдзб;на, пется ца И=2 равных участковд1 сджд 10 ячейку пям 5 Ги юнеэаторд слуЧайНЫХ ЧИСЕЛ - 5) ДГЭЭЦЯЮТСЯ Х, И .1,) хЗдесь х, - значение аргументаФункции К(х) н пдчдлс 1.-юо участкаапс:роксимдции х - дпипа Э-юэ 50участка дппроксимдц и, ). = О,1-1 -ескость памяти ге. ераторд. В данномгенераторе кд)дому числу К стднонится н соотнетс 111 е м 1 ожсс:тнох. + К . с требуемым законом распре гг ,.57деления юде , - )дни)мерно рдспределецнье цд ипт ",: валсО, л х.) случайи 1 А числа, В результате функцияраспределения б 7, ет представ.ед н пыхогп)ом и т к. случдйпых чпсеп пепас)ром и 1Тд:11 п 11 х Гочс.к хПРИ)Д)1 Яа 1 ИХ ПСМ 1 У КажемОГО УЧЛСТкд дппр)1 смдцип, д множеством точек;.Н пмс)шяих здддсное рдспределеппе. ри этом количество различцихслучдйьсх чисел, снимаемых с выходаюепс)рдтора, будет определяться неемкостьк) пдмяти 1 а разрядностью чисел х + К . Нд фию. 1 представле 7цд функциональная схема юецератора,формирующего случайные числа с требуемым законом распределения, представленные н форме с фиксированнойпамяти внутри интервала-1,В блоке 2 пдмяти числа х. хранятся1н обратном ходе, а цакапливаюпий сумматоР 4 опеРаЦию сложепиЯ х,Кг1также осуществляет в обратном коде(при этом К всегда положительноечисло, д х. может быть как положительным, тдк и отрицательным).Предлаюаемый генератор случайныхчисел работает в соответствии с микропрограммой, приведенной на фию. 4.Блок 8 управления формирует управляющие сиюпалы у ,= 1,5,По задне(му фронту сигнала у , поступающего1нд синхронход генератора 1, вырабатывается очередное ранномерно распределенное число, Под действием сигнала у происходит чтение из блока 2памяти чисел, адрес которых задаетсяи старшими разрядами генератора 1(разрядами числа К,) По этому адресу К, н ячейке записано два числах и Дх,)причем х, представлено в1обратном ходе н Форме с фиксированной запятой, а положительное нормализованное число Лх = 1",2 - вяформе с плавающей запятой. Очевидно,.что Лх с 1. Под действием сиюнала у прочитанное из блока 2 памя 3ти число х. записывается в накапли 1нающий сумматор 4, порядок р числасх, записывается н регистр 3, а1мацтиса М поступает на первую группу нходон комбинационной схемы 7сравнения. Наконец, под действиемсиюпала у число, поступившее навторую группу нходон коммутатора 6,проходит через него на вторую группу входов сумматора 4, юде и суммируется с х,В схеме 7 сравнения под действием сиюцд:а у происходит сравнениемантиссы Ы с равномерно распределенным н интервале .0,13 случайнымчислом К, снимаемым с п младших разрядов генератора 1. ЕслиК с М, то на выходе схемы 7 сравнения вырабатывается единичный сиг 5нал 2 , который поступает в блок 81управления. Если К ) М, то 21= О.Сигнал 2, = 1 говорит о том,что число К равномерно распределенов интервале О, М 3, поскольку КМ, 10причем 0,5М с 1, так как дх; -нормализованное число. В коммутаторе6 число К преобразуется в числоК путем сдвига на р разрядов в стогрону младших разрядов, где р 15порядок числа дх,. В результатеполучается равномерно распределенноев интервале 0, йхслучайноечисло К, которое суммируется в сумматоре 4 с х . под действием сигнала у 4. Таким образсм, регистр З,коммутатор 6 и схема 7 сравнения служатдля получения чисел К,равномернораспределенных в указанном интервале. 25Сумматор 4 имеет два управляющихвхода 17 и Ч . Под действием сигнала у , поступающего на вход Чпроисходит запись числа к. в регистр результата накапливающего сум- ЗОматора 4. Поскольку регистр результата сумматора 4 выполнен на двухступенчатых триггерах, то число х.появится на выходах сумматора 4 (навыходах регистра результата сумматора) в момент действия заднего фронта сигнала у . Под действием сигна 3ла у , поступающего на вход Ч,происходит суммирование числа х , уженаходящегося в сумматоре 4, с чис Олом К , снимаемым с выходов коммутатора 6. В момент действия сигнала у- эта сумма пройдет через групУпу 5 элементов И на выходы 11 генератора (сигнал уна микропрограмме не показан, поскольку у этоесть сигнал у, который проходитна пятый выход блока 8 управленияне всегда, а только при переходе микпрограммного автомата из состоянияа в состояние а(фиг. 2 и 4).Таким образом, происходит формирование случайного числа с требуемым законом распределения,Рассмотрим теперь случай 21 = О.Сигнал 2.= 0 указывает на то,чтоКМ й, следовательно, число Квышло за пределы интервала 0, л х.3.Поэтому это число К не может быть использовано для формирования очеред-, ного случайного числа с требуемым законом распределения, поскольку К не является равномерно распределенным числом в указанном интервале. В этом случае процедура формирования случайного числа с требуемым законом распределения начинается с самого начала, т,е, с выработки равномерно распределенного случайного числа генератором 1 под действием сигнала у (в микропрограмме на фиг. 4 в случае 2 = 0 устройство управления переходит из состояния а в состояние а с выдачей сигнала у ) ."1 Далее опять происходит сравнение нового числа К с мантиссой М , Указанная процедура будет повторяться до тех пор, пока не выполнится условие К с М. В случае Кт ( М сигнал 2 принимает единичное значение и предлагаемый генератор сформирует новое случайное число с требуемым законом распределения так, как это было уже описано. Поскольку х является нормализованным чис 1лом, то мантисса этого числа лежит в диапазоне 0,5М1, Считая, что среднее значение мантиссы М примерно равно 0,75, получим,что вероятность неблагоприятного события К ) М равна примерно 0,25, поскольку К равномерно распределено в интервале 0, 1 . Поэтому в среднем только в одном случае из четырех будет выполняться условие К т М, а в остальных трех случаях КМ. Следовательно, количество неудачных попыток сформировать случайное число с требуемым законом распределения в среднеи не будет превышать 257, а поэтому быстродействие такого генератора будет достаточно высоким (в среднем на получение одного случайного числа требуется не более 2,5 тактов работы генератора). В известном устройстве для получения одного ш-разрядного случайного числа требуется ш тактов работы генератора, поскольку в каждом такте формируется только один разряд случайного числа с заданным эаконом распределения.Рассмотрим теперь работу отдельных блоков предлагаемого генератора. Ба фиг. 2 приведена функциональная схема блока 8 управления. В этой схеме генератор 12 синхроимпульсов, 5 134519элемент 13 И и триггер 14 образуюттак называемую схему запуска 1 Триггер 14 устанавливается в единичноец ,цсостояние сигналом Пуск , поступа 5ющим ца первый 19, вход блока управления. В результате открываетсяэлемент 13 И, сицхроимпульсы с выхода генератора 12 начинают проходитьчерез элемент 13 И на сицхронходытриггеров 14 , 1414 и дешифратора 16, и блок управленйя начинаетсвою работу. После поступления на вто-,рой вход 19 блока управления сигнала окончания работы Е 4 вырабатывается сигнал, сбрасывающий триггер141 н нулевое состояние, и блок уп"равлеция прекращает свою работу.Посигналу Пуск также устанавливаются в исходное нулевое состояние триггеры 14 и 14(состояние а, намикропрограмме).В схеме блока 8 управления триггеры 14 и 14 , дешифратор 16,эле"менты И 17, - 174, элементы ИЛИ 2518, - 18 образуют схему управляющего автомата, интерпретирую- щего микропрограмму, приведеннуюна Фиг, 4,Триггер 14 используется для временного хранения сигнала Кпоступающего на третий вход 195 блока 8 управления с выхода схемы 7сравнения. Элемент 15 НЕ служит дляполучения инверсного значения сигнала Е, В зависимости от значений35сигналов Е, и К управляющий автомат Формирует уйранляющие сигналы у, у, у и у 4 согласцо микропрограмме,прйнеденной на фиг. 4. Элемент175 И служит для получения сигнала у 5, не показанного ца микропрограмме и, следовательно, це формируемогосхемой управляющего автомата,По существу сигнал у это сигнал у .Од 5 3нако н отличие от у сигнал у 5 Формируется только при переходе управляющего автомата из состоянияа 1 в состояние ат.е. когда получено очередное случайное число с требуемым законом распределения и необ- . ходимо выдать это число на выход генератора. Поэтому на второй входэлемента 175 И поступает сигнал. у, а на первый вход - сигнал с третьего выхода дешифратора 16 (на третьем выходе дешифратора 16 единичный сигнал будет в том случае. когда управляющий автомат цаходится в состоянии а). При синтезе управляющего анто 6мата была прицята следующая кодировка внутренних состояний автомата: состояние а, представлено кодом 00, состояние а, в . О 1, состояние а - 11, состояние а, - 10. Сам управляющий автомат построен по классической схеме микропрограммного автомата и синтезирован по известной методике, Блок управления имеет пять выходов. На 1-м ныходе 20 устройства управления Формируется сигнал у 1 - 1,5, причем сигналы у , у у , у снимаются с выходов управляющего автомата,а сигнал у 5 - с выхода элемента 17 И. На первый вход 19, блока управления поступает сиг" нал "Пуск", на второй вход 19 сигнал окончания работы 2,а на третий вход 19 - сигнал Е, с выхода схемы 7 сравнения,Все сигналы Е Е у. (кроме у ), а также состояния а айтомата указаны на микропрограмме принеденной на Фиг. 4. В схеме блока управления используются двухступечатые синхронные триггеры 14,-14 причем триггеры 14и 14 э имеют также асинхронные установочные входы.На фиг. 3 приведен пример конкретного выполнения коммутатора 6 для случая 2-разрядного порядка р и четырехразрядного числа К. Порядок р с выходов регистра 3 поступает на первую группу входов коммутатора 6 (входы 26, и 26 ), число К- на вторую группу входов (входы 27 - 274),а управляющий сигнал у 4 - на синхровход коммутатора (вход 28). Коммутатор имеет семь выходов 29;, 1 = 1,7. В схеме коммутатора используется дешифратор 2 1 на четыре выхода и четыре группы двухвходовых элементовИ, допускающих возможность монтажного обьединеьия их выходов (например элементы И с открытым коллектором, выходы которых можно объединять и через резистор подключать к источнику питания, либо другие типы элементов И, также позволяющие получать монтажное ИЛИ). Иэ приведенной Функциональной схемы коммутатора нидцо,что при р = 0 единичный сигнал будет только на первом выходе дешифратора 21 и поэтому разряды числа К через первые элементы И каждый группы пройдут на первые четыре выхода коммутатора (ныходы 29, - 29 4). При р = 1 единичный сигнал бу134519 дет на втором выходе дешифратора 21и разряды числа В через вторые элементы И каждой группы пройдут на выходы 29 - 29 коммутатора,т.е. сосдвигом на один разряд. Аналогичнопри р = 2 число К проходит на выходы коммутатора со сдвигом на днаразряда, а при р = 3 на три разряда в сторону младших раэрядон. Таким образом, в коммутаторе осуществляется сдвиг числа К на р разря-.дов. Аналогично строится схема коммутатора и на большее число входови выходов. 10 15 Формула изобретения ными входами второго и третьего триггерон и является входом "Пуск" генератора, входом "Стоп" которого является вход элемента НЕ, выход которого соединен с первым входом второго элемента И, выход которого соединен 50 с первым входом первого элемента ИЛИ,выход которого соединен с единичным входом второго .триггера, выход которого соединен с первым входом дешифратора, первый выход которого сое. динен с вторым входом первого эле" мента ИЛИ и с первым входом второго Генератор случайных чисел, содержащий первичный источник равномерно распределенных случайных чисел,первая группа выходов которого соединена с первой группой входов схемы сравнения и с первой группой информационных входов коммутатора, вторая группа информационных входов которого соединена с выходами разрядов ре- . гистра памяти, блок памяти, первая группа выходов которого соединена с второй группой входов схемы сравнения,группу элементов И , о т л ич аю щ и й с я тем,что, с целью уп- рощения, он содержит сумматор и блок управления, содержащий шесть элементов И, четыре элемента ИЛИ, элемент НЕ, дешифратор, четыре триг 35 гера и . генератор тактовых импульсов, выход которого соединен с первым входом первого элемента И и с синхронизирующим входом перного тригге-. ра, единичный выход которого соединен с вторым входом первого элемента И, выход которого соединен с синхронизирующими входами дешифратора, второго, третьего и четвертого триг-геров, единичный вход первого тригге ра объединен с установочными нуле 418элемента ИЛИ, выход которого соединен с синхронизирующим входом первичного источника равномерно распределенных случайных чисел, вторая группа выходов которого соединена с группой адресных входов блока памя-ти,вторая группа выходов которого соединена с входами соответствующих разрядон регистра памяти, а третья группа выходов блока памяти соединена с первой группой нходов сумматора,вторая группа входов которого соединена с группой выходов коммутатора, а группа выходов сумматора соединена с первыми входами соответствующих элементов И группы, выходы которых являются выходами разрядов случайного чйсла генератора, выход второго элемента И соединен с первым входом третьего элемента ИЛИ,второй вход которого подключен к второму выходу дешифратора и к единичному входу третьего триггера, единичный выход которого соединен с вторым входом дешифратора, третий выход которого соединен с вторым входом второго элемента И и с первым входом третьего элемента И, второй вход которого соединен с входом элемента НЕ, а выход третьего элемента И соединен с нулевым входом перного триггера и с первым входом четвертого элемента ИЛИ, выход которого соединен с нулевым входом третьего триггера, четвертый выход дешифратора соединен с вторым входом второго элемента ИЛИ и с первыми входами четвертого и пятого элементов И, вторые входы которых подключены соответственно к еди ничному и нулевому выходам четвертого триггера, выход четвертого элемента И соединен с нулевыми входами второго и четвертого триггеров, с управляющим входом коммутатора и с входом "Суммирование" сумматора,вы" ход пятого элемента И соединен с вторым входом четвертого элемента ИЛИ, третий выход дешифратора соединен с первым входом шестого элемента. И, выход которого соединен с вторыми входами элементов И группы, выход третьего элемента ИЛИ соединен с вторым входом шестого элемента И и с синхронизирующими входами блока памяти, регистра памяти, сум- матора.и схемы сравнения, выход которой соединен с единичным входом четвертого триггера.1345191 4 5 зводственно-полиграфическое предприятие, г. Ужгород, ул. Проектная, 4 Составитель А.Караседактор М.Келемеш Техред М.Дидык аказ 4920/47 Тираж 670 ВНИИПИ Государственного комитета ССС по делам изобретений и открытий 113035, Москва, Ж, Раушская наб., Корректор С,Чер 1Подписное