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

СОЮЗ СОНЕТСНИХСОЦИАЛИСТИЧЕСКИХРЕСПУБЛИК 1256161 3 8 594 Н РЕТЕН ЕЛЬСТ ГОСУДАРСТВЕННЫЙ КОМИТЕТ СССРПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТНРЫТИЙ ОПИСАНИ А ВТОРСКОМУ С 8(21) 3842075/24-2122) 07.01.8546 07.09.86. Бюл. У 33 (71) Ленинградский институт инженеров железнодорожного транспорта им, акад, В,Н,Образцова(56) Билинский И.Я., Микелсон А.К. Стохастическая цифровая обработка непрерывных сигналов. - Рига: Зинатне, 1983, рис. 5.2 а.Авторское свидетельство СССР В 1223350, кл. Н 03 К 3/84,28,06,84,(54) ГЕНЕРАТОР ПСЕВДОСЛУЧАЙНЫХСЕЛ(57) Изобретение относится к импульсной технике. Цель изобретения расширение функциональных возможностей и снижение уровня корреляцииформируемых чисел. Генератор содержит генератор 2 импульсов, элемент3 ЗАПРЕТ, делитель 4 частоты, сумматор 7, регистр 8 адреса и блок 9памяти. Для достижения поставленнойцели в устройство введены регистр5 сдвига и блок 6 памяти с образованием новых связей между элементами устройства, 1 э.п. ф-лы, 2 ил.15 30 40 Изобпетение относится к импульсной технике.Цель изобретения - расширениефункциональных возможностей и снижение уровня корреляции формируемых 5чисел.На фиг. 1 представлена структурная схема генератора псевдослучайных чисел", на фиг. 2 - схема регистра сдвига.10Генератор псевдослучайных чиселсодержит шину 1 "Пуск", генератор 2импульсов, элемент ЗАПРЕТ 3, делитель 4 частоты, регистр 5 сдвига,второй блок 6 памяти, сумматор 7,регистр 8 адреса, первый блок 9 памяти. Шина 1 "Пуск" соединена с первыми входами элемента ЗАПРЕТ 3, делителя 4 частоты и регистра 8 адреса, второй вход которого соединенс вторым входом делителя 4 частотыи выходом элемента ЗАПРЕТ 3, второйвход которого соединен с выходом генератора 2 импульсов. Входы первогоблока 9 памяти соединены с первойгруппой входов сумматора 7 и выходами регистра 8 адреса, разрядныевходы которого соединены с выходамисумматора 7, выход переноса и входпереноса которого соединены междусобой, Первый вход регистра 5 сдвигасоединен с выходом делителя 4 частоты. Шина 1 "Пуск" соединена с вторымвходом регистра 5 сдвига, выходы которого соединены с входами второго блока 6 памяти, выходы которогосоединены с второй группой входовсумматора 7.Регистр 5 сдвига содержит 1 последовательно соединенных счетныхтриггеров 10, -10, ипоследовательно соединенных Р-триггеров 11,11, выход последнего из.которых(11-го) соединен с входом первогосчетчика триггера 10, Выход с-го 45счетного триггера 10 с соединен свходом первого Р-триггера 10Входы синхронизации всех счетных триггеров 10 -10 и Р-триггеров 11с с+111 объединены и являются первым входом регистра 5 сдвига, второй входкоторого соединен с входами установки всех счетных триггеров 10 и Ртриггеров 11.Генератор псевдослучайных чиселработает следующим образом,ъВ 2 -1 ячейках первого блока 9памяти записана последоватепьностьравномерно распределенных псевдослучайных щ-разрядных чисел с периодом повторения М=2 -1, соответствующая одному из примитивных характеристических полиномов степени щ. Вовторой блок 6 памяти записано 2констант с 1, взаимно простых к периоду М=2 -1 и не удовлетворяющих уравнению 1(сс 1)шов Мщ,где с =1,2 К,2 -2=30 возможных значений должныбыть исключены значения с 1=1,2,3,4,27, 28, 29 и 30, являющиеся решениями уравнения при с =1, значения с 1==14, 15, 16 и 17, полученные прис=2. Для получения общего числа 2=16 констант могут быть исключеныеще два значения с 1=9 и 22, дающиемаксимальный уровень корреляции псевдослучайных чисел Х и Х +. при =3.1Для улучшения взаимно корреляционных свойств последовательностейКпсевдослучайных чисел Х, , получаемых в отдельных циклах, где К - номерцикла, из множества допустимых значений с 1 могут быть исключены такжевсе значения с 1 =2"и щось М и значения11.=М-), где с 1 - множество используемых значений с 1, 1=1,2щ,При этих условиях все последоваКтельности Х. 1 оказываются независимыми, т.е. не содержат одинаковыхразрядных последовательностей (М-последовательностей), и не включаютвзаимно обратных к себе последовательностей (последовательностей с взаимно обратным порядком следования чисел), отличающихся большими выбросамивзаимно корреляционной функции.Если период М=2 -1 является составным числом, то число допустимыхконстант с 1 уменьшается. При малыхзначениях периода М (щ=5- 8) общеечисло констант с 1 целесообразно взятьравным 2 или 2, При большем периоде (щ ) 9 ) с целью улучшения корреляционных свойств генерируемых последовательностей это число может бытьуменьшено до значений 2 или 2 .Для увеличения полного периодапоследовательности псевдослучайныхчисел, формируемых на выходах, в устройстве используется вспомогательныйгенератор псевдослучайных чисел,представляющий собой регистр 5 сдвигас обратной связью (фиг, 2), состоящий из 1 счетных триггеров 10 и (и 1256161Г) 0-триггеров 1. Если числа и и соответствуют параметрам примитивного характеристического полиномаеХ +Х +1, то регистром 5 сдвига генерируется последовательность псевдослучайных чисел периода И=2 - 1, При этом полный период последовательности псевдослучайных чисел, получаемых на выходе устройства, равен произведению периодов М М=(2 - 1)(2 - 1). Тат 10 ким образом, параметры вспомогательного генератора псевдослучайных чисел (регистра 5 сдвига) и и, 1 определяются соответственно требуемым периодом вьгходной последовательности и числом 2 констант с 1, записанных в блок 6 памяти.Условием случайности следования отдельных циклов в последовательности псевдослучайных чисел периода Н М=(2"-1)(2 -1) является отсутствие корреЛяции между последовательными индексами децимаций ц и о , гдеК К+7=1,М - номер цикла, с =1,2, Так как последовательность индексов децимаций г 1", хранимых в блоке 6 памяти, полностью определяется последовательностью адресов, формируемых в первых разрядах регистра 5 сдвига, требование некоррелированности от- З 0 дельных циклов последовательности полностью переносится на последовательность адресов, причем последовательные адреса А и А ,-, должны быть некоррелированны на максимально воз- З 5 можном интервале задержки , Этому условию удовлетворяет последовательность псевдослучайных чисел, получаемая на выходах счетных триггеров 10 в регистре 5 сдвига. 40Минимальные фазовые сдвиги Ябинарных последовательностей (М-последовательностей), получаемых на выходах этих триггеров, определяютсяп-г.неравенством 1 ш/11- - -(ИЛ- 45 - и/11, где г 1 - целая часть числа, т,е. ЯИ/г 1, Укаэанное значение В является максимально возможным для последовательности псевдослучайных чисел периода М. При всех значенияхс Я корреляция между Г-разрядными псевдослучайными числами А и А практически отсутству- ет. 55Делитель 4 частоты выполнен с коэффициентом деления, равным 2 -1, и фиксирует момент окончания очередного цикла генерации М=2"-1 непонторяющихся псевдослучайных чисел Х(с1Работа устройства инициируется сигналом по шине 1 "Пуск", По этому сигналу прекращается прохождение тактовых импульсов с выхода генератора 2 импульсов на выход элемента ЗАПРЕТ 3, делитель 4 частоты, регистр 5 сдвига и регистр 8 адреса устанавливаются в исходное состояние. Для регистра 8 адреса исходным состоянием является нулевое, а для регистра 5 сдвига - любое, отличное от нуля, например, все единицы (фиг, 2), По окончании сигнала на шине 1 "Пуск" тактовые импульсы начинают управлять работой устройства.В каждом такте работы двоичный код константы с, считываемый с выходов блока 6 памяти, суммируется с содержимым регистра 8 адреса, и результат суммирования по переднему фронту импульса синхронизации записывается обратно в регистр 8 адреса. Этот результат является очередным адресом, покоторому из блока 9 памяти считывается очередное псевдослучайное число, В следующем такте содержимое регистра 8 адреса снова увеличивается на величину1 В поле допустимых адресов блока 9 памяти отсутствует один адрес, соответствующий нулевой ячейке, поэтому при переходе через граничное значение адреса А=2 -1 в результате очередного прибавления константы необходима коррекция адреса, Эта коррекция выполняется с помощью обратной связи с выхода переноса сумматора 7 на его вход переноса. Когда результат суммирования вьгходит за границу допустимых адресов, на выходе переноса сумматора 7 образуется единичный сигнал (единица переноса). Этот сигнал по цепи обратной связи поступает на вход переноса сумматора 7 в младший разряд, в результате чего значение суммы на выходах сумматора 7 увеличивается на единицу. Та- ким образом, при переходе через границу адресов А=2 -1 к очередному адресу прибавляется константа с 1+1, в остальных случаях адрес модифицируется на величину 1. Этим обеспечивается работа сумматора 7 по модулю 2 -1 с исключением нулевого адреса из поля допустимьх адресов,