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

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

Иллюстрации

Показать все

Реферат

 

ОП ИСАНИЕ

ИЗОБРЕТЕНИЯ

К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ

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

Социалистических Республик 924706 (61) Дополнительное к авт. свид-ву (22)Заявлено 02.10.80 (21) 2988394/18-24 с присоединением заявки .% (23) Приоритет (5l)M. Кл.

6 06 с 7/58

3Ъоударстаеииый комитет

СССР ао делам изобретений и открытий

Опубликовано 30.04.82 Бюллетень М

Дата опубликования описания 30 .04 .82 (53) УДК681.325 (088.8) (72) Авторы изобретения

В.Н.Ярмолик и И.П.Кобяк

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

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

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

Недостатком данного генератора является наличие периода в формируемой последовательности и, кроме того, невозможность получения нулевого I5 кода псевдослучайного числа. Параллельный генератор псевдослучайных чисел позволяет получать нулевой код псевдослучайного числа и отли20 чается максимальным быстродействием.

В качестве основного недостатка генератора от меча ется сложнос т ь схем формирования сдвинутых последовательностей, определяемая числом входов сумматоров по модулю два. Каждый сумматор в среднем имеет тп /2 входа.

При этом затраты оборудования,необходимые для построения схем формироаания сдвинутых последовательностей, в несколько раз превышают затраты, идущие на построение кольцеваго регистра сдвига, состоящего из пт разрядов.

Наиболее близким по технической сущности к предлагаемому является генератор псевдослучайных чисел, состоящий из тп триггеров, группы weментов ИЛИ, первой и второй группы двухвходовых сумматоров по модулю два, первой и второй группы двухвходовых схем И и генератора равновероятной двоичной цифры. Количество сумматоров по модулю два, элементов

И и ИЛИ в группах равняется щ. Все узлы устройства соединены соответствующими связями.

706 0

S0

3 924

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

Недостатком описанного устройства во-первых, является невозможность получения íà его выходе rn-разрядного псевдослучайного числа f< =000...0.

Отсутствие комбинации Е = 000...0 приводит к искажению равномерного закона распределения, которое увеличивается с уменьшением величины

Вторым весьма существенным недостатком генератора псевдослучайных чисел является ограниченность его функциональных возможностей. При практической реализации генератора оказывается возможным построение такого генератора для весьма узкого класса неприводимых примитивных характеристик многочленов. Поэтому для некоторых значени" m построение генератора оказывается невозможным. Так, например, для г = 8, 16, 24, 32 отсутствуют порождающие многочлены требуемого вида, таким образом, нет возмож-ности реализации генератора в разрядность, согласованной с разрадностью

ЭВМ семейства ЕС. Кроме того, генератор отличается жесткостью структуры и неуниверсальностью, что объясняется невозможностью изменения вида порождающего многочлена для .фиксированного m в процессе его эксплуатации.

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

Для достижения поставленной цели в генераторе, содержащем m-триггеров, группу элементов ИЛИ, первую и вторую группы двухвходовых элементов И, генератор рав нов ероят ной дв оичной цифры, группу (m + 1) входовых сумматоров по мощулю два, группу (m — 1 ) входовых элементов ИЛИ-НЕ, третью группу из m подгрупп по m двухвходовых элементов И, причем к С-входам m триггеров и входу генератора равновероятной двоичной цифры подключен выход генератора тактовых импульсов, а единичный и нулевой выходы генератора равновероятной двоичной цифры подключены к первым входам первой и второй групп элементов И, выходы i-x элементов И первой и второй групп подключены ко входам -го элемента ИЛИ, ко вторым входам первой и второй групп элементов И поданы значения коэффциентов принимающих величину нуля или единицы, выход i-го элемента ИЛИ подключен к первому входу i ãî элемента

И R-й подгруппы третьей группы, выходы элементов И -й подгруппы третьей группы и выход 2-го элемента

ИЛИ-НЕ подключены ко входам 3-го (m + 1) входового сумматора по модулю два, выход -ro триггера подключен ко второму входу (+i-1-го элемента И ш+ Г-1-ой подгруппы третьей группы и к I+i-1-му входу m+1-3-ro элемента ИЛИ-НЕ, выход E,-ro (m+1)входового сумматора по модулю два подключен к О входу Р-го триггера ко второму входу В-i-го элемента И

1-ой подгруппы третьей группы и к

1-ому входу Р- -го элемента ИЛИ-НЕ.

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

Приведенная функциональная схема (фиг. 1) генератора для m = 5, подобно как и в общем случае, состоящий из m D-триггеров 1, группы элементов ИЛИ 2, первой и второй группы двухвходовых элементов И 3, 4, генератора 5 равновероятной двоичной цифры, группы (m+ 1) входовых сумматоров 6 по модулю два, группы (m-1) входовых элементов ИЛИ-НЕ 7, третьей группы из m подгрупп по m двухвходовых элементов И 8. Количество элементов ИЛИ 2, элементов И в первой и второй группах 3 и 4,(е + 1) входовых сумматоров 6 по модулю два, (m - 1) входовых элементов ИЛИ-НЕ 7 и триггеров 1 в группе равняется m

Единичные выходы 0-триггеров соединены со входами двухвходовых элементов И 8 третьей группы и входами элементов ИЛИ-НЕ.

5 92470

На выходах сумматоров 6 по моду" лю два последовательно будут генерироваться rn-разрядные коды псевдослучайных чисел двух И-последовательностей, причем периоды обеих последовательностей одинаковы. Последовательность следования же кодов отлична и случайна как в первой,так и во второй М-последовательности.

Таким образом, на выходе (1)-вхо- !в довых сумматоров 6 по модулю два (фиr. 1) генерируются m -разрядные сегменты двух отличных М-последовательностей одинаковой длины. При фиксированном значении равновероятной двоичной цифры устройство представляет собой генератор псевдослучайных чисел, генерирующий на своем выходе m -разрядные псевяослучайные числа. При переменном значении двоич- щв ной цифры в зависимости от ее величины на выходе генератора равновероятной двоичной цифры, единичный выход которого подключен к первой группе элементов И 3, а нулевой - ко д второй группе 4 (фиг. 1), код гпразрядного псевдослучайного числа той или иной И-последовательности с выходов (m+ 1) входовых сумматоров 6 по модулю два записывается íà Dтриггеры 1. Генератор 5 равновероятной двоичной цифры представляет со" бой простейший датчик равновероятной двоичной цифры, построенный на физических принципах.

Устройство работает следующим образом.

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

1 записывается произвольный код, в том числе и нулевой (фиг. 1) . На вы- 4О ходы элементов ИЛИ 2 проходят значения коэффициентов первого или второго характеристического многочлена в зависимости от того, равняется единице или нулю величина Я, на выходе генератора 5 в данный момент времени. В зависимости от значения величины с на выходах о+ 1) входовых сумматоров по модулю два образуется очередной т -разрядный код псевдо50 случайного числа первой или второй

M-последовательности. По приходу тактового импульса на синхронизирующие входы триггеров 1 через их D входы на триггерах 1 запишется код, полученный на выходе сумматоров 6 по модулю два. С приходом очередного синхронизирующего импульса процесс повторяется.

6 6

Подробный процесс генерирования псевдослучаиных чисел рассмотрим на генера торе ра ндомизи рова нных псевдослучайных чисел для = 3. Нь фиг.3 а показана временная диаграмма синхронизи рующих импульсов, по приходу которых триггеры устройства меняют свое состояние; на фиг. 3 б — временная диаграмма на единичном выходе генератора; на фиг. 3 в и 3 г приведены две М-последовательности. Стрелки с цифрами в кружках под ними означают последовательность переходов состояний триггеров 1 устройства.

В первоначальный момент на триггерах записан код 101. Так как в момент времени t q на единичном выходе генератора 5 находится единица (фиг. 3 б), то через элементы И 3 и элементы ИЛИ 2 на входы элементов

8 подаются коэффициенты . С учетом конкретных значений коэффициентов Я на выходах сумматоров 6 по модулю два очередное значение псевдослучайного числа „будет равняться 000.По приходу тактового импульса в момент времени на синхровходы

-триггеров 1 и вход генератора 5 псевдослучайное число „запишется на триггеры 1 и равновероятная двоичная цифра с примет значение, равное нулю. После прохождения переходных процесссв на выходах сумматоров 6 по модулю два устанавливается новое значение = 101. В следующий момент времени на триггерах 1 запишется код 10 1, так как на единич" ном выходе генератора 5 находится ноль. Подобным образом триггеры меняют свое состояние в зависимости от значения на единичном выходе генератора 5 и по приходу последующих так" товых импульсов. На фиг. 3 в и 3 г стрелками показана граф-схема пере" ° ходов состояний триггеров для моментов времени

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

35

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

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

7 92 <7 чисел. А так как состояние генератора 5 случайно, то и порядок следования кодов М-последовательностей будет абсолютно случайным, причем выходным значением устройства с равной вероятностью может быть любой п1-разрядный код, в том числе и нулевой. Подобный факт означает, что автокорреляционная функция выходной последовательности имеет ненулевое значение только при т.<Т, где - дли- тельность выходного сигнала между очередными синхроимпульсами. Такой вид автокорреляционной функции полнос т ью удовл ет в оряет т ре бова ниям, предъявляемым к последовательностям случайных чисел.

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

Природа выходных псевдослучайных чисел максимально приближена к истинно случайным числам. В данном устройств е, подобно как и в прототи пе, нарушего жесткое условие, что после определенного должно сл едо ва т ь

Ф1

„заранее точно известное, так как

1Н

1 может принимать равновероятно од1Ф1 но из двух значений, Возможность получения на выходе генератора кода псевдослучайнрго числа равного 000...0 приводит к выра внив анию мат емати че ского ожида ния вероятности появления любого кода, которая s данном случае равняется

Р() = 1/2 .

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

40 выходных последовательностей. Так автокорреляционная функция выходной последовательности при 1 7 будет иметь нулевое значение, а не значение равное 1/(2 - 1) что имеет место в про"

45 тотиее. Отсутствие запрещенных кодов позволяет повысить надежность генератора, так как наличие нулевого кода на триггерах 1 не срывает генерирования псевдослучайной последователь50

НОСТИ.

При практической реализации генератора рандомизированных псевдослучайных чисел оказывается возможным построение такого генератора для любого неприводимого примитивного характеристического многочлена. Поэтому для любого значения m, в том числе и для г» = 8, 12, 13, 14, 16, 19, 8

26, 27, 29, 30, 32 и т. д. реализации генератора рандомизирова нных псевдослучайных чисел возможна.

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

В процессе экс плуата ции генератора рандомизированных псевдослучайных чисел возможно изменение М-последовательностей путем замены коэффициентов Q и р< пораждающих их характеристических многочленов.

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

Удельные аппаратурные затраты на один разряд псевдослучайного числа составят один (m+ 1) .входной сумматор по модулю два, один триггер, один элемент ИЛИ-НЕ, один элемент ИЛИ, m + 2 элементов И, и 1/ генератора равновероятной двоичной цифры. Генератор

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

924706

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

Генератор псевдослучайных чисел, содержащий m D -триггеров, группу элементов ИЛИ, первую и вторую груп- 5 пы элементов И, генератор равновероятной двоичной цифры, причем к синхровходам D-триггеров и входу генератора равновероятной двоичной цифры подключен выход генератора так- О товых импульсов, а единичный .и нулевой выходы генератора равновероятной двоичной цифры подключены к первым входам элементов И первой и второй групп, выходы -х (1= 1, 2,..., m) элементов И первой и второй групп подключены к входам i -го элемента ИЛИ, отли ч.ающи йс я тем, что, с целью расширения функциональных возможностей генератора за счет рас- 20 ширения класса генерируемых псевдослучайных последовательностей чисел, он содержит группу (%+ 1) входовых сумматоров по модулю два, группу (m- 1) входовых элементов ИЛИ-НЕ и третью группу из п подгрупп по m элементов И, причем вторые входы элементов И первой и второй группы образуют соответственно первую и вторую группы входов генератора, а выход 1-го элемента ИЛИ подключен к первому входу -го элемента И

3 -й (1= 1, 2,...,m) подгруппы третьей группы, выходы элементов И -й подгру ппы трет ьей группы и выход

3-го элемента ИЛИ-HE подключен к входу 6-ro (e+ Ц входового сумматор по модулю два, выход i -го триггера подключен к второму входу + ч-1-ro элемента И {m+ 1 -9)-й. подгруппы третьей группы и к ф+ i - 12-му входу (re+ 1 - Ю-го элементов ИЛИ-НЕ, выход Р-го (w+ 1) входсвого сумматора по модулю два подключен к D -входу

8-ro триггера, к второму входу(- )ro элемента И -й подгруппы третьей группы и к 1-му входу (8-1)-го элемента ИЛИ-НЕ.

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

1. Яковлев В.В. и Федоров P.Ô.

Вероятностные вычислит ел ьные машины.

Л., "Иашиностроение", 1974, 2. Авторское свидетельство СССР

708381, кл. Я 06 " 1/02, 1977 (прототип 2 .

924706

4 з 4Е 6 s 7 в Ю

01) фигЗ

Яйг.4

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

Редактор В.Пилипенко Техред С.Мигунова Корректор A ° Гриценко

Заказ 2820/67 Тираж 732 Подпис ное

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

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

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