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

 

О П И С А Н И Е 378826

ИЗОБРЕТЕНИЯ

К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ

Союз Советских

Социалистических

Республик

Зависимое от авт. свидетельства №вЂ”

М. Кл. С 06f 1/02

Заявлено 17.XI I.1970 (№ 1605941/18-24) с присоединением заявки №вЂ”

Приоритет

Опубликовано 18.IV.1973. Бюллетень № 19

Дата опубликования описания 17Л"П.1973

Комитет по делам изобретеиий и открытий при Совете Министров

СССР

УДК 681,332.65 (088.8) Авторы изобретения

В. М. Бойченко, А. Е. Лаусенко и А. В. Бойченко

Заявитель

ГЕНЕРАТОР СЛУЧАЙНЫХ ЧИСЕЛ

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

iB настоящее время в основном используются псевдослучайные числа, вырабатываемые на ЦВМ. Однако для их получения требуются значительные затраты машинного времени, что приводит к снижению эф фективности использования ЦВМ и, главное, к потере реального масштаба времен и при цифровом моделировании сложных систем.

Предлагаемый генератор, основанный на методе обратных функций, при котором для .получения последовательности случайных чисел с заданным законом распределения. применяется функциональное преобразование, основанное на кусочно-линейной аппроксимации распределения F(x), позволяет получить случайные числа по произвольному закону распределения. При этом область возможных значений х разбивается íà п равных интервалов.

Известные генераторы случайных чисел (ГСЧ) с заданным законом распределения, основанные на методе обратных функций, отличаются друг от друга способом отыскивания интервала и, следовательно, быстродействием и объемом аппаратуры. Можно выделить ГСЧ с параллельным, последовательным и логарифмическим с пособами отыскивания интервала. В ГСЧ с логарифмическим перебором отыскивания интервала происходит за т+1 тактов, где m — двоичная разрядность числа х;, т. е. n=2m.

Предлагаемый генератор случайных чисел основан на методе обратных функций с логарифмическим способом перебора интервалов, в котором отыскивание нужного интервала осуществляется не за т+1 тактов, как в из10 вестном ГСЧ с логарифмическим перебором, а за т тактов. Это позволяет в два раза увеличить число интервалов разбиения п, что значительно увеличивает точность функционального преобразования. Кроме того, не15 сколько упрощена структурная схема ГСЧ за счет отсутствия схемы задержки, что значительно упрощает настройку генератора.

На фиг. 1 изображена блок-схема предлагаемого ГСЧ с формированием случайных

20 чисел по произвольному закону распределения способом логарифмического перебора за m тактов; на фиг. 2 — схема специализированного дешифратора.

Генератор содержит генератор 1 равномер25 но распределенных случайных чисел, цифровую схему сравнения 2, постоянное запоминающее устройство 3, генератор тактов 4, специализированный дешифратор 5, регистр

6 формирования случайного числа, входные 7

30 и выходные 8 вентили.

378826

Входы регистра формирования случайного числа х; через одни входы входных вентилей

7 соединены с выходами генератора тактов 4, а через вторые — с выходами цифровой схемы сравнения 2, один вход которой соединен с выходом генератора равномерно распределенных случайных чисел, а второй вход— с выходом постоянного запоминающего устройства (ПЗУ) 8. Выходы регистра 6 с одной стороны через специализированный дешифратор для логарифмического перебора соединены со входами ПЗУ 8, с другой стороны соединены с одними входами выходных вентилей 8, другие входы которых соединены с одним из выходов генератора тактов 4.

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

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

m = l og ï.

Начало логарифмического перебора всегда и начинается с середины области разбиения —, 2 поэтому первый импульс выхода генератора тактов поступает непосредственно на ПЗУ 8 и выбирает серединное значение области рази биения х;= —, которое поступает на один из входов цифровой схемы сравнения 2. Этот же импульс поступает на одни из входов входных вентилей, на вторые входы которых поступает результат сравнения равномерно распределенного случайного числа, выдаваемого генератором 1 равномерно распределенных случайных чисел по команде генератора тактов 4 и серединного значения обп ласти разбиения х;= —.

2 п

При 3(F х — — ) регистр б устанавлива2) ется входным вентилем 7 в нулевое состояние. Это означает, что дальнейший перебор

/ п1 пойдет влево. При $)F х,.= ) регистр 6 устанавливается в единичное состояние (дальнейший перебор пойдет вправо). Таким образом, установка регистра б в нужное состояние производится первым импульсом генератора тактов.

Информация о состоянии регистра б поступает на, дешифратор 5, который выполнен в виде отдельных блоков (O1, O4 ..., O 1), каждый из которых осуществляет один шаг логарифмического перебора (см. фиг. 2) .

Второй импульс генератора тактов поступает на один из входов входных вентилей регистра б и считывает с дешифратора 5 одно из знап Зп чений области разбиения — „ли — в за4 4 висимости от состояния регистра б. Сигнал с дешифратора 5 выбирает из ПЗУ 8 значеп1 ние функции распределения F х = — ) или

Sn I х;= — 4) в зависимости от направления логарифмического перебора. Результат сравнения этого значения с равномерно распределенным случайным числом устанавливает регистр 6 в единичное или нулевое состояние.

Информация о состоянии регистра, поступает на все блоки дешифратора, начиная с бло" 2.

Аналогично происходит установка остальных триггеров регистра. т-ый импульс генератора тактов 4 считывает с блока Dm деши фратора значение аргумента последнего шага перебора, которое выбирает из ПЗУ 8 значение функции распределения этого аргумента. Результат сравнения этого значения с равномерно распределенным случайным числом устанавливает последний триггер регистра б в нужное состояние. Этот же импульс генератора тактов подается на вторые входы выходных вентилей и тем самым осуществляет считывание с них случайного числа х;, распределенного по заданному закону

F(x;).

Предмет изобретения

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