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

25

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

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

На фиг. 1 представлена структурная схема генератора псевдослучайных чисел; на фиг. 2 - схема регистра сдвига. О

Генератор псевдослучайных чисел содержит шину 1 Пуск, генератор 2 импульсов, элемент ЗАПРЕТ 3, делитель 4 частоты, регистр 5 сдвига, второй блок 6 памяти, сумматор 7, 5 регистр 8 адреса, первый блок 9 памяти. Шина 1 Пуск соединена с первыми входами элемента ЗАПРЕТ 3, де- лителя 4 частоты и регистра 8 адреса, второй вход которого соединен 20 с вторым входом делителя 4 частоты и выходом элемента ЗАПРЕТ 3, второй вход которого соединен с выходом генератора 2 импульсов. Входы первого блока 9 памяти соединены с первой группой входов сумматора 7 и выходами регистра В адреса, разрядные входы которого соединены с выходами сумматора 7, выход переноса и вход переноса которого соединены между 30 собой. Первый вход регистра 5 сдвига соединен с выходом делителя 4 частоты. Шина 1 Пуск соединена с вторым входом регистра 5 сдвига, выходы которого соединены с входами второ- jj го блока 6 памяти, выходы которого соединены с второй группой входов сумматора 7.

Регистр 5 сдвига содержит Е последовательно соединенных счетнь1Х до триггеров 10,-lOg, п-Z последовательно соединенных D-триггеров lU 11, , выход последнего из. которых (11,-го) соединен с входом первого счетчика триггера 10. Выход t-ro 45 счетного триггера 10. соединен с входом первого В-триггера 10р.,i.Входы синхронизации всех счетных триггеров 10,-lOj и D-триггеров 11,+. 11 объединены и являются первым вхо- jo дом регистра 5 сдвига, второй вход которого соединен с входами установки всех счетных триггеров 10 и D- триггеров 11.

Генератор псевдослучайных чисел работает следующим образом.

В ячейках первого блока 9 памяти записана последоватепьность равномерно распределенных псевдо5

О

5 0 0 j

о 5 jo

случайных т-разрядных чисел с периодом повторения , соответствующая одному из примитивных характеристических полиномов степени т. Во второй блок 6 памяти записано 2 констант q, взаимно простых к периоду -1 и не удовлетворяющих уравнению

|CLq)raod ,

где I 1,2,...,К.

Например при , и из

rh

2 возможных значений должны быть исключены значения ,2,3,4, 27, 28, 29 и 30, являющиеся решени ями уравнения при , значения q 14, 15, 16 и 17, полученные при . Для получения общего числа 2 16 констант могут быть исключены еще два значения и 22, дающие максимальный уровень корреляции псевдослучайных чисел X и X при . Для улучшения взаимно корреляционных свойств последовательностей псевдослучайных чисел Х , получаемых в отдельных циклах, где К - номер цикла, из множества допустимых значений q могут быть исключены также все значения mod Ми значения q.М-q., где q; - множество используемых значений q, ,2,...,m-l. При этих условиях все последова( ..г И

тельности tX. оказываются независимыми, т.е. не содержат одинаковых разрядных последовательностей (М-по- слёдовательностей), и не включают взаимно обратных к себе последовательностей (последовательностей с взаимно обратным порядком следования чисел) , отличающихся большими выбросами взаимно корреляционной функции.

Если период -1 является составным числом, то число допустимых констант q уменьшается. При малых значениях периода М () общее число констант q целесообразно взять равным 2 или . При большем периоде (т : 9 ) с целью улучшения корреляционных свойств генерируемых последовательностей это число может быть уменьшено до значений 2 или . Для увеличения полного периода последовательности псевдослучайных чисел, формируемых на выходах, в устройстве используется вспомогательный генератор псевдослучайных чисел, представляющий собой регистр 5 сдвига с обратной связью (фиг. 2), состоящий из счетных триггеров 10 и (пf) I -триггеров П. Если числа п и . соответствуют параметрам примитивного характеристического полинома X +Х +1, то регистром 5 сдвига генерируется последовательность псевдослучайных чисел периода . При этом .полный период последовательности псевдослучайных чисел, получаемых на выходе устройства, равен произведению периодов N М(2 -1)(2 -1), Та

КИМ образом, параметры вспомогательного генератора псевдослучайных чисе (регистра 5 сдвига) п и. I определяются соответственно требуемым периодо выходной последовательности и числом 2 констант q, записанных в блок 6 памяти.

Условием случайности следования отдельных циклов в последовательности псевдослучайных чисел периода N М(2 -1)-(2 -1) является отсутствие корреляции между последовательными индексами децимаций q и q -, где 1,N - номер цикла, ,2,... Так как последовательность индексов децимаций q, хранимых в блоке 6 памяти, полностью определяется последовательностью адресов, формируемых в первых разрядах регистра 5 сдвига, требование некоррелированности от- дельных циклов последовательности поностью переносится на последовательность адресов, причем последовательные адреса А и должны быть некоррелированны на максимально воз- можном интервале задержки . Этому условию удовлетворяет последовательность псевдослучайных чисел, получаемая на выходах счетных триггеров 10 в регистре 5 сдвига.

Минимальные фазовые сдвиги S бинарных последовательностей (М-по- следовательностей), получаемых на выходах этих триггеров, определяются

неравенством га/Л- - 3„,„ M/2J- п/1, гдеt - целая часть числа, т.е. S y-XlM/lJ. Указанное значение Sf,nn является максимально возможным для последовательности псевдо случайных чисел периода М. При всех значениях t S корреляция между Е-разрядными псевдослучайными числами А и А практически отсутствует.

Делитель 4 частоты выполнен с коэффициентом деления, равным 2-1, и фиксирует момент окончания очеред0

5

ного цикла генерации неповторяющихся псевдослучайных чисел Х- .

Работа устройства инициируется сигналом по шине 1 Пуск. По ятому сигналу прекращается прохождение тактовых импульсов с выхода генератора 2 импульсов на выход элемента ЗАПРЕТ 3, делитель 4 частоты, регистр 5 сдвига и регистр 8 адреса устанавливаются в исходное состояние. Для регистра 8 адреса исходным состоянием является нулевое, а для регистра 5 сдвига - любое, отличное от нуля, например, все единицы (фиг. 2). По окончании сигнала на шине 1 Пуск тактовые импульсы начинают управлять работой устройства.

В каждом такте работы двоичный код константы , считываемый с выходов блока 6 памяти, суммируется с содержимым регистра 8 адреса, и результат суммирования по переднему фронту импульса синхронизации записывается обратно в регистр 8 адреса. Этот результат является очередным адресом, по-которому из блока 9 памяти считывается очередное псевдослучайное число. В следующем такте содержимое регистра 8 адреса снова

увеличивается на величину 1 . I .

В поле допустимых адресов блока 9 памяти отсутствует один адрес, соответствующий нулевой ячейке, поэтому при переходе через граничное значение адреса -1 в результате очередного прибавления константы с необходима коррекция адреса. Эта коррекция выполняется с помощью Обратной связи с выхода переноса сумматора 7 на его вход переноса. Когда результат суммирования выходит за границу допустимых адресов, на выходе переноса сумматора 7 образуется единичный сигнал (единица переноса). Этот сигнал по цепи обратной связи поступает на вход переноса сумматора 7 в младший разряд, в результате чего значение суммы на выходах сумматора 7 увеличивается на единицу. Та-,. КИМ образом, при переходе через границу адресов А к очередному адресу прибавляется константа q-t-1 , в остальных случаях адрес модифицируется на величину q. Этим обеспечивается работа сумматора 7 по модулю 2 -1 с исключением нулевого адреса из поля допустимых адресов.

5125

По Олончании очередного цикла генерации по импульсу синхронизации с выхода делителя 4 частоты регистр 5 сдвига устанавливается в новое состояние, в результате чего из бло- ка 6 памяти считывается новая константа q. По окончании циклов работы регистр 5 сдвига устанавливается в исходное состояние, после чего процесс генерации псевдо- случайных чисел повторяется.

Формула изобретения.

1, Генератор псевдослучайных чи- сел, содержащий шин:у Пуск, соединенную с первыми входами элемента ЗАПРЕТ, делителя частоты и регистра адреса, второй вход которого соединен с вторым входом делителя часто- ты и выходом элемента ЗАПРЕТ, второй вход которого соединен с выходо м генератора импульсов, первый блок памяти, входы которого соединены с первой группой входов сумматора и вы- ходами регистра адреса, разрядные входы которого соединены с выходами сумматора, выход переноса и вход пе1 4

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

2. Генератор по и. 1, отличающийся тем, что регистр сдвига содержит Е последовательно соединенных счетных триггеров, n-f последовательно соединенных D-триг- геров, выход последнего из которых соединен с входом первого счетного триггера, выход Z-ro счетного триггера соединен с входом первого D- триггера, входы синхронизации всех счетных триггеров и D-триггеров объединены и являются первым входом регистра сдвига, второй вход которого соединен с входами установки всех счетных триггеров и D-триггеров.

Изобретение относится к им- пульсной технике. Цель изобретения расширение функциональных возможностей и снижение уровня корреляции формируемых чисел. Генератор содержит генератор 2 импульсов, элемент 3 ЗАПРЕТ, делитель 4 частоты, матор 7, регистр 8 адреса и блок 9 памяти. Для достижения поставленной цели в устройство введены регистр 5 сдвига и блок 6 памяти с образованием новых связей между элементами устройства. 1 з.п. ф-лы, 2 ил. Q S tc ел О5 05 -; фиг.1

CUHJrpOHl/3Oция о

та-9 HoS/(a

фид.2

Редактор В.Петраш Заказ 4834/55

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

Техред М.Ходанич Корректор М.Максимишинец

Тираж 816 . Подписное ВНИИПИ Государственного комитета СССР

по делам изобретений и открытий 113035, Москва, Ж-35, Раушская наб., д. 4/5

.Производственно-полиграфическое предприятие, г, Ужгород, ул. Проектная, 4 .