Генератор випадкових чисел

Изобретение относится к вычислительной технике и может быть использовано для генерирования равномерно распределенных случайных чисел при решении задач вероятностного моделирования, реальных, процессов. Известен управляемый преобразователь законов распределения вероятностей, содержащий n первичных датчиков случайных импульсов, генератор тактовых импульсов, первый выход которого соединен со входом "сдвиг" циклического регистра сдвига, (n-1) элементов И, выходы которых соединены со входами первого элемента ИЛИ, выход которого является выходом преобразователя и соединен со входом "сброс" циклического регистра сдвига, выходы которого соединены с первыми входами соответствующих элементов И [Авт.св. СССР № 898427, кл. G 06 F 7/58]. Недостатком данного устройства является функциональная сложность, что приводит к большим аппаратурным затратам. Известен генератор случайных чисел, содержащий блок памяти, сумматор, выход которого является выходом генератора и подключен к информационному входу блока памяти, выходы первой и последней ячейки которого соединены со входами сумматора [Рабинер Л., Голд Б. Теория и применение цифровой обработки сигналов. М., Мир, 1978]. Недостатком данного генератора является низкое быстродействие, так как после выработки очередного случайного числа необходимо выполнить сдвиг содержимого ячеек в блоке памяти. Известен также генератор случайных чисел, содержащий генератор тактовых импульсов, реверсивный счетчик, выход которого соединен со входами первого и второго дешифраторов, два элемента И-НЕ, генератор случайной последовательности импульсов, выход которого соединен с первым входом второго элемента И-НЕ, выход которого соединен со входом управления направлением счета реверсивного счетчика, выход которого является выходом генератора, выход первого дешифратора соединен со вторым входом первого элемента И-НЕ, выход второго дешифратора соединен со вторым входом второго элемента И-НЕ, выход генератора тактовых импульсов подключен к счетному входу реверсивного счетчика [Патент РФ № 1661761, кл. G 06 F 7/58, 1992}. Недостатком этого генератора является его функциональная сложность, требующая больших аппаратурных затрат. Наиболее близким техническим решением является генератор случайных чисел, содержащий блок памяти, два счетчика, элемент задержки, регистр памяти и сумматор, выход которого является выходом генератора и соединен с информационным входом регистра памяти, выход которого соединен с информационным входом блока памяти и с первым входом сумматора, второй вход которого подключен к выходу блока памяти, синхронизирующий вход которого подключен к выходу источника тактовых импульсов и ко входу элемента задержки, выход которого соединен со счетными входами первого и второго счетчиков, информационные выходы которых соединены соответственно с адресным входом считывания и адресным входом записи блока памяти [Авт.св. СССР № 1388859, кл. G 06 F 7/58 (прототип)]. Недостатком данного генератора являемся то, что недостаточно точно соблюдается равномерность распределения случайных чисел и период повторения их серий небольшой. В основу изобретения поставлена задача повышения качества генерируемых равномерно распределенных случайных чисел, для чего генератор случайных чисел совершенствуется путем обеспечения условий суммирования произвольного количества операндов за счет введения в генератор дополнительно (n-1) счетчиков адреса чтения. Для решения поставленной задачи в генератор случайных чисел, содержащий блок памяти, суммирующий блок, регистр памяти, первый счетчик адреса чтения, счетчик адреса записи и элемент задержки, причем выход суммирующего блока является выходом генератора и соединен с информационным входом регистра памяти, выход которого соединен с информационным входом блока памяти, первый вход суммирующего блока соединен с первым выходом блока памяти, синхронизирующий вход которого подключен к выходу источника тактовых импульсов и к входу элемента задержки, - выход которого соединен со счетными входами первого счетчика адреса чтения и счетчика адреса записи, информационные выходы которых соединены соответственно с первым адресным входом чтения и адресным входом записи блока памяти, дополнительно введено (n-1) счетчиков адреса чтения, счетные входы которых подключены к выходу элемента задержки, а информационные выходы соединены соответственно со второго по n-й адресными входами чтения блока памяти, выходы со второго по n-й которого соединены соответственно со второго по nй входами суммирующего блока. Соответствующий сравнительный анализ с прототипом показывает, что заявляемый генератор случайных чисел отличается тем, что в нем подключены дополнительные счетчики, информационные выходы которых подключены к адресным входам блока памяти, что обеспечивает улучшение качества генерируемых случайных чисел за счет суммирования большого количества операндов. Таким образом, заявляемый генератор соответствует критерию изобретения "новизна". Сравнение заявляемого решения не только с прототипом, но и с другими техническими решениями в данной области техники, не позволило выявить в них признаки, отличающие заявляемое решение от прототипа, что позволяет сделать вывод о соответствии критерию "существенные отличия", На фиг.1, приведена функциональная схема генератора случайных чисел; на фиг.2 - примеры интерпретации двоичных кодов случайных чисел на выходе генератора. На фиг.1 обозначены: суммирующий блок 1. регистр памяти 2, блок памяти 3, счетчики адреса чтения 4, счетчик адреса записи 5, элемент задержки 6, шина тактовых импульсов 7. Выход суммирующего блока 1 является выходом генератора случайных чисел и подключен ко входу регистра памяти 2, выход которого соединен с информационным входом блока памяти 3, л выходов которого соединены со входами суммирующего блокоа 1, а каждый из п адресных входов подключены соответственно к выходу с первого по n-й выходы счетчиков адреса чтения 4, входы которых подключены к выходу элемента задержки 6 и ко входу счетчика адреса записи 5, выход которого подключен к адресному входу чтения блока памяти 3, Шина тактовых импульсов 7 соединена с управляющим входом блока памяти 3 и со входом элемента задержки 6. Предлагаемый генератор формирует очередное случайное число по соотношению где М - разрядность двоичных чисел. В настоящее время цифровая вычислительная техника использует двоичные числа с фиксированной точкой как целые числа в дополнительном коде, когда точка расположена после младшего разряда. Выполнение суммирования случайных числе x(m-k) по модулю (mod 2M-1) означает следующее. Пусть производится суммирование дВУХ чисел Реализация соотношений (3) упрощается для дополнительного кода представления целых двоичных чисел. В этом случае суммирование по алгоритму (3) производится путем выполнения операции сложения двух чисел без учета переполнения разрядной сетки. Так для М -16 имеем 2(м-1) - 32768. Покажем выполнение формул (3) на примерах: Сложение по (mod 2м-1) выполнено автоматически, при этом перенос "1" не учитывается. Генератор случайных числе реализует соотношение (1), когда суммируется по (mod 2м-1) произвольное количество целых двоичных чисел. Их можно просуммировать последовательно Соотношение (4) автоматически выполняет n-входовой сумматор, в котором не учитывается перенос "1" из старшего разряда (этот перенос теряется). В итоге получаем результат Х(m) как целое двоичное число, лежащее в пределах Вырабатываемые случайные числа по алгоритму (5) имеют почти равномерный закон распределения с периодом цикличности Тц > 2 м [Крут Д. Искусство программирования на ЭВМ. М., Мир, 1977, т. 2]. Алгоритм (1) при n> 4 формирует равномерно распределенные случайные числа, которые имеют практически безграничный период цикличности. Предлагаемый генератор, быстродействие которого, как и у известного, равно быстродействию суммирующего блока можно с успехом использовать для цифровой обработки сигналов, а также при решении задач вероятностного моделирования реальных процессов. В блоке 3 памяти хранится К³Кn равномерно распределенных случайных чисел, при этом, в процессе реализации соотношения (1) блок памяти самообновляется. Для первоначального запуска генератора равномерно распределенные случайные числа можно взять из любой готовой таблицы. В вышеупомянутой книге Крут Д. Искусство программирования для ЭВМ. М., Мир, 1977 рекомендует индексы k1;k2,...kn в соотношении (1) выбирать по правилу kj - kj-1 >50, где (kj - kj-1) - числа простые, считая К0=0. Для примера можно ограничиться случаем n = 4, при этом индексам присвоить значения: k1 = 53; k2 = 59 + k1= 112; k3 = 67 + k2 =179;k4=73 + k3 = 252. Тогда в блоке памяти 3 можно хранить 28 = 256 равномерно распределенных случайных чисел, и этого достаточно для реализации алгоритма (1) при суммировании четырех операндов x(m-k1); x(m- k2); x(m- k3); x (m-k4). Аналогично можно определить объем блока памяти 3 при суммировании произвольного количества чисел x(m-Kj). Для обеспечения высокого качества случайных чисел следует использовать блоки генератора повышенной разрядности, а сами числа перед выходом усекать до заданной разрядности. В настоящее время наибольшее распространение получила 16-разрядная вычислительная техника, поэтому следует суммировать 32-разрядные операнды x(m-kj) с округлением результата x(m) до 16разрядного числа. На фиг.2 приведены примеры интерпретации 16-разрядных двоичных чисел x(m) с фиксированной запятой в зависимости от принятых правил размещения точки. Если точка расположена после младшего разряда (целые числа), то числа x(m) равномерно распределены в пределах: на фиг.2а имеем (-32768£x(m)) < +32768); на фиг.2б имеем (0 : x(m) < +65536, при этом знак + (код "0" только подразумеваемые. При интерпретации дробных чисел точка располагается после знакового разряда, в том числе при условном кодировании знака. На фиг.2а,б,в представлена интерпретация дробных чисел соответственно: (-1,0 ≤ x(m) < +1,0); (+0,0 ≤ x(m) < 1,0); (0,5 £ x(m) 50, а операнд x(m-1) ОТСТОИТ всего на один такт, от вырабатываемого числа x(m). Это приводит к неравномерности закона распределения. Увеличив количество суммируемых чисел x(m-kj) пo соотношению (1) неравномерность закона распределения случайных чисел x(m) устраняется, а период цикличности становится практически безграничным. Для достижения такого эффекта дополнительно введено (n-1) счетчиков, адреса чтения операндов. Таким образом, введение (n-1) счетчиков позволяет увеличить количество суммируемых операндов с двух до n при генерировании очередных случайных чисел без изменения быстродействия генератора. Качество случайных чисел |(т) повышается за счет улучшения равномерности распределения и особенно резкого увеличения периода цикличности.