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

,БО 110861 3 К 38 ИСАНИЕ ИЗОБРЕТЕНИЯор го ввФ ГОСУДАРСТНЕННЦЙ НОМИТЕТ СССРПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТНР ИЙ АВТОРСКОМУ СВИДЕТЕЛЬ(71) Казанский ордена Ленина и дена Трудового Красного Знамени сударственный университет им. В.И. Ульянова-Ленина (53) 621,374,2(088.8)(56) 1. Авторское свидетельство СССР Р 748394, кл. С 06 Р 1/02, 1980.2, Авторское свидетельство СССР У 943722, кл. С 06 Р 7/58, 1982, (54)(57) ГЕНЕРАТОР ПСЕВДОСЛУЧАЙНЫХ ЧИСЕЛ, содержащий генератор М -последовательности, первый вход которого соединен с первым выходом блока управления и первым входом блока задания длины последователь" ности, первый выход которого сое" динен с вторым входом генератора М"последовательности, а второй выход - с первым входом блока злементов И, второй вход которого соединен с выходом дешифратора, входкоторого соединен с выходом блокасравнения, первый вход которогосоединен с блоком задания векторастационарного распределения, выходгенератора тактовых импульсов соединен с вторым входом блока задания длины последовательности, о тл и ч а ю щ и й с я тем, что, сцелью расширения функциональныхвоэможностей путем увеличения ко"личества формируемых последовательностей, в него дополнительно введены блок умножения и блок задания матрицы преобразования, выход которого соединен с первым входом блокаумножения, второй вход которого соединен с выходом генератора М -последовательности, причем выход блока умножения соединен с вторым входом блока сравнения, а второй выход блока управления соединен стретьим входом блока задания длиныпоследовательности.0861 .1 реходных вероятностей и Одним и тем же заданным вектором стационарного 1 11Изобретение относится к импульсной технике.Известен генератор псевдослучайных чисел, содержащий цатчик равномерно распределенных псевдослучайных чисел, регистр кадя датчик потоков импульсов, логические элементы И, ИЛИ, позволяющий изменять вероятность появления ециничного сигнала на своих выходах Г 1 1Однако с помощью такого генератора нельзя получить заданный закон распределения чисел.Наиболее близким по техническо 10 1) 20 25 ) ) 0 Л сб му решению к предлагаемому является генератор псевдослучайных чисел, содержащий генератор А -последовательности, выход которого соединен с первым входом блока сравнения, выход которого соединен с входом дешифратора, выход которого соединен с первыми входами элементов И группы, выходы которых образуют первый выход генератора, блок задания длины последовательности и блок задания распределения и матрицы переходов, первый выход которого соединен с вторым входом блока сравнения, второй выход блока задания распределения и матрицы переходов соединен с управляющим входом деширратора, первый и второй входы блока задания распределения и матрицы переходов являются соответственно первым и вторым входами генератора, третий вход блока задания распределения и матрицы переходов является третьим входом генератора и соединен с первым входом генератора М -последовательности и первым входом блока задания длины последовательности, первый выход которого соединен с вто - рым входом генератора И-последовательности, второй выход блока задания длины последовательности соединен с вторыми входами элементов И группы, третий выход блока задания длины последовательности является вторым выходом генератора, а второй вход блока задания длины последовательности соединен с четвертым входом блока задания распределения и матрицы переходов и является четвертым входом генератора 21.Такой генератор позволяет Ъорцировать последовательности чисел, описываемые разными матрицами пераспределения.Недостатком известного генератора. является малое количество формируемых последовательностей.чисел, которое не превышает 2где и - число двоичных разрядов генератора И-последовательности, чтосужает область его применения.Цель изобретения - расширениефункциональных воэможностей путемувеличения количества Формируемыхпоследовательностей.Поставленная цель достигаетсятем, что в генератор псевдослучайных чисел, содержащий генераторК-последовательности, первый входкоторого соединен с первым выходомблока управления и первым входомблока задания длины последовательности, первый выход которого соединен с вторым входом генератораИ-последовательности, а второй выход - с первым входом блока элементов И, второй вход которого соединен с выходом дешифратора, вход которого соединен с выходом блокасравнения, первый вход которого соединен с блоком задания вектора ста ционарного распределения, выход генератора тактовьх импульсов соединен с вторым входом блока заданиядлины последовательности, дополнительно введены блок умноженияи блок задания матрицы преобразования, выход которого соединен с первым входом блока умножения, второйвход которого соединен с выходомгенератора И-последовательности,причем выход блока умножения соединен с вторым входом блока сравнения, а второй выход блока управления соединен с третьим входом блока задания длины последовательности сНа чертеже представлена структурная схема генератора псевдослучайных чисел,Генератор псевдослучайных чиселсодержит генератор 1 М-последовательности, первый вход которого соединен с первым выходом блока 2 управления и первым входом блока 3 задания длины последовательности, первый выход которого соединен с вторым входом генератора 1 И-последовательлности, а второй выход - с первым вхоцом блока А элементов И, второйвх которого соединен с выходом дешифратора 5, вход которого соединен с выходом блока 6 сравнения, первый вход которого соединен с блоком 7 задания вектора стационарного распределения, выход генератора 8 тактовых импульсов соединен с вторым входом блока 3 задания длины последовательности, блок 9 умножения, блок 10 задания матрицы преобразования, выход которого соединен с первым входом блока 9 умножения, второй вход которого соединен с выходом генератора 1 М-последовательгности, причем выход блока 9 умножения соединен с вторым входом блока 6 сравнения, а второй выход блока 2 управления соединен с третьим входом блока 3 задания длины последовательности. Позициями 11 - 17 обозначены шины, соединяющие блоки устройства.Блок 9 умножения выполнен на элементах И, ИСКЛЮЧАЮЩЕЕ ИЛИ и осуществляет умножение матрицы преобразования на случайный вектор.,Дешифратор 5 выполнен на элемен" тах ИСКЛЮЧАЮЩЕЕ ИЛИ.Блок 2 управления содержит кнопочный набор и КЯ-триггер, управляе" мый кнопками "Пуск" и "Сброс".Блок 7 задания вектора стационар. ного распределения содержит кнопочные наборы по числу компонент вектора стационарного распределения.Блок 1 О задания матрицы преобразования содержит набор кнопок, каждая иэ которых определяет один элемент матрицы преобразования.Принцип действия устройства заключается в следующем,Генератор 1 М-последовательносйти имеет 2 -1 состояний, где п - ,число триггеров в регистре гене-,ратора 1. Эти состояния эакодируемчислами от 1 до 2 - 1 и будем использовать все множество чисел .В двоичной системе счисления чис.ла х, формируемые генератором 1М-последовательности, представляютсобой векторы размера и:(х 1 у хну1 хеу х )уфгде х, - значение -го двоичногоразряда числа х,Блок 9 умножения матрицы преобразования на случайный вектор осуществлет преобразование случайного вектора х в вектор й= Вх,В= (Ь 11), , 1=1, и (1),5 где В - матрица преобразования,элементы которой Ь 11 могутпринимать значения О илиДля того, чтобы преобразование (1)было взаимно однозначным, ранг мат 1 О рицы В должен равняться и. При этомкаждому числу х преобразование(1) ставит в соответствие некоторое число и. Числа и, как и числах, могут принимать значения от 1до 2 - 1.Разобьем множество чисел и на Мнепустых непересекающихся подмножеств 1 а;. Если состоянию х генератора 1 отвечает число Ч е 1 йфо будем считать, что устройство вэтот момент времени находится всостоянии С; . Обозначим через С(Г)событие, означающее, что в моментг устройство находится в состоянииС., а символ р"(с)- относительнуючастоту наблюдения события С завремя прохождения генератором 1 все.иго множества 2 -1 состояний, ТогдаЗОЗ 5 где Р, - относительная частота пе%11рехода устройства из состояния С, в состояние С:,ш. - число переходов из состоя.ния С в состояние С ,щ; ш; - число наступлений событияС, (число элементов подмножества 1 81.Матрица переходов Р = (Р 1),элементы которой вычислены йо формуле (2), является стохастическойи неразложимой. Стационарное распределение, отвечающее этой матрице,имеет компоненты ш; /(2"- 1),1=1,2, 1 с.Вектор стационарного распределения задают с помощью чисел г, г,г , определяющих нижние грайицы подмножеств 0. Эти числа сблока 7 задания вектора стационар-ного распределения поступают вблок 6 сравнения, который в сочетании с дешифратором 5 осуществляетразбиение множества чисел Ч на 1подмножеств 0;)и определяет, длякакого значения г вья 1 олияется усчовие Я С 0, Появлеи 11 е единичногоСигнала иа г-м выходе де 1 шгФратора5 означает выполнение условияг 1 Е О и переход устройства в состояние С, . Полученный процесс ь 1 ме-"ет стационарный вектор с компонентамии,112-11.1 - Г,к2 -1 г г 3 2 -1 2 -1+1Последовательность сигналов на выходе устройства определяется заданным вектором стационарного распределения и последовательностью чисел с 1, которой можно управлять путем задания матрицы В. Как следуетиз (3), при изменении В стационарное распределение ие изменяется.Следовательно, изменяя матрицу Бможно получать на выходе устройства отличные друг от друга поспедовательиости сигналов, имеющие одини тот же заданный вектор стационарного распределения. Известно,. чгоколичество отличных друг от другаиевырожденных матриц В равноИ=МИИ;К,( /поэтому, задавая разные матрицы Б,можно получить И последовательнос:тей чисел с 1. Некоторые из получен-иых таким образом носледовательностей отличаются друг от друга толькоциклическим сдвигом. Соответствующие им последовательности сигналовна выходе устройства также отличаются только циклическим сдвигом.При использовании таких последовательностей может оказаться, чтоони не дают новой информации, Вэтих случаях они должны быть исключены. Пля того, чтобы различия между последовательностями чиселне сводились только к циклическомусдвигу, достаточно зафиксироватьодин из элементов этих последовательностей, Пусть, например, такимэлементом будет число о, отвечающее значению х = 100 О.Ч = В (1, О, О.О)г,Очевидно, что значение о в этомслучае определяется только первым столбцом матрицы В. Следовательно,если при измепеиии матрицы В первы 11 столбец будет оставаться неизменным,. то выбранному значению5 х = 1000 всегда будет отвечать Одно и то же число ч,Таким образом, для получения последовательностей чисел О, различия1 чежду которьгми не сводятся только10 к циклическим сдвигам, достаточнопри изменении матрицы В зафиксировать Один из ее столбцов, Числотаких г 1 оследовательиостей равно11/(2 ь - 1). Соответствующие им15 после 71,овательиости Выходных сигналов представляют собой псевдослучайный процесс с заданным векторомстационарного заспределеиия и некоторой матрицей переходов Р, злемен 20 ты которой могут быть вычислены поФормуле (2) .Устройство работает следующимобразом,Матрицу В задают с помощью блока 10 задания матрицы преобразования, который содержит и кнопок,служащих цля задания элементов матрицы В, Вектор стационарного распределения задают с помощью и-разрядц ных двоичных чисел г 1 для вводакоторых служит блок 7 задания вектора стационарного распределения.С помощью блока 2 управления пошине 1 Ь задают число тактов сдвига генератора 1 М-последовательнос 35ти, а по шине 13- сигнал установкиисходного состояния, Начало работыопределяется моментом снятия сигнала установки исходного состояния.При этом на сиихровход генератора1 М-последовательности по шине 16начинают поступать тактовые импульсы, Генератор 1 формирует и-разрядные псевдослучайные двоичные числа, которые поступают по шине 11 вблок 9 умножения матрицы преобра"зования на случайный вектор, гдеосуществляется преобразование (1),Умножение матриц 1 ь 1 В на случайныйвектор, формируемый генератором50осуществляется с помощью узлов умножения строки матрицы преобразования на случайный вектор, число которьгх равно и, Злементы матрицыВ поступают по шине 12, причем на551-и узел поступают элементы х-йстр ок 11 матриггы В а иа вьгходе 1 гфоузла формируется 1-я компоненты вектоРа й г 1 = Ь 11 х,+) Ь;Р ЯВЬХ,Тиражударственного комиам ивобретений ива, Ж, Раушская 62тета ССткрытий