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

1

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

л

Известен генератор псевдослучайных чисел, содержащий два регистра сдвига и группу сумматоров по модулю два 1.

Недостатком этого генератора является сложность структурного построения. Кроме того, при построении - Генератора необходимо выбирать структуры исходных генераторов такими, чтобы их периоды являлись взаимно

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

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

10 вторую группы элементов И, группу элементов ИЛИ, группу триггеров и генератор равновероятной двоичной цифры 2.

15

Известный генератор предназначен для генерирования за один такт двух m разрядных псевдослучайных чисел, причем вероятность появления нуля или единицы в разрядах псевдослучайных

20 чисел по первому и второму каналам равняется 0,5.

Недостаток известного устройства низкое быстродействие.

Цель изобретения - увеличение быстродействия генератора псевдослучайных чисел.

Поставленная цель достигается тем что а генератор псевдослучайных чисел, содержащий первую и вторую группы трехвходовых сумматоров по модулю два, первую и вторую группы элементов И, группу элементов ИЛИ, группу триггеров и генератор равновероятной двоичной цифры, ко входу которого подключен выход генератора тактовых импульсов, а единичный и нулевой выходы генератора равновероятной двоичной цифры подключены к первым входам элементов И первой и второй группы соответственно, ко второму входу j (j - число сумматоров по модулю два в первой группе) старших элементов И первой группы подключены выходы j старших трехвходовых сумматоров по модулю два первой группы, ко второму входу m-j (m - число элементов И в,каждой группе, а число элементов ИЛИ в группе - число триггеров в группе) старших элементов И второй группы подключены выходы m-j старших трехвходовых сумматоров по модулю два второй группы, выходы i-ых (,2,...) элементов И первой и второй группы подключены ко входам i-ro элемента ИЛИ, выход которого подключен к D входу i-ro три1- гера,к синхровходу которого подключен выход генератора тактовых импульсов , к первым входам i-ых трехвходовых сумматоров по модулю два первой и второй групп подключены единичные выходы (ffl-j + i) и (j + i)-btx триггеров соответственно, ко вторым входам j трехвходовых сумматоров по модулю два первой группы подключены выходы младших триггеров, ко вторым входам m-J трехвходовых сумматоров по модул два второй группы подключены выходы m-j младших триггеров, к третьим входам j трехвходовых сумматоров по модулю два первой группы подключен нулевой выход.генератора равновероятной двоичной цифры, к третьим входам m-j трехвходовых сумматоров по модулю два второй группы подключен нулевой и единичный выход генер атора равновероятной двоичной цифры, соответственно введены группа четырехвходовых сумматоров по модулю два, п групп сумматоров по модулю два, по j (i-v3)-входовых сумматоров по модулю

два в i-ей группе и m-n-j {п+3)-входовых сумматоров по модулю два в п-ой группе, причем к первым, вторым и третьим входам (т-О-ых четырехвходовых сумматоров по модулю два подключены выходы (2m-2j-i)-ых, (2m-j-)-ых и (т-)-ых триггеров (, m-1) соответственно, а выходы j четырехвходовым сумматором по модулю

два подключены ко второму входу j младших элементов И второй группы, к четвертым входам j четырехвходовых сумматоров по модулю два подключен единичный выход генератора равновероятной двоичной цифры, на первый, второй и третий входы (i+З) входового сумматора по модулю два i-ой группы заведены выходы (т+1-)-ых (j+1-)bix триггеров и нулевого выхода генератора равновероятной двоичной цифры соответственно, а на (К+3)-ие входы Б-го (+3)-входового .сумматора по модулю два заведены входы (m-j+1-K)-ro триггера, кроме того,

вторые входы m-j младших элементов И первой группы подключены к выходам m-j (i+З) входовых сумматоров по модулю два.

На фиг. 1 приведена функциональная схема генератора псевдослучайных чисел при m и j 1; на фиг. 2 - временная диаграмма его работы.

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

состоит из m триггеров 1, m элементов ИЛИ 2, первой группы из m элементов ИЗ, второй группы из m элементов И Ц, генератора 5 равновероятной двоичной цифры, nsJm/j-l по j

+ 3 входовых сумматоров по модулю два в (-ОЙ группе и т-п j п+3 входовых сумматоров по модулю два в п-ой группе 6, j четырехвходовых сумматоров по модулю два 7 первой группы из j трехвходовых сумматоров по модулю два 8, второй группы из m-j трехвходовых сумматоров по модулю два 9.

Количество трехвходовых сумматоров по модулю два в первой группе равняется j, а во второй группе m-j. В то же время количество (i+З) входовых сумматоров по модулю два 6 равняется m-j, а количество четырехвходовых - j. На выходах («3) входовых сумматоров по модулю два блока 6 и трехвходовых сумматоров по модулю два 8 получается значение |псевдослучайного числа ,а. .. а, а на выходах четырехвходовых сумматоров по модулю два 7 и трехвходовых второй группы 3 значение псевдослучайного числа .а,,, ... а .Числа 1 и 2 представляют собой т-разрядные коды или их инверсии М последовательностей, порождаемых следующими полиномами 4(Z) и f (Z) , причем периоды обоих последовательностей одинаковы Последовательность следования кодов отлична и случайна как в первой, так и во второй М последовательност Появление прямого кода М последовательности или его инверсии по пер вому и второму каналу определяется значением очередного отсчета на выходе генератора равновероятной двоичной цифры. Выходы D-триггеров и г нератора равновероятной двоичной цифры соединены со входами трехвходовых сумматоров по модулю два первой и второй группы. Выходы О-триггеров соединены со входами m-j многовходовых сумматоров по модулю два 6. В зависимости от значения равновероятной двоичной цифры на выходе генератора 5 равновероятной двоичной цифры код псевдослучайного числа 1 или 2 с выходов сумматоров по модулю два через элементы ИЛИ 2 записывается на D-триггеры. Генератор представляет собой простой датчик равновероятной двоичной цифры. Функционирование генератора псев дослучайных чисел происходит следую щим образом. В начальный момент на D-триггеры записывается ненулевой код. На выходах сумматоров по модулю два 6 и образуется очередной код псевдослучайного числа первой М последовател ности в том случае, если х(К) в дан ный момент времени равняется О, а н выходе сумматоров по модулю два 7 и образуется обратный код псевдослуча ного числа, М последовательности, так как х(К)1. В случае, ко да х{К)1, на выходе блоков 6 и 8 о разуется обратный код, в котором пр инвертированы значения разрядов псе дослучайного числа, а на выходе бло ков 7 и 9 соответственно прямой, та как X(К)0. В зависимости от значения очередной двоичной цифры на выходе генератора 5x(K),1j по при98 ходу тактового импульса на синхронизирующие входы триггеров 1 на их D-входы через первую или вторую группы элементов И 3, + и через элементы ИЛИ 2, определяющие выходы обоих групп элементов И, подается очередной код первой или второй М последовательности. С приходом очередного тактового импульса процесс повторяется. Временная диаграмма работы предлагаемого генератора псевдослучайных чисел полностью соответствует временной диаграмме работы известного генератора, т.е. они генерируют абсолютно идентичные последовательности. В то же время предлагаемое устройство отличается значительно большим быстродействием. Частота следования тактовых импульсов будет определяться временем прохождения электрического сигнала по самому длинному пути, т.е. величиной Т t3, причем величина Т не зависит от значения т. При любом m величина Т неизменна. Для случая m 10 и j 3 величина задержки для известного устройства определяется выражением Т lit , что в Ф 2 j-раза больше чем в предлагаемом устройстве, а для ш 20 Т 17t.jf ttg 21t-7, т.е. Хф Рзз больше, чем в предлагаемом устройстве. Таким образом видно, что быстродействие предлагаемого устройства существенно увеличилось по сравнению с известным для любых т, так при m 10 и m 20 быстродействие увеличивается более чем в два и более чем в пять раз соответственно. Таким образом, природа выходных псевдослучайных последовательностей предлагаемого генератора максимально приближена к истинно случайным числам, он отличается высоким быстродействием и простотой технической реализации. Удельные аппаратурные затраты на один разряд псевдослучайного числа составляют незначительный объем элементов И, ИЛИ, т. и триггеров. Данный генератор псевдослучайных чисел позволяет получать числа по двум каналам, кроме того, его применение позволяет повысить точность и достоверность решения задачи методом Монте-Карло и получать истинно белый шум для построения генератора случайных процессов.

Формула изобретения

Генератор псевдослучайных чисел, содержащий первую и вторую группы трехвходовых сумматоров по модулю два, первую и вторую группы элементов И, группу элементов ИЛИ, группу триггеров и генератор равновероятной двоичной цифры, ко входу которого подключен выход генератора тактовых импульсов, а единичный и нулевой выходы генератора равновероятной двоичной цифры подключены к первым входам элементов И первой и второй группы соответственно, ко второму входу j (j - число сумматоров по модулю два в первой группе) старших элементов И первой.группы подключены выходы j старших трехвходовых сумматоров по модулю два первой группы, ко второму входу m-j (m - число элементов И в каждой группе, а число элементов ИЛИ в группе - число триггеров в группе) старших элементов И второй группы подключены выходы m-j старших трехвходовых сумматоров по модулю два второй группы, выходы i-ых { 1,2,...) элементов И первой и второй группы подключены ко входам i-ro элемента ИЛИ, выход которого подключен к О-входу i-ro триггера, к синхровходу которого подключен выход генератора тактовых импульсов, к пер вым входам i-ых трехвходовых суммато ров по модулю два первой и второй групп подключены единичные выходы (m-j+i) и (j+i)-ыx триггеров соответственно, ко вторым входам j трехвходовых сумматоров по модулю два первой группы подключены выходы j младших триггеров, ко вторым входам ni-j трехвходовых сумматоров по модулю два второй группы подключены выходы m-j младших триггеров, к третьим входам j трехвходовых сумматоров по модулю два первой группы подключен нулевой выход генератора равновероятной двоичной цифры,к третьим

входам m-j трехвходовых сумматоров по модулю два второй группы подключен нулевой и единичный выход генератора равновероятной двоичной цифры соответственно, отличающийс я тем, что, с целью увеличения быстродействия генератора псевдослучайных чисел, он содержит группу четырехаходовых сумматоров по модулю два, п групп сумматоров по модулю два, по j(i+3)входовых сумматоров по модулю два в i-ой группе и m-nx j (п4-3)-входовых сумматоров по модулю два в п-ой группе, причем к первым, вторым и третьим входам(т-i)-ых четырехвходовых сумматоров по модулю два подключены выходы (2т-2j-i)-ых, (2m-j-i)-ых и (т-)-ых триггеров (,m-t) соответственно, а выходы j четырехвходовых сумматоров по модулю два подключены ко второму входу j младших элементов И второй групк четвертым входам j четырехвхопыдовых сумматоров по модулю два подключен единичный выход генератора равновероятной двоичной цифры, на первый, второй и третий входы f-го (i+3) входового сумматора по модулю два i-ой группы заведены выходы(т+1-i)-ых (j + l-i)-bix триггеров и нулевого выхода генератора равновероятной двоичной цифры соответственно, а на (К+3)-ие входы Р-го (i+3)-входного сумматора по модулю два заведены входы (m-j+ +1-К)-го триггера, кроме того, вторые входы rp-j младших элементов И первой группы подключены к выходам m-j(i+3)-вxoдoвыx сумматоров по модулю два. Источники информации, принятые во внимание при экспертизе 1.Яковлев В.В. и Фидоров Р.Ф. Вероятностные вычислительные машины. Л., Машиностроение, 197, с. .Авторское свидетельство СССР по заявке № 2815712/18-2, кл. G Об F 1/02, 19.03.80 (прототип).