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

ел tc

;о

1C

00

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

Целью изобретения является повышение быстродействия при получении многоразрядных псевдослучайных чисел.

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

Генератор содержит группу D-триггеров 1 коммутатор 2, генератор 3 равновероятного бинарного сигнала, генератор 4 тактовых импульсов, сумматор 5 по модулю два, группу элементов ИСКЛЮЧАЮЩЕЕ ИЛИ 6. Генератор работает следуюшим образом. Пусть на п-м такте его работы в груп- пе D-триггеров 1 записано двоичное т-раз- рядное число Л „. Соответствующий этому числу двоичный код подается на инфор- мационные входы коммутатора 2. Коммутатор 2 передается на выход сигналы X(i)n,...X(k)n лишь с определенных D-триггеров группы, выбранных исходя из условия получения псевдослучайной последовательности макси- мальной длины при определенном виде по- рождаюшего полинома. В результате форми- руется определенная структура обратной связи. Изменение этой структуры, т. е. переход к другому режиму работы генератора, отвечающему иному порождаюш,ему полиному, осуществляется после подачи соответствующего сигнала на управляющий вход коммутатора, являющийся тем самым входом задания режима работы генератора. Число выходных щин коммутатора 2. может изменяться от 1 до 3 в зависимости от используемого порождающего полинома. Сигналы Л (1 )„,...A {ft)n с выхода коммутатора 2, а также сигнал Q с выхода, генератора равновероятного бинарного сигнала 3 поступают на входы сумматора 5 по модулю два. Генератор равновероятного бинарного сигнала формирует случайную последовательность, принимающую в произвольный момент времени с равной вероятностью два возможных значения: или Q l, причем средняя частота изменений этих значений должна быть несколько большей, чем период М-последовательности, равный . На выходе сумматора по модулю два образуется двоичный сигнал (:),® ...®A (fe)n® Q, подаваемый на D- вход первого триггера группы D-триггеров 1. Двоичный код, соответствующий записанному в группе D-триггеров 1 числу А п, подается также на входы блока ИСКЛЮЧАЮЩЕЕ ИЛИ, реализующего в обратном коде кусочно-линейную зависимость: ( 1)-2А„ при Г1Х -|2А „-() при . Действительно, пусть А „ - двоичный код, снимаемый с инверсных выходов D-триггеров на п-м такте работы: (и)л|А (т-|)л1...1А (1)„

где А(,)л - значение, имеющее место в f -M разряде кода, i,2,...,m; Х() или А (,-). Если А (я1), что соответствует выполнению условия , то на вторых входах всех элементов ИСКЛЮЧАЮЩЕЕ ИЛИ блока 6 появится нулевой сигнал. Вследствие этого сигналы на выходах этих элементов будут повторять сигналы на их первых входах. Если пренебречь пока воздействием сигнала с выхода сумматора 5 по модулю два, это означает, что на D-входах D-триггеров будет иметь место кодовая комбинация: А (т-1)л1А()п|.-.|Х(1)„|0. В момент появления тактового импульса от генератора 4 на тактовых входах D-триггеров все они установятся в состояния, соответствующие сигналам на D-входах. В результате на инверсных выходах D-триггеров образуется J oдoвaя комбинация Е(Хп.) iX(«-Y)X Х|Х(-1)„..|Х()1 , которую можно также представить в виде разноса двух кодов: Е(Х) 1/1...,,..;,J X(.-x,J.../X(,,J01. Так как первый.код соответствует значению , а второй 2А „, то получаем, что в данном случае F(Xn)2 -1-2А л.

Если же У(т), что соответствует выполнению условия , то на вторых входах всех элементов ИСКЛЮЧАЮЩЕЕ ИЛИ 6 появится единичный сигнал. Вследствие этого сигналы на выходах этих

элементов будут инверсными по отношению к сигналам на их первых входах. Опять временно пренебрегая сигналом с выхода сумматора-5 по модулю два, получим, что с приходом тактового импульса от тактового генератора 4 на инверсных выходах Dтриггеров образуется кодовая комбинация

F((m-)(m-2)n.(i-,n, КОТОруЮ, ДОбавляя еще один (m-f i) разряд можно также представить в следующем виде:

F(A n)A(m)nlA (m-l)n|A(m.-2)n|...|A (l)n|0 -

(„)„|01......|1. Так как первая кодовая комбинация соответствует значению 2Х„, вторая равна 2, а третья - единице, то в итоге получаем (А„)2А„-()Учитывая сигнал с выхода сумматора 5 по модулю два, получаем, что в момент появления очередного тактового импульса с генератора 4 тактовых импульсов на инверсных выходах D-триггеров группы 1 формируется очередное псевдослучайное число в соответствии с соотнощением A n+i f(A n)- -7„+, ДА„)--(А (1)„® ... %x®Qn+., W f(A n) определяется указанной формулой. В результате на инверсных выходах D-триггеров образуется псевдослучайная апе- риодичная последовательность независимых равномерно расположенных т-разрядных двоичных чисел.

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

Формула изобретения Генератор псевдослучайных чисел, содержит группу D-триггеров, инверсные выходы которых соединены с информационными входами коммутатора, управляющий вход которого является входом задания режима работы генератора, выход коммутатора подключен к первому входу сумматора по модулю два, генератор равновероятного бинарного сигнала и генератор тактовых импульсов, выход которого соединен с тактовыми входами Ь-триггеров группы, отличающийся тем, что, с целью повышения быстродействия, в него введена группа элементов ИС

КЛЮЧАЮЩЕЕ ИЛИ, причем первый вход каждого г-го элемента ИСКЛЮЧАЮЩЕЕ ИЛИ группы соединен с инверсным выходом /-го /)-триггера группы, а выход - с /)-входом (г+1)-го D-триггера группы (,2, т-1) группы, m - число разрядов формируемого числа, вторые элементы ИСКЛЮЧАЮЩЕЕ ИЛИ групп соединены с инверсным выходом т-то )-триггера группы, /)-вход первого триггера группы соединен с выходом сумматора по модулю два, второй вход которого соединен с выходом генератора равновероятного бинарного сигнала.

Изобретение относится к вычислительной технике и может быть использовано при решении задач методом Монте-Карло, статистическом моделировании и т.д. Целью изобретения является повышение быстродействия. Генератор содержит группу Д-триггеров 1, коммутатор 2, генератор равновероятного бинарного сигнала 3, генератор тактовых импульсов 4, сумматор по модулю два 5, блок элементов ИСКЛЮЧАЮЩЕЕ ИЛИ 6. Генератор позволяет получать псевдослучайную апериодическую последовательность независимых равномерно распределенных M-разрядных случайных чисел X в соответствии с рекуррентным соотношением, приведенным в описании изобретения. 1 ил, 1 табл.

1№ разрядов подключения обратной связи

М 2 - 1