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

 

СОЮЗ СОВЕТСКИХ

СОЦИАЛИСТИЧЕСКИХ

РЕСПУБЛИК (51)4 G 06 F 7/58

ГОСУДАРСТВЕННЫЙ КОМИТЕТ СССР

ПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТНРЫТИЙ

ОПИСАНИЕ ИЗОБРЕТЕНИЯ /И., Н ASTQPCHOMV СВИДЕТЕЛЬСВ ТВУ

1 (54)(57) ГЕНЕРАТОР ПСЕВДОСЛУЧАЙНЫХ

ЧИСЕЛ, содержащий группу из n (n— число разрядов генератора) D-триггеров, группу из п элементов И, группу

Из и сумматоров по модулю два, групЮ Ф

I 6у- 62 (2i) 3409302/18-24 (22) 23.03.82 (46) 30.12.86. Бюл. Р 48 (72) В.A. Песошин, В.Ф. Гусев, И.К. Галеев, О.И. Далин, Г.И. Кренгель и И.M. Якимов (53) 681.325(088.8) (56) 1. Яковлев В.В., Федоров Р.Ф.

Стохастические вычислительные машины.

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

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

11 468231, кл. G 06 F 7/58, 1973.

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

Ф 752769, кл. Н 03 К 3/84, 1977.,.SU 1280639 А 1 пу из и элементов задержки и блок памяти, отличающийся тем, что, с целью упрощения генератора, выход i-го (i=1,п) D-триггера соединен с входом i-ro элемента задержки, выход которого является выходом i-ro разряда генератора и соединен с первыми входами-i-.ãî элемента И и (i+i)-го сумматора по модулю два, входы блока памяти образуют группу управляющих входов генератора, а выходы блока памяти соединены с вторыми входами соответствующих элементов И группы, выходы которых соединены с вторыми входами соответствующих сумматоров по модулю два группы, выходы которых соединены с входами соответствующих

D-триггеров группы, выход n-ro элемента задержки соединен с первым входом первого сумматора по модулю два. Ю(1280619

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

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

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

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

Наиболее близким к предлагаемому является генератор псевдослучайных чисел, содержащий D-триггеры, элементы задержки, сумматоры по модулю два, запоминающее устройство (состоящее из блока управления), элементы И и блок элементов согласования (3 g.

Известный генератор обладает возможностью регулирования периода

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

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

Для достижения поставленной цели в генераторе псевдослучайных чисел, содержащем группу из и (и — число

Разрядов генеРатоРа) D-тРиггеРов, 55 группу из и элементов И, группу из и сумматоров по модулю два, группу из п элементов задержки и блок памя ти, выход i-го (i=1,n) D-триггера соединен с входом х-го элемента задержки, выход которого является выходом i-ro разряда генератора и соединен с первыми входами i-го элемента И и (i+1)-ão сумматора по модулю два,,входы блока памяти образуют группу управляющих входов генератора, а выходы блока памяти соединены с вторыми входами соответствующих элементов И группы, выходы которых соединены с вторыми входами соответствующих сумматоров по модулю два группы, выходы которых соединены с входами соответствующих D-триггеров группы, выход и-го элемента задержки соединен с первым входом первого сумматора по модулю два.

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

Генератор псевдослучайных чисел содержит п Р-триггеров 1„.,п элементов И

2„,п сумматоров 3, по модулю два,п элементов 4„ задержки; блок 5 памяти, выходы генератора б;, вход 7 обратной связи, вход 8 управления, Т-триггер 9,, сумматор 10 по модулю два, 7-разрядную ячейку 11 генератора и Z-разрядную ячейку 12 генератора.

D-триггер 2„, элемент И 2 суммаУ тор З„по модулю два и элемент 4 заJ держки в совокупности представляют собой управляемый триггер, который при подаче на первый вход элемента

И 2„ сигнала "1" с выхода блока 5 памяти работает в режиме Т-триггера, а при подаче "0" — в режиме D-триггера.

Элемент 4 „ задержки служит для задержки сигнала с выхода D-триггера 1„. на время, необходимое для записи в него новой информации (при конкретной технической реализации

D-триггера 1 может отпасть необхоJ димость в задержке сигнала элементом 4„ задержки).

Блок 5 памяти служит для хранения информации, управляющей элементами

И 2„.

Генератор работает следующим об-. разом.

На входы 8 подаются сигналы, опрашивающие блок 5 памяти, например на первые входы первых k элементов

И 2 подаются сигналы "1", а на первые входы остальных элементов И 2

11

J сигналы 0 . При этом образуется k

1280619

0 0 0 О 1 О О

0 О О О О О О

C=A * (2) По матрице С построим схему re25 нератора (фиг. 3), используя D-триггеры и сумматоры по модулю два.

Схему на фиг. 3 можно изобразить в другом виде (фиг. 4).

Схема на фиг. 4 с переупорядоченной нумерацией изображена на фиг.5. е

Так как 2 -1 и k взаимно простые числа (п=7, k=4), то генератор псевдослучайных чисел, изображенный на фиг. 3, формирует М-последователь35 ность (2).

1 .0 0 1 О О 1

1 О О О 0 О О

0 1 О О О О О

О 0 1 О 0 О О

0 0 О 1 О О 0

Т=2 -1

1 или 3

2 или 3

31

1 или 5

1,3,4 или 6

4или5

127

511

1023

2047

32767

131071

3 или 14

Т-триггеров и (n-k) D-триггеров. Эквивалентная схема генератора (при данных управляющих сигналах) представлена на фиг. 2. Данная схема реаI лизует генератор псевдослучайных чисел с одновременным обновлением информации в k разрядах за такт рабо:ы.

Предварительно в генератор заносится начальное состояние (цепи синхронизации и установки в начальное 10 состояние на фиг. 1-7 не показаны).

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

h состояний T=2 -1, т.е. генератор фор- 15 мирует последовательность максимальной длины (М-лоследовательность).

Доказательство этого утверждения разберем на примере работы 7-разрядного (п=7) генератора псевдослучай- 20 ных чисел. Из таблицы выберем k=4.

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

10 Зили7

11 2 или 9

15 1,4,7 8,11 или 14

Построим 7-разрядный генератор псевдослучайных чисел с одновременным обновлением 4 разрядов за такт работы

1 О 0 1 О О 0

О 1 О 0 1 О О

О О 1 0 О 1 О

0 О О 1 О О 1

1 О О О 0 О О

О 1 0 О О 0 О

0 О 1 0 0 0 0

1280619

Продолжение таблицы з

7 или 11

3 или 17

2 или 19

21

3 или 28

13 или 30

33

Ч(х) =

=/С +хЕ/= (4) 0 0 0 0 0 0 1

1 1 0 0 0 0 0

0 1 1 0 0 0 0

0 0 1 0 0 0 0 (3) 0 0 0 1 1 0 0

0 0 0 0 1 0 0

0 0 0 0 0 1. 1

22 1 или 21

23 5,9,14 или 18

25 3,7,18 или 22

28 3,9,13,19 или 25

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

Схемы, изображенные на фиг. 3 и 5, идентичны: формируют одну и ту же М-последовательность, следова40 тельно, они описываются одним и тем же характеристическим многочленом, неприводимым и примитивным.

Функционирование схемы, изображенной на фиг. 5, описывается матрицей С .

262143

2097151

4194303

8388607

33554431

2147483647

8589934591

Матрице С соответствует характеристический многочлен V (x), который вычисляется через определитель (1). х 0 0 0 0 0 1

1 1+х0 0 0 0 0

011+х00 0 0

0 0 1 х 0 0 0

0 0 0 11+х0 0

0 0 0 0 1 х 0

0 0 0 0 0 1 1+х

Используем один из методов преобразования определителей, заключающийся в следующем: определитель не меняется, если к элементам одной из его строк (столбца) прибавить соответствующие элементы другой строки (столбца). Преобразуем определитель (4).

Сложим содержимое 6-го и 7-ro столбцов (используя операцию суммирования по модулю два) и результат запишем в 7-й столбец, затем сложим содержимое 6-й и 7-й строк, результат запишем в 6-ю строку. Получим следующий определитель:

12В061а x О О 0 0 0 1

1 1+х 0 О О О О

О 1!+хО О О О

О О 1 х О О О

О О 0 1 1+х О 0

О О 0 О 1 1+х 0

"0 О О О О 1 х

Ч(х)f0 х О 0 О О О 1

1 t+x 0 0 0 0 0

О t 1+х 0 О О О

О О 1 1+х 0 О О

О О О 1 1+х О О

О О О О 1 х О

О О О О О 1 х ф(х) = (6) Видно, что символ 1, расположенный на главной диагонали на пересечении 7-й строки и 7-го столбца, переместился на место пересечения

4-й строки и 4-го столбца.

Определителю (6) соответствует матрица В, описывающая функционирование генератора псевдослучайных чисел:

40

О О О О О О

1 1 О О О О О

О 1 1 О О О О

О О 1 1 О О, О

О О 0 1 1 О О

9 0 О О 1 О О

О О О О О 1 О

45 (7) 50

Матрице В соответствует схема на фиг. 6.

Применяя те же операции над 4-м и 5-м столбцами и 4-й и 5-й строками,, а затем над 5-м и 6-м столбцами и

5-й и 6-й строками, получим:

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

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

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

Т-триггеров и D-триггеров, не изменяя их количества.

Можно предложить следующую последовательность расчета генераторов псевдослучайных чисел с одновременным обновлением информации в нескольких разрядах за такт: выбирают и длину регистра генератора псевдослучайных чисел; но п выбирают (например, из таблицы) k — число одновременно обновляемых разрядов, соблюдая при этом условие взаимной простоты 2"-1 и k иначе генератор не будет формировать М-последовательность; берут k T-триггеров и (и-k)

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

Подавая соответствующие сигналы из блока 5 памяти на входы элементов

И 2„, можно при одном и том же п, но при разных k получать различные

М-последовательности.

Устройство, представленное на фиг. 1, является ячейкой однородной среды (универсальной ячейкой) генератора псевдослучайных чисел. Можно соединить несколько таких устройств (например, два, фиг. 7) друг с другом, подключая выход 6„ предыдущего устройства к входу 7 обратной

1280619

10 связи последующего устройства, и получить генератор псевдослучайных чисел большой разрядности. При этом общее количество триггеров n=l+z и количество Т-триггеров k=t+s должно соответствовать таблице, а также должно соблюдаться условие взаимной простоты 2 -1 и k.

Если отсутствует необходимость 10 получения различных М-последовательностей (при одном и том же n) блок 5 памяти будет работать в режиме постоянного опроса (на первые входы элементов И 2 подаются постоянные сиг- 15

J налы "0" или "1") . При этом блок 5 памяти и элементы И 2 „ вырождаются в набор перемычек, соединяющих выходы

D-триггеров 1„ с входами сумматоров

З по модулю два, а все устройство 20 представляет собой набор Т-триггеров и D-триггеров (фиг. 2) .

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

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

i2806)9

1280619

Ри2. 7

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

Редактор А. Лежнина Техред,Л.Олейник Корректор М. Максимишинец

Заказ 7067/54 Тираж 671 Подписное

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

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

Производственно-полиграфическое предприятие, r, Ужгород, ул. Проектная, 4