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

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

Иллюстрации

Показать все

Реферат

 

ОПИСА

ИЗОБРЕТЕННАЯ

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

Социалистических

Республик (63) Дополнительное к авт. свнд-ву (22) Заявлено 11.07.77 (21) 2505976/18-24 с присоединением заявки М (23) Приоритет

Опубликовано 0501.80. Бюллетень Nо 1

Дата опубликовании описания 0501.80 ($f) . Кл.2

G 07 С 15/00

G 06 F 1/02

Государственный комитет

СССР по делам изобретений и открытий (5Ç) УДК 6 81 . 3 2 5 (088.8) (72) Авторы изобретения

В.Н. Ярмолик и A.Í. Морозевич

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

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

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

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

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

Цель изобретени я — расширение функциональных возможностей генератора за счет устранения повторения последовательности кодов псевдо -лучайных чисел на выходах генератора, Для достижении я пост Bнл&н ной цели генератор содержит первую и вторую группы элементов И, группу элементов ИЛИ, вторую группу сумматоров по модулю два и генератор равновероятной двои--ной цифры, ко входу которого подключен выход генератора тактовых импульсов, а единичный и .Улевой выходы генератора ранновероятной двоичной цифры подключены к первым входам первой и второй группы элементов И соответственно, ко второму входу i-ro элемента И первой группы подключен выход i-ro сумматора по модулю два первой группы, ко второму входу i-го элемента И

2О второй rpynvv подключен сумматора по модулю два второй группы, ныходы i-ых элементов И первой и нторой групп подключены ко входам

i-ro элемента ИЛИ, выход которого

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

10 вой группы подключены выходы 3 младших триггеров, к вторым входам щ-j мпа,„ших сумматоров по модулю два первой группы подключены выходы m-j старших сумматоров по модулю два первой группы, ко вторым входам тп-3 5 старших сумматоров по модулю два второй группы подключены выходы m-j младших триггеров, к вторым входам младших сумматоров по модулю два второй группы подключены выходы j старших сумматоров по модулю два второй группы.

На фиг.l приведена структурная схема генератора для случая, когда

m = 5; на фиг.2 — функциональная схема генератора рандомизированных. псевдослучайных чисел для m = 3; на фиг.3 — временная диаграмма его работы. В общем случае генератор рандомизированных псевдослучайных чисел состоит из m триггеров 1, 20

m элементов ИЛИ 2, первой группы двухвходовых сумматоров по модулю два 3, первой группы элементов И 4, второй группы двухвходовых сумматоров по модулю два 5, второй груп- 25 пы элементов И 6 и генератора равно.вероятной двоичной цифры 7 (см.фиг.l, для m = 5) . Количество сумматоров по модулю два и элементов И в группе равняется m (фиг.l) . Выходы D- 30 триггеров соединены со входами сумматоров по модулю два согласно следующей системы уравнений:

35 где Ь „„ .; †единичный выход (m-1) -го триггера, g,+,. — выход (m+j-1)го сумматора йо модулю два, ® означает операцию суммирования по модулю два. Причем для органиэации связей первой группы сумматоров по модулю два используется система уравнений (1) при значении номера разряда регистра сдвига, выход которого соединен со входом сумма45 тора по модулю два в обычных структурах (I)i равной 3, а для второй группы сумматоров по модулю два при m-j. Так для случая m = 5 на входы сумматоров по модулю два.первой группы 3 (фиг,l) заведены связи в соответствии с системой: а =Ъ ОЬэ; „=,еЬ,; л,=ь,еЬ„; (,=Ь, Э,;,ci„=b„ a4, а на,входы сумматоров по модулю два второй группы 5 в соответствии со следующей системой о =Ь ®b

5 5

На выходах первой и второй группы сумматоров по модулю два последова- Я) тельно будут генерироваться m-разрядные коды псевдослучайных чисел

М-последовательностей, порождаемых следующими полиномами Ч (х) — х"+ x + 1 и 9 (х) = х + х + 1, причем периоды обоих последовательностей одинаковы. Последовательность следования же кодов отлична и случайна как в первой, так и во второй

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

В зависимости от значения равновероятной двоичной цифры на выходе генератора 7 единичный выход которого подключен к первой группе элементов И 4, а нулевой — ко второй группе 6 (фиг.l) . Код псевдослучайного числа с первой или второй группы сумматоров по модулю два через элементы ИЛИ 2 записывается íà Dтриггеры. Генератор 7 представляет собой простейший датчик равновероятной двоичной цифры, построенный на физических принципах.

Фукционирование генератора псевдослучайных чисел происходит следующим образом.

В начальный момент íà D-триггеры

1 записывается ненулевой код (фиг.1) .

На выходах сумматоров по модулю два первой группы 3 образуется очередной код псевдослучайного числа первой М-последовательности, а на выходе второй группы 5 — второй Мпоследовательности. B зависимости от значения очередной двоичной цифры на выходе генератора 7 по приходу тактового импульса на синхронизирующие входы триггеров 1 на их D входы через ту или иную группы элементов И и через элементы ИЛИ 2, объединяющие выходы обоих групп И, подается очередной код первой или второй М-последовательности. С приходом очередного синхронизирующегG импульса процесс повторяется.

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

m = 3, а на фиг.3 — временная диаграмма его работы. На фиг, За показана временная диаграмма синхронизирующих импульсов, по приходу которых триггеры устройства меняют свое состояние; на фиг. Зб-временная диаграмма на единичном выходе генератора 7; на фиг. 3 в и 3 г приведены две последовательности, порождаемые полиномами P(x) = х + х + 1 и Ч(х) =х +х+1, для j =1 и — 2. Стрелки с цифрами в кружках над ними означают последовательность переходов состояний триггеров устройства. В первоначальный момент на

708381

40 триггерах записан код 101, тогда 1 = 100, а 2 = 011. Так как в момент времени t< на единичном выходе генератора 7 находится единица, то приходу синхрокмпульса через верхнюю группу элементов И и элементы ИЛИ 5 на триггерах запишется код числа

100. После прохождения переходных процессов на выходах сумматоров установляются новые значения 1 = 011 и 2 = 110. В следующий момент времени на триггерах запишется код (2 = 110, т.к. на единичном выходе генератора 7 находится нуль.

Подобным образом триггеры меняют " свое состояние в зависимости от значения генератора 7 и по приходу последующих импульсов. На фиг. Зв и Зг стрелками показана граф-схема переходов состояний триггеров для t, 2 3 ло

Иэ вышеприведенного описания

20 функционирования генератора псевдослучайных чисел следуют следующие факты. Значения 1 и 2, генерируемые на выходах первой и второй группы сумматоров Iio модулю два в 25 каждый конкретный такт, являются значениями кодов из двух отличных M-последовательностей. Последующее значение (1 или 2 в худшем случае является следующим кодом М-последо- 30 вательности, получаемой при одном сдвиге в последовательном генераторе псевдослучайных чисел. Так, 1 принимает последовательные значения, которые получались бы в последователь-3$ ном генераторе 100 через 3 такта после 101, 011 через 3 такта после 100, 101 через 1 такт после 011, 111 через 4 такта после 101 (фиг,2,3) Отсюда очевидно, что 1 и 2 принимают значения иэ двух различных Мпоследовательностей (но,имеющих одинаковый состав кодов), порядок следования которых случаен. Нетрудно заметить, что при фиксировании на выходе генератора 7 нуля или единицы генератор псевдослучайных чисел будет функционировать как обычный генератор псевдослучайных чисел, А так как состояние его случайно, то и порядок следования кодов М-последо- 50 вательности будет абсолютно случаен.

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

5S функции выходных последовательностей имеют ненулевое значение только при

4 (C, где С вЂ” длительность выходного сигнала между очередными синхроимпульсамк. Такой вид автокорреля- бО ционной функции полностью удовлетворяет требованиям, поедъявляемым к случайным числам, Преимущества генератора заключаются в следующем. Природа выхолных $5 псевдослучайных последовательностей максимально приближена к кстккно случайным числам. В данном устройстве нарушено жесткое условие, имеющее место во всех генераторах псевдослучайных чисел к приводящее к такому недостатку, что после опредепенного (1; должно следовать (i заранее точно известное, В данном генераторе псевдослучайных чисел такое условие не соблюдается, так как (-;1„ „ может принять равновероятно одно из двух значений. Заметим, что в физических генераторах случайных чисел Ц(1+1 может принимать любое значение из всего набора возможных кодов.

Предлагаемый генератор отличается простотой технической реализации.

Удельные аппаратурные затраты на один разряд псевдослучайного числа составят один двухвходовой сумматор по модулю два, одну схему И, — схе,1

1 мы ИЛИ вЂ, D-триггера к — генерато2 о le ра 7.

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

Генератор 7, примененный в устройстве, может быть построен по самой простейшей схеме (напркмер триггер с коммутируемым питанием), так как требованкя к равновероятности выходной двоичной цифры являются очень низкими. Даже прк отказе этого генератора, т.е. когда на его выходе будет зафиксировано значение нуля или единицы, устройство в целом будет функционировать, но в этом случае период будет равен 2 — 1, а не бесVII конечности. Этот факт говорит о надежности функцконкрованкя предлагаемого устройства и стабильности его вероятностных характерксткк.

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

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

Генератор псевдослучайных чисел, содержащий первую группу сумматоров по модулю два к группу -,ðèããеров, входы синхронизации которых подключены к выходу генератора тактовых импульсов, о т л к ч а .о щ и йс я тем, что, с целью ра л:ренкя функциональных зо зко...<н о от ейл г:".Iÿð àтора за счет устранения повTçðå 11ля последовательности кодов псевдослу708381 чайных чисел на выходах генератора, он содержи т первую и вторую группу элементов И, группу элементов ИЛИ, вторую группу сумматоров по модулю два и генератор равновероятной двоичной цифры, ко входу которого подключены выход генератора тактовых импульсов, а единичный и нулевой выходы генератора равновероятной двоичной цифры подключены к первым входам первой и второй групп элементов И соответственно, ко второму входу i-го элемента И первой группы подключен выход i-го сумматора по модулю два первой группы, ко второму входу i-ro элемента И второй группы подключен выход 1-го сумматора по модулю два второй группы, выходы i-ых элементов И первой и второй групп подключены ко входам

i-го элемента ИЛИ, выход которого подключен ко входу i-го триггера, к первым входам i-ых сумматоров по модулю два первой и второй групп подключены единичные выходы 1-ых триггеров, ко вторым входам j старших сумматоров по модулю два первой группы подключены выходы 3 младших триггеров, к вторым входам m-j

5 младших сумматоров по модулю два первой группы подключены выходы

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

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

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

Л,, Машиностроение, 1974, с.344.

2. Авторское свидетельство СССР по эаявке 9 2415584/24 от 20 апреля

1977 г. (прототип) .

708381 о г з; s

Составитель A. Карасов

Редакто Д. 3 бов Тех ед N.Êåëåìåø Корректо И. Михеева

Р 2 B E

Заказ 8492/46 Тираж б41 Подписное

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

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

Филиал ППП Патент, r. Ужгород, ул „ Проектная,4