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

ОП ИСАНИЕ

ИЗОБРЕТЕН ИЯ

К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ

Союз Советски к

Социапмстмческмн

Республмк

«» 903874 (61) Дополнительное к авт. свид-ву (22) Заявлено 23.06.80 (21) 2945038/18-24 с присоединением заявки И(23) П риоригет

Опубликовано 07.02,82. Бюллетень Юе 5

Дата опубликования описания 07.02 82 (5l)N. Кл.

806F: 7/58 Ьаударстиииый комитет

СССР ао делам изобретений и открытий

Рз) П (681.325. (088.8) (72) Автор изобретения

В. Н. Ярмолик (71) Заявитель

Минский радиотехнический институт (54) ГЕНЕРАТОР ПСЕВДОСЛУЧАЙНЫХ ЧИСЕЛ

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

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

Недостатком этого генератора явля1S ется сложность структурного построения.

Кроме того, при построении генератора необходимо выбирать структуры исходных генераторов такими, чтобы их периоды

20 .являлись взаимно простыми числами, что не всегда оказывается возможным.

Наиболее близким по технической сушности к изобретению . вляется генератор псевдослучайных чисел, содержащий триггеров со счетным входом и w - сумматоров по модулю,два(2).

Величина .. 1 выбирается в зависимости от разрядности регистра сдвига ил(от количества триггеров со счетным входом), Подобный генератор предназначен для генерирования за один такт, по ткриходу тактового импульса, очередного и - разрядного псевдослучайного числа. В отличие от известных устройств подобного типа данный генератор отличается максимальным быстродействием и минимальными удельными аппаратурными затратами.

В то же время он обладает одним существенным недостатком, который выражается в том, что не для любого w оказывается известной величина

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

903874

Поставленная цель достигается тем, что в генератор псевдослучайных чисел, содержащий м триггеров первой группы, дополнительно введены и триггеров второй группы, м групп элементов И и и и -входовых сумматоров по модулю два, причем в каждой из групп элементов И сопержится по ил элементов И, выходы и элементов И в-ой группы (k =.1, 2, ...,

i --го триггера второй группы, а единич-. ный выхоп 4 -го триггера первой группы 15 подключен ко второму входу (i+I-1 )-го элемента И -ой группы, а выход <-го сумматора по модулю пва подключен ко второму входу L-ro элемента И (4 +1) -ой группы; Bbixog 4 -ro сумматора по мо- 2О дулю пва подключен к D входу (l-4)го триггера первой группы, к синхровходу которого подключен выход генератора тактовых импульсов, причем выходами устройства являются выхопы ю суммато- 25 ров по модулю два, с которых по приходу тактового имлульса снимается очередНое псевдослучайное число, à P,S вхопы триггеров второй группы являются входом устройства. ЗО

Ф

На фиг. 1 приведена общая функциональная схема генератора; на фиг. 2— функциональная схема генератора при =3, J =1, на фиг. 3 — последовптельНость состо Яний триггеров известного и 35 предлагаемого генераторов.

Функциональная схема генератора псевдослучайных чисел включает первую группу,из и триггеров 1, вторую группу из м триггеров E,ì групп из авух40 входовых элементов И 3 и и ил -Bxollosaix сумматоров 4 по модулю пва, причем выходы м элементов И. i -ой группы 3 подключены к м входам 4. -го сумматора

4 по модулю. два, к первому входу < -го элемента И Е -ой группы 3 подключен единичный выход < -го триггера второй группы 2, а выход 4 — ro триггера 1

Первой группы подключен ко второму вхоlly (i+ Ю-1)-ro элемента И 1 -ой группы

3, а выход < -го сумматора 4 по модулю два подключен ко второму влопу 4 -го элемента И (1+ 1„)-ой группы 3, выход

4-го сумматора 4" по модулю два подключен к D входу (м+1-а)-го триггера 1 первой группы, к синхровходу которого йодключен выход генератора тактовых импульсов, причем выхопами устройства являются выходы м сумматоров по модулю два, с которых по приходу тактового импульса снимается, очередное псевдослучайное число, à RS входы триггеров второй группы 2 являются входами устройства. функционирование генератора псевдослучайных чисел происходит следующим образом.

В исходном состоянии на триггеры второй группы 2 по RS входам записываются значения коэффициентов, задающих структуру цепи обратной связи регистра сдвига, а содержимое -ro разряда триггеров 1 первой группы может принимать значения нуля,или единицы. Запрещенным является код, рав ный нулю, хра ня щийся на триггерах первой группы 1, в противном случае последовательность копов выражается в последовательность нулевых кодов. В зависимости от коаов, храняшихся на триггервх 1 и 2 первой и второй группы на выходе комбинационной части, состоящей из элементов И 3 и сумматоров 4 по модулю пва формируется значение очередного кода. По приходу тактового импульса значение очередного кода записывается на триггеры,l первой группы. После прохождения переходных процессов во всех цепях на выходе сумматоров 4 по модулю два получается значение очередного. кода, таким образом

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

На фиг. 3 приведена последовательность состояний триггеров первой группы.

Анализируя эту последовательность можно заметить, что предлагаемый генератор при =3 и =1 функционирует как и известный, В то же время структура генератора, приведенного на фиг. 1 и фиг. 2,позволяет генерировать любыем последовательности на базе регистра сдвига определенной разрядности. Причем замена одной м последовательности на другую производится .путем перезаписи на триггерах второй группы новых коэффициентов, соответствующих новой последовательности. Возможность перезаписи коэффициентов позволяет генерировать произвольные последовательности и, ".àêè; образом, расширить функциональные возможности генератора псевдослучайных чисел. формула изобретения

Генератор псевдослучайных чисел, сопержащий и триггеров первой группы, 5 903874 6 о т л и ч а ю ш и и с я тем, что, с второму входу 3 -го элемента И (j, + f)целью расширения функциональных возмож- ой группы, выход i -го сумматора по ностей генератора за счет обеспечения модулю flB& подключен к 0 входу (и+1- ) генерирования любой м последователь- -го триггера первой:группы,ксинхровходу ности, он содержит триггеров второй g которого подключен выход генератора группы, vn групп по » эпементов И в тактовых импульсов, причем выходами кажцой группе и м сумматоров по моду- устройства являются выходы сумматоров лю цва, выходы м элементов И j -ой,по модулю два, а входами хS вхоцы группы (ь =1, 2, ..., и) подключены к триггеров второй группы. ь вхоцам Ф-го сумматора по модулю 1О

"два соответственно, к первому вхоцу4- Ис точники информации, го элемента И -ой группы (4 =1, 2,..., принятые во внимание при экспертизе

m) подключен ециничный выход 4, -го 1. Яковлев В.В. и Федоров P.Ô. Ветриггера второй группы, единичный выход роятностные вычислительные машины, Л., 4-го триггера второй группы, единичный 15 "Машиностроение, 1974, с. 344. выхоц -го триггера первой группы подключен ко второму вхоцу (i + "-1)-го 2.Авторское свидетельство СССР элемента И -ой группы, выхоц i. -го N. 57282З, кл. 607 С 15/00, 1977 сумматора по модулю цва подключен ко (прототип) .

903874

Составитель А. Карасов редактор Н. Лазаренко Texpea N. Надь Корректор А. Дзятко

Заказ 1 23/31 Тираж 731 Подписное

ВНИИПИ Госуаарственного комитета СССР по аелам изобретений и открытий

113035, Москва, Ж-35, Раушская наб., a. 4/5

Филиал ППП Патент, г. Ужг.;."ц., ул. Проектная, 4