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

(23) Приоритет ео делам изобретений и открытийОпубликовано 28.02.83. Бюллетень8 Дата опубликования описания 02.03.83(72) Автор изобретения А, Н. Морозевич Минский радиотехнический институт(54) ГЕНЕРАТОР ПСЕВДОСЛУЧАЙНЫХ ЧИСЕЛ Изобретение относится к вычислительной технике и может быть использовано. в качестве устройства для получения случайных чисел при решении задач мето два Монте-Карло, а также для построения генераторов случайных процессов с заданными характеристиками,Известен генератор псевдослучайных; чисел, содержащий регистр сдвига с сумматором по модулю два в цепи обратной 1 освязи Г 1 3.Недостатком атого генератора являеъся невысокое быстродействие и наличиепериода в формируемой последовательнооти. 15Известен также генератор псевдослучайных чисел, содержащий группу сумматоров по модулю два и грушту триггеров,выходы синхронизации которых подключены к выходу генератора тактовых импульгосов 21,В данном генераторе псевдослучайныхчисел повышено быстродействие, но период генерируемой последовательности сохранен таким же как в 1 1 1,Наиболее близким к предлагаемомупо технической сущности является генератор псевдослучайных чисел, содержащий две группы сумматоров по модутцодвв, две группы элементов И, группуалементов ИЛИ, группу триггеров, входы синхронизации которых подключены квыходу генератора тактовых импульсови входу генератора равновероятной двоичной цифры, причем к первым входам1 -ых сумматоров по модулю два подключены единичные выходы 1 -ы)с триггеров,к вторым входамстарших сумматоровпо модулю два подключены выходы )младших триггеров, к вторым входам1 тт- младших сумматоров по модулю двв4подключены выходы тп- т старших суммаоров по модулю два Г 3,") В известном устройстве при высоком быстродействии практически отсутствует период последовательности, кодов форми5 10010Кроме того, выход генератора 4 тактовых импульсов подключен к входу генератора 5 равновероятных двоичныхцифр и первым входам триггеров 3,Устройство функционирует следующим 5образом.Исходное состояние триггеров - произволвное. В зависимости от значениядвоичной цифры, сформированной генератором 5, иа выходах сумматоров 1 появляется ачередной код первой или второй М-последовательности. По переднемуфронту тактового импульса в триггеры 3записывается код с выходов сумматоров1, по зецнему фронту тактового импульса генератор 5 формирует очередное значение равновероятной двоичной цифры.Генератор 5, как и в прототипе, мо.жет быть построен по простейшей схеме,например триггер с коммутируемым пигнием, физических генераторов равнсвероятной двоичной цифры,Более подробно процесс генерированияпсевдослучайных чисел поясним на конкретном примере. Пусть в первоначальный момент времени на триггерах 3(фиг, 2) записан код 101 и пусть генератор 5 на своем втором (прямом) выходе формирует сигнал, как это представлено на фиг. 3. Тогда до прихода первого зОтактового импульса на выходах сумма 1торов 1 в соответствии с (1) формируется код=010, а на выходах сумматоров 2 в соответствии с (2) - код=101, По переднему фронту первого так тового импульса, пришедшего с выходагенератора 4 на первые (синхро-) входытриггеров 3, в триггера 3 записываетсякод 010. По заднему фронту первоготактового импульса (фиг. 3) значение , 40сигнала на выходах генератора 5 меняется на противоположное. После окончания переходных процессов на выходахсумматоров 1 устанавливается код 100,на выходах сумматоров 2 - также код 45100, Подобным образом триггеры меняют свое состояние в зависимости отзначения сигналов на выходе генератора5 и по приходу последующих импульсов,На фиг. 4 стрелками с номерами пока озана последовательность перехода состояний триггеров в течение первых девятитактов работы"устройства. Из вышеприведенного описания функционирования генератора псевдослучайных55 чисел следует, что значения я формьурруемые на выходах сумматоров 1 по модулю два первой группы, в каждый кон 97 6кретный такт являются значениями кодов двух различающихся между собой М-последовательностей, Каждое последующее значениеявляется следующим. значением либо одной и той же М-после довательности, либо. другой Мпоследовательности, что определяется значением двоичной цифры, формируемой на выходе генератора 5 равновероятной двоичной цифры. Нетрудно замеФить, что при фиксировании на первом выходе генератора 5 значений 1 " или 0" предлагаемый генератор генерирует одну из двух М-последовательностей, представленных на фиг. 4. На фиг. 4 пунктирами показчны для сравнения направления изменения состояний регистра сдвига последовательного генератора псевдослучайных чисел,типа (1)Преимущества предлагаемого генератора псевдослучайных чисел по сравнению с прототипом заключаются в сокращении объема используемого оборудования, Так удельные аппаратные затраты на один разряд псевдослучайного числа в прототипе составляют один сумматор по модулю два, один элемент И, 1/2 элемента ИЛИ, 1) -триггера, 1/2 генератора рав новероятной двоичной цифры и 1/2 генератора тактовых импульсов. В предлагаемом,же устройстве для этих целей требуется лишь один сумматор по модулю два, 1/2 Э -триггера, 1/2 щ генератора равновероятной двоичной цифры и 1/2 генератора тактовых импульсов. Следует. заметить, что в прототипе и предлагае- мом устройстве значения а икорт релированы, так как порождаются одним состоянием триггеров (в предлагаемом устройстве зависимость меньше, так как одно и тоже состояние триггеров может породить дм значения 1, два значения , в прототипе - только по одному). В ряде случаев наличия корреляции огра-.1ничивает использомние устройства в двухканальном режиме. При реализации одноканального режима, например при генерировании только последовательности, в устройстве-прототипе все равно требуется две группы по и) сумматоров по модулю дм. В предлагаемом же усз- ройстве п 1 сумматоров по модулю два второй группы используются только цля организации второго канала. Следомтель но, в одноканальном режиме преимущества предлагаемого устройства более очевидны.Кроме того, как это следует из (1) и (2) и видно из фиг. 4 в устройстве7 1001 генерируются последовательности из 2 щ чисел (включая нулевую комбинацию), а не 2 -1. Последнее также является отличительным положительным свойством устройства.Предлагаемое устройство формирует последовательность практически неограниченной длины,так как период последовательности стремится к бесконечности даже при ограниченной разрядной сетке базового регистра сдвига, Кроме того, устройство позволяет воспроизводить три типа последовательности (в базовом -, один) при одном и том же порождающем полиноме.Предлагаемое устройство отличается высоким быстродействием: скорость формирования о -разрядного числа в и раз выше. формула изобретения два первой группы, причем выходы(( т 1 ) младших триггеров группы подключены к вторым входамстарших сумматоров по модулю два первой группы, 5 а вторые входытп - младших сумматоров по модулю два первой группы подипочены к выходам Ф -1 старших сумматоров по модулю два первой группы, о тличающийся тем,что,сцелью ф упрощения генератора, информационныевходы триггеров группы подключены к выходам соответствующих сумматоров по модулю два первой группы, третьи входы которых подключены к первому .выходу генератора равновероятной двоичной цифры, второй выход которого подключен к первым входам сумматоров по модулю два второй группы, вторые входы которых подключены к выходам 20 соответствующих сумматоров по модулюдва первой группы.Генератор псевдослучайных чисел, содержащий две группы из п 1 сумматоров 25 по модулю два и группу из гп триггеров, синхронизирующие входы которых подключены к выходу генератора тактовых импульсов и входу генератора равновероятной двоичной цифры, а выходы тригге- ЗО ров группы подключены к первым входам соответствующих сумматоров по модулю Источники информации,принятые во внимание при экспертизе1. Яковлев В.В., федоров Р.ф.Вероятностные вычислительные машины,Л., "Машиностроение", 1974, с. 344,2 Авторское свидетельство СССР% 634329, кл. С 06 Р 7/58, 1976,3, Авторское свидетельство СССР