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

X

САЭ 00 00 00

сл

со

Изобретение относится к вычислительной технике и может быть использовано для генерирования равномерно .распределенных случайных двоичных чисел при решении задач вероятностного моделирования. Целью изобретения является упрощение генератора. Генератор реализует алгоритм суммирования двух равномерно распределенных случайных чисел по модулю 1/2, задержанных на один и К 50 циклов выработки случайных чисел и 7 содержит блок 3 памяти, сумматор 1 , промежуточный регистр 2 памяти, два счетчика 4, 5 и элемент задержки 6. При поступлении сигнала в блок памяти с шины тактовых импульсов считываемое случайное число из блока памяти по адресу, которым служит содержимое первого счетчика, суммируется с ранее выработанным числом, Хранящимся в промежуточном регистре. Вновь выработанное случайное число с выхода сумматора поступает на вход генератора и на входпромежуточного регистра, с выхода которого ранее выработанное случайное число записывается в блок памяти по адресу, которым является содержимое второго счетчика. После считьшания и записи информации в блок памяти состояние счетчиков изменяется на единицу, состояние которых разнесено на К-1 единиц по модулю К, где К - объем блока памяти. 3 ил. (Л

cpu.i

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

Цель изобретения - упрощение ге- нератбра.

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

Генератор случайных чисел (фиг. 1 содержит сумматор.1, регистр 2 памяти, блок 3 памяти, первый 4 и второй 5 счетчики, элемент 6 задержки, шину 7 тактовьк импульсов.

Генератор случайных чисел реализует следующий алгоритм:

X(n) x(n-l)+X(n-K) (mod -). (1)

Выполнение операции суммирования (1) по модулю (mod ) означает следующее .

Обозначим

Y(n) X(n-l)+X(n-K). Если - I Y(n) + -j(2) |, то Х(п)Х(п).

Если + Y(n) +1,, то X(n)Y(n)-l.

Если -1 Y(n) - г., то X(n)Y(n)+l.

(3)

Реализация соотношений (3) упро- щйется для дополнительного кода представления двоичных чисел. Цифровая вычислительная техника обрабатывгшт двоичные числа в дополнительном коде, поэтому реализацию формулы (1) рассматриваем для дополнительного кода. В этом случае суммирование по алгоритму (1) производится путем выполнения операции сложения двух чисел без учета переполнения при условии, что максимально возможное абсолютное значение машинного числа равно 1/2. Это связано с тем, что для дополнитель- ного кода при переполнении положительного результата сложения автоматически вычитается величина 1,0, а

0

5

0

5

0

при переполнении отрицательного числа - прибавляется 1,0.

На фиг. 2а показана плотность вероятности случайных чисел Х(п-1);

Х(п-К) в пределах (- - v + Тогда

число Y(п) имеет плотность распределения вероятностей треугольной формы (фиг. 26) в пределах (-1,0-;+1,0). Введение поправок по соотношениям (3) переводит плотность распределения вероятностей (2) в величины распределения вероятностей значений чисел Х(п) прямоугольной формы (фиг. 2в) т.е. получается новое равномерно распределенное случайное число Х(п), вычисленное по алгоритму (1), Для хранения чисел Х(п-1), i 1,2,...,К, достаточно иметь блок 3 памяти объемом К 50 ячеек. Для удобства аппаратурной реализации генератора случайных чисел (счетчики) целесообразно выбрать 2 64 ячейкам.Однако это условие не обя зательно, так как известны счетчики, вырабатывающие коды по произвольному модулю К.

Вырабатываемые равномерно распределенные случайные числа по алгоритму (1) имеют период цикличности Р 2 , где m - разрядность двоичных чисел. Так при (числа с фиксированной занятой в ЭВМ серии ЕС, АСВТ, СМ) период Р 4 10 чисел.

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

В блоке 3 памяти хранится К равномерно распределенных случайных чисел, и блок памяти в процессе гене- рации чисел самообновляется. Для первоначального запуска генератора равномерно распределенные случайные числа можно взять из таблиц.

На фиг. 3 приведены примеры интерпретации двоичных кодов вырабатываемых т 16-разрядных случайных чисел Х(п) на выходе генератора. При представлении двоичных чисел в дополнительном коде фиксированая запятая

может находиться в произвольном месте. Обычно запятая размещается сраз после старшего (знакового) разряда (абсолютные значения изменяются в пределах (О f 1) или после младшего разряда (целые числа в пределах 2И-) ..4.2 - 1-1).

При расположении запятой сразу после старшего (знакового) разряда имеем следующее. При раздвоении содержимого знакового разряда случайные числа изменяются (см. фиг. За)

пределах (- г г + ). На фиг. 36

представлены случайные числа в пределах (-1,0 -г +ljO). Если ввести дополнительный разряд с состоянием О, считая его старшим, то получим случайные числа (см. фиг. Зв) в пределах (Ог1).

При расположении запятой после младшего разряда (целые числа) имеем следующее: на фиг. 36 - числа в пределах ( ) ;. на фиг. Зв - числа в пределах (0 ).

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

При первоначальном запуске в блоке 3 памяти хранится К равномерно распределенных случайных т разряд- ных двоичных чисел с фиксированной запятой в дополнительном коде, взятых из любой таблицы равномерно распределенных чисел. Первый и второй счетчики находятся в начальном состояний, при этом коды их состояний различаются на К-1 единиц по модулю (mod К), например при К 2 64 можн установить начальное состояние: первый счетчик 4 - код 000000, второй счетчик - код 11111.

Перед генерированием очередного случайного числа Х(п) по алгоритму (1) в блоке 3 памяти хранится К равномерно распределенных случайных чисел, состояние первого счетчика 4 произвольное, состояние счетчика 5 отличается от состояния первого счечика 4 на К-1 единиц по модулю К. В промежуточном регистре 2 хранится ранее выработанное случайное число Х(п-1).

Генерация очередного равномерно распределенного случайного числа по алгоритму Х(п)Х(п-1)+Х(п-К)

(mod г) начинается с поступлением

по шине 7 тактового импульса, который поступает на вход элемента 6 задержки и на управляющий вход блока 3 памяти.

По этому тактовому импульсу на первый вход сумматора 1 с выхода блока 3 памяти поступает число Х(п-К) по адресу, которым служит код содержимого первого счетчика 4. Число Х(п-1) с выхода промежуточного регистра 2 поступает по информационному входу в блок 3 памяти и записывается в нем по адресу, которым служит Ko;j содержимого второго счетчика 5. . Число Х(п-) с выхода промежуточного регистра 2 также поступает на второй вход сумматора I, на выходе которого вырабатывается очередное случайное число Х(п ) по алгоритму (1). Выработанное случайное число Х(п) поступает на вход генератора и в промежуточный регистр 2. Тактовый импульс задерживается в элементе 6 задержки на время считывания и записи в блок 3 памяти соответственно чисел Х(п-К) и Х(п-1) по адресам, которыми являются коды состояний соответственно первого 4 и второго 5 счетчиков. Задержанный в элементе 6 задержки импульс поступает на счетные входы первого 4 и второго 5 счетчиков, состояния которых изменяются на единицу по модулю К.

Сумматор 1 представляет собой : обычный сумматор, предназначенный для сложения двух двоичных чисел в дополнительном коде, при этом факт переполнения разрядной сетки сумматора не учитывается. Пределы изменений значений случайных чисел интерпретируются, как показано на фиг. 3. После выработки случайного . числа Х(п) генератор находится в сос- тоянии готовности к выработке очередного случайного числа Х(п-1).

Так как адреса считывания и записи случайных чисел разнесены на К-1

единиц, а выработанное на предыдущем цикле генерирования случайное число поступает с выхода промежуточного регистра 2, то число Х(п) участвует при генерировании только случайного числа Х(п+К) и предлагаемый генератор реализует алгоритм (1), который также реализуется известным устройством-прототипом .

i VopMyna изобретения

Генератор случайных чисел, содержащий элемент задержки, два счетчика, блок памяти, отличаю- П1 и и с я тем, что, с целью упрощения j он содержит регистр памяти и сумматор, выход которого является выходом генератора и соединен с информационным входом регистра памяти, выход которого соединен с информационным входом блоPj()

Я./„) «

J

фиЗ.1

Редактор Е. Копча

Составитель А. Карасов

Техред М.Дидык Корректор Н. Король

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

фие.З