Генератор псевдослучайных чисел Советский патент 1986 года по МПК G06F7/58 

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

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

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

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

f5

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

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

геры) 21 .У; азанный генератор облаца.- на фиг. 2-1- примеры выполнения геет высоким быстродействием, однако отсутствует возможность формирования различных М-последовательностей

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

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

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

Для достижения поставленной цели в -генераторе псевдослучайных чисел, содержащем группу из п (п - число разрядов генератора) D-триггеров, группу из п элементов И, группу из п сумматоров по модулю два, группу из п элементов задержки и блок памяти, выход i-ro (i 1,n) С-т.риггера

fO

f5

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

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

5

0

5

0

5

0

5

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

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

D-триггер 2j, элемент И 2, сумматор 3jпо модулю два и элемент 4 задержки в совокупности представляют собой управляемый триггер, который при подаче на первый вход элемента И 2j сигнала 1 с выхода блока 5 памяти работает в режиме Т-триггера, а при подаче О -- в режиме D-триг- гера.

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

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

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

На входы В подаются сигналы, опрашивающие блок 5 памяти, например на первые входы первых k элементов И 2J подаются сигналы 1, а на первые входы, остальных элементов И

сигналы О, При этом образуется k

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

Предварительно в генератор заносится начальное состояние (цепи синхронизации и установки в aчaльнoe состояние на фиг. 1-7 не показаны). С приходом тактового импульса гене- ратор псевдослучайных чисел переходит в следующее состояние. Период смены состояний -1, т.е. генератор формирует последовательность максимальной длины (М-доследовательность).

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

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

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

1001000 0100100 0010010 0001001 1000000 0100000 0010000

(2)

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

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

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

000-00 1 100000

11 0000 010000

001100 000100

о о о о 1. 1

(3)

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

25

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

X О О О О О 1 1 Ц-х О О О О О О 1 1+х О 00 О 00 1x000 О О О 1 1+х О О 00001x0 00000 1 1+х

Ч(х) /С +хЕ/

(4)

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

.4

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

Ч(х)

7 X О О О О О 1

1 1+х О О О О О О 1 1+х О О 00 001x000 О О О 1 1+х О О О О О О 1 1+х О

О О О О О 1 X

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

(6)

к О О О О О 1 1 1+х О О О 00 О 1 1+х О О О О 00 1 1+х о о о О О О 1 1+х О О 00001x0 О О О О О 1 X

Видно, что символ 1, расположен- ньй на главной диагонали на пересечении 7-й строки и 7-го столбца, переместился на место пересечения 4-й строки и 4-го столбца.

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

000001

100000 1 10000 01 100-0 001100 00010 о 00001 о

(7)

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

,,

20

25

280619„

о

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

два на входе можно заменить Т-триг- 0 гером).

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

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

Можно предложить следующую последовательность расчета генераторов

30 псевдослучайных чисел с одновременным обновлением информации в нескольких разрядах за такт: выбирают п - длину регистра генератора псевдослучайных чисел,- по п выбирают (на35 пример, из таблицы) k - число одновременно обновляемых разрядов, соблюдая при этом условие взаимной простоты и k, иначе генератор не будет формировать М-последователь40 ность; берут k Т-триггеров и (n-k) D-триггеров, соединяют последовательно друг за другом, причем выход последнего триггера соединяют с входом первого триггера. Взаимное располо45 жение Т-триггеров и D-триггеров можно выбирать произвольно.

Подавая соответствующие сигналь: из блока 5 памяти на входы элементов И 2j, можно при одном и том же п,

50 но при разных k получать различные М-последовательности.

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

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

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

о

набор перемычек, соединяющих выходы D-триггеров 1 ; с входами сумматоров

О

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

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

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

Зз

гаккяяюяа mtr vk с ЧИ

k

ю

Фиг.

Ц

10

ю

W

Ю

Ю

Фиг. 5

Ю

Фиг. 6

(ригЛ