Генератор последовательностей случайных чисел

 

Изобретение позволяет генерировать последовательности случайных чисел с заданным одномерным законом распределения вероятностей и автокорреляционной функцией (АКФ). Устройство Относится к вычислительной технике и может быть использовано в качестве приставки или внутреннего блока вычислительной машины. В отличии от аналогов и прототипа с целью расширения возможностей управления видом АКФ генерируемых последовательностей в устройстве используется матрица вероятностей переходов (М В П), хранящаяся в блоке памяти. В каждый момент времени разыгрывается с помощью датчика случайных чисел состояние k МВП и из исходной совокупности некоррелируемых случайных чисел с требуемым законом распределения выбирается число, заключенное между квантилями k/n и (k-1)/n порядков. Сумматор , схемы сравнения, элементы задержки, блоки ключей, регистры памяти, счетчики используются для выбора этого числа и сравнения его с квантилями распределения. 1 ил. I с С

СОЮЗ СОВЕТСКИХ

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

РЕСПУБЛИК (я)5 G 06 F 7/58

ГОСУДАРСТВЕННОЕ ПАТЕНТНОЕ

ВЕДОМСТВО СССР (ГОспАтент сссР) ОПИСАНИЕ ИЗОБРЕТЕНИЯ

К ПАТЕНТУ (21) 4905564/24 (22) 11.11.90 (46) 23,08.93. Бюл. N 31

° (71) Иркутский институт народного хозяйства (72) С.И.Молчан, А,А.Преловская и В.P.Суслов (73} Иркутский институт народного хозяйства (56) Авторское свидетельство СССР

М 314208, кл, G 06 F 7/58, 1969.

Авторское свидетельство СССР

hh 1179325, кл. 6 06 F 7/58, 1984, (54) ГЕНЕРАТОР ПОСЛЕДОВАТЕЛЬНОСТЕЙ СЛУЧАЙНЫХ ЧИСЕЛ (57) Изобретение позволяет генерировать последовательности случайных чисел с заданным одномерным законом распределения вероятностей и автокорреляционной функцией (АКФ). Устройство относится к выИзобретение относится к моделированию случайных величин и последовательностей на вычислительных машинах и может быть использовано в качестве приставки или внутреннего блока ЭВМ.

Цель изобретения — расширение функциональных возможностей устройства эа

Счет управления видом автокорреляционных функций генерируемых последовательностей случайных чисел посредством матрицы вероятностей переходов цепи

Маркова, На чертеже изображен генератор.

Генератор содержит генератор 1 тактовых импульсов. элементы И 2 и 3, триггер 4, элементы 5. 13 и 15 задержки, счетчики 6, 14

« Ы 1836680 А3 числительной технике и может быть использовано в качестве приставки или внутреннего блока вычислительной машины. 8 отличии от аналогов и прототипа с целью расширения возможностей управления видом АКФ генерируемых последовательностей в устройстве используется матрица вероятностей переходов (M В П), хранящаяся в блоке памяти. В каждый момент времени разыгрывается с помощью датчика случайных чисел состояние k МВП и из исходной совокупности некоррелируемых случайных чисел с требуемым законом распределения выбирается число, заключенное между квантилями k/и и (k — 1)/и порядков. Сумматор, схемы сравнения. элементы задержки, блоки ключей, регистры памяти. счетчики используются для выбора этого числа и сравнения его с квантилями распределения, 1 ил, и 21, регистры 7 и 10, блоки 8 и 17 памяти, сумматор 9, схемы 11, 19 и 22 сравнения, датчики 12 и 20 случайных чисел и блоки 16, 18 и 23 кл,ючей.

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

В исходном положении в регистре 7 установлен номер начального состояния а, 1 < а < n, где n — размерность матрицы 2 вероятностей переходов, записанной в блок 8 памяти, обьемом и. Счетчики 6 и 14 установлены в нулевое состояние, счетчики 21 — в единичное, На выходе датчика 12 случайных чисел находится число, распределенное по равномерному в (О, 1) закону, На выходе датчика 20 случайных чисел находится чис1836680 ло, распределенное по закону, требуемому для генерируемой- последовательности. В блоке 17 памяти размерностью и, записаны . внешний,квантщщй. 59p9+K8 I/и, i = 1, 2 ... n. требуемого две Венефируемой последовательмасти закона распределения вероятносто. 8 регистре 10 записан нуль, На выходе схемы.22 сравнения..сигнал отсутствует, следователт ю.: 6лок,23 кщочей заперт и значение с еь@офа фучика 20 случайных чисел на выход гвиеретора не передается; Триггер 4 открыазет мем®нт И 3 и закрывает элемент

И2.

Импульс от тенератора 1 тактовых импульсов через:. элемент И 3 поступает на вход элемента 5 задержки и на счетный вход счетчика 6, вызывай увеличение состояния счетчика на единицу. Чисе из.блока 8 памятии, адрес которого устайоален в. счетчике 6 . и регистре 7, поступает на первый вход сумматора 9 и суммируются.с нулеаю, йоступаю° щим на второй вход сумматора 9 из регистра 10, Импульс с выхода элемента 5 задержки поступает на вход "Запись" регистра Ю и число иэ сумматора 9 записывается в регистр 10.. Число. из регистра 10 нжтупает на второй вход сумматора 9 и на первый вход схемы 11 сравнения, на втором входе. которой находится значение случайного числа, полученного от датчика 12 случайных чисел, Если значение на первом входе схемы 11 сравнения больше. либо равно значение на ее втором входе; то на вы-. ходе схемй пояаляется сигйэл. Если сигнал не появляется, t0 следующий импульс от генератора 1 тактовых импульсов вызывает перезапись следующего числа из блока 8 памяти. s сумматор 9 с последующим его суммированием с числом, хранящимся в регистре 10; Схема работает описанным обра зом до тех пор, пока не появится сигнал на выходе схемы 11 сравнения. Сигнал с выхода схемы 11 сравнения поступает на вход

"Запись" регистра 7, на счетный вход триггера 4, меняя era состоянйе на противоположное, на вход "Опрос" датчика 12 случайных и йа вход "Установка в нуль" регистра 10. При этом значение с выхода счет. чика 6 переписывается в регистр 7, регистр

10 обнуляется и на выходе датчика 12 случайных чисел появляется новое число, элемент И 2 открывается, элемент И 3 закрывается.

Импульс от генератора 1 тактовых импульсов через элемент И 2 поступает на вход элемента 13 задержки и на счетный . вход счетчика 14. Состояние счетчика 14 увеличивается на единицу. Число из блока

17 памяти, адрес которого установлен в счетчике 14, поступает на информационный

I вход блока 18 ключей, на разрешающий вход которого приходит импульс с выхода элемента 13 задержки, Блок 18 ключей открывается, нэ первый вход схемы 19 сравнения поступает число из блока 17 памяти и сравнивается с числом на ее втором входе, полученным от датчика 20 некоррелираванных случайных чисел, Если число на втором входе схемы 19 сравнения не меньше числа

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

Счетчике 14.не произойдет переполнение, Пусть произошло переполнение счетчика

14, Счетчик 14 устанавливается в начальное состояние. Сигнал с его выхода по перепол. 20 нению поступает нэ вход элемента 15 задержки и открывает блок 16 ключей. Значение с выхода счетчика 21 через блок 16 ключей поступает на первый вход схемы 22 сравне. ния, на втором входе которой находится

25 . значение с выхода регистра 7. Если сравнения не произойдет, нэ выходе схемы 22 сравнения сигнал не появится и сигнал с выхода элемента 15 задержки установит счетчик 21 в начальное состояние и вызовет генерирование датчиком 20 нового случайного числа. Цикл сравнения содержимого блока 17 памяти с этим новым случайным числом повторяется. Схема работает таким обрэзом до тех пор, пока нэ.выходе схемы

35 22 сравнения не появится сигнал. Этот сигнал устанавливает счетчик 6 и триггер 4 в начальное состояние и, поступая на разрешающий вход блока 23 ключей, вызывает поступление числа с выхода датчика 20 спу40 чайных чисел нэ выход устройства. Сигнал с .выхода элемента 15 задержки установит счетчик 21 в начальное состояние и вызовет генерирование датчиком 20 нового случайного числа. Триггер 4 открывает элемент И

45 3 и закрывает элемент И 2. Устройство переводится в исходное состояние. Цикл работы устройства заканчивается.

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

55 разыгрывают случайное целое число

i, 1 < l < n (n — размерность матрицы вероятностей переходов) и случайное число а, равномерно распределенное на интервале (О, 1). Первый элемент i-той строки матрицы перехода сравнивают с а, и, если он меньше

1836680 а, с.а сравнивают сумму первого и второго элементов, Последовательное суммирование элементов 1-той строки матрицы вероятностей переходов и сравнение этой суммы с а продолжают до тех пор, пока сумма не станет больше либо равна а. По номеру столбца k последнего элемента в сумме и определяют порядок квантили k/n исходной случайной величины с требуемым законом распределения вероятностей, Последоеа- . 10 тельным перебором производят выбор числа с требуемым законом распределения. расположенного между квантилями порядка k/n и (k — 1)/n. Таким образом, если порядок квантилей меняется от. квантили с квантили на фиксированную величину и матрица вероятностей переходов дважды стохастическая (сумма элементов в каждой строке и каждом столбце равна единице}, то закон распределения вероятностей выходной случайной последовательности не бу. дет отличаться от закона распределения вероятностей исходной случайной величины, а динамические (корреляционные) свойства генерируемой последовательности определяются матрицей вероятностей переходое.

Таким. образом, при помощи предлагаемого устройства осуществляется управление генерироеанием последовательностей случайных чисел посредством матрицы вероятностей переходов (узлы 5-12) и выбор случайного числа с требуемым законом распределения на основе состояния, установленного матрицей переходов и значений квантилей для требуемого закона распределения (узлы 13-23), При этом обеспечивается сохранение исходного, требуемого закона распределения вероятностей и введение необходимой и легко управляемой через матрицу вероятностей переходов корреляционной зависимости.

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

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

55 разрядных выходов второго счетчика соединена с группой информационных входов второго блока ключей, выход первой схемы сравнения соединен с установочным входомтриггера, отл и чаю щи й-с ятем, что, с целью расширения функциональных возможностей эа счет обеспечения управления видом автокорреляционных функций генерируемых последовательностей, в него введены второй датчик случайных чисел, второй блок памяти, вторая и третья схемы сравнения, сумматор, два регистра и третий элемент задержки, причем первый выход триггера соединен с вторым входом второго элемента И, выход которого соединен со счетным входом третьего счетчика и через второй элемент задержки с входом записи первого регистра, группа выходов которого соединена с первыми руппами входов сумматора и второй схемы сравнения, выход. которой соединен с входом сброса первого регистра, со счетным входом триггера, е входом записи второго регистра и с входом опроса второго датчика случайных чисел, группа выходов которого соединена с второй группой входов второй схемы сравнения. второй вмход триггера соединен с вторым входом первого элемента И, выход которого соединен через тре ий элемент задержки с управляющим входом nepsoro 5noка ключей, группа выходов-которогв соединена с первой группой входов третьей схемы сравнения, выход которой соединен со счетным входом второго счетчика, установочный вход которого подключен через первый элемент задержки к выходу переполнения первого счетчика, который соединен с управляющим входом второго блока ключей, группа выходов которого соединена с первой группой входов первой схемы сравнения, выход которой соединен с управляющим входом третьего блока ключей и с установочным входом третьего счетчика, rpynna разрядных выходов которого соединена с первой группой адресных входов второго блока памяти и с rpynnOA информационных входов второго регистра, группа выходов которого соединена с второй группой входов первой схемы сравнения и с второй группой адресных входов второго блока памяти, группа выходов которого соединена с второй группой входов сумматора, группа выходов которого соединена с группой информационных входов первого регистра, группа выходов первого датчика случайных чисел соединена с второй группой входов третьей схемы сравнения и с группой информационных входов третьего блока ключей. группа выходов которого образует группу выходов устройства.

Составитель С.Молчан

Редактор М.Кузнецова Техред М.Моргентал Корректор Д,дивринц

Заказ 3020 Тираж Подписное

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

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

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