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

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

Иллюстрации

Показать все

Реферат

 

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

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

РЕСПУБЛИН

3(59 Н 03 К 3 84

ОПИСАНИЕ ИЗОБРЕТЕНИЯ и АВТОРСИОМЪ СВИДЕТЕЛЬСТВУ

ГОСУДАРСТЕЕННЦЙ НОМИТЕТ СССР

ПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТНРЦТИЙ (2i ) 3537239/18-21 (22) 06.01.83 (46) 15.08.84. Бюл. Ф 30 (72) Г. Г. Баранов, В.М. Захаров, Ю.С. Комаров, Е.Л. Столов и P.Õ. Латыпов (71) Казанский ордена Ленина и ордена Трудового Красного Знамени государственный университет им. В.И. Ульянова-Ленина (53) 621.374.2(088.8) (56) 1. Авторское свидетельство СССР

У 748394, кл. С 06 F 1/02, 1980.

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

У 943722, кл. G 06 F 7/58, 1982. (54)(57) ГЕНЕРАТОР ПСЕВДОСЛУЧАЙНЫХ

ЧИСЕЛ, содержащий генератор М -последовательности, первый вход которого соединен с первым выходом блока управления и первым входом блока задания длины последовательности, первый выход которого сое-. динен с вторым входом генератора

lA-последовательности, а второй выход — с первым входом блока злемен„,Я0„„1108614 А тов И, второй вход которого соединен с выходом дешифратора, вход которого соединен с выходом блока сравнения, первый вход которorо соединен с блоком задания вектора стационарного распределения, выход генератора тактовых импульсов соединен с вторым входом блока задания длины последовательности, о тл и ч а ю шийся тем, что, с целью расширения функциональных воэможностей путем увеличения ко" личества формируемых последователь ностей, в него дополнительно введены блок умножения и блок задания ма рицы преобразования, выход которо- g

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

1 11

Изобретение относится к импульсной технике.

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

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

Наиболее близким IIo техническому решению к предлагаемому является генератор псевдослучайных чисел, содержащий генератор 9 -последовательности, выход которого соединен с первым входом блока сравнения, выход которого соединен с входом дешифратора, выход котороro соединен с первыми входами элементов И группы, выходы которых образуют первый выход генератора, блок задания длины последовательности и блок задания распределения и матрицы переходов, первый выход которого соединен с вторым входом блока сравнения, второй выход блока задания распределения и матрицы переходов соединен с управляющим входом дешифратора, первый и вто.рой входы блока задания распределения и матрицы переходов являются соответственно первым и вторым входами генератора, третий вход блока задания распределения и матрицы переходов является третьим входом генератора и соединен с первым входом генератора M -последовательности и первым входом блока зада. ния длины последовательности, первый выход которого соединен с вто— рым входом генератора И-последовательности, второй выход блока задания длины последовательности соединен с вторыми входами элементов

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

Такой генератор позволяет ¹pмировать последовательности чисел, описываемые разньп.и матрицами пе086 1 > . 1 реходных Вероятностей и Одним и тем же заданным вектором стационарного

1п

11

20 ,Ф ()

35 аЯ

Л сб распределения.

Недостатком известного генератора. является малое количество формируемых последовательностей.чи11 сел, которое не превышает 2 где n — число двоичных разрядов генератора И-последовательности, что сужает область его применения.

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

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

К-последовательности, первый вход которого соединен с первым выходом блока управления и первым входом блока задания длины последовательности, первый выход которого соединен с вторым входом генератора

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

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

Генератор псевдослучайных чисел содержит генератор 1 М-последовательности, первый вход которого соединен с первым выходом блока 2 управления и первым входом блока 3 задания длины последовательности, первый выход которого соединен с вторым входом генератора 1 И-последовательности, а второй выход — с первым вхоцом блока А элементов И, второй

1108614 вх „которого соединен с выходом дешифратора 5, вход которого соединен с выходом блока 6 сравнения, первый вход которого соединен с блоком

7 задания вектора стационарного распределения, выход генератора 8 тактовых импульсов соединен с вторым входом блока 3 задания длины последовательности, блок 9 умножения, блок 10 задания матрицы-преобразования, выход которого соединен с первым входом блока 9 умножения, второй вход которого соединен с выходом генератора 1 И-последовательг ности, причем выход блока 9 умножения соединен с вторым входом блока 6 сравнения, а второй выход блока 2 управления соединен с третьим входом блока 3 задания длины последовательности. Позициями 11 — 17 обозначены шины, соединяющие блоки устройства.

Блок 9 умножения выполнен на элементах И, ИСКЛЮЧАЮЩЕЕ ИЛИ и осуществляет умножение матрицы преобразования на случайный вектор..

Дешифратор 5 выполнен на элементах ИСКЛЮЧАЮЩЕЕ ИЛИ.

Блок 2 управления содержит кнопочный набор и RS-триггер, управляемый кнопками "Пуск" и "Сброс".

Блок 7 задания вектора стационар. ного распределения содержит кнопочные наборы по числу компонент вектора стационарного распределения.

Блок 1О задания матрицы преобразования содержит набор кнопок, каждая иэ которых определяет один элемент матрицы преобразования.

Принцип действия устройства заключается в следующем, Генератор 1 M-последовательносП ти имеет 2 -1 состояний, где п — . число триггеров в регистре гене-, ратора 1. Эти состояния эакодируем числами от 1 до 2 — 1 и будем использовать все множество чисел .

В двоичной системе счисления числа х, формируемые генератором 1

M-последовательности, представляют собой векторы размера n: (х1 у хну ° ° ° y х у ° е ° у х ),ф

1 ф1 где х. — значение i-ro двоичного разряда числа х.

Блок 9 умножения матрицы преобразования на случайный вектор осуществлет преобразование случайного вектора х в вектор q

= Вх, В = (bij), i, j = 1, п (1),.

5 где  — матрица преобразования, элементы которой b1j могут принимать значения 0 или

Для того, чтобы преобразование (1) было взаимно однозначным, ранг мат1О рицы В должен равняться п. При этом каждому числу х преобразование (1) ставит в соответствие некоторое число q. Числа q как и числа х, могут принимать значения от 1

15 до 2 — 1.

Разобьем множество чисел q íà k непустых непересекающихся подмножеств 1а;). Если состоянию х генератора 1 отвечает число q е (Q;), будем считать, что устройство в этот момент времени находится в состоянии С; . Обозначим через С„(t) событие, означающее, что в момент

t устройство находится в состоянии

С„., а символ р"(с)- относительную частоту наблюдения события С за время прохождения генератором 1 все. и

ro множества 2 -1 состояний, Тогда

ЗО р с.Фс.(t+111 т .

Р, =1 (с. (t. (1с щ1- „ =-11-, (z1 где Р, — относительная частота пе%

1) рехода устройства из состояния С, в состояние С:, m . — число переходов из состоя1j ния С; в состояние С ,щ; m; — число наступлений события

С, (число элементов подмножества (81.

Матрица переходов P = (P1 ), элементы которой вычислены йо формуле (2), является стохастической и неразложимой. Стационарное распре деление, отвечающее этой матрице, имеет компоненты m; /(2"- 1), i = 1 2, ... k

Вектор стационарного распределения задают с пОМОщью чисел Г„, Г

Г, определяющих нижние грайиk цы подмножеств (Q f . Эти числа с блока 7 задания вектора стационар ного распределения поступают в блок 6 сравнения, который в сочетании с дешифратором 5 осуществляет разбиение множества чисел q íà k подмножеств %Q;) и определяет, для какого значения 1 вь?полE?яетс>? ус.чо вие q 6 I O„j. Появленi!B е>???ци iiiopo

Сигнала иа i-м выходе де?ши1>ратopB

5 означает выполнение условия

q г. I О„) и переход устройства в состояние С1 ° Полу BHE?6EEE пр Оцес с Iiме ет стационарный вектор с компонентами е4 !

»)

2 -1+? - r, к

2 г-? ? -?

2 3 !

2-1 2 -1

При этом

>Ф1 . i. 9

1,„?

1 и? =- 2 К вЂ” 1 гь г -- Г k 1 г1 (r 1+1

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

Следовательно, изменяя матрицу Б можно получать на выходе устройства отличные друг î- друга поспедовательиости сигналов, имеющие один и тОт же зада?!ный ВОКТор стациОнар ного распределения. Известно,. чго количество Отли E?6?x дру Ov друга иевырожденных матриц В равно

N 11»

1 >» ч) (/

N, = 2 — 2, 1 = 1, 2,, ? поэтому, задавая разные матрицы Б, можно получить N последовательнос:тей чисел q. Некоторые из получен-ных таким образом иоследовательностей отличаются друг от Ifpyra только циклическим сдвигом. Соответствующие им последовательности сигналов на выходе устройства также отличаются только циклическим сдвигом.

При использовании таких последовательностей может оказаться, что они не дают новой информации, В этих случаях они должны быть исключены. Пля того, чтобы различия между последовательностями чисел не сводились только к циклическому сдвигу, достаточно зафиксировать один из элементов этих последовательиОстеи Пустьр например) тЯК? м элементом будет число q, отвечающее значению х = 100 ...О.„

«q = В (1, О., О, ..., О) .

Очевидно, что значение q в этом случае Определяется только первым ст?>лбцом матрицы В. Следовательно, если при измепении матрицы В первый -толбец будет оставаться иеизиенны??, то выбранному значению

5 х х= i00 ... 0 всегда будет отвечать Одно и То же число q, Таки? Образом, для получения последовательностей чисел ?1, различия

??ежду ?.-Оторьгми не сводятся только

10 к циклическим сдвигам, достаточно грн изменении матрицы В зафиксиропять Один из ее столбцов. Число таких г?оследс>вятельиостей равно

N/(2 ь — 1) . Соответствующие им

15 НОсл? /I oBQTP flüíÎÑT- ? Вь?кодных сигнЯ лов представляют собой псевдослучайный процесс с заданным вектором стационарного распределения и некот Ор о-! матр ице и переходов Р, злеме н2п ты ко-орой могут быть вычислены по формуле (2) .

Устройство работает следующим образом.

Матрицу В задают с помощью бло2> ка 10 задания матрицы преобразования, который содержит г? кнопок, служащих цля задания элементов матрицы В. Вектор стационарного распределения задают с помощью и-разряднь|х двоьчнь?х чисел г р для ввода которых служит блок 7 задания вектора стационарного распределения.

С помощью блока 2 управления по шине 14 задают число тактов сдвига генератора 1 М-последовательнос355 ти, а по шине 13- сигнал установки исходного состояния. Начало работы определяется моментом снятия сигнала установки исходного состояния.

При этом на синхровход генератора

1 М-последовательности по шине ll6 начинают поступать тактовые импульсы, Генератор 1 формирует и-разрядные псевдослучайные двоичные числа, которые поступают по шине 11 в блок 9 умножения матрицы преобразования на случайный вектор, где осуществляетсч преобразование (1), Умножение матриць? В на случайный вектор, формируемый генератором 1, 50 осуществляется с помощью узлов умножения строки матрицы преобразования ня случайный вектор, число которьгх равно и. Злементы матрицы

В поступают по шине 12, причем ня .>ь 1-й.узел поступают элементы х-й строки ?яатриць? В, Я иа вьгходе 1-I-o узла формируется 1-я компоненты вектора и q „= Ь, „х,(+) Ь; х (3? ... Q+ b „x, х., j = 1,п О, при q) r, 1, при q †.,логический уровень на выходе i-ой схемы сравнения.

Номер подмножества tQ;%, в которое попало число q, определяется с помощью дешифратора 5. Логическая р функция i-ro выхода дешифратора 5 описываеТся выражением е уО+ у1,, i 1, 2, ° ° ° k f г, у„ где yf — логический уровейь на выЗО ходе i-й схемы сравнения блока 6.

Появление единичного уровня на.

1- -и выходе дешифратора 5 означает, что число q попало в подмножество

Q) . Выходные сигналы дешифратора

5 стробируются с помощью блока 4 элементов И, который содержит k

7 110 где Ь;., j = 1, п — элементы i-й строки матрицы В, компоненты случайного вектора, формируемого генератором 1;

Q+) — символ суммир ования по модулю 2.

Полученные в результате преобразования (1) случайные числа q 1 поступают в блок 6 сравнения, где сравниваются со значениями интервалов разбиения множества чисел q.

Блок 6 содержит k схем сравнения, причем для i-й схемы сравнения имеет место следующее соотношение

8614 8 элементов И. Стробирующий сигнал, поступающий по шине 17, появляется при условии выполнения заданного числа сдвигов в генераторе 1 и окончания переходных процессов в генераторе 1, блоках 9 и 6 и дешифраторе 5.; Матрица переходных вероятностей и вектор стационарного распределения псевдослучайного процесса, полученного на выходах блока 4, описываются выражениями (2) и (3) соответственно, если количество чисел в сформированной псевдослучайной последовательности и количество использованных для этой цели состояний генератора 1 М-последовательности равны 2 — 1. Выполне»

0 ние этого условия обеспечивает блок

3 задания длины последовательности, сигнал установки исходного состояния которого поступает по шине 13 с блока 2 управления. После снятия этого сигнала на шине 16 появляется заданное число тактовых импульсов, которые осуществляют сдвиг содержимого в регистре генератора 1 M-последовательности, после чего появляется на шине 17 сигнал и открывает элементы И блока 4. После поступлен ния по шине 17 2 — 1 сигналов рабо. та устройства прекращается.

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

М/(2 — 1) раз больше последова2 тельностей, где N вычисляется по формуле {4).

1 108614

Составитель Ю. Бурмистров

Техред Т. Фанта Корректор В. Бутяга

Редактор Л. Веселовская

Заказ 5884/43 Тираж 862

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

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

Подписное

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