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

iU(

О

СП

00 СХ)

Изобретение относится к вычислительной технике и может найти применение при статистическом моделировании на электронных вычислит ель ньпс машинах.

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

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

Генератор случайных чисел содержит- датчик 1 равномерно распределен- нь1х случайных чисел, блок 2 памяти, первый регистр 3, второй регистр 4, сумматор 5, группу 6 элементов И, элемент ИЛИ 7, блок 8 управления, преобразователь 9, первый коммутатор 10, схему 11 сравнения, второй коммутатор: 12,

Блок 8 управления (фиг.2) содержит генератор 13 синхроимпульсов, элемент И 14, три. триггера первый элемент НЕ 16, депшфратор 17, группу 18J-18J элементов И, группу

А элементов ИЛИ, второй элемент НЕ 20, третий элемент НЕ 21.

Преобразователь 9 (фиг.З) содержит дешифратор 22 и два элемента ИЛИ 23,1 и 23..

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

0

5

0

5

0

5

0

5

увеличивая общего количестве участков аппроксимации, т.е. не увеличивая аппаратурных затрат.

Генератор работает следующим образом.

Первоначально область определения функции распределения делится на N равных участков, где N 2. Здесь п - разрядность равномерно распределенных случайных чисел R ,снимаемых с первой группы выходов первичного источника . В дальнейшем отдельные участки, в свою очередь, могут быть разделены на несколько равных частей.

В соответствии с принятым способом аппроксимации заданного распределения первоначально необходимо случайным образом определить номер участка аппроксимации, из которого на выход генератора вьщается случайное число с требуемым законом распределения. С этой целью датчик 1 формирует равномерно распределенное случайное число R,,которое и определяет номер первоначально выбранного участка. Если окажется, что первоначально выбранный участок был, в свою очередь, разделен на более мелкие участки, то вновь формируется случайное число R , которое определяет порядковый номер участка аппроксимации внутри первоначально выбранного участка . Описанная процедура может повторяться до тех пор, пока не будет определен окончательный номер выбранного участка аппроксимации, т.е. в предлагаем мом генераторе допускается многократное разбиение требуемых участков на более мелкие части. После определения номера выбранного участка аппроксимации на выходе генератора с по-: мощью сумматора 5 окончательно формируется случайное число g с требуемым законом распределения g R . Здесь X j - значение аргздаента функ- Iции распределения,в начале выбранног го i-ro участка аппроксимации, К1 равномерно распределенное на интервале 0,х j случайное число, Лх j - длина выбранного участка аппроксимации (длина шага аппроксимации).

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

3fo число R.

случайное число RJ, то и используется в качестве адреса ячейки памяти, в которой записаны х . иДх,-, относящиеся к первоначально выбранному участку аппроксимации. Однако, если выбранньш с помощью R участок делится в свою очередь на несколько частей, то по адресу R в блоке 2 памяти записывается базовый адрес А и число г. Базовый адрес используется при формировании адреса ячеек памяти, в которых записаны Xj и Лх., относящиеся к участкам аппроксимации, полученным в результате разбиения первоначального интервала на более мелкие части, а число 2 определяет количество этих новых разбие-. НИИ первоначального участка, В последний разряд каждой ячейки памяти записывается также служебный признак Z . Если признак z j О, то это означает, что в данной ячейке записа- ны х и 4xj, Если Z j 1 , то в данной ячейке записаны Лиг. В блоке 2 памяти Xj хранится в обратном коде в форме с фиксированной запятой,/1 х-- в форме с плавающей запятой.

Предлагаемый генератор случайных чисел работает в соответствии с микропрограммой, приведенной на фиг,4 В микропрограмме приняты следующие обозначения: z - сигнал с выхода схемы 11 сравнения; z - сигнал Стоп, z - признак вида информации, хранящейся в блоке 2 памяти, у.,у. 1,6 - управляющие сигналы, форми-

Q 5 о 5

0

5

адрес Л под действием сигнала у за- письгеается в накапливающий сумматор 5, а число г - в первый регистр 3, В любом случае признак Zj записьгоает- ся в последний разряд регистра 4, Под действием сигнала у происходит формирование числа 8 х .+ R . При этом число R j формируется в первом коммутаторе 10, а операция сложения X j и R выполняется в накапливающем сумматоре 5. Под действием сигнала у сформированное в сумматоре число g с требуемым законом распределения через группу 6 элементов И проходит на выход генератора. Под действием сигнала у происходит чтение из блока 2 чисел по адресу А , где А - базовый адрес, поступающий на первую группу входов коммут а- тора 12 с выходов сумматора 5, - равномерно распределенное г-разряд- ное случайное число, которое проходит через коммутатор 12 на младшие разряды адресной группы входов блока 2 памяти.

В схеме 11 сравнения происходит формирование сигнала z, при этом z О, если , и z, 1 .при . Здесь RJ- равномерно распределенное случайное число, снимаемое с второй группы выходов датчика 1 и поступающее на вторую группу .входов схемы И сравнения. Мантисса М поступает на первую группу входов схемы 11 сравнения с выходов регистра 4,

Признак Zj 1 означает, что в выбранной ячейке памяти записаны А и t. Другими, словами, если гз 1 то в

Изобретение относится к вычислительной технике. Предназначено для генерирования случайных чисел с заданным законом распределения и может найти применение при статистическом моделировании на ЭВМ. Цель изобретения состоит в повышении точности воспроизведения заданного распределения. Введение второго регистра 4, элемента ИЛИ 7, преобразователя 9, второго коммутатора 12 позволяет повысить точность воспроизведения заданного распределения за счет неравномерного разбиения области значений функции распределения, при котором длина участка аппроксимации выбирается, исходя из заданной точности воспроизведения. 1 з.п. ф-лы, 4 ил.

руемые блоком 8 управления, интерпре- до процессе формирования очередного слу- тирующим приведенную микропрограмму, а - состояния блока В управления. По заднему фронту сигнала у , поступающего на синхронизирующий вход датчика 1, формируется очередное равно- 45 мерно распределенное случайное число, Под действием сигнала у происходит чтение из блока 2 памяти чисел по адресу R (адрес R через второй коммутатор 12 проходит с первой группы Выходов датчика 1 на адресные входы блока 2 памяти). Под действием сигнала УЗ прочитанное из блока 2 па- мяти число X . записьтается в накапли- вакяций cyMikiaTop 5, порядок Р числа их поступает в первый регистр 3, а мантисса М - во второй регистр 4, В случае, когда из выбранной ячейки

50

55

чайного числа g мы попали на участок аппроксимации, который был поделен на более мелкие части. В этоМ случае необходимо сформировать новый адрес ячейки памяти, в которой записаны искомые х- и Дх . Этот адрес формируется под действием сигнала у, во втором коммутаторе 12, на первую группу входов которого поступает базовый адрес А с выходов сумматора 5 (в сумматор 5 адрес А был записан в предшествующем также под действием сигнала уд при чтении информации из блока 2 памяти, которое происходило под действием сигнала у). Сиг-нал у поступает на управлякщие входы коммутатора 12, разрещая тем са|Мым прохождерше базового адреса А.

происходит чтение А и г, то базовый

процессе формирования очередного слу-

чайного числа g мы попали на участок аппроксимации, который был поделен на более мелкие части. В этоМ случае необходимо сформировать новый адрес ячейки памяти, в которой записаны искомые х- и Дх . Этот адрес формируется под действием сигнала у, во втором коммутаторе 12, на первую группу входов которого поступает базовый адрес А с выходов сумматора 5 (в сумматор 5 адрес А был записан в предшествующем также под действием сигнала уд при чтении информации из блока 2 памяти, которое происходило под действием сигнала у). Сиг-нал у поступает на управлякщие входы коммутатора 12, разрещая тем саМым прохождерше базового адреса А.

Одновременно разрешается прохождение

случайного числа, поступпютцего с первой группы выходов датчика 1 на вторую группу входов коммутатора 12. Количество разрядов случайного числа определяется преобразователем 9, группа выходов которого подключена к третьей группе входов коммутатора 12. Таким образом, преобразователь 9 управляет процессом прохождения че- рез коммутатор 12, формируя на своих выходах открывающие сигналы. В свою очередь, на группу входов преобразователя 9 поступает число г с первого регистра 3. Преобразователь 9 пре- образует двоичное число г в унитарный ток, причем количество единичных сигналов нд выходах равно самому числу г. В общем случае, через коммутатор 12 проходит г-разрядное число , причем ,где п - количество разрядов числа §. Таким образом, на выходах коммутатора 12 формируется исполнительный адрес вида А , при :: этом для правильной работы коммутато- ра младшие г разрядов базового адреса А должны быть нулевыми, поскольку эти разряды замещаются случайным г-разрядньш числом f. Добавление в младщие разряды исполнительного адре- са случайного числа производится потому, что первоначальный интервал аппроксимации был разделен на 2 более мелких частей, и поэтому необходимо

случайньЫ обра.зом выбрать один, из 2 интервалов внутри первоначально . выбранного инте15Вала. Заметим, что по исполнительному адресу А § могут быть записаны как х .иДх., так и.

N

А И Г. Это необходимо цпя того, чтобы реализовать возможность многократного деления любого (не только первоначального) интервала на 2 частей. При поступлении сигнала у на первый синхронизирующий вход коммутатора 2 на его выходы проходит равномерно /распределенное п-разрядное случайное число R,. Это число R, используется в качестве адреса ячейки памяти, в которой хранится информация, относящаяся к одному из 2 первоначальных интервалов. При этом 1 старщих разрядов этого адреса являются нулевыми, а общий объем блока 2 памяти равен 2 ячеек. Обычно 1 не велико лежит в пределах .

На фиг.2 приведена схема блока 8 управления, который работает в соответствии с микропрограммой, приведен

Q 5 0 5 0

5

ной на фиг.4. Сигнал Пуск поступает на вход блока .8 и переводит триггер 15, в единичное состояние. В результате открывается элемент И 14 и импульсы с выхода генератора 13 поступают на синхронизирующие входы триггеров 152 и 15.j и дешифратора 17. Блок 8 управления начинает свою работу и на его выходах формируются уп-. равлякмдие сигналы у, где i - порядковый номер выхода в группе выходов--. На микропрограмме не показан сигнал у, который совпадает с сигналом у, но в отличие от у 2 формируется только при переходе блока 8 из состояния ад в состояние а .Сигналы z,, z и z поступают соответственно на входы задания логических условий блока 8 управления. В зависимости от значения этих сигналов, а также от состояния а , и происходит формирование управляющих сигналов у.. В частности, при поступлении сигнала z Стоп на выходе элемента И 18 фор 4ируется сигнал, который переводит триггер 15, в нулевое состояние и закрьшает элемент И 14. В результате блок 8 управления прекращает свою работу, поскольку тактовые импульсы не проходят через элемент И 14 на синхронизирующие йходы дешифратора 17 и триггеров 15 и 15 . В схеме блока 8 управления для исключения гонок и неустойчивых состояний используются двухступенчатые тригге-т ры 15, 15, 15,, причем триггеры 15 и 153 имеют также асинхронные установочные входы.

Формула и

3 о

р е т е н и я

0

5

9

соединена с первой группой информационных вход ов сумматора, вторая группа информационных вхЬдов которого соединена с выходами коммутатора вторая группа информационных входов которого соединена с группой выходов регистра,, группа информацион ных входов которого соединена с второй группой выходов блока памяти, второй выход блока управления соединен с входом записи регистра и с вхо записи сумматора, выходы которого соединены с первыми входами элементов И группы, вторые входы которых соединены с третьим выходом блока управления, четвертый выход которого соединен с входом разрешения суммирования сумматора и с управляющим входом коммутатора, входы Пуск и Стоп блока управления являются входами Пуск и Стоп генератора соответственно, выходы элементов И группы являются разрядными выходами генератора, отличающийся тем, что, с целью повьшения точности воспроизведения заданного закона распределения за счет неравномерного разбиения области значений Фз нкции распределения, в него введены дешифратор, три элемента ИПИ, второй коммутатор и второй регистр, группа выходов которого соединена с второй группой входов схемы сравнения, выход младшего разряда второго регистра соединен с вторым входом логических условий блока управления, пятый выход которого соединен с первым равляющим входом второго коммутатора и с первым входом первого элемента ИЛИ, второй вход которого соединен с шестым выходом блока управления, с вторым управляющим входом второго коммутатора и с входом записи дешифратора, первый информационный выход которого соединен с первьгм входом второго элемента ИЛИ, с первым входом третьего элемента ИЛИ и с первым входом первой группы информационных входов второго коммутатора, вторая группа информационных входов которого соединена с второй группой выходов датчика равномерно распределенных случайных чисел, третья группа информационных входов второго коммутатора соединена с группой выходов сумматора, вход записи второго регистра соединен с вторым вьЬсодом блока управления, выход первого элемен9578810

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

15 третьим входом третьего элемента ИЛИ, выход второго элемента ИЛИ соединен с вторым входом первой группы информационных входов второго коммутатора, . третий вход первой группы информа20 ционных входов которого соединен с выходом третьего элемента ИЛИ.

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

45 мационный вход которого соединен с прямым выходом третьего триггера, обнуляющий вход которого соединен с обнуляющим входом второго триггера, с единичны: входом первого триггера

50 и с входом Пуск блока управления, вход Стоп которого соединен с первым входом второго элемента И и входом первого элемента НЕ, выход которого соединен с первым входом тре-

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

35

1А95788

вход задания логических условий которого соединен с первым входом четвертого элемента И и входом второго элемента НЕ, выход которого соединен с первым входом пятого элемента И, выход которого соединен с вторым входом первого элемента ИЛИ, третий вход которого соединен с выходом четм

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

ся вторым выходом блока управления, второй вход заданий логических условий которого соединен с первым входом шестого элемента И и через третий элемент НЕ соединен с вторыми входами пятого и четв-ертого элемен-. тов И выход которого соединен с ну- .левым входом второго триггера и является четвертым выходом блока

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

фие.З

Начало

гтп