Генератор случайных чисел
Изобретение относится к вычислительной технике и может быть использовано для генерирования равномерно .распределенных случайных двоичных чисел при решении задач вероятностного моделирования. Целью изобретения является упрощение генератора . Генератор реализует алгоритм суммирования двух равномерно распределенных случайных чисел по модулю 1/2, задержанных на один и К 50 циклов выработки случайных чисел и 7 содержит блок 3 памяти, сумматор 1 , промежуточный регистр 2 памяти, два счетчика 4, 5 и элемент задержки 6. При поступлении сигнала в блок памяти с шины тактовых импульсов считываемое случайное число из блока памяти по адресу, которым служит содержимое первого счетчика, суммируется с ранее выработанным числом, Хранящимся в промежуточном регистре. Вновь выработанное случайное число с выхода сумматора поступает на вход генератора и на входпромежуточного регистра, с выхода которого ранее выработанное случайное число записывается в блок памяти по адресу, которым является содержимое второго счетчика. После считьшания и записи информации в блок памяти состояние счетчиков изменяется на единицу, состояние которых разнесено на К-1 единиц по модулю К, где К - объем блока памяти. 3 ил. (Л
СОЮЗ СОВЕТСКИХ
СОЦИАЛИСТИЧЕСКИХ
РЕСПУБЛИК (19) (11) 9 А1 (51) 4 G 06 F 7 58
ОПИСАНИЕ ИЗО6РЕТЕНИЯ
Н А BTOPCHOMV СВИДЕТЕЛЬСТВУ
ГОСУДАРСТВЕННЫЙ КОМИТЕТ СССР
ПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТКРЫТИЙ (21) 411457) /24-24 (22) 04.09.86 (46) 15,04.88. Бюл. Р 14 (72) И. Я. Миронов (53) 681.325(088.8) (56) Авторское свидетельство СССР
N - 1049904, кл. G 06 F 7/58, 1982.
Авторское свидетельство СССР
1(- 1275436, кл, G 06 F 7/58, 1985. (54) ГЕНЕРАТОР СЛУЧАЙНЫХ ЧИСЕЛ (57) Изобретение относится к вычислительной технике и может быть использовано для генерирования равномерно.распределенных случайных двоичных чисел при решении задач вероятностного моделирования. Целью изобретения является упрощение генератора. Генератор реализует алгоритм суммирования двух равномерно распределенных случайных чисел по модулю
1/2, задержанных на один и К 50 циклов выработки случайных чисел и содержит блок 3 памяти, сумматор 1, промежуточный регистр 2 памяти, два счетчика 4, 5 и злемент задержки 6. При поступлении сигнала в блок памяти с шины тактовых импульсов считываемое случайное число из блока памяти по адресу, которым служит содержимое первого счетчика, суммируется с ранее выработанным числом, хранящимся в промежуточном регистре.
Вновь выработанное случайное число с выхода сумматора поступает на вход генератора и на вход промежуточного регистра, с выхода которого ранее выработанное случайное число записывается в блок памяти по адресу, которым является содержимое второго счетчика. После считывания и записи информации в блок памяти состояние счетчиков изменяется на единицу, состояние которых разнесено на К-1 единиц по модулю К, где К вЂ” объем блока памяти. 3 ил.
8859 дующее.
Обозначим
1 138
Изобретение относится к вычислительной технике и может быть использовано для генерирования равномерно распределенных случайных двоичных чисел при решении задач вероятностноrо моделирования„
Цель изобретения — упрощение генератбра.
На фиг. 1 приведена функциональная схема генератора случайных чисел; на фиг. 2 — графики,.поясняющие фор" мирование равномерно распределенных случайных чисел; на фиг. 3 — примеры интерпретации двоичных кодов случайных чисел на выходе генератора, Генератор случайных чисел (фиг. 1) содержит сумматор.l, регистр 2 памяти, блок 3 памяти, первый 4 и второй
5 счетчики, элемент 6 задержки, шину
7 тактовых импульсов.
Генератор случайных чисел реализует следующий алгоритм<
x(n)=I x(n-))+x(n-к)) (пюа -). ())
Выполнение операции суммирования
1 (1) по модулю (mocl -) означает сле2
Y(n) = X(n-1)+Х n-K), (2)
1 I
Если — - 6Y(n) + -„;, то Х(п) =Х(п), 1
Если + — Y(n) c +1„.то X(n)=Y(n)-1е
Если -1 « Y (n) (— -., то X(n) =Y (n)+ !
1 (3) Реализация соотношений (3) упрощается для дополнительного кода представления двоичных чисел. Цифровая вычислительная техника обрабатывает двоичные числа в дополнительном коде, поэтому реализацию. формулы (1) рассматриваем для дополнительного кода.
В этом случае суммирование по алгоритму (1) производится путем выполнения операции сложения двух чисел без учета переполнения при условии, «ro максимально возможное абсолютное значение машинного числа равно 1/2. Это связано с тем, что для дополнительного кода при переполнении положительного результата сложения автоматически вычитается величина 1,0, а при переполнении отрицательного числа — прибавляется 1,0.
На фиг. 2а показана плотность вероятности случайных чисел X(n-1);
1, 1
X(n-К) в пределах (- — —, + -) . Тогда
2 2 число Y(n) имеет плотность распределения вероятностей треугольной формы (фиг. 2б) в пределах (-1, 0 +
+!,О). Введение поправок по соотношениям (3) переводит плотность распределения вероятностей (2) в величины распределения вероятностей значений чисел X(n) прямоугольной формы (фиг. 2в) т.е. получается новое равномерно распределенное случайное число X(n), вычисленное по алгоритму (1) . Для хранения чисел X(n-1), 1,2. ..К, достаточно иметь блок
3 памяти объемом К 50 ячеек. Для удобства аппаратурной реализации генератора случайных чисел (счетчики) целесообразно выбрать К=2 =2 =64
6 ячейкам, Однако это условие не обязательно, так как известны счетчики, вырабатывающие коды по произвольному модулю К.
Вырабатываемые равномерно распределенные случайные числа по алгоритму (!) имеют период цикличности
Р 2, где m — разрядность двоичных чисел, Так при m=32 (числа с фиксированной занятой в ЭВ!! серии ЕС, АСВТ, CM) период P 0 4 ° 10 чисел.
Измерения статистических свойств образуемых генератором случайных чисел показывают, что их распределения близки к равномерному, причем их энергетический спектр тоже почти равномерный, т ° е, генерируемый шум близок к белому. Рассмотренный генератор можно с успехом использовать для цифровой обработки сигналов, а также при решении задач вероятностного моделирования.
В блоке 3 памяти хранится К равномерно распределенных случайных чи сел, и блок памяти в процессе генерации чисел самообновляется. Для первоначального запуска генератора равномерно распределенные случайные числа можно взять из таблиц.
На фиг. 3 приведены примеры интерпретации двоичных кодов вырабатываемых тч=16-разрядных случайных чисел X(n) на выходе генератора. При представлении двоичных чисел в дополнительном коде фиксированая запятая
1388859 может находиться в произвольном месте. Обычно запятая размещается сразу после старшего (знакового) разряда (абсолютные значения изменяются в пределах (Π†. 1) или после младшего разряда (целые числа в пределах (-21 1 —;(+2(1 — 1)) ..
При расположении запятой сразу после старшего (знакового) разряда имеем следующее. При раздвоении содержимого знакового разряда случайные числа изменяются (см. фиг. 3a) в
1 . 1 пределах (- — —, + -). На фиг. Зб
2 2 представлены случайные числа в пределах (-1,0 †: +1,0). Если ввести дополнительный разряд с состоянием
11 t l
О, считая его старшим, то получим случайные числа (см, фиг. Зв) в пределах (О-:1).
При расположении запятой после младшего разряда (целые числа) имеем следующее: на фиг. Зб — числа в пределах ((-2 1 —;(+2 -1)); на фиг ° Зв — числа в пределах ((01-: +2 - lg ) . I
Генератор случайных чисел работает следующим образом.
При первоначальном запуске в блоке 3 памяти хранится К равномерно распределенных случайных тп-разрядных двоичных чисел с фиксированной запятой в дополнительном коде, взятых из любой таблицы равномерно распределенных чисел, Первый и второй счетчики находятся в начальном состоянии, при этом коды их состояний различаются на К-1 единиц по модулю а (mod К), например при K= 2 =64 можно установить начальное состояние: первый счетчик 4 — код 000000, второй счетчик — код 11111, Перед генерированием очередного случайного числа X(n) по алгоритму (1) в блоке 3 памяти хранится К равномерно распределенных случайных чисел, состояние первого счетчика 4 произвольное, состояние счетчика 5 отличается от состояния первого счетчика 4 на К-1 единиц .по модулю К.
В промежуточном регистре 2 хранится ранее выработанное случайное число
X(n-1).
Генерация очередного равномерно распределенного случайного числа по алгоритму X(n) -(X(n-1)+Х(п-K))
1 (mod -) начинается с поступлением
2 по шине 7 тактового импульса, который поступает на вход элемента 6 задержки и на управляющий вход блока
3 памяти.
Ло этому тактовому импульсу на первый вход сумматора 1 с выхода бло ка 3 памяти поступает число X(n-К) по адресу, которым служит код содержимого первого счетчика 4. Число
X(n-1) с выхода промежуточного регистра 2 поступает по информационному входу в блок 3 памяти и записывается в нем по адресу, которым служит код содержимого второго счетчика 5..
Число X(n-1) с выхода промежуточного регистра 2 также поступает на второй вход сумматора 1, на выходе которого вырабатывается очередное случайное число X(n ) по алгоритму (1). Выработанное случайное число X(n) поступает на вход генератора и в промежуточнь|й регистр 2 ° Тактовый импульс задерживается в элементе 6 задержки на время считывания и записи в блок 3 памяти соответственно чисел X(n"K) и X(n-1) по адресам, которыми являются коды состояний соответственно
30 первого 4 и второго 5 счетчиков. Задержанный в элементе 6 задержки импульс поступает на счетные входы первого 4 и второго 5 счетчиков, состояния которых изменяются на единицу по модулю К.
35 Сумматор 1 представляет собой обычный сумматор, предназначенный
; для сложения двух двоичных чисел в
: дополнительном коде, при этом факт переполнения разрядной сетки сумма40 тора не учитывается. Пределы изменений значений случайных чисел интерпретируются, как показано на фиг, 3. После выработки случайного . числа X(n) генератор находится в сос4 тоянии готовности к выработке оче45 редного случайного числа X(n-1).
Так как адреса считывания и записи случайных чисел разнесены на К-1
50 единиц, а выработанное на предыдущем цикле генерирования случайное число поступает с выхода промежуточного регистра 2, то число X(n) участвует при генерировании только случайного
55 числа Х(п+К) и предлагаемый генератор реализует алгоритм (1), который также реализуется известным устройством-прототипом.
1388859 ормулаиз обретения р ) ) Х1
Составитель А. Карасов
Техред M.Äèäûê Корректор Н. Король
Редактор Е. Копча.
Заказ j580/49 Тираж 704 Подписное
ВНИИПЙ Государственного комитета СССР по делам изобретений и открытий
113035, Иосква, Ж35, Раушская наб., д. 4/5
Производственно-полиграфическое предприятие, r. Ужгород, ул. Проектная, 4
Генератор случайных чисел, содержащий элемент задержки, два счетчика, блок памяти, о т л и ч а ю— шийся тем, что, с целью упрощения, он содержит регистр памяти и сумматор, выход которого является выходом генератора и соединен с информационным входом регистра памяти, выход которого соединен с информационным входом блока памяти и с первым входом сумматора, второй вход которого подключен к выходу блока памяти, синхронизирующий вход которого подключен к выходу источника тактовых импульсов и к входу элемента задержки, выход которого соединен со счетными входами первого и второго счетчиков, информационные выходы которых соединены соответственно с адресным входом считывания и с адресным входом записи блока памяти.
