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

 

ГЕНЕРАТОР ПСЕВДОСЛУЧАЙНЫХ ЧИСЕЛ, содержащий k Т-триггеров и n-k D-триггеров, отличающийся тем, Ч.ТО, с цешью расширения его функциональных возможност й за счет управления периодом М-последовательности , он содержит первую группу из k-1 переключателей, вторую группу из n-k-1 переключателей,два коммутатора и блок памяти, группа входов которого является группой входов генератора, первая группа выходов блока памяти подключена к группе .входов первого коммутатора соответ- . отвенно, а вторая группа выходов, блока памяти подключена к группе входов второго коммутатора соответственно , первый выход которого подключен к входу первого D-триггера, а n-k-1 остальных выходов второго коммутатора подключены соответственно к первым входам n-k-1 переключателей второй группы, второй вход каждого из которых подключен к выходу. Одноименного D-триггера, а выход каждого переключателя второй группы подключен к входу последующего D-триггера, первый выход первого коммутатора подключен к входу первого Т-триггера, а k-1 остальных выходов первого коммутатора под (Л ключены соответственнок первым входам k-1 переключателей первой с группы, второй вход каждого из когторых подключен к выходу одноименного Т-триггера, а выход каждого переключателя первой группы подключен к входу последующего Т-триггера, выход (n-k)-го D-триггера подключен к входу первого коммутатора а выход k-ro Т-триггера - к входу второго коммутатора л ts5

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

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

РЕСПУБЛИК

3(5g G 06 F 7 58

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

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

ОПИСАНИЕ ИЗОБРЕТЕНИЯ

Н ABTOPCKOMY СВИДЕТЕЛЬСТВУ (21) 3358542/18-24 (22) 08.10,81 (46) 07.04.83, Бюл. Р 13 (72) В.A. Песошин, В.Ф. Гусев, И.К. Галеев, О.И. Лапин, В.М. Кузнецов и Г.И. Кренгель (53) 681.325(088.8) (56) 1. Яковлев В.В. и Федоров P.Ô.

Стохастические вычислительные машины. Л., "Машиностроение", 1974.

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

Р 585513, кл. G 06 F 7/58, 1976.

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

9 468231, кл. G 06 F 7/58, 1973 (прототип) . (54) (57) ГЕНЕРАТОР ПСЕВДОСЛУЧАЙНЫХ

ЧИСЕЛ, содержащий k T-триггеров и

n-k D-триггеров, о т л и ч а ю— шийся тем, что, с целью расширения его функциональных возможностей за счет управления периодом M-последовательности, он содержит первую группу из k-1 переключателей, вторую группу из и-k-1 переключателей,два коммутатора и блок памяти, группа входов которого является группой входов генератора, первая группа выходов блока памяти подключена к группе

„„SU„„1010622 А.входов первого коммутатора соответ-. ственно, а вторая группа выходов. блока памяти подключена к группе. входов второго коммутатора соответственно, первый выход которого подключен к входу первого D-триггера, а n-k-1 остальных выходов второго коммутатора подключены соответст-. венно к первым входам n-k-1 переключателей второй группы, второй вход каждого из которых подключен к выходу. одноименного D-триггера, а выход каждого переключателя второй группы подключен к входу последующего D-триггера, первый выход первого коммутатора подключен к входу первого Т-триггера, à k-1 остальных

Ф выходов первого коммутатора подключены соответственно к"первым входам k- I переключателей первой группы, второй вход каждого из ко-. торых подключен к выходу одноимен- . ного Т-триггера, а выход каждого переключателя первой группы подключен к входу последующего Т-триггера, выход (n-k)-го D-триггера подключен (" к входу первого коммутатора,- а выход k-ro ..Т-триггера - к входу второго коммутатора.

1010622

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

Известен генератор псевдослучай- 5 ных чисел (генератор М-последовательности), содержащий сдвиговый регистр с сумматором по модулю два в цепи обратной связи. В этом генераторе очередное t-разрядное двоич- 10 ное число образуется на выходах разрядов регистра через каждые S тактов (S >, t) 1.13.

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

Известен также генератор псевдослучайной последовательности, содержащий генератор тактовых импульсов, регистры, сумматоры по модулю два, коммутатор, дешифратор, делитель и триггер, позволяющий формировать последовательности различных периодов (2 g.

Однако указанный генератор обладает значительной сложностью.

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

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

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

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

n-k-1 переключателей, два коммутатора и блок памяти, группа входов которого является группой входов

50 генератора, первая группа выходов блока памяти подключена к группе входов первого коммутатора соответственно, а вторая группа выходов блока памяти подключена к группе 55 входов второго -коммутатора, соответственно, первый выход которого подключен к входу первого D-триггера, а и-k-1 остальных выходов второго коммутатора подключены соответствен- б11 но к первым входам и-k- 1 переключателей второй группы, второй вход каждого из которых подключен к выходу одноименного D-триггера, а выход каждого пеРеключателя втоРой груп- 65 пы подключен к входу последующего

D-триггера, первый выход первого коммутатора подключен к входу первого Т-триггера, à k-1 остальных выходов первого коммутатора подключены соответственно к первым входам

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

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

Т-триггера — к входу .второго коммутатора.

На фиг.1 показана схема генератора псевдослучайных чисел; на фиг.2 пример технического решения коммутаторов 5 и 6; на фиг. 3 — схема генератора с одновременным обновлением разрядов за такт работы; на фиг.4-7 примеры выполнения генератора псевдослучайных чисел; на фиг. 8 — примеры соединения генераторов; на фиг. 9 — схема генератора с одновременным обновлением информации в k+m разрядах за такт работы.

Генератор псевдослучайных чисел содержит Т-триггеры 1, переключатели 2, D-триггеры 3, переключатели

4, коммутаторы 5 и б, блок 7 памяти с входами 8, входы 9 и 10 и выходы

11 и 12 расширения, а также входы

13 и 14 управления расширением.

Каждый коммутатор содержит элементы И 15, элементы ИЛИ 16, элемент

НЕ 17, входы 18-23 и выходы 24-28.

На фиг. 4-7 генераторы содержат также суммуторы 29 по модулю дна.

На фиг. 8 показаны генераторы псевдослучайных чисел 30 и 31, выходы 32-35 и входы 36-39 расширения, а также входы 40-43 управления расширением.

Переключатели 2; (4j) могут быть выполнены, например, в виде сумматоров по модулю два, при этом, если на первый вход переключателя подается сигнал "0", то осуществляется передача сигнала по второму входу на выход.

Коммутаторы 5 и б для подключения входных сигналов на один из выходов, в соответствии с сигналами, поступающими на управляющие входы, могут быть выполнены, например,как показано на фиг.2.

При отсутствии сигнала "1" на входе 13 (14) управления расширением сигнал по входу 18 переключается на один иэ выходов 24-28 по сигналам управления, поступающим на входы 19-23, причем только на одном из входов должен присутствс— вать сигнал "1", а на остальных входах — сигналы "0".

1010622

0 0 0 1 0 0 1

1 0 0 О 0 0 О

О 1 0 О 0 0 0

О 0 1. 0 О 0 О

0 О 0 1 0 0 0

0 0 0 О 1 0 О

О 0 О 0 0 1 0

1 или 3

2 или 3

31 ь

1 или 5

1,3 4 или б

4 или 5

3 или 7

2 или 9

127

511

1023

2047

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

3 или 14

3276 7

131071

262143

1048575

7 или 11

18.

3 или 17

При наличии сигнала "1" на входе 13(14) управления расширением коммутатор 5(б) переключает сигнал с входа 9(10) расширения на один из выходов 24(28),а сигнал с входа

18 — на выход 11(12) расширения. 5 Блок 7 памяти служит для хранения информации, управляющей коммутаторами 5 и б. Сигналы, появляющиеся на первой группе выходов блока 7, управляют первым коммутатором 10

5, а сигналы второй группы выходов— вторым коммутатором 6.

Блок 7 памяти совместно с коммутаторами 5 и б подключает выход E-го

D- òðèããåðà Зр к входу одного иэ

Т-триггеров (к входу 1-го Т-триггера 1„ непосредственно, а к входам

2-го,...,k-го Т-триггера 1 через переключатель 2 ), а выход k-ro

Т-триггера 1 — к входу одного из

D-триггеров 3 . (к входу 1-го D-триг«20 гера 3„ непосредственно, а к входам

2-го,..., Й-го (E=n-k) -триггера 3. через переключатель 4).

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

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

7 памяти, на выходах которого появляются сигналы, управляющие коммутаторами 5 и б, например, которые так- 30 же подключают выход 2-го Р-триггера

Зр к входу первого D-триггера 3..

На первые входы всех переключате. лей 2- (4 ) подаются сигналы "О", что заставляет их работать в режиме 35 повторителей сигналов по вторым входам.

Эквивалентная схема генератора (при данных управляющих сигналах) представлена на фиг.. 3.

Данная схема реализует генератор псевдослучайных чисел с одновременным обновлением Й разрядов Яа такт работы.

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

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

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

Матрица A описывающая работу генератора псевдослучайных чисел (1), выглядит следующим .образом..,Построим 7-разрядный генератор с одйовременным обновлением 4 разрядов за такт работы (3) .

1010622

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

2 или 19

1 или 21

5,9,14 или 18

3,7,18 или 22

3,9,13,19 или 25

2097151

4194303

8388607

33554431

268435455

23

28

1 О О 1 О О О

О 1 О О 1 О О

О О 1 О О 1 О

О О О 1 О О 1

1 О О О О О О

О 0 0 0 О 1

11+х О 00 О О С = A (2) 20

О 1 О О О О О

О О 1 О О О О (4) О О О О 1 х О

00 0001х х О 0 О 0

1 1+x О О О

0 1

О О

9(x) 50

О О О О О О 1

1 1 О О О О О

О 1 1 О О О О

О О 1 О О О О

О О. О 1 1 О О (3) Ч(х) =

0 О О О 1 О 0

О О О О О 1 1

По матрице С построим схему генератора (фиг. 4), используя D-триггеры и сумматоры по модулю два.

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

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

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

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

М-последовательность и наоборот,каждой N-последовательности соответствует свой характеристический многочлен (4) .

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

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

Матрице С соответствует характеристический многочлен Ч(х), который вычисляется через определитель (1) 011+х0000 ф(х)=С+хЕ=О О 1 х 0 0 О

О О О 1 1+x 0 О

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

40 строк, результат запишем в 6-ую строку. Получим следующий определитель

О 1 1+хОО 0 0

О О 1 х О 0 0 (5)

О О О 11+хО О

0 0 О О 1 1+х О

О О О О О 1 х

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

55 .5-й и б-й строками, получим х О 0 0 О р 1

1 1+х 0 О О О 0

О 1 1+х 0 0 0 О

О О 1 1+х 0 О 0

О О О 1 l+x О 0

О О О О 1 х 0

О О О 0 О 1 х

1010б 22

0 0 0 0 0 0 1

1 1 0 0

0 1 1 0

0 0 1

0 0 0

0 0 0

0 0 0 0

В=

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

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

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

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

Схему на фиг. 7, используя Т- и

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

Т-триггером).

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

Более того, используя вышеукаэан- З5 . ные операции над определителями, можно символы "1", присутствующие на главной диагонали определителя, перераспределять в любые места на главной диагонали, не .изменяя их коли- 40 чества, следовательно, получать .генераторы .псевдослучайных чисел с любым (удобным для разработчика) расположением Т- и D-триггеров, не изменяя их количества (схема на 45 фиг. 3 является одним из возможных вариантов применения предлагаемого изобретения).

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

1. Выбирается длина и регистра генератора (n=k+2).

2 ° По и выбирается (из таблицы) число k одновременно обновляемых ,разрядов, соблюдая при этом условие взаимной простоты 2 -1 и k иначе

1 генератор не будет формировать М-последовательность. 60

3. Берется k Т- триггеров и

Й D-триггеров (n-k= Я), соединяются последовательно друг эа другом, причем выход последнего триггера соединяется с входом первого триг- S5 гера. Вообще говоря, расположение триггеров с установочными входами и триггеров со счетными входами выбирается произвольно.

Однако для предлагаемого изобретения необходимо все Т-триггеры соединить последовательно друг за другом и все D-триггеры также соединить последовательно друг за другом, а выход последнего Т-триггера соединить с входом первого Т-триггера (фиг. 3).

На управляющие входы 8 подается код, по которому Т-.триггеры в количестве k-i+1, начиная с номера соединяются последовательно друг за другом и D-триггеры в количестве

2-j+1 начиная с номера j также соединяются последовательно друг эа другом, причем k-ill и 2-j +k-i+2 соответствуют таблице (f - j+k-i+Z=n) (Я-)+1с-i+2} а 7-i+1 иЯ -1 взаимнопростые числа. Образуется генератор псевдослучайных чисел с периодом смены состояний Т, необходимым пользователю и соответствующим управляющему .коду, поданному на входы 8 (И+" " )

T = 2 . -1, Для нормальной работы генератора необходимо, чтобы первые i-1 Т-триггеры и первые j-1 D-триггеры предварительно были установлены в нулевое состояние.

Можно соединить два подобных генератора (см. фиг. 8) между собой и пблучить один генератор псевдослучайных чисел, соединив расширяющие выходы 32 и 33 первого к расширяющимся входам 36 и 37 второго и расширяющиевыходы втооого 34 и 34 к расширяющим входам первого. При этом на входы 40-43 управления расширением нацо подать сигнал "1". Эквивалентная схема, образующаяся при этом, показана на фиг. 9.

В этом генераторе количество

Т-триггеров k+m и общее количество триггеров k+m+1+r должны соответствовать таблице и обязательно выполнение условия взаимной простоты

{k+m+0+r )

k+m и2 -+ В этом случае генератор формирует M-последовательность с периодом . (1 +т+Вн )

T = 2 1 °

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

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

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

1010622

1010622

xozoera

49ug. д .

Фиг. ба. 7

1010622

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

Редактор М.Рачкулинец Техред O,Íåöå Корректор F.. Рошко

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

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

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

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