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

 

ОПИСАНИЕ

ИЗОБРЕТЕНИЯ

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

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

Ссщиалистических

Республик ii l О05045

{61) Дополнительное к ввт. свид-ву— (22) Заявлено 181281 (21) 3365888/18-24

Р М К з с присоединением заявки ¹â€” а 06 F 7/58

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

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

{23) Приоритет—

Опубликовано 150383. Бюллетень № 10

Дата опубликования описания 15. 03. 83 (53) УДК 681. 325 (088. 8) (71) Заявитель

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

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

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

ЭВМ, что позволит увеличить производительность вычислительных средств; при решении определенного круга задач.

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

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

Параллельный генератор псевдослучайных чисел (1) отличается.максимальным быстродействием.

Сложность схем формирования сдвинутых последовательностей определяется числом входов сумматоров по модулю два. Каждый сумматор в среднем имеет m/2 входов. При этом

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

Известен также генератор псевдослучайных чисел, позволяющий получать последовательности: псевдослучайных чисел, максимально близкие по природе к истинно случайным чис- 10 лам. его техническая реализация осуществляется при малых удельных .аппаратурных затратах f2 j.

Недостатком данногб устройства является ненозможность получения на 15

его выходе m-разрядного псевдослучайного числа („ = ООО„О, отсутстние которого приводит к искажению равномерного закона распределения, которое увеличивается с уменьшением ве- р0 личины m..

Известен генератор псевдослучайных чисел, который позволяет получить на выходе код псевдослучайного числа равного 000...0, что приводит 25 ,к выравниванию математического ожи1, дания вероятности появления любого кода (3 ).

Недостаток этого генератора заключается н большой аппаратурной сложности. Удельные аппаратурные затраты на« один разряд псевдослучайного числа составляют один (пч+1)— нходоный сумматор по модулю два,. один триггер, одну схему ИЛИ-НЕ,од.ну схему ИЛИ, rrr + 2 схемы и и 1/rn генератор ранновероятной двоичной цифры. Кроме того, подобный генератор должен иметь в своем составе дна регистра для хранения коэффициентов "ни Ре 40

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

НЕ, группу из m — 2 элементов ИЛИ-HE группу из m сумматоров по модулю два (4).

В данном Устройстве предусмотре- 50 на возможность получения на выходе генератора комбинации 000.;..О,что приводит к выравниванию вероятности поЯвлениЯ коДа к, Р Я<) котоРаЯ для любого к равняется 1/2

Таким образом, закон распределения выходных последовательностей в данном устройстве является равномерным, так как вероятность появления на его выходе любого кода одинакова и равняется 1/2 . Последовательнос- 60 ти, генерируемые на выходе рассмотренного устройства, относятся к клас-. су так называемых последовательностей де Брюйна (de Bruijn) или циклами де Брюйна. Введение нулевой 65 комбинации н М-последовательность ухудшает корреляционные свойства последовательности, причем этот недостаток присущ всем последовательностям, относящимся к последовательностям де Брюйна. Кроме того, недостатком рассмотренного устройства является наличие периода в формируемой последовательности, который ограничивается величиной гп где m — количество триггеров, иду» щее на построение устройства.

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

Поставленная цель достигается тем, что генератор псевдослучайных чисел, содержащий генератор тактовых импульсов, группу za rn(rn = 1,2,... число разрядов генератора ) D-триггеров, первую группу из rn сумматоров по модулю два и первую группу из двух элементов HE причем выход генератора тактовых импульсов подключен к С-входам 0-триггеров группы, а выход i --го (i =1 m ) D-триггера группы подключен к первому вхо- ду i -ro сумматора по моДулю два первой группы, введены дне группы

rro rn элементов И, вторая группа из

rn сумматоров по модулю дна, вторая группа из m — 1 элементов НЕ, группа из тп элементов 2И-ИЛИ, генератор равновероятной двоичной цифры, кроме того, н первую группу элементов, HE дополнительно введено п-2 элементов НЕ, причем к 0-входу i.-ro

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

j -го (j = 1,rn — 1) 0-триггера подключен к входам m -,) старших элементов И первой группы, выход (j+1)го элемента НЕ первой группы подключен соответственно к входам j младших элементов И первой группы, выход i --ro элемента И первой группы подключен к второму входу i-го сумматора по модулю два первой группы, к третьим входам.п(1п:.7р 1/2 rrr ) старших сумматоров по модулю два первой группы подключены единичные выходы младших 0-триггеров группы соответственно, а к третьим входам младших сумматоров по модулю два первой группы подключены выходы r)1-r1 старших сумматоров по модулю два первой группы соответственно, выхо-, ды rn трехвходовых сумматоров по модулю два первой группы подключейы к входам fA элементов HE первой группы соответственно, выход j -ro элемента НЕ первой группы подключен к соответствующим входам m- g стар1005045 ших элемент н Н второй группы, выход

j --го элемента НЕ второй группы под-. ключен к соответствующим входам ,младших элементов И второй группы, выход .t-ãî элемента И второй груп -. пы подключен к первому входу l--ro суьв атора по модулю два второй группы, к второму входу которого подключен выход .i--ro сумматора по модулю два первой группы, к третьии входам и старших сумматоров по модулю два второй группы подключены выходы и младших сумматоров по модулю два первой группы соответственно, а к третьии входам m --n младших сумматоров по модулю два второй 15 группы подключены выходы ttI — n старших сумматоров по модулю два первой группы соответственно, выходы tlt — 1 старших сумматоров по модулю два

:второй группы подключены к входам 2О

tn - 1 элементов НЕ второй группы соответственно, кроме того, к перво= му и второму входам 1-го элемента 2

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

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

Генератор псевдослучайных чисел содержит m=5 3 -триггеров 1, две группы.

-по tn элементов И 2 и 3, две группы по ttt сумматоров по модулю два 4 и 5, первую, группу из tn элементов HE 6, вторую 45 группу из rn — 1 элемента НЕ 7., группу из tn элементов 2 И-ИЛИ 8, генератор 9 равновероятной двоичной цифры, генератор 10 тактовых импульсов . . 50

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

В начальный момент на D -тригге.ры 1 записывается произвольный код

55 в том числе и нулевой. На вы- ходах сумматоров по модулю два первой группы 4 Формируется т -разрядный код „, который является продолжением.кода р в соответствии с за- 60 данной. M-последовательностью (вид .М-последовательности определяется полиномом 9(x) 1+х1 + х "), а на выходах элементов 5 - код являющийся продолжением кодаф„. Ilo,ÿ приходу тактового импульса на синхронизирующие входы D -триггеров 1 выходов элементов В на D -триггеры

1 записывается код, полученный на выходе сумматоров 4 или 5, т.е . или (. С прйходои очередного сйнхронизирующего импульса процесс повторяется.

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

tn = 5 и для сЕ„= Î,с = О, d - =1, с6, = О, d g- 1, а на Фиг. 3 — временная диаграмма его работы.

На фиг. 3 показана последователь ность, генерируемая на выходе обычного последовательного генератора псевдослучайных чисел построенного согласно следующему пораждающему полиному ч(х) 1+ х> + х . Фигур-. ными скобками обозначены сегменты

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

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

10101 и на выходе устройства (сумматор . 5) †.код f+ = 1ОООО. Так как, например, значение х(0) в нулевой момент равняется 1, по приходе синхроимпульса íà D-триггеры записывается код 10101. После прохожде« ния переходных процессов на выходах сумматоров 4 . формируется код 10000, а на выходе устройства — код „=10100.

В следующем такте на Э -триггеры запишется код 10100, так как значение х(11 О. Подобным образом В"триг геры меняют свое состояние в зависимости от значения,на выходе генератора 9 равновероятности двоичной цифры и по приходе последующих тактовых импульсов. На фиг. 3 сплоыными стрелкаии.показана последовательность выходных кодов рассматриваемого устройства для х(0) .1, х(1) О, х(2) I, х(3) .1.

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

1005045 может быть любой rn-разрядный код, в том числе и нулевой.

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

Природа выходных псевдослучайных чисел, подобно как и в устройствах (2 3 и (3), максимально приближена к истинно случайным числам. В данном устройстве также нарушено жесткое условие, что после опреде- 1О ленного, ; должно следовать „+1 заранее точно известное, так как в данном случае 1+1 может принимать равновероятное одно из двух значений. 15

В отличие от устройства (2 ) на выходе рассматриваемого генератора псевдослучайных чисел возможно получение кода 000...0 что приводит к выравниванию математического ожида- 2р ния вероятности появления любого ,кода F, которая в данном случае равняется Р() =,д . Отсутствие запрещенных кодов f позволяет повы2 сить надежность генератора псевдо- 25 случайных чисел, так как, подобно ,устройствам (3 ) и (4 ), наличие нулевого кода на триггерах не срывает генерирования псевдослучайной последовательности.

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

З-триггер, один элемент 2 И-ИЛИ, два 35 трехвходовых сумматора по модулю два, два (rn - 1)-входовых элементов И два элемента HE и — генератор рав1 новероятной двоично3 цифры, что значительно меньше соответствующих 4р затрат в устройстве (4 1.

В сравнении с базовым объектом генератором псевдослучайных чисел (1)предлагается устройство, отличающееся рядом преимуществ. Во-первых, 45 свойства выходной последовательности, получаемой на выходе рассматриваемого. генератора, значительно лучше свойств последовательностей, получаемых на выходе базового объекта. Так 5О период выходных последовательностей в предлагаемом автором устройстве равен о, а вероятность появления

f 1 любого кода равняется P($)=

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

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

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

Генератор псевдослучайных чисел, содержащий генератор тактовых импульсов, группу из п(п — число разрядов генератора) Э вЂ” триггеров, первую группу иэ TTl Чумматоров по модулю два и первую группу иэ двух элементов НЕ, причем выход генератора тактовых импульсов подключен к С-входам Э -триггеров группы, а выход i -ro

1,tn )l>-триггера группы подключен к первому входу 1-го сумматора по модулю два первой группы, о т л и ч а ю шийся тем, что, с целью расширения функциональных воэможностей эа счет улучшения корреляционных свойств генератора, дополнительно введены две группы no m элементов И, вторая группа из m сумматоров по модулю два, вторая группа иэ

rn — 1 элементов НЕ, группа из rn элементов 2 И-ИЛИ, генератор равновероятной двоичной цифры, кроме того,в первую группу элементов НЕ дополнительно введено тп — 2 элементов НЕ,причем к Р -входу i -го 3 --триггера подключен выход 1 -го элемента

2 И-ИЛИ группы, нулевой выход j-го (j = 1,m — 1 ) Й -триггера подключен к входам rn- ) старших элементов И первой группы, выход (j + 1) -го элемента НЕ первой группы подключен к соответствующим входам j младших элементов И первой группы, выход

i-го элемента И первой группы подключен к второму входу i --ro сумматора по модулю два первой группы, к третьим входам н (и >, 1/2 m) старших сумматоров по модулю два первой группы подключены единичные выходы и младших В -триггеров группы соответственно, к третьим входам .tTI- и младших сумматоров по модулю два первой группы подключены выходы

m - и старших сумматоров по модулю два первой группы соответственно, выходы m трехвходовых сумматоров по модулю два первой группы подключены к входам тп элементов НЕ первой группы соответственно, выход j -ro элемента НЕ первой группы подклю" чен к соответствующим входам т -j старших элементов И второй группы, выход j -ro элемента НЕ второй группы подключен к соответствующим

1005045

: входам g младших элементов И второй группы, выход i.-го элемента И второй группы. подключен к первому входу z-го сумматора по модулю два второй. группы, к второму входу которого подключен выход i -го.сумматора по модулю два первой группы, к третьим входам и старших сумматоров по модулю два второй группы подключены выходы и младших сумматоров по модулю два первой группы соответственно, а к третьим входам щ-и младших сумматоров по модулю два второй группы подключены выходы tn- M старших сумматоров по модулю два первой. группы соответственно, выходы l5

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

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

1. Яковлев B.Â. и Федоров Р.Ф.

Вероятные вычислительные машины.Л., "Машиностроение", 1974, с. 344.

2. Авторское свидетельство СССР

708381;кл. 6 07 С 15/00, 1980, 3. Авторское свидетельство СССР по заявке У 2988394/18-24, кл. 6 06 Г 7/58, 16.04.80.

4. Авторское свидетельство. СССР по заявке 9 2920810/18-24, кл. G 06 F 7/58, 26.11.80 (прототип).

Х(2) = у 1д1110 11000111 11дд1 10100 100DO

fur. Ф

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

Редактор Л.Алексеенко Техред Л.Пекарь Корректор N.Äåì÷èê

Заказ 1900/64 Тираж 704 Подписное

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

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

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