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

 

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

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

РЕСПУБЛИН (191 (! (!

4(5)) Н 03 К 3/о4

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

H ABTOPCH0MV СВИДЕТЕЛЬСТВУ

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

10 ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТНРЫТИЙ (21) 3653202/24-2! (22) 13.07.83 (46) 30.05.85.Вюл. и 20 (72) P.M,Ìàícóðoa (71) Казанский ордена Трудового Красного Знамени и ордена Дружбы народов авиационный институт им.А.Н.Туполева (53) 621.374.2(088.8) (56) l. Яковлев В.B., Федоров P.Ô.

Стохастические вычислительные машины.

Л., "Машиностроение", 1974, с.247,,рис.!!7.

2."The Radio and Electronic Engineer" S. 40, Р 2, 1970, р.85, fig.3. " (54) (57) ГЕНЕРАТОР ПСЕВДОСЛУЧАЙНЬИ

ЧИСЕЛ, содержащий генератор тактовых импульсов, выход которого соединен с .входами синхронизации и триггеров, выход i-го триггера (i I,К) соединен с первым. входом j -го сумматора (j i l,Ê) по модулю два, выход

m -го триггера (m=i+A; 1 : А п-1) соединен с вторым входом j-ro сумматора (g = (=I,Ê) по модулю два, отличающийся теМ, что, . с целью расширения .функциональных возможностей за счет управления корреляцией в последовательности генерируемых чисел, в,него введены дешифратор, и элементов К {2И)-ИЛИ, блок вывода из нулевого состояния, и входов которого соединены с выходами и триггеров, а выход — с информационным входом первого триггера, j-й выход дешнфратора (j 1,К) соединен с первыми входами соответствующих групп

2И и элементов К(2И)-ИЛИ, выход .Х-гЬ триггера соединен с вторым входом

Ь-ro элемента 2И (Ф +. Ь)-ro элемента (У 1 9n - 1; I с. Ь а К) К(2И)-ИЛИ, выход «

j ãî сумматора (j I,К) по модулю два соединен с вторым входом (К-С)-го. MJ элемента 2И (j-С)-ro элемента (ОбС< С К-1)К(2И)-ИЛИ, выход первого элемен" та К(2И)-ИЛИ соединен с (и+1)-м входом блока вывода из нулевого состоя ния, выходы остальных элементов К(2И)"

ИЛИ соединены с информационными вхо,дами соответствующих триггеров.

I I 591 59 2

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

Известны генераторы псевдослучайных чисел, содержащие регистр сдвига с логической обратной связью. Указан« 5 ные генераторы выдают некоррелированные псевдослучайные числа с высокой степенью равномерности закона распределения 1.1), Однако схемные решения данных ге- I0 нераторов не позволяют получать кор- q релированные числа с управляемой степенью корреляции. Для генерации таких чисел необходимы дополнительные устройства - корреляторы, обла- 15 дающие значительной конструктивной сложностью.

Наиболее близким по техническому реШению к изобретению является генератор равномерно распределенных псев-20 досл5чайных чисел, содержащий генератор -.àêòовых импульсов, n D-триггеров и К сумматоров по модулю два (n K), причем вхацы i-го сумматора по модулю два (I» i » К) соединены с 25 вьгходами i-го и (з.+и-К)-га тригге" ров, а выход -, с входом i-го D-триггера, при этом вход тп-га D-триггера (К+ i » m я и) соединен с выходом (m-К)-ro

D-триггера, а выход генератора тактовых импульсов подключен к входам синхронизации всех D-триггеров121.

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

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

Поставленная цель достигается тем„ что в генератор псевдослучайных чисел, содержащий генератор тактовых 50 импульсов, выход которого соединен с входами синхронизации и триггеров, выход i-го триггера (i=1,Ê) соединен

° с первым входам j-го сумматора (ji

, l,K) по модулю два, выход m-го триг- 55 гера (m=1+A;-1 А (n-1) соединен с вторым входом j-го сумматора (j=i= l,K) по модулю два, введены дешифратор, и элементов К(2И)-ИЛИ, блок вывода из нулевого состояния, и входов которого соединены с выходами и триггеров, а выхоц — с информационным входом первого триггера, j-й .выход дешифратара ()=ГК) соединен с первыми входами соответствующих групп

AH п элементов К (2H)-ИЛИ, выход P.-го триггера соединен с вторым входом

Ь-го элемента 2И (21.Ь)-го элемента (II, =l,n-l; I» Ь» К) К(2И)-ИЛИ, выход j«ro сумматора (j=l,К) па модулюpsa соединен с вторым входом(К-С)-го элемента 2И (j-С)-го элемента (О С»К-1) К(2И)-ИЛИ, выход первого элемента К(2И)-ИЛИ соединен с „ (n+1)-и входом блока вывода из нулевого состояния, выходы остальных элементов К(2И) -ИЛИ соединены с информационными входами соответствующих триггеров °

На фиг.l приведена структурная. схе" ма генератора псевдослучайных чисел; на фиг,2 — функциональная схема примера конкретного выполнения генератора псевдослучайных чисел, на фиг.3семейство корреляционных характерис" тик последовательности чисел, полученных с выхода 10-разрядного генератора (п=10;К=7) при различном чис" ле S сдвигов за такт, Генератор псевдослучайных чисел (фиг.l) содержит генератор l тактовых. импульсов, выход которого соединен с входами синхронизации и-триггеров

2, выход j-ro триггера 2 ° (i 1,К) ., соединен с первым входом j --го сумматора 3 (j = i . I,К) .по модулю два, выход ш-га триггера

2д (ш=1+А; 1 » А и-1) соединен с вторым входом j -го сумматора 3;1 (1

=i=1 Ê) по модулю два, дешифратор

4, и элементов К(2И)-ИЛИ 5, блок 6 вывода из нулевого состояния, и входов которого соединены с выходами триггеров 2, а выход — с информационl ным входом первого триггера 2, -й выход дешифратора 4 (1=Г,K) соединен с первыми входами соответствующих групп 2И и элементов К(2И)-ИЛИ 5, выход 3-га триггера 22 соединен с вторым входом Ъ-го элементе 2И(2+Ь)-га элемента (2 = 1, n"l; I Ь К)

К(2И)-ИЛИ 5е.Ь, выход j-го сумматора 31 (1=1,К) по модулю два соединен с вторым входом (K"С)- ro элемента 2И (j-С)-га элемента(О С » К -I)

К(2И)-ИЛИ 51 с, выход первого эле" мента К(2И)-ИЛИ 5 соединен с (n+I)-м

1,1591 входом блока 6 вывода иэ нулевого состояния, выходы остальных элементов

К(2И)-ИЛИ 5 соединены с информацион" ными входами соответствующих триггеров 2 - 2„., 5

Пример конкретного выполнения генератора псевдослучайных чисел (фиг.2) приведен для n=5 К=3 и обеспечивает экспоненциальный закон изменения корреляции. 1О

Генератор псевдослучайных чисел (фиг.!) работает следующим образом, Установленный на дешифраторе 4 (например, с помощью тумблерного ре" с гистра) двоичный код величины числа 15

8 сдвигов эа один такт дае-. на груп" пы 2И соответствующих элементов

К(2И)-ИЛИ 5qy э 5q5 э ° ° ° 5„з (I Sс K) разрешающий потенциал, обеспечивая тем самым подключение выходов сумма" 20 торов 3g з+,, 2„.,,,3 к входам . триггеров 2, 2»...2з соответственно.

Выходы триггеров 2„, 2,.. .2„, подключаются к входам трйггеров Т, 25

2,,...2„ соответственно, При каждом конкретном сдвиге S триггеры

2 - 2д вместе с сумматорами 3 z, —

3 по модулю два и тактовым генератором I представляют собой регистр сдвига с S-разрядным сдвигом за такт.

При этом и групп элементов К(2И)-ИЛИ г с, с с с с . я ) ° ° 11 ).бц ф ° ° е -pj J ° ° ° pq е е ° 5pg ре-й ставляют собой многоразрядный коммутатор, управляемый дешифратором 4.

Импульсы с выхода тактового генератора 1, поступающие на входы синхронизации триггеров 2 - 2 ;обеспечивают операцию S-разрядного сдни" га sa такт. Такий образом, в каждом рабочем такте на выходах триггеров

2 — 2 устройства,.появляется: очередное псевдослучайное число. Для вывода регистра сдвига иэ запрещенного нулевого состояния, в которое он может попасть под влиянием случайных сбоев, служит блок 6. Если все триггеры 2 - 2„ окаэывйются в у р и

00 ...010 ...О 1 ! О ...000 ...0 О

0 1 ...000 ...О 0

° ° Ф

0 О ...000 ...1 0

Единичные элементы первой строки означают, что первый разряд следующего числа образуется суммированием по модулю два n-ro u i-ro разрядов егистра. Единичные элементы других

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

Величина 1 выбирается в зависимости

15 от и йо таблице, составленной исходя иэ условия примитивности, соответствующих характеристических полиномов. Таблица представлена до п=31.

3 4 5 6 7 !О Il l5 I 7 20 21 22 25 28 31

2 3 3 5 6 7 9 14 14 17 19 21 22 25 28

Выражение (1) с ростом п стремит- ся к более простой форме вида г(2) 2 ° 55

При S ) I связи генератора случайных чисел определяются в соответст"

59 4 нулевом состоянии, на выходе блока появляется сигнал, который переводит триггер 2 в единичное состояние. В нормальном рабочем режиме. блок 6 не влияет на работу устройства и пропускает сигналы с выхода элемента К (2И)-ИЛИ 5„ на вход триг" гера 2„.

При И=1 в устройстве осуществляется обычный одноразрядный сдвиг sa такт, и в последовательности генерируемых в каждом такте чисел при" сутствует корреляция, определяемая выражением

2 (2 -3)"0,5(2 -3) по тгИ

),5 — при п (1) где r(T) — нормированная корреляцион« ная функция;

Я вЂ” смещение.

В данном случае устройство работает в соответствии с матрицей Т размера (n p n), задающей правило функционирования ст о"ства вии с матрицей Тз, где S i. Поскольку в схеме осуществляется S-разрядный сдвиг за такт, корреляционная зависимость в последовательности чисел имеет вид г(С)2 " где $, Таким образом, в данном устройстве в результате введения дешифратора, элементов K(2H)-ИЛИ и блока вы1159159 вода из нулевого состояния обеспечивается (по сравнению с известным устройством) получение при разли ных величинах сдвига $ корреляционных

5 зависимостей ви а г (") ll59159

0, 0,Т

0„

0, 0

0,1

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

Редактор Л.Веселовская Техред Л.Микеш Корректор О.Луговая

Заказ 3608/56 краж 872 Подписное

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

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

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