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

(54) ГЕНЕРАТОР ПСЕВДОСЛУЧАЙНЫХ ПОСЛЕДОВАТЕЛЬНОСТЕЙ

Изобретение относится к вычислитепьной технике и может найти применение при модепировании случайных процессов и исследовании помехоустойчивости различных систем, а также в бортовых и наземных системах радиосвязи и радионавигахии для измерения параметров движущегося объекта в качестве модулирующих сигналов. Известно устройство формирования псевдослучайных последовательностей, со держащее регистр сдвига и сумматор по модулю два в цепи обратной связи, позволяющее получить псевдослучайную последовательность максимальной длительности с периодом 2 -1 ij. Недостаток этого устройства - нагмг чие корреляции между генерируемой последовательностью и задержанной последовательностью относительно самой себя на некоторое число дискретов, а также узость класса формируемых псевдослучай ных последовательностей. Известен формирователь псевдослучайных последовательностей, содержащий П- - разрядный регистр сдвига с сумматором по моду то два в цепи обратной связи и р дополнительных сумматоров по модулю два, на выходах которых формируются псевдослучайные последовательности, причем Г п|2.Дополнительные сумматоры по модупю два позволяют получить псевдослучайные последовательности с разпичным фазовым сдвигом 2. Это устройство позволяет формировать псевдослучайные последовательности с равномерным спектром, но оно имеет не равный нулю коэффициент корреляции между сдвинутыми копиями последовательности. Наиболее близким по технической сущности к предлагаемому явлйется устройство формирования псевдослучайных последовательностей (ПСП), .содержащее генератор тактовой частоты, выход которюго связан с входами фазовращателя и первого датчика псевдослучайной последовательности, один выход которого связан е первым входом коррелятора, а другие выходы первого Датчика псевдослучайной последовательности связаны с деигафршто- ром, выход которого с одной стороны свя зан с другим входом коррелятора, а с другой стороны через фазоврашатепь связан с входом другого датчика псевдослучайной последовательности, выход которо го подключен к третьему входу корре ля тора . Сущность работы данного устройства заключена в том, что первый и второй датчики псевдослучайных последовательностей формируют пос ледова те пьности длины N , (Р - простое число разпичной фазовой структуры), т.е. на основе различных неприводимых и приметивных полиномов, причем ф)аза второго датчика псевдослучайной последовательности сдвигается на один символ после жаждого периода псевд оспу чай ной последовательности генерируемой датчиком псевдослучайной поспедовательности. За период ПСП вычисляется взаимнокорреляциоввая функция при i -ом сдвиге между ПСП, генергру емыми первь М и вторым датчиками псевдослучайных последовательностей. В обшем случае на выходе устройства формирования псевдослучайных последовательностей образуется многоуровневая ПСП длины N с двузначной функцией автпкогреияции. fRlm N +N-f msOmo6H LR(n)-() m Omo8K a значение каждого симвода многоуровневой последоватепьности опредепяется по формуле

где Xjj псевдослучайные поспедова тельности, генерируемые соответственно перИзПч и вторым датчиками псевдоспу- чайргых последовательностей.

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

а) - встречается на перйоде 2 - -и2(

б)(3 с-1 - встречается на периоде последовательности 2 - 2 - -Ч раз;

Пик-фактор псевдослучайной последовательности, формируемой в известном устройстве имеет значение

(

(6)

В лучшем случае (0-1) пик-фактор имеет значение j р.

ПСП, формируемые в известном устройстве, могут иметь минимальное значение пик-фактора у 2 в случае, когда формируемые датчиками бинарные псевдослучайные последовательности имеют нечетную степень п 3, 5, 7, ,,.. Это значение в)о( встречается на период последовательности раз. Пpиc(2Иилиd-2 24, н.о.д. ( П , к ) - нечетное, а X,j, di 2. Пусть PI 2, простое, получаем а) - встречается на периоде многоуровневой поспедовательности (/2((-е52 . б)а -1 - встречается на периоде многоуровневой последоватепьнрсти р-р -i раз. c) встречается на периоде многоуровневой последовательности /2(рП-«-р(п-|)/2 раз, где 6 н.о.д. (ft, fe ) f)/C - нечетное; d /SCp -Oили причем ) XJ4,i Vj5j. Если на выходе коррелятора со сбросом каждому символу поставить в соответствие (6) .если j (,еслиа| - 4.)/2. ,еслиа - -р % то пик-фактор выходной последовательности может определяться простой формулой (которая приближенно выполняется и для / ffloгoypoвнeвoй псевдослучайной поспедо- |Вательности) ,(4) где N - длина последовательности (период)J Е - энергия последоватепьности, определяемая числом не нулевых элементов последовательности на ее периоде. Автокорреляционная функция выходной ПСП. формируемой в известном устройстве, при отображении ее уровнями (+1,-1, О) имеет следующее значение р(тЬЕ-р т 0 mod N IRM-O m О mo3N 59 пик-фактора хуже значений, которые имеют псевдоспучайные поспедоватепьности. Недостатком известного устройства является также узкий класс формируемых поспедоватепьностей. Это объясняется тем что период последовательностей при fJ 2 может иметь только одно из следующих значений: К -2 -1 - когда датчиками формируют ся ПСП типа М-последовательностей; N - 4)f + 2, N - простое, X -в 1,2,.. 1( - и 2 J.O7 1.1- М - 4j( +27, VI - простое число, J- f ii , « N j(2 Х ) 2 простые числа. Цель изобретения - уменьшение пикфактора формируемой псевдослучайной последовательности, что позволит повысить его точность, и увеличение класса формируемых псевдослучайных последовательностей. Поставленная цель достигается тем, что в генератор псевдослучайных последовательностей, содержащий генератор тактовых импульсов, выход которого соединен с первым входом фазовращателя и с вхо- дом первог.о генератора М-последовательности, выход которого соединен с первым входом коррелятора, второй вход которого подключен к выходу дешифратора и к второму входу фазовращателя, выход которого соединен с входом второго генератора М-поспедовательности, разрядные выходы первого генератора М-последовательности соединены с входами дешифратора соответственно, введены компаратор, суммато и блок.задержки, входы которого подключены к разрядным выходам второго генератора М-последовательности соответственно, выход которого соединен с входом сумматора, выход которого соединен с третьим входом коррелятора, ЕЫХОД которого соединен с входом компаратора, выход которого является выходом генератора выходы блока задержки соединены с соответствующими входами группы сумматора. На чертеже изображен генератор псев дослучайных последовательностей. Устройство содержит генератор 1 так товых импульсов, выход которого связан с входами фазовращателя 2 и первого генератора 3 М-последовательности, один выход которого соединен с первым входом коррелятора 4, а другие выходы первого генератора 3 М-последовательности связаны с дешифратором 5, выход которого соединен с другим входом коррелятора 4 и через фазовращатель 2 связан с входом второго генератора 6 М-послбДовательности, выходы которого 38 через блок 7 задержки и сумматор 8 соединены с третьим входом коррелятора 4, причем второй вход сумматора 8 coeJ динен с основным выходом второго генератора 6 М-последоватепьности, а выход коррепятора 4 подключен к входу компаратора 9. Генератор 1 тактовых импульсов ЕЫполняет операцию генерирования импульсов заданной частоты, с помощью котоpjx осуществляется -синхронная работа всех элементов и блоков устройства формирования псевдослучайных последовательностей. Фазофращатель 2 осуществляет изменение фазы (задержку фазы) по сигналу с дешифратора 5. Выходное значение напряжения фазовращателя подчиняется вы-, ражению где Y - значение выхода дешифратора; U(i) - выходное напряжение генератора тактовой частоты. Первый генератор 3 М-последоватепьности выполняет операцию генерирования псевдослучайной последовательности с основанием f) -которая удовлетворяет некоторому полному значению задержки п i(x.bIC-K ГАеС4-{о,(,...,-|}. Коллектор 4 выполняет операцию следующего вида: (R{m 5: X;Y;. ля .дискретных величин .RlmbJ x((tn)dt о АЛЯ непрерывных значений X и V. При Р - 2 коррелятор наналогичен коррелятору известного устройства. При pf2 коррелятор осуществпят перемножение с весом по правилу К . если XrVum -n.. О. еслиХ - УишВ общем случае коррелятор 4 имеет следующие узлы: весовой перемножитель; интегратор или сумматор. Дешифратор 5 представляет собой И ходную схему совпадения на определеное вх довое состояние псевдослучайной оследовательности, генерируемой первым атчиком 3 псевдослучайной поспедова7- 9 тепьностн. Если значение П -разрял.ного слова ПСП совпадает с кодом :схемы совпадения, на выходе дешифратора будет напряжение, которое соответствует логической I. Второй генератор 6 М-последоватепь ности выполняет операцию генерирования псевдослучайной последовательности с основанием .р , но полином задержки отличен от полинома задержки первого датчика 3 псевдослучайнойпоспедовательности. Блок 7 задержки осуществляет формирование ПСП, имеющих фазовый сдвиг относительно ПСП, генерируемой вторым датчиком 6 псевдослучайной поспедовательности. Число формируемых копий для каждого периода N ПСП выбирается в соответствии с разложением на множители, tn О, 1, 2, .... Сумматор 8 осуществляет операцию сложения гп +1 величин. Сложение может быть проведено аналоговым или дискрет- ным методами. Компаратор 9 осуществляет преобра зование уровней коррелятора 4 в три ypo ня (1 о,- 1). .Генератор . работает следующим обра ° В момент включения в первый 3 и вто рой 6 генераторы М-последовательности вводятся состояния, отличные от нуля, а Дешифратор 5 настроен на Комбинацию символов, которые вводятся в первый генератор 3 М-последовательаости в начальный момент времени. Это позвопяет на выходе дешифратора 5 получить импуяьс, который осуществляет установку корреггатора 4 в нулевое состояние, а также производит задержку изменения . фазы второго генератора 6 М-поспедоватепьности, за счет того, что логическая 1 на выходе дешифратора 5 не пропуск кает тактовый импульс через фазовращатель 2 на вход второго генератора б М последовательности. Затем происходит формирование символов псевдослучайных последовательностей в первом 3 и втором 6 генераторах М-последовательности а в блоке 7 задержки осуществляется формирование m -копий псевдослучайных последовательностей, которые имеют такую же форму, как и псевдоспучайная последовательность, генерируемая вторым генератором 6 М-поспедоватепьности, но имеющие фазовый сдвиг, кратный значениюЕ -,4,,..,Симвопы с выхода второго генератора 6 М-последоватегаьности и ее копии, сдвинутые на ft символов одна 8. 8 относитепьно другой, поступают на сумматор 8, выпопняющий арифметическое суммирование. Результат суммы сдвинутых псевдослучайных последовательностей поступает на коррелятор 4 со сбросом, на другой вход Kotoporo поступает ПСП, формируемая первым генератором 3 М-поспедоватепьности. За время N-t(,(С,,-«длительность элементарного дискрета формируемь1х ПСП) вычисляется значение взаимокорреляционной функции между ПСП, генерируемой первым генератором 3 М-последовательности, и последовательностью, образованной суммой (т+1) копий ПСП такой же формы, как ПСП, генерируемая вторым генератором 6 М-поспедоватепьности. В соответствии с избранным правилом в компараторе 9 происходит отображение значения ВКФ в уровни (1,и 1,0). Одновременно с отображением уровней происходит сброс коррюлятора 4 в нулевое состояние, так как ровно через период ПСП на выходе дешифратора 5 появится логическая , которая производит сброс коррелятора 4 в нуль раз за период. Кроме того, логическая Vj, производит изменение фазы ПСП, генерируемой вторым генератором 6 М-последовательности. Далее цикл работы устройства повторяется. Через П сдвигов фаза ПСП генерируемая другим датчиком псевдослучайной последовательности, примет исходное состояние и начнет вырабатываться второй период выходной псевдослучайной последовательности, состоящей из трех сивопов (+1, -1,0). Сущность работы предлагаемого устройства основана на новом свойстве взаимо корреляционной функции между одной Мпоследовательностью основания р и суммой ш - копий другой М-последователь- . ности такого же основания. Если р -1-(р)-1, ; - нечетное, то {)ункцая взаимной корреляции (ФВК) между псевдослучайной последовательностью и суммой р -1 копий другой псевдослучайной М-последовательности V принир -1мает всего три значения на периоде r-j -Пусть -2, тогда () - встречается (.2) /2 , .Li,, (2-() 2 встречается 1. . раз( (2.м)- 2 5-встречается ;.e-.;2,n-e..V2 где -1 H,o.9.n,kl, п/6 - нечетное; d или d . Пусть Р 2, простое, тогда а;--р-( - встречается I / (-()/ ;раз i--(р Я+р встречается ilp-.)раз , Cogp(p)i n v j ,:-, 2, 3, 4, 5, .... J О, 3, 5, 7, 9, 11, „.(нечетное), ilf2 - нечетное; 6 1 рПОипис1ЦСр -р Я Пик-фактор псевдослучайных поспеДов геяьностей, генерируемых в ,преД1Югаемо устройстве, определяется по выражению R(m) T,EOmoa(-ti-l)/p R(m) ( в случае m 0, т.е. сум мирование фаз другого датчика псевдослу чайной последовательности отсутствует и ПСП, генерируемые в предлагаемом устройстве, эквивалентны ПСП, генериру емым в известном. В случае 4 i и Р 2 а также X , 1 и Р- любое простое в предлагаемом устройстве, формируемые ПСП имеют лучший пик-фактор, т.е. Укогда (I -1). В таблице приведены сравнительные характеристики известного и предлагаем го устройства. Рассмотрим процесс формирования псевдослучайной последовательности, обр зовываемой на выходе предлагаемого уст ройства, если р« 2, , тогда длина первой последовательности, удовлетворяю щей условию образования, равна 2)-- U)M 1 Эта псевдослучайная последователь- ность может быть образована из М-посл ДовательноСти основания 2 степени 6. Пусть первый Датчик 3 псевдослучайной последовательности генерирует М-последовательность периода N 63 генера- торного полинома X X + . Форма этой последовательности следующая ( ++ - --+ ++-+- ++++ ++-Н-++ - -Н--+Учитывая формулу (7), находим 2 , d 5; d 1-1. Ограничимся - 5. Исходя из выражения V; определ ем, что 5 этого выражения на 9 8. 10 ходим, что попином другой псевдослучайной поспецоватепьности должен быть Х 4Х 4 Х+Х+1 О. Форма этой псевдослучайной последовательности +-н--++nil--+-+ + + М Ji:.0 ++ ++л- ++ ++++Если эту фазу последовательности генерирует другой датчик 6 псевдослучайной последовательности, тогда следующие две псевдослучайные носледовательности , ) J Ь2 ---ьи-н Гу«73 1 j Г 42 : ++++- t +-4- +--t--++ +- - + + генерируются -в блоке генерирования tn дополнительных копий 7 другого датчика псевдослучайной последовательности. В сумматоре 8 происходит спожение псевдослучайных последовательностей Yj Y и Y; .Складовая по тактам символы этих последовательностей, получим следу;юшие значения символов суммы /5-vaJ 2 V - - -- ri I I I i3+3-H-H-33++3+- - Hj-H I 3+ЗЧЧНЧ-3 3 НЧ-ЗЧН--НЧ-Н-Н-3+3++-Н-3 §++3+++. В корреляторе 4 за каждый период всевдослучайной последовательности будет образован один символ выходной последовательности. Эта последовательность имеет вид 5.19, 13,13, 13, 13, 13, -. 19, 13, -3;j.3, -3, -i9,-13,43, -19, -3; -3, 13, -19, -3, -19, -19, 13, 13. 13, 13, .... Преобразователь 9 уровней отображает выходную псевдослучайную последовательность на выходе коррелятора 4 в псевдослучайную последоватещзность со значениями символов ll. О, ЕС пи выбрать правило преобразования - , . , тогда на выходе образуется периодическая псевдослучайная последовательность-1,1, 1, 1, 1, 1, -1, 1, О, 1, О, 1. 1, 1, -1, О, О, -1-1, -1, О, -1, -1, 1, 1, 1, 1, 1, -1, 1, 1, О Полученная последовательность .имеет пик-фактор, равный 1, 3, 3, 3, что соответствует табличному значению дпя - -« Аналогично можно показать, что и при Р 2 также на выходе устройства образуются псевдослучайные троичные после- овательности с достаточно малым пик- актор {. Увеличение класса формируемых псев- дсюпучайных последовательностей происхо дит за счет того, что в предлагаемом устройстве образуется ряд псевдослучайных последовательностей не только периода f - -1, но и периода ТГТ В расс 1атриваемом выше примере чис ло дополнительных фаз, формируемых в блоке генерирования ЦП дополнительных копий 7 другого датчика псевдослучайной последовательности, выбрано равным f Р 2.Однако такое чиспо формируемых дпйй $тпяется.избыточным.. Достаточно формировать вceгoП t:v0 p(-fдoпoIIнителькых копий. Суммирование сумматора 8 тогда осуществляется по правилу ff -iTrP т fell- -CL ib-p Формула изобретенияс первым входом фазовращателя и с вхоГенератор псевдослучайных поспедова-ности, выход которого соединен с первым

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

первого генератора М-последоватепьff - . 1г -1 , Эти формулы следуют непосредственно из свойств М-поспедоватепьностей. Таким- образом, предлагаемое устройство формирования псевдослучайных последователь костей имеет преимущества перед известным, заключающиеся в увеличении класса формируемых псевдослучайных последовательностей и уменьшении пик-4|актора формируемых псевдослучайных последовательностей. Введение блок задержки, сумматора и компаратора позволяют существенно расширить ансабль псевдослучайных последовательностей с малым пик-фактором без существенного усложнения устройства.

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

выход которого является выходом генератора, выходы блока задержки соединены с соответствующими разрядными входами сумматор.

Источники информации, принятые во внимание при экспертизе

Н ОЗВ 29/00, 1974 (прототип).