Генератор псевдослучайных чисел Советский патент 1980 года по МПК G07C15/00 G06F1/02 

1

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

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

Недостатком этого генератора явлется наличие периода в формируемой последовательности.

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

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

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

последовательност) кодов псевдослучайных чисел на выходах генератора. Для достижения поставленной цели генератор содержит первую и вторую группы элементов И, группу элементов ИЛИ, вторую группу сумглаторов по модулю два и генератор равновероятной двоичной цифры, ко входу

Q которого подк.г1ючен выход генератора тактовых импульсов, а единичный и нулевой выходы генератора равновероятной двоичной цифры подключены к , первым входам первой и второй группы элементов И соответственно, ко второму входу i-ro элемента И первой группы подключен выход i-ro сумматора по модулю два первой группы, ко второму входу i-ro элемента И второй группы подключен выход i-ro сумматора по моду.шо два второй группы, выходы i-ых элементов И первой и второй групп подключены ко входам i-ro элемента ИЛИ, выход которого

5 подключен ко входу i-ro триггера, к

первым входам i-ых сумматоров по

модулю два первой и второй групп

подключены единичные выходы i-ых

, триггеров, ко вторым входам j

Q. старших cy J iaтopoв по модулю два первоП группы подключены выходы j млад ших триггеров, к вторым входам т-j мпа. дшх сумматоров по модулю два пе вой группы подключены выходы т-j старших сумматоров по модулю два пе вой группы, ко вторым входам т-j старших сумг аторов по модулю два второй группы подключены выходы га-j /lлaдшиx триггеров, к вторым входам j младших сумматоров по модулю два второй группы подключены выходы j старших сумматоров по модулю два второй группы. На фиг.1 приведена структурная схема генератора для случая, когда лп 5 на фиг, 2 - функциональная схема генератора рандомизированных псевдослучайных чисел для m 3; на фиг,3 временная диаграмма его работы В общем случае генератор рандомизированных псевдослучайных чисел состоит из m триггеров 1, га элементов ИЛИ 2, первой группы двухвходовых сумматоров по модулю два 3, первой группы элементов И 4 второй группы двухвходовых сумматоров по модулю два 5, второй груп пы элементов И 6 и генератора равн вероятной двоичной цифры 7 (см.фиг для m 5). Количество сумматоров по модулю два и элементов И в груп пе равняется m {фиг.1). Выходы Dтриггеров соединены со входами сум маторов по модулю два согласно сле дующей системы уравне1Шй : «m-i- m-i® ni-j-i. . - О rti-i w-i® m+j-i. --Т, где bf.|- - единичный выход (m-i)триггера, а n.,..j--i - выход ( го сумматора по модулю два, @ - означает операцию суммирования по модулю два. Причем для организации связей первой группы сумматоров по модулю два испальзуется система уравнений (1) при значении номера разряда регистра сдвига, выход которого соединен со входом сумматора по модулю два в обычных струк турах (I), равной j, а для второй группы сумматоров по модулю два при m-j. Так для случая m 5 на входы сумматоров по модулю два-пер вой группы 3 (фиг.1) заведены связ в-соответствии с системой: ,c,,,c,--Ъ,, а на .входы сумматоров по модулю два второй группы 5 в соответствии со следующей системой Ь4®.э--Ьз®°5- 2-Ь2®а;,с( На выходах первой и второй группы cyiviMaTOpoB по модулю два последовательно будут генерироваться т-разрядные коды псевдослучайных чисел М-последовательностей,порождаемых следующими полиномами Ч (х) х+ х+ 1 и f (х) х5+ х2+ 1, причем периоды обоих последовательностей одинаковы. Последовательность следования же кодов отлична и случайна как в первой, так и во второй М-последовательностях. Таким образом, на выходах сумматоров по модулю два обеих групп генерируются две разные М-последовательности одинаковой длины. D-триггеры и сумматоры по модулю два (кроме связей второй группы сумматоров) представляют генератор псевдослучайных чисел, ко- торые повторяют логику его работы. В зависимости от значения равновероятной двоичной цифры на выходе генератора 7 единичный выход которого подключен к первой группе элементов И 4, а нулевой - ко второй группе 6 (фиг.1). Код псевдослучайного числа с первой или второй группы сумматоров по модулю два через элементы ИЛИ- 2 записывается на Dтриггеры. Генератор 7 представляет собой простейший датчик равновероятной двоичной цифры, построенный на физических принципах. Фукционирование генератора псевдослучайных чисел происходит следующим образом. В начальный момент на D-триггеры 1 записывается ненулевой код (фиг,1). На выходах сумматоров по модулю два первой группы 3 образуется оче-, редной код псевдослучайного числа первой М-последовательности, а на выходе второй группы 5 - второй Мпоследовательности. В зависимости от значения очередной двоичной цифры на выходе генератора 7 по приходу тактового импудьса на синхронизирующие входы триггеров 1 на их D входы через ту или иную группы элементов И и через элементы ИЛИ 2, объединяющие выходы обоих групп И, подается очередной код первой или второй М-последовательности. С приходом очередного синхронизирующего импульса процесс-Повторяется. - Более подробно процесс генерирования псевдослучайных чисел поясним на конкретном примере. На фиг.2 приведена функциональная схема генератора псевдослучайных чисел для m 3, а на фиг.З - временная диаграмма его работы. На фиг. За показана временная диаграмма синхронизирующих импульсов, по приходу которых триггеры устройства меняют свое состояние; на фиг. Зб-временная диаграмма на единичном выходе генератора 7; на фиг. 3 в и 3 г приведены две последовательности, порождаемые полиномами Ч (х) х + 1 и /(х) 1, для j 1 и j 2. Стрелки с цифрами в кружках над ними означают последовательность переходов состояний триггеров устройства. В первоначальный момент на триггерах записан код 101, тогда 1 100, а 2 011. Так как в мо мент времени t на единичном выходе генератора 7 находится единица, то приходу синхроимпульса через верхнюю группу элементов И и элементы ИЛИ на триггерах запишется код числа 100, После прохождения переходных процессов на выходах сумматоров установляются новые значения fcl 011 и 2 110. В следующий момент времени на триггерах запишется код 2 110, т.к. на единичном выходе генератора 7 находится нуль. . Подобным образом триггеры меняют свое состояние в зависимости от зна чения генератора 7 и по приходу пос ледующих импульсов. На фиг. Зв и Зг стрелками показана граф-схема переходов состояний триггеров для t,, tg 3 -fo Из вышеприведенного описания функционирования генератора псевдослучайных чисел следуют следующие факты. Значения 1 и 2 , генерируемые на выходах первой и второй группы сумматоров по модулю два в каждый конкретный та.кт являются значениями кодов из двух отличных М-по ледовательностей. Последующее значение 1 или 2 в худшем случае является следующим кодом М-последовательности, получаемой при одном сдвиге в последовательном генераторе псевдослучайных чисел. Так, 1 принимает последовательные значения, которые получались бы в последовател ном генераторе 100 через 3 такта пос ле 101, 011 через 3 такта после 100 101 через 1 такт после Oil, 111 через 4 такта после 101 (фиг.2,3) Отсюда очевидно, что 1 и 2 принимают значения из двух различных Мпоследовательностей (но. имеющих одинаковый состав кодов), порядок следования которых случаен. Нетрудно за метить, что при фиксировании на выходе генератора 7 нуля или единицы генератор псевдослучайных чисел будет функционировать как обычный ге нератор псевдослучайных чисел. А так как состояние его случайно, то и порядок следования кодов М-последо вательности будет абсолютно случаен В силу этого такой недостаток как периодичность,в данном устройстве устраняется, что,в свою очередь, означает, что автокорреляционные функции выходных последоватезльностей имеют ненулевое значение только при t С, где t - длительность выходного сигнала между очередными синхроимпульсами. Такой вид автокорреляционной функции полностью удовлетворяет требованиям, поедъявляемым к случайным числам. Преимущества генера ора заключаются в следующем. Природа выхолных псевдослучайных последовательностей максимально приближена к истинно случайным числам. В данном устройстве нарушено жесткое условие, имеющее место во всех генераторах псевдослучайных чисел и приводящее к такому недостатку, что после определенного должно следовать заранее точно известное. В данном генераторе псевдослучайных чисел такое условие не соблюдается, так может принять равновероятно одно из двух значений. Заметим, что в физических генераторах случайных чисел e,i может принимать любое значение из всего набора возможных кодов. Предлагаемый генератор отличается простотой технической реализации, Удсгльные аппаратурные затраты на один разряд псевдослучайного числа составят один двухвходовой суктматор по модулю два, одну схему И, - схемы ИЛИ, -|-О-триггера и - генератора 7. Данный генератор псевдослучайных чисел позволяет получать числа по двум каналам. Генератор 7, примененный в устройстве, может быть построен по самой простейшей схеме (например триггер с ко1«1мутируемым питанием) , так как требования к равновероятности выходной двоичной цифры являются очень низкими. Даже при отказе этого генератора, т.е. когда на его выходе будет зафиксировано значение нуля или единицы, устройство в целом будет функционировать, но в этом случае период будет равен 2 - 1, а не бесконечности. Этот факт говорит о надежности функционирования предлагаемого устройства и- стабильности его вероятностных характеристик. Применение подобного генератора псевдослучайных чисел позволит повысить качество псевдослучайных последовательностей,, а тем самым точность и достоверность решения задач методом Монте-Карло, Кроме тoгo подобные устройства позволят получать истинно Белый шу:- для построения генераторов случайных процессов. Формула изобретения Генератор псевдослучайных чисел, содержащий группу сумматоров по модулю два и группу триггеров, входы синхронизации которых подключены к выходу генерааора тактовых импульсов, о т л к чающийс я тем, что г с целью pacuJиpeния функциональных зоз.мо;:гностей генератора за счет устране::Шя повторения последовательности кодоз псевдослучайных чисел на выходах генератора, он содержит первую и вторую группу элементов И, группу элементов ИЛИ, вторую группу сумматоров по модулю два и генератор равновероятной двоичной цифры, ко входу которого подключены выход генератора тактовых импульсов, а единичный и нулево выходы генератора равновероятной двоичной цифры подключены к первым входам первой и второй групп элементов И соответственно, ко второму входу i-ro элемента и первой группы подключен выход i-ro сумматора по модулю два первой группы, ко второму входу i-ro элемента И второй группы подключен выход i-ro сумматора по модулю два второй группы, выходы i-ых элементов И первой и второй групп подключены ко входам i-ro элемента ИЛИ, выход которого подключен ко входу триггера, к первым входам i-ых сумматоров по модулю два первой и второй групп

подключены единичные выходи i-ых триггеров, ко вторым входам j старших сумматоров по модулю два первой группы подключены выходы j младших триггеров, к вторым входам т-j младших сумматоров по модулю два первой группы подключены выходы т-j старших сумматоров по модулю дв первой группы, ко вторым входам т-j старших сумматоров по модулю два второй группы подключены выходы т-j младших триггеров, ко вторым входам j младших сумматоров по модулю два второй группы подключены выходы j старших сумматоров по модулю два второй группы.

Источники информации, принятые во внимание при экспертизе

1.Яковлев В.В., Федоров Р.Ф, Вероятностные вычислительные машины, Л., Машиностроение, 1974, с.344.

2.Авторское свидетельство СССР по заявке № 2415584/24 от 20 апреля 1977 г. (прототип).

f) П П П Г| П П i

о f 2 J 7 S 9

h

Фиг.З