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

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

Изобрете1гае относится к вычислительной технике и может быть использовано в качестве устройства аля получения случайных чисел при решении задач методом Монте-Карло, а также для построения генераторов случайных процессов с .заданными характеристиками. Весьма важной областью применения подобных устройств является область генерирования случайных процессов с равномерным спектром, используемых для идентификации систем автоматического управления. Известен генератор псевдослучайных чисел, содержаи1ий два регистра сдвига и группу сумматоров по модулю дваШ . Недостатком этого генератора является сложность структурного построения. Кроме того, при построении генератора необходимо выбирать структуры исходных генераторов такими, чтобы их периоды .являлись взаимно простыми числами, что не всегда оказывается возможным. Наиболее близким по технической сущности к изоб ретению гвпяется генератор псевдослучайных чисел, содержащий триггеров со счетным входом в v - i сумматоров по модулю два 2 . Величина .j выбирается в зависимости от разрядности регистра сдвига w (от колвчества триггеров со счетным входом). Подобный генератор предназначендля генерирования за один такт, по приходу тактового импульса, очередного ил - раэрядного псевдослучайного числа. Б отлвчие от известных устройств подобного типа данный генератор отличается максимальным быстродействием и минимальными удельными аппаратурными затратами. В то же время он обладает одним существенным недостатком, который выражается в том, что не для любого vn оквгзывается известной величина j . Цель изобретения - расширение функциональных возможностей генератора псевдослучайных чисел, что достигается возможностью построения генератора для любого m и для любого неприводимого многочлена при фиксированном . 390 Поставленная цепь достигается тем, чго в генератор псевдослучайных чисел, содержащий ж триггеров первой группы, дополнитепьновведены и триггеров второй групш:., И1 групп элементов И и ;m-BxoaoBMK сумматоров по модулю цва, причем в каждой из vvi групп элементов И содержится по wi элементов И, выходы И1 элементов И группы (i 1, 2, . ,м} подключеш. к (входам i-го сумматора по модулю два, а к-первому входу i -го элемента И i -ой группы (1, 2, ...,Hi) подключен единичный выход i -го триггера второй группы, а единичЕый выход it-го триггера первой группы подключен ко второму входу ()-ro элемента И t-ой группы, а выход i-rq сумматора по модулю два подключен ко второму входу-f -ro элемента И (i +) -о группы; выход i -го сумматора по модулю два подключен к D входу (vMi-l-t)го триггера первой группы, к сиихровходу которого подключен выход генератора тактовых импульсов, причем выходами устройства являются выходы HI сумматоров по модулю два, с которых по прихоцу тактового импульса снимается очёредНое псевдослучайное число, а R,S входы триггеров шторой группы являются входом устройства. На фиг. 1 приведена общая функциональная схема генератора , на фиг. 2 функциональная схема генератора при « 3, 1; на фиг. 3 - последовательность состояний триггеров известного и предлагаемого генераторов. Функциональная схема генератора псевдослучайных чисел включает первую группу ,из И1 триггеров 1, вторую группу из in триггеров 3.,wi групп из i двухвходовых элементов И 3 и vn wi -входо&ЫХ сумматоров 4 по модулю два, причем выходы уп элементов И i -ой группы 3 подключены к vi входам t, -го сумматора х1 ,,„. 4 по модулю, два, к первому входу г -го V элемента И L -ой группы 3 подключен единичный выход f -го триггера второй группы 2, а выход i -то триггера 1 Первой группы подключен ко второму вхоДУ (1+г-1)-го элемента И -ой группы -- О, а ВЫХОД t -ГО сумматора 4 по модулю два под1Шючеи ко второму влоду i -го ajjeMeHTa И (г+О-ой группы 3, выход -го сумматора Фпо модулю два подключен к D входу (w-l-i)-ro триггера 1 первьй группы, к синхровходу которого Подключен выход генератора тактовых импульсов, причем выходами устройства 4 являются выходы м сумматоров по модулю два, с которых по приходу тактового импульса снимается .очередное псевдослучайное число, а RS входы триггеров второй группы 2 являются входами устройства. Функционирование генератора псевдослучайных чисел происходит следующим образом. В исходном состоянии на триггеры второй группы 2 по RS входам записываются значения коэффициентов, задающих структуру цепи обратной связи регистра сдвига, а содержимое к-го разряда триггеров 1 первой группы может принимать значения нуля, или единицы. Запрещенным является код, равный нулю, хранящийся а триггерах первой группы 1, в против„QJ случае последовательность кодов выраншется в последовательность нулевых кодов. В зависимости от кодов, хранящихся на триггервх 1 и 2 первой и второй группы на-выходе комбинационной части, состоящей из элементов И 3 и сут маторов 4 по модулю два формирует я значение очередного кода- По приходу тактового импульса значение очередного па записывается на триггеры,, первой группы. После прохождения переходных процессов во всех цепях на выходе сумматоров 4 по модулю два получается значение очередного кода, таким образом на выходе устройства генерируется последовательность кодов VM последовательности. На фиг. 3 приведена последовательность состояний триггеров первой группы. Анализируя эту последовательность можно заметить, что предлагаемый генератор при И1 3 и J 1 функционирует как и известный , В то же время структура генератора, приведенного на фиг. 1 и фиг. 2,позволяет генерировать любыеvn последовательности на базе регистра сдвига определенной разрядности. Причем замена одной vn последовательносmtv гчг I-IT-iti-TS Tti-v UTr if Trrrt n Г nVTrni-ЧТГГ ГТС1 t ITtbY i ти на другую производится .путем перезаписи на триггерах второй группы новых коэффициентов, соответствующих новой последовательности. Возможность переза- и коэффициентов позволяет-генериро,, пят(, ттгж.чпппкиыр IVI ппг-ПйПпвятяльностн вать произвольные i последовательности и, raKiCvi образом, расщирить функциональные возможности Генератора псевдослучай цых чисел. фор,ду„а изобретения Генератор псевдослучайных чисел, содержащий m триггеров первой группы. отличающийся тем, что, с целью расширения функциональных возмож ностей генератора за счет обеспечения генерирования любой и/1 последовательности, он содержит триггеров второй группы, у групп по и элементов И в каждой группе и w сумматоров по модулю два, выходы W элементов И г -ой группы (, 2, ...,) подключены к ) входам i-го сумматора по модулю два соответственно, к первому входуi,го элемента И -ой группы ( 1, 2 и) подключен единичный выход i -го триггера второй группы, единичный выхо i-го триггера второй группы, единичны выход i -го триггера первой группы под к.пючен ко второму входу (i +v-l)-ro элемента И -ой группы, выход i -го сумматора по модулю два подключен ко второму входу I -го элемента И (4. + ) - о и группы, выход i -го сумматора по модулю два подключен к О входу (и-bl-i) -го триггера первой .группы, к синхровхоцу которого подключен выход генератора тактовых импульсов, причем выходами устройства являются выходы сумматоров по модулю два, а входами R,S входы триггеров второй группы. Источники информации, принятые во внимание при экспертизе 1. Яковлев В. В, и Федоров Р. Ф. Вероятностные вычислительные машины, Л., ГМашиностроение, 1974, с. 344., , 2.Авторское свидетельство СССР № 572823, кл. G 07 С 15/ОО, 1977 (прототип).

ф1/г.г