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

Союз СоветскннСоцмалмстмческмкРеспублик ОП ИСАНИЕИЗОБРЕТЕН ИЯК АВТОРСКОМУ СВИДЕТЕЛЬСТВУ и 907548(53)М. Кл. С 06 Р 7/58 Государственный квинтет Опубликовано 23.02,82. Бюллетень М 7Дата опубликования описания 25, 02. 82 по делам нзабретеннй н открытнй(7 ) Заявитель Минский радиотехнический институт(54) ГЕНЕРАТОР ПСЕВДОСЛУЧАЙНЫХ ЧИСЕЛ Изобретение относится к вычислительной технике и может быть использовано в качестве устройства для получения случайных чисел при решении задач методом Монте-Карло, а также для построения генераторов случайных процессов с заданными характеристиками, кроме того, применение подобных устройств может быть использовано для генерирования случайных процессов с равномерным спектром, используемых для идентификации систем автоматического управления. Известен генератор псевдослучайных чисел, содержащий два регистра сдвига и группу сумматоров по модулю два 1.Недостатком этого генератора является сложность структурного построения, Кроме того, при построении генератора необходимо выбирать структуры исходных генераторов такими, чтобы их периоды являлись взаимно простыми числами, что не всегда оказывается возможным. Наиболее близким по техническойсущности к изобретению является генератор псевдослучайных чисел, содержащий первую и вторую группы двухвходовых сумматоров по модулю два,первую и вторую группы трехвходовых осумматоров по модулю два, первую ивторую группы элементов И, группуэлементов ИЛИ, группу триггеров и генератор равновероятной двоичнойциФры21. 15Известный генератор предназначендля генерирования за один такт двух в разрядных псевдослучайных чисел, причем вероятность появления нуля или единицы в разрядах псевдослучайных чисел по первому и второму каналамравняется 0,5.Недостаток известного устройстваниэкое быстродействие.90754 Цель изобретения - увеличение быстродействия генератора псевдослучайных чисел. Поставленная цель достигается тем, цто в генератор псевдослучайных чисел, содержащий первую и вторую группы трехвходовых сумматоров по модулю два, первую и вторую группы элементов И, группу элементов ИЛИ, группу10 триггеров и генератор равновероятной двоичной цифры, ко входу которого подключен выход генератора тактовых импульсов, а единичный и нулевой выходы генератора равновероятной15 двоичной цифры подключены к первым входам элементов И первой и второй группы соответственно, ко второму входу ) ( - число сумматоров по модулю два в первой группе) старших элементов И первои группы подключ20 чены выходы ) старших трехвходовых сумматоров по модулю два первой группы; ко второму входу щ(щ - число элементов И в,каждой группе, а число элементов ИЛИ в группе " число триггеров в группе) старших элементов И второй группы подключены выходы щ старших трехвходовых сумматоров по модулю два второй группы, выходы 1-ых (1=1,2,) элементов И первой и второй группы подключены ко входам 1-го элемента ИЛИ, выход которого подключен к 0 входу 1-го триггера,к синхровходу которого подключен выход генератора тактовых импуль- З 5 сов, к первым входам 1-ых трехвходовых сумматоров по модулю два первой и второй групп подключены единичные выходы (щ-+1) и +1)-ых триггеров40 соответственно, ко вторым входам ) трехвходовых сумматоров по модулю два первой группы подключены выходы младших триггеров, ко вторым входам щ-) трехвходовых сумматоров по модулю два второй группы подключены выхо 45 ды щ-) младших триггеров, к третьим входам ) трехвходовых сумматоров по модулю два первой группы подключен нулевой выход генератора равновероя;- ной двоичной цифры, к третьим входам щ-) трехвходовых сумматоров по модулю два второй группы подключен нулевой и единичный выход генератора равновероятной двоичной цифры, соответственно введены группа четырехвходовых сумматоров по модулю два, и групп сумматоров по модулю два, по (1+3)-входовых сумматоров по модулю 8два в -ой группе и щ-п 1 (и+3)-входовых сумматоров по модулю два ви-ой группе, причем к первым, вторыми третьим входам (щ)-ых четырехвходовых сумматоров по модулю два подключены вь 1 ходы (2 щ-)-ых, (2 щ-1)-ых и (щ)-ых триггеров (1=щ-,щ) соответственно, а выходы 1 четырехвходовым сумматором по модулюдва подключены ко второму входу 1младших элементов И второй группы,к четвертым входамчетырехвходовыхсумматоров по модулю два подключенединичный выход генератора равновероятной двоичной цифры, на первый, второй и третий входы Я-го (1+3) входового сумматора по модулю два 1-ойгруппы заведены выходы (щ+1-1)-ых+1- )-ых триггеров и нулевого выхода генератора равновероятной двоичной цифры соответственно, а на. сумматора по модулю два заведены входы (щ-)+1-К)-го триггера, кроме того,вторые входы щ-) младших элементов Ипервой группы подключены к выходамщ-) (1+3) входовых сумматоров по модулю два.На фиг, 1 приведена Функциональная схема генератора псевдослучайных чисел при щ = 4 и 1 = 1; кафиг. 2 - временная диаграмма его работы,Генератор псевдослучайных чиселсостоит из щ триггеров 1, щ элементов ИЛИ 2, первой группы из щ элементов И 3, второй группы из щ элементов И 4, генератора 5 равновероятной двоичной цифры, и " щ/-1 по 1+ 3 входовых сумматоров по модулюдва в -ой группе и щ-и ) и+3 входовых сумматоров по модулю два ви-ой группе 6, ) четырехвходовых сумматоров по модулю два 7, первой группы из ) трехвходовых сумматоров помодулю два 8, второй группы из щ-)трехвходовых сумматоров по модулюдва 9. Количество трехвходовых сумматоров по модулю два в первой группе равняется ), а во второй группещ-). В то же время количество (1+3) входовых сумматоров по модулю два 6 равняется щ-), а количество цетырехвходовых - 1. На выходах (13) входовых сумматоров по модулю два блока 6 и трехвходовых сумматоров по модулю два 8 получается значение907548 5 1 о и.15 е- го г 5 зо 35 40 5псевдослучайного числа 1=а,а а, а на выходах четырехвходовых сумматоров по модулю два 7 и трехвходовых второй группы 9 значение псевдослучайного числа2=а,а , а . Числа1 и 2 представляют собой в-разрядные коды или их инверсии М последовательностей, порождаемых следующими полиномами (Е)=Л -2+1 и 9 (2)=2 +2+1, причем периоды обоих последовательностей одинаковы. Последовательность следования кодов отлична и случайна как в первой, так и во второй М последовательност Появление прямого кода М последовательности или его инверсии по первому и второму каналу определяется значением очередного отсчета на выходе генератора равновероятной двоичной цифры. Выходы О-триггеров и г нератора равновероятной двоичной цифры соединены со входами трехвходовых сумматоров по модулю два первой и второй группы.Выходы О-триггеров соединены со входами щ-) многовходовых сумматоров по модулю два 6.В зависимости от значения равно- вероятной двоичной цифры на выходе генератора 5 равновероятной двоич. - ной цифры код псевдослучайного числа 1 или 2 с выходов сумматоров по модулю два через элементы ИЛИ 2 записывается на О-триггеры, Генератор представляет собой простой датчик равновероятной двоичной цифры,Функционирование генератора псевдослучайных чисел происходит следующим образом. ходу тактового импульса на синхронизирующие входы триггеров 1 на их О-входы через первую или вторую группы элементов И 3, 4 и через элементы ИЛИ 2, определяющие выходы обоих групп элементов И, подается очередной код первой или второй М последовательности. С приходом очередного тактового импульса процесс повторяется.Временная диаграмма работы предлагаемого генератора псевдослучайных чисел полностью соответствует временной диаграмме работы известного генератора, т.е, они генерируют абсолютно идентичные последовательности,В то же время предлагаемое устройство отличается значительно большим быстродействием. Частота следования тактовых импульсов будет определяться временем прохождения электрического сигнала по самому длинному пути, т,е. величиной Т = 41, причем величина Т не зависит от значения в. При любом п 1 величина Т неизменна, Для случая щ =10 и 1 = 3 величина задержки для известного устройства определяется выражением Т = 11 й, что в - = 2 - ра 4. 4 за больше чем в предлагаемом устрой.стве, а для я = 20 Т = 17 1 4 =21= 217, т.е, + = ( + раз больше, чем в предлагаемом устройстве. Таким образом видно, что быстродействие предлагаемого устройства существенно увеличилось по сравнению с известным для любых в, так при в = 10 и в = 20 быст" родействие увеличивается более чем в два и более чем в пять раз соответственно.В начальный момент на О-триггеры записывается ненулевой код, На выходах сумматоров по модулю два 6 и 8 образуется очередной код псевдослучайного числа первой М последовательности в том случае, если х(К) в данный момент времени равняется О, а на выходе сумматоров по модулю два 7 и 9 образуется обратный код псевдослучайного числа, второй М последовательности, так как х(К)=1. В случае, когда х(К)=1; на выходе блоков 6 и 8 образуется обратный код, в котором проинвертированы значения разрядов псевдослучайного числа, а на выходе бло 55 ков 7 и 9 соответственно прямой, так как х(К)=0. В зависимости от значения очередной двоичной цифры на выходе генератора 5 х(К)60,1 по приТаким образом, природа выходных псевдослучайных последовательностей предлагаемого генератора максимально приближена к истинно случайным числам, он отличается высоким быстродействием и простотой технической реализации.Удельные аппаратурные затраты на один разряд псевдослучайного числа составляют незначительный объем элементов И, ИЛИ, гп и триггеров. Дан" ный генератор псевдослучайных чисел позволяет получать числа по двум каналам, кроме того, его применение позволяет повысить точность и достоверность решения задачи методом Монте-Карло и получать истинно белый шум для построения генератора случайных процессов.907548 40 Генератор псевдослучайных чисел, содержащий первую и вторую группы трехвходовых сумматоров по модулю два, первую и вторую группы элементов И, группу элементов ИЛИ группу триггеров и генератор равновероятной двоичной цифры, ко входу которого подключен выход генератора тактовых 10 импульсов, а единичный и нулевой выходы генератора равновероятной двоичной цифры подключены к первым входам элементов И первой и второй группы соответственно, ко второму входу ) 1 Б ( - число сумматоров по модулю два в первой группе) старших элементов И первой. группы подключены выходыстарших трехвходоеых сумматоров по модулю два первой группы, ко второму 20 входу щ- (щ - число элементов И в каждой группе, а число элементов ИЛИ в группе - число триггеров в группе) старших элементов И второй груп-. пы подключены выходы щ- старших 25 трехеходовых сумматоров по модулю два второй группы, выходы 1-ых ( =1,2,) элементов И первой и второй группы подключены ко входам 1-го элемента ИЛИ, выход которого подклю- зО чен к 0-входу 1-го триггера, к синхровходу которого подключен выход генератора тактовых импульсов, к первым входам 1-ых трехеходоеых сумматоров по модулю два первой и второй групп подключены единичные выходы (щ+) и (1+)-ых триггеров соответственно, ко вторым входамтрехвходовых сумматоров по модулю два первой группы подключены выходымладших триггеров, ко вторым входам щтрехвходовых сумматоров по модулю два второй группы подклюцены выходы щ- младших триггеров, к третьим входамтрехеходовых сумматоров по модулю два первой группы подключен нулевой выход генератора равнояероятной двоичной цифры,к третьим входам щтрехвходовых сумматоровпо модулю два второй группы подключен нулевой и единичный выход генератора равновероятной двоичной цифрысоответственно, о т л и ч а ю щ и йс я тем, что, с целью увеличениябыстродействия генератора псевдослучайных чисел, он содержит группучетырехвходовых сумматоров по модулюдеа, п групп сумматоров по модулюдва, по 1(+3)-входоеых сумматоровпо модулю два в 1-ой группе и щ-и хх (и+3)-входовых сумматоров по модулю два в и-ой группе, причем к первым, вторым и третьим входам(щ-)-ыхчетырехаходовых сумматоров по модулюдва подключены выходы (2 щ в )-ых,(1=щ,щ) соответственно, а выходычетырехвходовых сумматоров помодулю деа подключены ко второму входумладших элементов И второй группы, к четвертым входамцетырехеходовых сумматоров по модулю два подключен единичный выход генератораравновероятной двоичной цифры, на первый, второй и третий входы с-го (+3)входового сумматора по модулю два1-ой группы заведены выходы(щ+1 в )-ых(+1-)-ых триггеров и нулевого выхода генератора раеновероятной двоичнойцифры соответственно, а на (К+3)-иевходы 1 -го (+3)-входного сумматорапо модулю два заведены входы (щ++1-К)-го триггера, кроме того, вторые вхоДы щмладших элементов Ипервой группы подключены к выходамщ(+3)-входовых сумматоров по модулю два. Источники информации,принятые во внимание при экспертизе 1, Яковлев В.В. и фидоров Р,ф. Вероятностные вычислительные машины. Л "Машиностроение", 1974, с, 344. 2. Авторское свидетельство СССР по заявке М 2815712/18-24,кл. 6 Об Р 1/02, 19 03,80 (прототип).