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

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

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

На чертеже изображен генератор.

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

и 21, регистры 7 и 10, блоки 8 и 17 памяти, сумматор 9, схемы 11, 19 и 22 сравнения, датчики 12 и 20 случайных чисел и блоки 16, 18 и 23 ключей.

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

В исходном положении в регистре 7 установлен номер начального состояния а, 1 а п, где п - размерность матрицы 2 вероятностей переходов, записанной в блок 8 памяти, объемом л. Счетчики 6 и 14 установлены в нулевое состояние, счетчики 21 - в единичное. На выходе датчика 12 случайных чисел находится число, распределенное по равномерному в 0, 1 закону. На выходе датчика 20 случайных чисел находится чис00

со о,

0 00

о

со

ло, распределенное по закону, требуемому для генерируемой последовательности. В блоке 17 памяти размерностью п, записаны значения квантилей порядка t/п, i 1,2 ... п, требуемого для генерируемой последовательности закона распределения вероятностей, В регистре 10 записан нуль. На выходе схемы 22 сравнения сигнал отсутствует, следовательно, блок 23 ключе заперт и значение с выхода датчика 20 случайных чисел на выход генератора не передается. Триггер 4 открывает элемент И 3 и закрывает элемент И 2.

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

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

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

на ее первом входе, то на выходе схемы появляется сигнал, который, поступая на счетный вход счетчика 21, увеличивает его состояние на единицу. При приходе следующих тактовых импульсов устройства работа5 ет аналогичным образом до тех пор, пока в Счетчике 14 не произойдет переполнение. Пусть произошло переполнение счетчика 14, Счетчик 14 устанавливается в начальное состояние. Сигнал с erg выхода по перепол0 нению поступает на вход элемента 1.5 задержки и открывает блок 16 ключей. Значение с выхода счетчика 21 через блок 16 ключей поступает на первый вход схемы 22 сравнения, на втором входе которой находится

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

0 генерирование датчиком 20 нового случайного числа. Цикл сравнения содержимого блока 17 памяти с этим новым случайным числом повторяется. Схема работает таким образом до тех пор, пока на выходе схемы

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

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

Описанное устройство реализует следующие информационные преобразования,

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

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

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

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

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

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

5 элемента И, выход которого соединен со счетным входом третьего счетчика и через второй элемент задержки с входом записи первого регистра, группа выходов которого соединена с первыми группами входов еум0 матора и второй схемы сравнения, выход которой соединен с входом сброса первого регистра, со счетным входом триггера, с входом записи второго регистра и с входом опроса второго датчика случайных чисел,

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

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

ч

/

IMiMI

ж

SH&r

2«

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