Генератор псевдослучайных чисел
Союз Советскмн
Соцмалмстмческмк
Республик
ОП ИСАНИЕ
ИЗОБРЕТЕН ИЯ
К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ
4 06 Р 7/58 Гасударственный квинтет Опубликовано 23. 02.82. Бюллетень М 7 Дата опубликования описания 25. 02. 82 по делам нзабретеннй н открытнй (53) УДК 681. ° 325 (088 . 8 ) (72) Авторы изобретения В.Н. Ярмолик, A.Å. Леусенко и А.Н. Морозевич f, ! 1 (7I ) Заявитель Минский радиотехнический институт (54) ГЕНЕРАТОР ПСЕВДОСЛУЧАЙНЫХ ЧИСЕЛ Изобретение относится к вычислительной технике и может быть использовано в качестве устройства для получения случайных чисел при решении задач методом Монте-Карло, а также для построения генераторов случайных процессов с заданными характеристиками, кроме того, применение подобных устройств может быть использовано для генерирования случайных процессов с равномерным спектром, используемых для идентификации систем автоматического управления. Известен генератор псевдослучайных чисел, содержащий два регистра сдвига и группу сумматоров по модулю два (1). Недостатком этого генератора является сложность структурного построения. Кроме того, при построении генератора необходимо выбирать структуры исходных генераторов такими, чтобы их периоды являлись взаимно простыми числами, что не всегда оказывается возможным. Наиболее близким по технической сущности к изобретению является ге5 нератор псевдослучайных чисел, содержащий первую и вторую группы двухвходовых сумматоров по модулю два, первую и вторую группы трехвходовых 1О сумматоров по модулю два, первую и вторую группы элементов И, группу элементов ИЛИ, группу триггеров и генератор равновероятной двоичной цифры (2). 1S Известный генератор предназначен для генерирования за один такт двух m разрядных псевдослучайных чисел, причем вероятность появления нуля или единицы в разрядах псевдослучайных чисел по первому и второму каналам равняется 0,5. Недостаток известного устройстваниэкое быстродействие. 90754 Цель изобретения - увеличение быстродействия генератора псевдослучайных чисел. Поставленная цель достигается тем, что в генератор псевдослучайных чисел, содержащий первую и вторую группы трехвходовых сумматоров по модулю два, первую и вторую группы элементов И, группу элементов ИЛИ, группу 10 триггеров и генератор равновероятной двоичной цифры, ко входу которого подключен выход генератора тактовых импульсов, а единичный и нулевой выходы генератора равновероятной 1S двоичной цифры подключены к первым входам элементов И первой и второй группы соответственно, ко второму входу j (j - число сумматоров по модулю два в первой группе) старших элементов И первои группы подклюZ0 чены выходы j старших трехвходовых сумматоров по модулю два первой группы; ко второму входу m-j (m - число элементов И в,каждой группе, а число элементов ИЛИ в группе " число триггеров s группе) старших элементов И второй группы подключены выходы m-j старших трехвходовых сумматоров по модулю два второй группы, выходы 1-ых (i=1,2,...) элементов И первой и второй группы подключены ко входам i-ro элемента ИЛИ, выход которого подключен к 0 входу i-ro триггера,к синхровходу которого подключен выход генератора тактовых импуль- З сов, к первым входам i-ых трехвходовых сумматоров по модулю два первой и второй групп подключены единичные выходы (m-j+i) и (j+i)-ых триггеров 40 соответственно, ко вторым входам j трехвходовых сумматоров по модулю два первой группы подключены выходы младших триггеров, ко вторым входам m-j трехвходовых сумматоров по модулю два второй группы подключены выходы m-j младших триггеров, к третьим входам j трехвходовых сумматоров по модулю два первой группы подключен нулевой выход генератора равновероя;ной двоичной цифры, к третьим входам m-j трехвходовых сумматоров по модулю два второй группы подключен нулевой и единичный выход генератора равновероятной двоичной цифры, соответственно введены группа четырехвходовых сумматоров по модулю два, и групп сумматоров по модулю два, по j(i+3)-входовых сумматоров по модулю 8 ф два в i-ой группе и m-u-j (n+3)-входовых сумматоров по модулю два в и-ой группе, причем к первым, вторым и третьим входам (m-1)-ых четырехвходовых сумматоров по модулю два подключены выходы (2m-2j- )-ых, (2m-j-i)-ых и (m-i) ûõ триггеров (=тп-j, m-1) соответственно, а выходы j четырехвходовым сумматором по модулю два подключены ко второму входу j младших элементов И второй группы, к четвертым входам j четырехвходовых сумматоров по модулю два подключен единичный выход генератора равновероятной двоичной цифры, на первый, второй и третий входы Я-го (i+3) входоsoro сумматора по модулю два i-ой группы заведены выходы (m+1-i)-ых (j+1-9 )-ых триггеров и нулевого выхода генератора равновероятной двоичной цифры соответственно, а на (К+3)-ие входы Р-го (i+3) — входового . сумматора по модулю два заведены входы (m-j+1-К)-го триггера, кроме того, вторые входы в-1 младших элементов И первой группы подключены к выходам m-j (i+3) входовых сумматоров по модулю два. На фиг. 1 приведена функциональная схема генератора псевдослучайных чисел при m = --4 и j = 1; ка фиг. 2 - временная диаграмма его работы. Генератор псевдослучайных чисел состоит из m триггеров 1, m элементов ИЛИ 2, перво" группы из в элементов И 3, второй группы из m элементов И 4, генератора 5 равновероятной двоичной цифры, и m/j- 1 по j + 3 входовых сумматоров по модулю два в i-ой группе и m-n j n+3 входовых сумматоров по модулю два в и-ой группе 6, j четырехвходовых сумматоров по модулю два 7, первой группы из j трехвходовых сумматоров по модулю два 8, второй группы из m-j трехвходовых сумматоров по модулю два 9. Количество трехвходовых сумматоров по модулю два в первой группе равняется 1, а во второй rpynnem-j. В то же время количество (i+3) входовых сумматоров по модулю два 6 равняется m-j, а количество четырехвходовых — j. .На выходах (i 3) входовых сумматоров по модулю два блока 6 и трехвходовых сумматоров по модулю два 8 получается значение 907548 t0 и. t5 е- го г5 зо 4D 5 псевдослучайного числа 1=а,а а>, а на выходах четырехвходовых сумматоров по модулю два 7 и трехвходовых второй группы 9 значение псевдослучайного числа 2=а,а,... а . Числа g 1 и $ 2 представляют собой m-разрядные коды или их инверсии M последовательностей, порождаемых следующими полиномами $(Z)=2"1-2 +1 и V (Z)=Z +Z +1, причем периоды обоих последовательностей одинаковы. Последовательность следования кодов отлична и случайна как в первой, так и во второй И последовательност Появление прямого кода И последовательности или его инверсии по первому и второму каналу определяется значением очередного отсчета на выходе генератора равновероятной двоичной цифры. Выходы 0-триггеров и r нератора равновероятной двоичной цифры соединены со входами трехвходовых сумматоров по модулю два первой и второй группы. Выходы 0-триггеров соединены со входами m-j многовходовых сумматоров по модулю два 6. В зависимости от значения равновероятной двоичной цифры на выходе генератора 5 равновероятной двоич.— ной цифры код псевдослучайного числа 1 1 или 2 с выходов сумматоров по модулю два через элементы ИЛИ 2 записывается на 0-триггеры. Генератор представляет собой простой датчик равновероятной двоичной цифры. Функционирование генератора псевдослучайных чисел происходит следующим образом. ходу тактового импульса на синхронизирующие входы триггеров 1 на их 0-входы через первую или вторую группы элементов И 3, 4 и через элементы ИЛИ 2, определяющие выходы обоих групп элементов И, подается очередной код первой или второй И последовательности. С приходом очередного тактового импульса процесс повторяется. Временная диаграмма работы предлагаемого генератора псевдослучайных чисел полностью соответствует временной диаграмме работы известного генератора, т.е. они генерируют абсолютно идентичные последовательности, В то же время предлагаемое устройство отличается значительно большим быстродействием. Частота следования тактовых импульсов будет определяться временем прохождения электрического сигнала по самому длинному пути, т.е. величиной Т = 4tg, причем величина Т не зависит от значения m. При любом m величина Т неизменна. Для случая m = 10 и j = 3 величина задержки для известного устройства определяется выражением Т = 1it, что в — = 2 ра4 4 4 за больше чем в предлагаемом устрой.стве, а для я = 20 Т = 17t> t 4t> = 21 = 21t, т.е. + = 3 + раз больше, чем в предлагаемом устройстве. Таким образом видно, что быстродействие предлагаемого устройства существенно увеличилось по сравнению с известным для любых m, так при m = 10 и m = 20 быст" родействие увеличивается более чем в два и более чем в пять раз соответственно. В начальный момент íà D-триггеры записывается ненулевой код. На выходах сумматоров по модулю два 6 и 8 образуется очередной код псевдослучайного числа первой M последовательности в том случае, если х(К) в данный момент времени равняется О, а на выходе сумматоров по модулю два 7 и 9 образуется обратный код псевдослучайного числа, второй М последовательности, так как х(К)=1. В случае, когда х(К)=1; на выходе блоков 6 и 8 образуется обратный код, в котором проинвертированы значения разрядов псевдослучайного числа, а на выходе бло55 ков 7 и 9 соответственно прямой, так квк x K -=О. В зависимости от значения очередной двоичной цифры на выходе генератора 5x(K)E(0,1 по приТаким образом, природа выходных псевдослучайных последовательностей предлагаемого генератора максимально приближена к истинно случайным числам, он отличается высоким быстродействием и простотой технической реализации. Удельные аппаратурные затраты на один разряд псевдослучайного числа составляют незначительный объем элементов И, ИЛИ, m и триггеров. Дан" ный генератор псевдослучайных чисел позволяет получать числа по двум каналам, кроме того, его применение позволяет повысить точность и достоверность решения задачи методом Монте-Карло и получать истинно белый шум для построения генератора случайных процессов. 7 формула изобретения 907548 Генератор псевдослучайных чисел, содержащий первую и вторую группы трехвходовых сумматоров по модулю два, первую и вторую группы элементов И, группу элементов ИЛИ, группу триггеров и генератор равновероятной двоичной цифры, ко входу которого подключен выход генератора тактовых 10 импульсов, а единичный и нулевой выходы генератора равновероятной двоичной цифры подключены к первым входам элементов И первой и второй группы соответственно, ко второму входу j 1з (j - число сумматоров по модулю два в первой группе) старших элементов И первой. группы подключены выходы j старших трехвходоеых сумматоров по модулю два первой группы, ко второму щ входу m-j (m - число элементов И в каждой группе, а число элементов ИЛИ в группе - число триггеров е группе) старших элементов И второй груп-. пы подключены выходы m-j старших 25 трехеходовых сумматоров по модулю два второй группы, выходы i — ых (! =1,2,...) элементов И первой и второй группы подключены ко входам i-ro элемента ИЛИ, выход которого подклю- з0 чен к 0-входу i-го триггера, к синхровходу которого подключен выход генератора тактовых импульсов, к первым входам i-ых трехеходоеых сумматоров по модулю два первой и второй групп подключены единичные выходы (m-j+i) и (j+i)-ых триггеров соответственно, ко вторым входам j трехвходовых сумматоров по модулю два первой группы подключены выходы j младших триггеров, ко вторым входам m-j трехвходовых сумматоров по модулю два второй группы подключены выходы m-j младших триггеров, к третьим входам трехеходовых сумматоров по модулю два первой группы подключен нулевой выход генератора равновероятной двоичной цифры,к третьим входам m-j трехвходовых сумматоров по модулю два второй группы подключен нулевой и единичный выход генератора равновероятной двоичной цифры соответственно, о т л и ч а ю щ и и с я тем, что, с целью увеличения быстродействия генератора псевдослучайных чисел, он содержит группу четырехвходовых сумматоров по модулю деа, и групп сумматоров по модулю два, по j(i+3)-входоеых сумматоров по модулю два a i-ой группе и m n < х j(п+3)-входовых сумматоров по модулю два в и-ой группе, причем к первым, вторым и третьим входам(м-I) ûx четырехвходовых сумматоров по модулю два подключены выходы (2m-2j -i)-ых, (2m-j -i)-ых и (m-i)-ых триггеров (I=ITl J,m l) o T8eT T HHo, Bblxo ды j четырехвходовых сумматоров по модулю деа подключены ко второму входу j младших элементов И второй группы, к четвертым входам J четырехеходовых сумматоров по модулю два подключен единичный выход генератора равновероятной двоичной цифры, на первый, второй и третий входы с-го (i+3) входового сумматора по модулю два i-ой группы заведены выходы(а+!†!)-ых (j+1-i)-ых триггеров и нулевого выхода генератора раеновероятной двоичной цифры соответственно, а на (К+3)-ие входы 3 --го (i+3)-входного сумматора по модулю два заведены входы (m-j+ +1-К)-ro триггера, кроме того, вторые входы щ-j младших элементов И первой группы подключены к выходам m-j(i+3)-входовых сумматоров по модулю два. Источники информации, принятые во внимание при экспертизе 1. Яковлев В.В. и Фидоров P.Ô. Вероятностные вычислительные машины. Л., "Машиностроение", 1974, с. 344. 2. Авторское свидетельство СССР по заявке Й 2815712/18-24, кл. 6 Об F 1/02, 19.03.80 (прототип). 907548 (и) ti() fz(n и х(и) 0 2 1 0001 Ф f010 ) У » С0gyq q T 000 0777 0010+ 0100 0 100 ,OOl1 l 011 Q (110 1 1 6 0 7 1 о T 9 0 0 110 1I 01 1001 0Т00 О ОО Заказ 592/58 Тираж 732 Подписное ВНИИПИ Государственного комитета СССР по делам изобретений и открытий 113035, Москва, 8-35, Раушская наб., д. 4/5 Филиал ППП "Патент", г. Ужгород, ул. Проектная, 4 Составитель A. Карасов Редактор В. Лазаренко TexpeA A.Áàáèíåö Корректор С. Шекмар
