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

 

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

СОК)3 СОВЕТСКИХ.

СОЦИАЛИСТИЧЕСКИХ

РЕСПУБЛИК д11 4 G 06 F 7/58!

ЩО

ПАТЕНТН9БИБД1

ОПИСАНИЕ ИЗОБРЕТЕНИЯ

К ASTOPCHOMV СВИДЕТЕЛЬСТВУ

ГОСУДАРСТВЕННЫЙ НОМИТЕТ

ПО ИЗОБРЕТЕНИЯМ И ОТКРЫТИЯМ

ПРИ ГКНТ СССР

1 (21) 4348503/24-24 (22) 24.12.87 (4&) 23.07.89. Бюл. У 27 (71 ) Казанский авиационный институт им. А.Н.Туполева (72) В.М.Тарасов (53) 681.3(088.8) (56) Авторское свидетельство СССР

У 1008737, кл. С 06 F 7/58, 1981, Авторское свидетельство СССР

11 1345191, кл. G 06 F 7/58, 1987. (54) ГЕНЕРАТОР СЛУЧАЙНЫХ ЧИСЕЛ (57) Изобретение относится к вычислительной технике. Предназначено для генерирования случайных чисел с за-

„„Я0„„1495788 А 1

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

1495788

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

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

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

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

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

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

Преобразователь 9 (фиг.3) содержит дешифратор 22 и два элемента

ИЛИ 23,, и 23 г °

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

V появляется аппроксимация, чтобы погрешность аппроксимации не превышала заданной величины. Другими словами, те участки, где погрешность аппроксимации велика, можно проходить с меньшим шагом аппроксимации 4 х., а oct тальные участки — с большим шагом

4x . В результате перераспределения

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

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

Первоначально область определения функции распределения делится на N равных участков, где N = 2". Здесь

n — разрядность равномерно распределенных случайных чисел R „, снимаемых с первой группы выходов первичного источника 1. В дальнейшем отдельные участки, в свою очередь, могут быть разделены на несколько равных частей.

В соответствии с принятым способом аппроксимации заданного распределения первоначально необходимо случайным образом определить номер участка аппроксимации, из которого на выход генератора выдается случайное число с требуемым законом распределения.С этой цельюдатчик 1 формирует равномерно распределенное случайное число К„которое и определяет номер первоначально выбранного участка. Если окажется, что первоначально выбранный участок был, в свою очередь, pasделен на более мелкие участки, то вновь формирует"я случайное число R, 19 которое определяет порядковый номер участка аппроксимации внутри первоначально выбранного участка., Описанная процедура может повторяться до тех пор, пока не будет определен окончательный номер выбранного участка аппроксимации, т.е, в предлагае мом генераторе допускается многократное разбиение требуемых участков на более мелкие части. После определения номера выбранного участка аппроксимации на выходе генератора с по- мощью сумматора 5 окончательно формируется случайное число g с требуемым

I законом распределения g = х.+ R., 2

Здесь х; — значение аргумента функ-! ции распределения,,в начале выбранно"., ro i-го участка аппроксимации, R равномерно распределенное на интервале (О,bx )случайное число, 4 х,длина выбранного участка аппроксимации (длина шага аппроксимации).

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

1 служебная информация. Поскольку в предлагаемом генераторе для определе14 ния номера участка аппроксимации используется равномерно распределенное случайное число R ., то это число R

1 1 и используется в качестве адреса ячейки памяти, в которой записаны х . и Ах; относящиеся к первоначально . выбранному участку аппроксимации. Однако, если выбранный с помощью R участок делится в свою очередь на несколько частей, то по адресу R в блоке 2 памяти записывается базовый адрес А и число r. Базовый адрес используется при формировании адреса ячеек памяти, в которых записаны х < и 4х., относящиеся к участкам аппроксимации, полученным в результате разбиения первоначального интервала на более мелкие части, а число 2 опре-! деляет количество этих новых разбие-. ний первоначального участка. В последний разряд каждой ячейки памяти записывается также служебный признак z . Если признак z З = О, то это. означает, что в данной ячейке записаны х1 и 4х,. Если z з= 1, то в данной ячейке записаны А и r. В блоке 2 памяти х. хранится в обратном коде в

1 форме с фиксированной запятой, 4 х;— в форме с плавающей запятой.

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

В микропрограмме приняты следующие обозначения: я — сигнал с выхода

1 схемы 11 сравнения; я — сигнал "Стоп", z — признак вида информации, хранящейся в блоке 2 памяти, у .,у =

I 6 — управляющие сигналы, форми- . руемые блоком 8 управления, интерпретирукщим приведенную микропрограмму, а — состояния блока 8 управления.

По заднему фронту сигнала у, поступающего на синхронизирующий вход датчика 1, формируется очередное равномерно распределенное случайное число.

Под действием сигнала у происходит чтение из блока 2 памяти чисел по адресу R, (адрес R, через второй коммутатор 12 проходит с первой группы выходов датчика 1 на адресные входы блока 2 памяти). Под действием сигнала уз прочитанное из блока 2 па- мяти число х . записывается в накаплиI вающий сумматор 5, порядок Р числа

Дх,, поступает в первый регистр 3, а мантисса М вЂ” во второй регистр 4. В случае, когда из выбранной ячейки происходит чтение А и r то базовый

95788

6 адрес А под действием сигнала уз записывается в накапливающий сумматор 5, а число r — н первый регистр 3. В любом случае признак z3 записывается в последний разряд регистра 4.

Под действием сигнала у происходит формирование числа g = x .+ R . При !

2 этом число R 2 формируется в первом коммутаторе 10, а операция сложения х . и R выполняется в накапливающем ! сумматоре 5. Под действием сигнала у сформированное в сумматоре чис5 ло g с требуемым законом распределения через группу 6 элементов И проходит на выход генератора. Под действием сигнала у происходит чтение из блока 2 памяти чисел по адресу

А, где A — базовый адрес, поступающий на первую группу входов коммун!атора 12 с выходов сумматора 5, равномерно распределенное r-разрядное случайное число, которое проходит через коммутатор 12 на младшие

26 разряды адресной группы входов блока 2 памяти.

В схеме 11 сравнения происходит формирование сигнала z при этом

У

z О, если R2 М, и z 1 при R2 И.

Здесь R — равномерно распределенное случайное число, снимаемое с второй группы выходов датчика 1 и поступающее на вторую группу.входов схемы 1 сравнения. Мантисса M поступает на первую группу входов схемы 11 сравнения с выходов регистра 4.

Признак zz= 1 означает, что в выбранной ячейке памяти записаны А и f

Другими, словами, если zз= !, то s процессе формирования очередного случайного числа g мы попали на участок аппроксимации, который был поделен на более мелкие части. В этоМ случае необходимо сформировать новый адрес

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

1495788 случайного числа, поступающего с первой группы выходов датчика 1 на вторую группу входов коммутатора 12. Количество разрядов случайного числа

5 определяется преобразователем 9, группа выходов которого подключена к третьей группе входов коммутатора 12.

Таким образом, преобразователь 9 управляет процессом прохождения (через коммутатор 12, формируя на своих выходах открывающие сигналы. В свою очередь, на группу входов преобразователя 9 поступает число r с первого регистра 3. Преобразователь 9 пре- 15 образует двоичное число r в унитарный ток, причем количество единичных сигналов на выходах равно самому числу г. В общем случае, через коммутатор 12 проходит г-разрядное число (, 20 причем r 6п,где и — количество разрядов числа F Таким образом, на выходах коммутатора 12 формируется исполнительный адрес вида А (, при этом для правильной работы коммутато- 25 ра младшие r разрядов базового адреса А должны быть нулевыми, поскольку эти разряды замещаются случайным

r-разрядным числом (. Добавление в младшие разряды исполнительного адре- 30 са случайного числа производится потому, что первоначальный интервал аппроксимации был разделен на 2 более

r мелких частей, и поэтому необходимо случайным образом выбрать один из

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

i 1У

А и r. Это необходимо для того, что- 40 бы реализовать возможность многократного деления любого (не только первоначального) интервала на 2 частей. г

При поступлении сигнала у на первый синхронизирующий вход коммутатора 12 на em выходы проходит равномерно ,распределенное и-разрядное случайное число R . Это число R, используется в качестве адреса ячейки памяти, в которой хранится информация, относяг щаяся к одному из 2 первоначальных интервалов, При этом 1 старших разрядов этого адреса являются нулевыми, а общий объем блока 2 памяти равен

2 " ячеек. Обычно 1 не велико лежит в пределах 1 4 2, На фиг,2 приведена схема блока 8 управления, который работает в соответствии с микропрограммой, приведенной на фиг.4. Сигнал "Пуск" поступает на вход блока 8 и переводит триггер 15, в единичное состояние. В результате открывается элемент И 14 и импульсы с выхода генератора 13 поступают на синхронизирующие входы триггеров 15 и 15> и дешифратора 17.

Блок 8 управления начинает свою работу и на его выходах формируются управляющие сигналы у, где i — порядковый номер выхода в группе выходов-.

На микропрограмме не показан сигнал у, который совпадает с сигналом у, но в отличие от у формируется толь2 ко при переходе блока 8 из состояния аз в состояние à2 .Сигналы z н zi и z3 поступают соответственно на входы задания логических условий блока 8 управления. В зависимости от значения этих сигналов, а также от состояния а; и происходит формирование управляющих сигналов у . В част1 ности, при поступлении сигнала z и 1„Ф

Стоп. на выходе элемента И 18 фор2

Мируется сигнал, который переводит триггер 15, в нулевое состояние и закрывает элемент И 14, В результате блок 8 управления прекращает свою работу, поскольку тактовые импульсы не проходят через элемент И 14 на синхронизирующие входы дешифратора 17 и триггеров 15 < и 15 . В схеме блока 8 управления для йсключения гонок и неустойчивых состояний используются двухступенчатые тригге-.. ры 15, 15, 15, причем триггеры

15 и 15 > имеют также асинхронные установочные входы.

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

1 . Генератор случайных чисел, содержащий датчик равномерно распределенных случайных чисел, блок управления, блок памяти, регистр, коммутатор, сумматор,. схему сравнения, группу элементов И, причем первая группа выходов датчика равномерно распределенных случайных чисел соединена с первой группой информационных входов коммутатора и с первой группой входов схемы сравнения, выход

"Равно" которой соединен с первым входом логических условий блока управления, первый выход которого соединен с входом опроса датчика равномерно распределенных случайных чисел, первая группа выходов блока памяти

1495788 10

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

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

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

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

1 495788

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

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

1495788

Составитель Д.Феликсон

Техред А.Кравчук Корректор C.Øåêìàð

Редактор В.Бугренкова

Заказ 4267/46 Тираж 668 Подписное

ВНИИПИ Государственного комитета по изобретениям и открытиям при ГКНТ СССР

113035, Москва, Ж-35, Раушская наб., д. 4/5

Производственно-издательский комбинат "Патент", r Ужгород, ул. Гагарина, 101