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

(504 С 0 Щ АТЕИТНВБИБЛ 1 РЕТЕН ТЕЛЬСТВУ юл. У 27авиационный инстит в8)свидетельст С 06 Р 7/58 идетельство С 06 Р 7/58 СЛУЧАЙНЫХ ЧИ СС 198 ССР выч е относится кке, Предназначлучайных чисел ено для с заГОСУДАРСТВЕННЫЙ НОМИТЕТПО ИЗОБРЕТЕНИЯМ И ОТНРЫТИЯПРИ ГКНТ СССР ОПИСАНИЕК АВТОРСКОМУ СВИ(57) Изобретени лительной техн генерированияБОип 149578 данным законом распределения и можетнайти применение при статистическоммоделировании на ЭВМ, Цель изобретения состоит в повьппении точностивоспоиэведеиия заданного распределения, Введение второго регистра 4,элемента ИЛИ 7, преобразователя 9 ивторого коммутатора 12.позволяет повысить точность воспроизведения заданного распределения эа счет неравномерного разбиения области значенийфункции распределения, при которомдлина участка аппроксимации выбирается исходя из заданной точности воспроизведения,э.п.ф-лы, 4 ил.Изобретение относится к вычислительной технике и может найти применение при статистическом моделированиина электронных вычислительных машинах.Целью изобретения является повышение точности воспроизведения заданного закона распределения за счет неравномерного разбиения области значений Функции распределения, при ко-.тором длина участка аппроксимациивыбирается исходя из заданной точности воспроизведения.На фиг.1 приведена функциональнаясхема генератора случайных чисел;на Фиг.2 н 3 - функциональные схемы.блока управления и преобразователяна Фиг,4 - микропрограмма работы генератора случайных чисел.Генератор случайных чисел содер"жит: датчик 1 равномерно распределенных случайных чисел, блок 2 памяти,первый регистр 3, второй регистр 4,сумматор 5, группу 6 элементов И,25элемент ИЛИ 7, блок 8 управления,преобразователь 9, первый коммутатор 1 О, схему 11 сравнения, второйкоммутатор.12,Блок 8 управления (фиг.2) содер 30жит генератор 13 синхроимпульсов,элемент И 14, три триггера 15 -15 з,первый элемент НЕ 16, дешифратор 17,группу 1 8 -1 8элементов И, группу19-19элементов ИЛИ, второй элемент НЕ 20, третий элемент НЕ 21.Преобразователь 9 (Фиг.3) содержит дешифратор 22 и два элементаИЛИ 23 и 23 гОтличительной особенностью предлагаемого генератора случайных чиселявляется то, что он позволяет с бо;лее высокой точностью воспроизводитьзаданное распределение. Более высокая точность достигается за счет того что отдельные участки Функциираспределения, в свою очередь, делятся на несколько частей, В результатепоявляется аппроксимация, чтобы погрешность аппроксимации не превышалазаданной величины. Другими словами,те участки, где погрешность аппроксимации велика, можно проходить с меньшим шагом аппроксимации Д х., а остальные участки - с большим шагом6 х . В результате перераспределения1длин участков аппроксимации можнообеспечить заданную точность, не увеличивая общего количестве участков аппроксимации, т.е. не увеличивая аппаратурных затрат.Генератор работает следующим образом,Первоначально область определенияфункции распределения делится на Иравных участков, где И = 2". Здесьи - разрядность равномерно распределенных случайных чисел К , снимаемыхс первой группы выходов первичногоисточника 1, В дальнейшем отдельныеучастки, в свою очередь, могут бытьразделены на несколько равных частей,В соответствии с принятым способом аппроксимации заданного распределения первоначально необходимо случайным образом определить номеручастка аппроксимации, из которогона выход генератора выдается случайное число с требуемым законом распределения. С этой целью датчик 1 Формируетравномерно распределенное случайноечисло Ккоторое и определяет номер первоначально выбранного участка. Еслиокажется, что первоначально выбранный участок был, в свою очередь, разделен на более мелкие участки, товновь формирует"я случайное число К ,1которое определяет порядковый номеручастка аппроксимации внутри первоначально выбранного участка, Описанная процедура может повторяться дотех пор, пока не будет определенокончательный номер выбранного участка аппроксимации, т,е, в предлагаенмом генераторе допускается многократное разбиение требуемых участков наболее мелкие части, После определения номера выбранного участка аппроксимации на выходе генератора с по-мощью сумматора 5 окончательно формируется случайное число 8 с требуемым1законом распределения я = х.+ В.,Здесь х; - значение аргумента функции распределения,в начале выбранно".,го 1-го участка аппроксимации. К, -равномерно распределенное на интервале О,дх, неслучайное число, д х,длина выбранного участка аппроксимации (длина шага аппроксимации).При подготовке генератора к работе в блок 2 памяти записывается вся информация, характеризующая закон распределения, т,е, х ., Дх а также служебная информация. Поскольку в предлагаемом генераторе для определе 14 ния номера участка аппроксимации используется равномерно распределенное случайное число К ., то это число К.1и используется в качестве адреса ячейки памяти, в которой записаны х . и Дх;, относящиеся к первоначально . выбранному участку аппроксимации. Однако, если выбранный с помощью К, участок делится в свою очередь на несколько частей, то по адресу К в блоке 2 памяти записывается базовый адрес А и число г. Базовый адрес используется при формировании адреса ячеек памяти, в которых записаны хи Дх относящиеся к участкам аппроксимации, полученным в результате разбиения первоначального интервала на более мелкие части, а число 2 определяет количество этих новых разбие-, ний первоначального участка. В последний разряд каждой ячейки памяти записывается также служебный признак г . Если признак г З = О, то это. означает, что в данной ячейке записаны х 1 и дх Если гз= 1, то в данной ячейке записаны А и г, В блоке 2 памяти х, хранится в обратном коде в1форме с фиксированной запятой, д х; - в форме с плавающей запятой.Предлагаемый генератор случайных чисел работает в соответствии с микропрограммой, приведенной нафиг.4. В микропрограмме приняты следующие обозначения: г - сигнал с выхода схемы 11 сравнения; г - сигнал "Стоп", гэ - признак вида информации, хранящейся в блоке 2 памяти, уу =1,6 - управляющие сигналы, формируемые блоком 8 управления, интерпретирукщим приведенную микропрограмму,а - состояния блока 8 управления. По заднему фронту сигнала у , поступающего на синхронизирующий вход датчика 1, формируется очередное равномерно распределенное случайное число. Под действием сигнала упроисходит чтение из блока 2 памяти чисел по адресу К, (адрес К, через второй коммутатор 12 проходит с первой группы выходов датчика 1 на адресные входы блока 2 памяти). Под действием сигнала уз прочитанное из блока 2 па-мяти число х . записывается в накапливающий сумматор 5, порядок Р числа Лх поступает в первый регистр 3, а мантисса М - во второй регистр 4, В случае, когда из выбранной ячейки происходит чтение А и г, то базовый 957886адрес А под действием сигнала уз записывается в накапливающий сумматор 5,а число г - н первый регистр 3, Влюбом случае признак гз записывается в последний разряд регистра 4.Под действием сигнала у происходитформирование числа К = х .+ К. Пригэтом число Кформируется в первомкоммутаторе 1 О, а операция сложениях . и Квыполняется в накапливающемсумматоре 5. Под действием сигналау сформированное в сумматоре чис 5ло е с требуемым законом распределения через группу 6 элементов И проходит на выход генератора. Под действием сигнала упроисходит чтениеиз блока 2 памяти чисел по адресуА, где А - базовый адрес, поступающий на первую группу входов коммунатора 12 с выходов сумматора 5,равномерно распределенное г-разрядное случайное число, которое проходит через коммутатор 12 на младшие25 разряды адресной группы входов блока 2 памяти.В схеме 11 сравнения происходитформирование сигнала г , при этомг= О, если КтМ, и г,= 1.при КМ.Здесь К - равномерно распределенноеслучайное число, снимаемое с второйгруппы выходов датчика 1 и поступающее на вторую группу .входов схемы 1сравнения. Мантисса М поступает напервую группу входов схемы 11 сравнения с выходов регистра 4.Признак гз= 1 означает, что в выбранной ячейке памяти записаны А и г.Другими, словами, если гз= , то впроцессе формирования очередного случайного числа я мы попали на участокаппроксимации, который был поделенна более мелкие части. В этоМ случаенеобходимо сформировать новый адрес46 ячейки памяти, в которой записаныискомые х; и ах . Этот адрес формируется под действием сигнала у вовтором коммутаторе 12, на первуюгруппу входов которого поступает базовый адрес А с выходов сумматора 5(в сумматор. 5 адрес А был записан впредшествующем также под действиемсигнала уз при чтении информации изблока 2 памяти, которое происходилопод действием сигнала у ). Сиг-.нал упоступает на управляющие входы коммутатора 12, разрешая тем са;мым прохождение базового адреса А. .Одновременно разрешается прохождениеслучайного числа, поступающего с первой группы выходов датчика 1 на вторую группу входов коммутатора 12. Количество разрядов случайного числа5определяется преобразователем 9,группа выходов которого подключена ктретьей группе входов коммутатора 12.Таким образом, преобразователь 9 управляет процессом прохождениячерез коммутатор 12, формируя на своихвыходах открывающие сигналы. В своюочередь, на группу входов преобразователя 9 поступает число г с первого регистра 3. Преобразователь 9 преобразует двоичное число г в унитарныйток, причем количество единичных сигналов на выходах равно самому числу г, В общем случае, через коммутатор 12 проходит г-разрядное число , 20причем г 6 п,где и - количество разрядов числа. Таким образом, на выходах коммутатора 1 2 формируется исполнительный адрес вида А , приэтом для правильной работы коммутатора младшие г разрядов базового адреса А должны быть нулевыми, посколькуэти разряды замещаются случайнымг-разрядным числом. Добавление вмладшие разряды исполнительного адреса случайного числа производится потому, что первоначальный интервал аппроксимации был разделен на 2 болеегмелких частей, и поэтому необходимослучайным образом выбрать один из2 интервалов внутри первоначально .выбранного интервала. Заметим, чтопо исполнительному адресу Амогутбыть записаны как х .и Дх , так и1 фА и г. Это необходимо для того, чтобы реализовать возможность многократного деления любого (не только первоначального) интервала на 2 частей.гПри поступлении сигнала уг на первыйсинхронизирующий вход коммутатора 12на его выходы проходит равномерно,распределенное и-разрядное случайноечисло К,. Это число К, используетсяв качестве адреса ячейки памяти, вкоторой хранится информация, относягщаяся к одному из 2 первоначальныхинтервалов, При этом 1 старших разрядов этого адреса являются нулевыми,а общий объем блока 2 памяти равен2 " ячеек. Обычно 1 не велико лежитв пределах 1 4 2,На фиг,2 приведена схема блока 8управления, который работает в соответствии с микропрограммой, приведенной на фиг,4. Сигнал "Пуск" поступает на вход блока 8 и переводит триггер 15, в единичное состояние. В результате открывается элемент И 14 и импульсы с выхода генератора 13 поступают на синхронизирующие входы триггеров 15 г и 15 и дешифратора 17. Блок 8 управления начинает свою работу и на его выходах формируются уп-. равляющие сигналы у , где д - порядковый номер выхода в группе выходов-. На микропрограмме не показан сигнал у , который совпадает с сигналом у, но в отличие от у формируется тольгко при переходе блока 8 из состояния а з в состояние а г . Сигналы я в г и гз поступают соответственно на входы задания логических условий блока 8 управления, В зависимости от значения этих сигналов, а также от состояния а; и происходит формирование управляющих сигналов у . В част 1ности, при поступлении сигнала г г иСтоп, на выходе элемента И 18 форй Мируется сигнал, который переводит триггер 15, в нулевое состояние и закрывает элемент И 14, В результате блок 8 управления прекращает свою работу, поскольку тактовые импульсы не проходят через элемент И 14 на синхронизирующие входы дешифратора 17 и триггеров 15 г и 15 , В схеме блока 8 управления для йсключения гонок и неустойчивых состояний используются двухступенчатые тригге-; ры 15 , 15 , 15 , причем триггеры 15 г и 15имеют также асинхронные установочные входы.формула изобретения1 . Генератор случайных чисел, содержащий датчик равномерно распределенных случайных чисел, блок управления, блок памяти, регистр, коммутатор, сумматор,. схему сравнения, группу элементов И, причем первая группа выходов датчика равномерно распределенных случайных чисел соединена с первой группой информационных входов коммутатора и с первой группой входов схемы сравнения, выход "Равно" которой соединен с первым входом логических условий блока управления, первый выход которого соединен с входом опроса датчика равномерно распределенных случайных чисел, первая группа выходов блока памяти5 10 15 20 соединена с первой группой информационных входов сумматора, втораягруппа информационных входов которого соединена с выходами коммутатора,вторая группа информационных входовкоторого соединена с группой выходов регистра группа информационных входов которого соединена с второй группой выходов блока памяти,второй выход блока управления соединен с входом записи регистра и с вхоцом записи сумматора, выходы которого соединены с первыми входами элементов И группы, вторые входы которых соединены с третьим выходом блока управления, четвертый выход которого соединен с входом разрешениясуммирования сумматора и с управляющим входом коммутатора, входы пПуск" и "Стоп" блока управления являются входами "Пуск" и "Стоп" генератора соответственно, выходы элементов И группы являются разрядными выходами генератора, о т л и ч а ю щ и й с я тем, что, с пелью повышения точности воспроизведения заданного закона распределения за счет неравномерногоразбиения области значений функциираспределения, в него введены дешифратор, три элемента ИЛИ, второй коммутатор и второй регистр, группа выходов которого соединена с второйгруппой входов схемы сравнения,выход младшего разряда второго регистра соединен с вторым входом логических условий блока управления, пятыйвыход которого соединен с первым управляющим входом второго коммутатора и с первым входом первого элементаИЛИ, второй вход которого соединен с шестым выходом блока управления, свторым управляющим входом второгокоммутатора и с входом записи дешифратора, первый информационный выходкоторого соединен с первым входомвторого элемента ИЛИ, с первым входом третьего элемента ИЛИ и с первымвходом первой группы информационныхвходов второго коммутатора, втораягруппа информационных входов которого соединена с второй группой выходов датчика равномерно распределенных случайных чисел, третья группаинформационных входов второго коммутатора соединена с группой выходовсумматора, вход записи второго регистра соединен с вторым выходом блока управления, выход первого элемен 25 30 35 40 45 50 55 та ИЛИ соединен с входом чтения блока памяти, третья группа выходов которого соединена с группой информационных входов второго регистра, группаинформационных входов дешифраторасоединена с группой информационныхвыходов первого регистра, группа информационных выходов второго коммутатора соединена с группой адресныхвходов блока памяти, второй выхоД дешифратора соединен с вторыми входамивторого и третьего элементов ИЛИ,третий выход дешифратора соединен стретьим входом третьего элемента ИЛИ,выход второго элемента ИЛИ соединенс вторым входом первой группы информационных входов второго коммутатора,. третий вход первой группы информационных входов которого соединен свыходом третьего элемента ИЛИ. 2, Генератор по п.1., о т л ич а ю щ и й с я тем, что блок управления содержит шесть элементов И,четыре элемента ИЛИ, три элемента НЕ,. три триггера, дешифратор и генератор тактовых импульсов, выход которого соединен с первым, входом первого элемента И и тактирующим входом первого триггера, прямой выход которого соединен с вторым входом первого элемента И, выход которого соединен с тактирующими входами второго и третьего триггеров и входом записи дешифратора, первый выход которого соединен с первыми входами первого и второго элементов ИЛИ, выход первого элемента ИЛИ является первым выходом блока управления, выход второго элемента ИЛИ соединен с единичным входом второго триггера, прямой выход которого соединен с первым информационным входом дешифратора, второй инфор-, мационный вход которого соединен с прямым выходом третьего триггера, обнуляющий вход которого соединен с обнуляющим входам второго триггера, с единичным входом первого триггера и с входом "Пуск" блока управления, вход "Стоп" которого соединен с первым входом второго элемента И и входом первого элемента НЕ, выход которого соединен с первым входом третьего элемента И, выход которого соединен с вторым входом второго элемента ИЛИ и первым входом третьего элемента ИЛИ и является третьим выходом блока управления, первыйвход задания логических условий которого соединен с первым входом четвертого элемента И и входом второго элемента НЕ, выход которого соединен с первым входом пятого элемента И, вы 5 ход которого соединен с вторым вхо" дом первого элемента ИЛИ, третий вход которого соединен с выходом четвертого элемента ИЛИ, который являет ся вторым выходом блока управления, второй вход заданий логических условий которого соединен с первым входом шестого элемента И и через третий элемент НЕ соединен с вторыми входами пятого н четвертого элемен-. тов И выход которого соединен с ну.левым входом второго триггера и является четвертым выходом блока уп равления, второй выход дешифраторасоединен с единичным входом третьеготриггера и вторым входом третьегоэлемента ИЛИ, выход которого соединен с первым входом четвертого элемента ИЛИ и является пятым выходомблока управления, третий выход дешифратора соединен с вторыми входамивторого н третьего элементов И, выход второго элемента И соединен снулевыми входами первого и третьеготриггеров, четвертый выход дешифратора соединен с третьими входами четвертого и пятого элементов И и с вторым входом шестого элемента И, выходкоторого соединен с вторым входомчетвертого элемента ИЛИ и являетсяшестым выходом блока управления.