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

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

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

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

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

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

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

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

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

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

Генератор псевдослучайных чисел содержит генератор 1 М-последователкости, первый вход которого соединен с первым выходом блока 2 управления и первым входом блока 3 задания ДJПIHЫ последовательности, первый выход которого соединен с вторы входом генератора 1 М-последовательности, а второй вьпюд - с первым входом блока 4 эхшментов К, второй

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

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

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

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

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

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

Принцип действия устройства заключается в следующем.

Генератор 1 М-последовательности имеет 2 -1 состояний, где п - . число триггеров в регистре гене-, ратора 1. Эти состояния закодируем числами от 1 до 1 и будем использовать все множество чисел.

В двоичной системе счисления числа к, формируемые генератором 1 М-последовательности, представляют собой векторы размера п:

X - Х, Xj, , i f)

где X j - значение i-го двоичного

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

q вх,

в (bij), i, j 1, п (1) где В - матрица преобразования,

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

Разобьем множество чисел q на k непустых непересекающихся подмножеств (а;. Если состоянию х генератора 1 отвечает число q е { Gl-,|, будем считать, что устройство в этот момент времени находится в состоянии С . Обозначим через Cj(t) событие, означающее, что в момент t устройство находится в состоянии С, а символ р(с)- относительную частоту наблюдения события С за время прохождения генератором 1 всего множества 2-1 состояний. Тогда

г /1 .(tlC.( №..

. а+1)/с. (t)l --V--W- (Zl j I i 1 J .(t)

где P. - относительная частота перехода устройства из состояния С. в состояние С- , ш. - число переходов из состояния С в состояние Cj, m - число наступлений события C.J (число элементов подмножества 4.Q, Матрица переходов Р (Р : ) , элементы которой вычислены по формуле (2), является стохастической и неразложимой. Стационарное распре деление, отвечающее этой матрице, имеет компоненты т-, /( 1),

Ij 9 К.

Вектор стационарного распределения задают с помощью чисел г.,, г, ..., г, определяющих нижние границы подмножеств {Q . Эти числа с блока 7 задания вектора стационарного распределения поступают в блок 6 сравнения, который в сочетании с дешифратором 5 осуществляет азбиение множества чисел q на k одмножеств определяет, для

какого значения i SbinojnrHeTCH условие qe ( Появление единичного сигнала на выходе дешифратора 5 означает выполнение условия переход устройства в состояние Cj . Полученный процесс i-ii-ieет стацт-юнариый вектор с компонентами;

. I- . н f - г.

У

-4 3

При этом

i 1, 2,

Г:

1

2 + г - г t i r. 1

1 +-(

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

N

M

N N

h

(4)

2,

ПОЭТОМУ; задавая разные матрицы В можно получить N последовательностей чисел q. Некоторые из полученньк таким образом последовательностей отличаются друг от друга только циклическим сдвигом, Соответствзлощие им последовательности сигналов на выходе устройства таюке отличатотся только циклическим сдвигом, При использовании таких последовательностей может ока.заться что они не дают новой информации, В этих случаях они должны быть исключены. Для того 5 чтобы разл1гчия между пocлeдoвaтeльнocтя и чисел q не сводились только к циклическому сдвигуS достаточно зафиксировать один из элементов этих последовательностей. ПустьS например, таким элементом будет число q, отвечающее значению х 100 ,,,05

0)

q Б (Is Oj 0;

Очевидно, что значение q в этом случае определяется только первьм

столбцом матрицы В, Следовательно, если при изменении матрицы В первый столбец будет оставаться неизMeiiHHM, то выбранному значению X 100 ...о О всегда будет отвечать одно и то же число q.

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

к циклическим сдвигам достаточно при изменении матрицы В зафиксировать один из ее столбцов. Число такизс последовательностей равно N/(2 1). Соответствующие им последовательности выходных сигналов представляют собой псевдослучайный процесс с задан 1ым вектором стационарного распределения и некоторой матрицей переходов Р, элементы которой могут быть вычислены по формуле (2).

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

Матрицу В задают с помощью блока 10 задания матрицы преобразования, который содержит кнопок, служагцих для задания элементов матрицы В. Вектор стационарного распределения задают с помощью п-разрядных двои1 ных 4Hcejr г j ддя ввода которых слу7(ит блок 7 задания вектора стационарного распределения. С помощью блока 2 управления по un-iFie 14 задают число тактов сдвига генератора 1 М последовательности, а по шине 13- сигнал установки исходного состояния. Начало работы определяется моментом снятия сигна ла установки исходного состояния, При этом на синхровход генератора 1 М-последовательности по шине 16 начинают поступать тактовые импульсы Генератор 1 формирует п-разрядные псевдослу айные дво-гчные числа J которые поступают по шине 11 в блок 9 умножения матрицы преобразования на случайньгй вектор, где осу1цествляется преобразование (1). Умножение матритда В на слз чайньй вектор j формируемый генератором 1, осуществляется с помощью узлов умножения строки матрицы преобразования на случайный вектор, число которых равно lu Элементы матрицы В поступают по шине 12, причем на 1--й уз ел лоступают элементы i -и строки матриць Bj а на выходе i-ro узла формируется i-я компоненты век тора q q; b Х-,© bv,Cg@ ,

©Vrt 7 n - элементы i-й ст bij . j ки матрицы В; 1,п - компоненты случайного вектора формируемого ге ратором 1; 0 - символ суммирования по модулю Полученные в результате, преобразования (1) случайные числа q поступают в блок 6 сравнения, где сравниваются со значениями интерва лов разбиения множества чисел q. Блок 6 содержит k схем сравнения, причем для i-й схемы сравнения име ет место следующее соотношение Го, при qy, г. , при q г, , где YJ - .логический уровень на вых де i-ой схемы сравнения. Номер подмножества Gt-Л, в которое попало число q, определяется с помощью дешифратора 5. Логическая функция i-ro выхода дешифратора 5 описывается вьфажением У . , v° У, - логический уровейь на вы где у ходе i-й схемы сравнения блока 6. Появление единичного уровня на iH выходе дешифратора 5 означает, что число q попало в подмножество (Q . Выходные сигналы дешифратора 5 стробируются с помощью блока 4 элементов И, который содержит k 14 8 элементов И. Стробирующий сигнал, поступаюпщй по щине 17, появляется при условии выполнения заданного числа сдвигов в генераторе 1 и окончания переходных процессов в генераторе 1, блоках 9 и 6 и дешифраторе 5% Матрица переходных вероятностей и вектор стационарного распределения псевдослучайного процесса, полученного на выходах блока 4, опи сываются выражениями (2) и (3) соответственно, если количество чисел в сформированной псевдослучайной последовательности и количество использованных для этой цели состояний генератора 1 М-после- . довательности равны 2 - 1. Вьшолнение этого условия обеспечивает блок 3 задания длины последовательности, сигнал установки исходного состояния которого поступает по шине 13 с блока 2 управления. После снятия этого сигнала на шине 16 появляется заданное число тактовых импульсов, которые осуществляют сдвиг содержимого в регистре генератора 1 М-последовательности, после чего появляется на шине 17 сигнал и открывает элементы И блока 4. После поступления по шине 17 2 - 1 сигналов работа устройства прекращается. Таким образом, введение в генератор псевдослучайных чисел бпока умножения и блока задания матрицы преобразования позволяет получить в N/(2 - 1) раз больше последовательностей, где N вычисляется по формуле (4).

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