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

(54) ГЕНЕРАТОР ПСЕВДОСЛУЧАЙНЫХ ЧИСЕЛ

Изобретение относится к вычислительной технике и может быть использованов качестве устройства для получения случайных чис.ел при решении задач методом Монте-Карло, а также для построения генераторов случайных процессов с заданными характеристиками. Известен генератор псевдослучайных ; чисел, содержащий регистр сдвига с сумматором по модулю два в цепи обратной связи СЗ- Недостатком этого генератора является невысокое быстродействие н наличие периода в формируемой последовательнооти. Известен также генератор псевдослучайных чисел, содержащий группу сумматоров по модулю два и группу триггеров, выходы синхронизации которых подключ ны к выходу генератора тактовых вмпуль:сов С2. В данном генераторе псевдослучайных чисел повышено быстродействие, но пероод генерируемой последовательности сох- ранен таким же как aflj. Наиболее близким к предлагаемому по технической сущности является генератор псевдослучайных чисел, содержащий две группы сумматоров по модулю два, две грутшы элементов И, группу элементов ИЛИ, группу триггеров, входы синхронизации которых подключены к выходу генератора тактовых шлпульсов и входу генератора равновероятной двоичной ЦИФ1Ы, причем к первым входам г -ых сумматоров по модулю два подклк чены единичные выходы -ы1с триггеров, к вторым входам j старыгах сумматоров по модулю два подключены выходы j младших триггеров, ц вторым входам ni-j младших сумматоров по модулю два подключены выходы m - j старших сумматоров по модулю два Гз . В известном устройстве при высоком быстродействии практически отсутствует период последовательности, кодов формируемых псевдослучайных чисел. Недостатком этого устройства является большой объем используемого оборудования. Цель изобретения - сокращение объема используемого оборудования, т.е. упрощение генератора. Поставленная цель достигается тем, что в генераторе псевдослучайных чисел, содержащем две группы из гп суммато ров по модулю два и группу из m триг геров, синхронизирующие входы которых подключены к выходу генератора тактовых импульсови входу генератора равновероятной двоичной цифры, а выходы триггеров группы подключены к первым входам соответствующих сумматоров по модулю два первой группы, причем выход j ( j m ) младших трт1ггеров группы подключены к вторым входам j старших сумматоров по модулю два первой группы а вторые входы m - j младших суммато- .ров по модулю два первой группы под|ключекы к вы ходам m -j старших сумма торов по модулю два первой группы, информационные входы триггеров группы подключены к выходам соответствующих сумматоров по модулю два первой группы третьи входы которых подключены к nei вому выходу генератора равновероятност ной двоичной цифры, второй выход кото- рого подключен к первым входам сумматоров по модулю два второй группы, вторые входы которых подключены к выходам соответствующих сумматоров по модулю два первой группьи На фиг. 1 приведена структурная схем генератора псевдослучайных чисел при Гп 5; на фиг. 2 - функциональная схема генератора при на фиг. 3 - npfrмер временной диаграммы сигналов, фор мируемых на выходе генератора тактовы импульсов (точка а), по приходу которы триггеры устройства меняют свое состоя ние, и на BfopoM (прямом) выходе генератора равновероятной двоичной цифры (точка в); на фиг. 4 - граф состояний и последовательности переходов элементов памяти (триггеров) генератора псевдослучайных чисел при m 3 для порождающего полинома f(x) определенный начальным состоянием 101 и временной диаграммой (фиг. 3).

Генератор псевдослучайных чисел состоит из m сумматоров 1 по модутпо два первой группы, гп сумматоров 2 по модулю два второй группы, m 3, генератора 4 такто№1Х импульсов, генератора 5 равновероятной двоичной цифа --«1®

i f,2,...,m, (2)

где d - выход i -го сумматора по Mt дулю два второй группы;

t - второй (прямой) выход генератора 5. ы. Причем входы сумматоров 1 по моулю два первой группы подключены к ыходам триггеров 3 и генератора 5 равовероятной двоичной цифры таким обраом, что на выходе сумматоров 1 форируются сигналы в соответствии со слеующей системой логических уравнений: -i©Vi ®b,,i,...j-i-, m-i VrVi©°m+j-i® ,J-H,...,m, де - единичный выход (m -i )-го триггера; q „, , ; - выход (m + j - i )-го сумматора по модулю два первой .группы; ) - первый (инверсный) выход генератора 5 равновероятной двоичной цифры; нак Ф - означает операцию суммирования по модулю два; i - номер разряда регистра сдвига, выход которого вместе с выходом m -го разряда соединен с входами сумматора по модулю два в последовательных структурах. Если m 5, j 3 и Ъ 0, то система (1) примет вид 0 01., .-b , (4Следовательно, при Ь 0 предлагаемое устройство (фиг. 1) позволяет генерировать пятиразрядные коды псевдослучайных чисел М-последовательности, порождаемой полиномом (x)x +Х + +1 (как в устройстве-прототипе). При 1 система (1) принимает вид ; с( «4 Ч® « Ч ® 012 Ъ2 ©«5 J Очевидно, Мтпоследрвательности, генерируемые при t 0 и Ъ 1, будут иметь одинаковые периоды, но очередность появления кодов и их состав различны (фиг. 4). Входы сумматоров 2 по модулю два второй группы подключены к сумматорам 1 по модулю два первой группы и второму выходу генератора 5 в соответствии со следующей системой уравнений: Кроме того, выход генератора 4 тактовых импульсов подключен к входу генератора 5 равновероятных двоичных цифр и первым входам триггеров 3. Устройство функционирует следующим образом. Исходное состояние триггеров - пронзвопБВое. В зависимости от значения двоичной цифры, сформированной генератором 5, на выходах сумматоров 1 появляется очередной код первой или второй М-последовательности. По переднему фронту тактового импульса в триггеры 3 записывается код с выходов сумматоров 1, по зрднему фронту тактового импульса генератор 5 формирует очередное зна чение равновероятной двоичной цифры. Генератор 5, как и в прототипе, мо.жат быть построен по простейшей схеме например триггер с коммутируемым , физических генераторов равновероятной двоичной цифры. Более подробно процесс генерирования псевдослучайных чисел поясним на ко кретном примере. Пусть в первоначальный момент времени на триггерах 3 (фиг. 2) записан код 101 и пусть генератор 5 на своем втором (прямом) выхо де формирует сигнал, как это представле но на фиг. 3. Тогда до прихода первого тактового импульса на выходах сумматоров 1 в соответствии с (l) формиру ет ся код § О10, а на выходах сумматоров 2 в соответствии с (2) - код f 2 1О1. По переднему фронту первого так тового импульса, пришедшего с выхода генератора 4 на первые (синхро-) входы триггеров 3, в триггера 3 записывается код 010. По заднему фронту первого тактового импульса (фиг. 3) значение сигнала на выходах генератора 5 меняется на противоположное. После окончания переходных процессов на выходах сумматоров 1 устанавливается код 100, на выходах сумматоров 2 - также код 1ОО. Подобным образом триггеры меняют свое состояние в зависимости от значения сигналов на выходе генератора 5 и по приходу последующих импульсов. На фиг. 4 стрелками с номерами показана последовательность перехода состояний триггеров в течение первых девяти тактов работы устройства. Из вышеприведенного описания функционирования генератора псевдослучайны чисел следует, что значения g , формируемые на выходах сумматоров 1 по мо дулю два первой группы, в каждый конкретшый такт являются значениями кодов двух различающихся между собой М-последовательностей. Каждое последующее значение 6. является следующим, значением либо одной и той же М-последовательности, либо, другой М-последовательности, что определяется значением двоичной цифры, формируемой на выходе генератора 5 равновероятной двоичной цифры. Нетрудно зaмefить, что при фиксировании на первом выходе генератора 5 значений 1 или О предлагаемый генератор генерирует одну из двух М-последовательностей, представленных на фиг. 4. На фиг. 4 пунктирами показаны для сравнения направления изменения состояний регистра сдвига последовательного генератора псевдослучайных чисел , типа (1). Преимущества предлагаемого генератора псевдослучайных чисел по сравнению с прототипом заключаются в сокращении объема используемого оборудования. Так удельные аппаратные затраты на один разряд псевдослучайного числа в прото- типе составляют один сумматор по модулю два, один элемент И, 1/2 элемента ИЛИ, D -триггера, 1/2 генератора равновероятной двоичной цифры и 1/2 генератора тактовых импульсов. В предлагаемом, же устройстве для этих целей требуется лишь один сумматор по модулю два, 1/2D -триггера, 1/2 генератора равновероятной двоичной цифры и 1/2 генератора тактовых импульсов. Следует заметить, что в прототипе и предлагает мом устройстве значения &- и Q,KOpvрелированы, так как порождаются одним состоянием триггеров (в предлагаемом устройстве зависимость меньше, так как одно и тоже состояние триггеров может породить два значения | , два значения 2 в прототипе - только по одному). В ряде случаев наличия корреляции огра ничивает использование устройства в двухканальном режиме. При реализации одноканального режима, например при генерировании только последовательности , в устройстве-прототипе все равно требуется две группы по гп сумматоров по модулю два. В предлагаемом же устройстве m сумматоров по модулю два второй группы используются только ддя организации второго канала. Следователь но, в одноканальном режиме преимущества предлагаемого устройства более очевидньт. Кроме того, как это следует из (1) и (2) а видно вз фиг. 4 в устройстве генерируются последовательности из чисел (включая нулевую комбинацию), а не , Последнее также является отличительным положительным свойством устройства. Предлагаемое устройство формирует последовательность практически неограниченной длины,так как период последовательности стремится к бесконечности даже при ограниченной разрядной сетке базового регистра сдвига. Кроме того, устройство позволяет воспроизводить три типа последовательности (в базовом - . один) при одном и том же порождающем полиноме. Предлагаемое устройство отличается высоким быстродействием: скорость формирования п -разрядного числа в п раз выше. Формула изобретения Генератор псевдослучайных чисел, содержаишй две группы из m сумматоров по модулю два и группу из гп триггеров синхронизирующие входы которых подключены к выходу генератора тактовых импульсов и входу генератора равноверо ятной двоичной цифры, а выходы триггеров группы подключены к первым входам соответствующих сумматоров по модулю два первой группы, причем выходы j ( j m ) младших триггеров группы подключены к вторым входам j старших сумматоров по модулю два первой группы, а вторые входы т - j младших сумматоров по модулю два первой группы подклк чены к выходам tti - j старших сумматоров по мйдупю два первой группы, отличающийся тем, что, с целью упрощения генератора, информационные входы триггеров группы подключены к выходам соответствующих сумматоров по модулю два первой группы, третьи входы которых подключены к первому . выходу генератора равновероятной двоичной цифры, второй выход которого подключен к первым входам сумматоров по модулю два второй группы, вторые входы которых подключены к выходам соответствующих сумматоров по модулю два первой группы. Источники информации, принятые во внимание при экспертизе 1. Яковлев В. В., Федоров Р.Ф. Вероятностные вычислительные машины. Л., Машиностроение, 1974, с. 344.. 2., Авторское свидетельство СССР № 634329, кл. Q 06 F 7/58, 1976, 3. Авторское свидетельство СССР № 708381, кл. Q Об F 7/58, 1978. (прототип).