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

 

ОПИСАНИЕ

ИЗОБРЕТЕНИЯ {-868734

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

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

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

Республик (63) Дополнительное к авт. саид-ву(22) Заявлено 1009.79 (21) 2815712/18-24 (51) М. Кл. с присоединением заявки ¹

G F 1/02

G 07 С 15/00

ГосударстаеняыЯ комктет

СССР яо делам язобретемкЯ н открытяЯ (23) Приоритет

Опубликовано 300981. бюллетень № 36

Дата опубликования описания 30.0981 (53) УДК 681. 325 (088.8) (12) Авторы изобретения

A.Å.ËåóñåHêî, В.Н.Ярмолии,и,.А.Н.Морозевич у 1

f

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

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

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

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

Известно также устройство, в котором для приближения свойств псевдослучайных чисел к свойствам истинно случайных, полученных физическими способами., период повторения последо-20 вательности увеличен до величины 22и 2 ко периодичность в указанном

° ° устройстве сохраняется.

Наиболее близким к предлагаемому 25 является генератор псевдослучайных чисел, содержащий первую и вторую группы двухвходовых сумматоров по модуюпо два, первую и вторую группы элементов И, группу элементов ИЛИ, груп- 30 пу триггеров и генератор равновероятной двоичной цифры. Подобный генератор предназначен для генерирования за один такт двух m-разрядных псевдослучайных чисел (3 ).

Недостаток описанного устройства— отличие вероятности появления нуля или.единицы в. разрядах чисел от 0,5 по обоим каналам. Так, вероятность появления нуля или единицы в любом разряде псевдослучайного числа по обоим каналам определяется иэ выражений (0к=1)= 2 + 2 (i)

Р(с „=o); (Ф

1 1

Известно, что построение таких высокоэффективных устройств, какие приведены в (2), имеет смысл при небольших значениях величины, m. В этом случае выражение g = — — — —.

2lll-1 У характеризующее отклонение от равновероятности, принимает значение, величина которого в ряде случаев оказывается недопустимой. Даже при

m=10 g =0,001.

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

Поставленная цель достигается тем, что генератор, содержащий первую и вторую группы двухвходовых сумматоров по модулю два, первую и вторую группы трехвходовых сумматоров по модулю два, первую и вторую группы элементов И, группу элементов

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

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

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

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

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

m=4.

В общем случае генератор псевдослучайных чисел состоит из m триг-геров 1, m элементов ИЛИ 2, первой группы Ь элементов И 3, второй группы m элементов И 4, генератора 5 равнонероятной двоичной цифры, пер20 вой. группы е-) двухвходоных сумматоров б по модулю два, второй группы двухвходовых сумматоров 7 по мо, дулю два, первой группы j трехвходовых сумматоров 8 по модулю 8, второй

25 группы m-j трехвходовых сумматоров

9 по модулю два.

Количество двухвходовых сумматоров по модулю два в первой группе равняется m-j, а во второй группе . В тоже время количество трехвходовых сумматоров по модулю два в первой и второй группе равняется j u m-j соответственно. На выходах двухвходоных и трехвходовых сумматоров по модулю дна первых групп получаются значения псендослучайного числа (1=

=а, а,...,а„„ а на вы::одах вторых групп получаются значения псевдослучайного числа 2=а, а,...,а, „. Чис1 Ф ла 1 и 2 представляют собой m40 разрядные коды или их инверсии Мпоследовательностей, порождаемых слу-. чайными полиномами 9 (2) 25 2 +1 и

9(2) =2 4 Е 41, причем периоды обоих последовательностей одинаковы.

45 Последовательность следования кодов

1 отлична и случайна как в первой, так и во второй М-последовательности. Появление прямого кода М-последовательности или его инверсии по первому и

50 второму каналу определяется значением очередного отсчета на выходе генератора равновероятной двоичной цифры. Выходы 0-триггеров и генератора равновероятной цифры соединены со

55 вход ми трехвходовых сумматоров по модулю два первой и второй группы согласно выражениям .

868734 по первому каналу и в соответствии с системой

a =Ь„®Ь6Ю" 0 =Ь ЭЬ 9Х; а, =Ь ОЬ, ЯХ

eb49õ; а =Ü„ea Л)

45 где Ь .(k) - значение на единичном выходе (m-i)-ro триггера в k-ый такт работы устройства,"

x(k) и x(k) — значения на единичном и нулевом выходах генератора равновероятной двоичной цифры, а (к) и а (к) - значения на выходах трехвходовых сумматоров по модулю два первой и второй .группы; знак Q означает операцию суммирования по модулю два.

Выходы 0-триггеров и выходы сумматоров по модулю два соединены со входами двухвходовых сумматоров по модулю два первой и второй групп согласно выражениям

;(Ю=Ь„„„(«)®а „(«),j=уи; (g

О;(«) =,„„(«1®С,„„, («), <=ь,-1, ям (Ь) При использовании выражений (3)(6) для организации связей в гене- }5 раторе псевдослучайных чисел для нумерации сумматоров по модулю два пер вых групп и вторых групп используются единые сквозные нумерации. Для случая

m-=5, j =--1 на выходы сумматоров по модулю два. На фиг.1 представлены связи

30 в соответствии с системой

7®Ь19Х i С38 =Ь69О,О =Ь5®С б С 4= 4@ Р ®Я4,a .=b ®a с)1 Ь1ЭОа. (7) по второму каналу. В зависимости от значения равновероятной двоичной цифры на выходе генератора 5 равновероятной двоичной цифры код псевдо- 5р случайного числа 1 или 2 с сумматоров по модулю два через элементы ИЛИ 2 записывается на О-триггеры.

Генератор 5 представляет, собой простейший датчик равновероятной двоич-, 55 ной цифры, построенной на физических принципах.

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

В начальный момент на 0-триггеры 1 записывается ненулевой код (фиг. 1) . dp

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

x(k) в данный момент времени равня- 65 ется О, а на выходе сумматоров 7 и

9 по модулю два образуется обратный код псевдослучайного числа второй

М-последовательности, так как xTk)

=1. В случае, когда х (k) =1, на выходе блоков 6 и 8 образуется обратный код, в котором проинвертированы значения разрядов псевдослучайного числа, а на выходе блокон 7 и 9, соответственно, прямой, так как xgk)=0.

B зависимости от значения очередной двоичной цифры на выходе генератора х(k)Я )О, Ц по приходу тактОвого импульса на синхронизирующие входы триггеров 1 на их входы через первую или вторую группы элементов И 3 и 4 и через элементы ИЛИ 2, объединяющие выходы обоих групп И, подается очередной код первой или второй М-последовательности. С приходом очередного тактового импульса процесс повторяется.

На Фиг.3 для каждого такта рабо ты k=1,10 показаны соответствующие значения выходных псевдослучайных чисел (1 и 2 и содержимое триггерного регистра 1 (). В первоначальный момент на триггерах записан код

0001,а значения (1(1) 0000 и (2(1)=

=1001, причем 1 есть инвертированный код первой М-последовательности, так как x(1) =0. Па приходу тактового импульса на триггеры записывается код числа (2 (1), таким образом во втором такте исходной информацией для формирования 1(2) и 2(2) является

1001. Так как х(2)=1> то 1(2) принимает неинвертированное значение кода первой М-последовательности, а 2(2)— инвертированное значение кода второй

М-последовательности. В следующий момент g(k) содержимое триггерного регистра принимает значение 1000. Подобным образом триггеры меняют свое состояние в зависимости от значения x(k) на выходе генератора равновероятной двоичной цифры по приходу последующих импульсов.

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

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

25 чайной последовательности с последовательностью отсчетов равновероятной двоичной цифры.Это следует из такого факта, что выражение для формирования значения любого разряда выходного псевдослучайного числа по обоим каналам на основании (3)-(6 ) представляется в виде выражений а1 (k)а (М)Юх(k), i 1m; (9) а (k) а (k)@>x(k), lfm, (10)

I где SP i; так, например, для а, Ь Юа Ь1® Ь79Ь6Юх=а Ех. Здесь в преобразованиях используется свойство сдвига и сложения M-последовательности.

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

Р(о„= ) =Р(а ® Х=1) =Р(ОзО+х= )= бз ) з

Учитывая, что а9 и х независимы, выражение (11) принимает вид

P(q„=<) =P(a,=o)P(x=q)+

+ Р(а5=4) P (X=O) )P — — „

"IX (<2 )

Анализ выражения (12) показывает, что вероятность появления единицы или 30 нуля на выходе генератора отличается от 0,5 на величину

Ч х»»»

2 "-1 где — отклонение от О, 5 вероятности

35 х появления единицы на выходе генератора равновероятной двоичной цифры.

Так как величина rIX =0,01 — 0,001 для известных устройств (1), то значение P(0=i) незначительно отличает- 40

1 ся от 0,5. Таким образом, вероятность появления нуля или единицы в разрядах псевдослучайных чисел по обоим каналам в предлагаемом устройстве максимально приближена к 0,5, Для случая 45 =10,âåëè÷èíà, характеризующая отклонение от 0,5, равна 0,00001-0,000001.

Таким образом, природа выходных псевдослучайных последовательностей максимально приближена к истинно слу- 5О чайным числам. Предлагаемый генератор отличается простотой технической реал ации. Удельные аппаратные затраты на один разряд псевдослучайного числа составляют один элемент и, 55 -элемента ИЛИ, двухвходового сум2 матора по модулю два, — трехвходовос го сумматора по модулю два, - триггера и $ генератора равновероятной двоичной цифры. Предлагаемый генератор псевдослучайных чисел позволяет 60 получать числа по двум каналам.

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

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

Генератор псевдослучайных чисел, ° содержащий первую группу из m-j двухвходовых сумматоров по модулю два, вторую группу из j двухвходовых сумматоров по модулю два, первую и вторую группы элементов И, группу элементов ИЛИ, группу триггеров и генератор равновероятной двоичной ци<рры,ко входу которого подключен выход генератора тактовых импульсов, а единичный и нулевой выходы генератора равновероятной двоичной цифры подключены к первым входам элементов И первой и второй групп соответственно вторые входы m-j H первой группы подключены, соответственно, к выходам m-j двухвходовых сумматоров по модулю два первой группы, вторые входы 1 младших элементов И второй группы подключены соответственно к выходам млацших двухвходовых сумматоров по модулю два второй группы, выходы 1--х элементов И первой и второй групп подключены к соответствующим входам i-го элемента

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

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

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

m-2j старших сумматоров по модулю два первой группы, выход генератора тактовых импульсов подключен к синхровходам триггеров, о т л и ч а ю— щ и й с я .тем, что, с целью повышения точности генератора, он содержит первую группу из j трехвходовых сумматоров по модулю два и вторую группу иэ m-j трехвходовых сумматоров по модулю два, к первым входам i-x трехвходовых сумматоров по модулю два первой и второй групп подключены единичные выходы (m-j+i)-x и (j+

+i)-х триггеров, соответственно, вторые входы трехвходовых сумматоров по.модулю два первой группы подключены к выходам j младших триггеров, вторые входы m-j трехвходовых сумматоров по модулю два второй группы подключены к выходам m-j младших триггеров, третьи входы трехвходовых сумматоров по модулю два первой группы подключены к нулевому выходу генератора равновероятной двоичной цифры, третьи входы j трех868734

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

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

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

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

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

У 524175, кл. G 06 F 1/02, 1975.

3. Авторское свидетельство СССР по заявке В 2505976/18-24, 15 кл. G 06 F 1/02, 1978 (прототип).

868734

x(k) tWPia> 1г1ц

I00Oe

100 1

„toto„t

1000

Л t 1000 0111.

00t1 р 0010

4 0 0111

5 О 0100 а î otto

0100 00!1

0110

Itt01

1 I

1101

1 И, 0100, 1010

11000!

1010 1001

10 t

Редактор И.Михеева

Заказ 8329/70 Тираж 748

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

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

Подписное

Филиал ППП "Патент", r.Óæãîðîä, ул.Проектная,4

4 О

g 1

9 0

00 01

1001

t tOt 0100

0100 1100

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

Техред Т.Маточка Корректор М.Коста