Генератор псевдослучайных последовательностей
Союз Советскик
Социалистическмк
Республик
ОП ИСАЙИ Е
ИЗОБРЕТЕН ИЯ
К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ (ii)953638
Ф
/ (61) Дополнительное к авт. свид-ву (22) Заявлено 13.03.81 (21) 3259180/18-24 (5 I ) М. Кл. с присоединением заявки РЙ—
Я 06 F 7/58
3Ьеударсткнный квинтет СССР
ao дилан изобретений и открытий (2З) Прноритет—, Опубликовано 23.08.82, Бюллетень №31 (53) УДК681.325 (088.8) Дата опубликования описания 23.08.82 (72) Автор изобретения
М. М. Юрцевич (71) Заявитель
Минский радиотехнический институт (54) ГЕНЕРАТОР ПСЕВДОСЛУЧАЙНЫХ ПОСЛЕДОВАТЕЛЬНОСТЕЙ
Изобретение относится к вычислительной технике и может найти. применение при моделировании случайных процессов и исследовании помехоустойчивости различных систем, а также в бортовых и наземных системах радиосвязи и радионавигации дпя измерения параметров движущегося объекта в качестве модупируюших сигналов.
Известно устройство формирования псевдоспучайных поспедоватепьностей, содержащее регистр сдвига и сумматор по модупю ABB в цепи обратной связи, позволяющее получить псевдослучайную поспедоватепьность максимапьной дпитепьи 15 ности с периодом 2 -1 jlJ.
Недостаток этого устройства — напи чие корреляции между генерируемой поспедоватепьностью и задержанной после- щ доватепьностью относительно самой себя на некоторое число дискретов, а также узость класса формируемых псевдоспучай+ ных последовательностей.
Известен формирователь псевдоспучайных последовательностей, содержащий бразрядный регистр сдвига с сумматором по модулю два в цепи обратной связи и
1 допопнитепьных сумматоров по модулю два, на выходах которых формируются псевдослучайные поспедоватепьности, причем г п(2.Допопнитeпьныe сумматоры по модупю два позвопяют попучить псевдослучайные поспедоватепьности с разпич- ным фазовым сдвигом (2f.
Это устройство позвопяет формировать псевдослучайные поспедоватепьности с равномерным спектром, но оно имеет не равный нулю коэффициент корреляции между сдвинутыми копиями поспедоватепьности, Наиболее близким по технической сущности к предлагаемому явпйется устройство формирования псевдоспучайных последовательностей (ПСП), .содержащее генератор тактовой частоты, выход которого связан с входами фазоврашатепя и первого датчика псевдослучайной поспедоватепь95363 ности, один выход которого связан с первым входом коррелятора, а другие выходы первого датчика псевдослучайной последовательности связаны с дешифратором, выход которого с одной стороны свя- > зан с другим входом коррелятора, а с другой стороны через фазовращатепь связан с входом другого датчика псевдоспучайной поспедоватепьности, выход которого подкщочен к третьему входу корре - la ля тора (31 .
Сущность работы данного устройства закпючена в том, что первый и второй датчики псевдоспучайных поспедонатепьностей формируют поспедоватепьности длины К = Р - 1 (Р— простое число разпичной фазовой структуры), т.е, на основе разпичных неприводимых и приметивных пониномов, причем фаза второго датчика псевдослучайной последовательности сдви- © гается на один симвоп после, каждого периода. псевдослучайной последовательности енерируемой первым датчиком псевдосцуйной оспедовательности. За период ПСП вычисляется взаимнокоррепяционная функ ция при -ом сдвиге между ПСП, генерируемыми первым и вторым датчиками псевдоспучайных носпедоватепьностей. В общем спучае на выходе устройства формирования псевдоспучайных поспедоватепьностей образуется многоуровневая ПСП длины И = Р -1 с двузначной функцией авИ ,т йюррепяции, (=N(z, где Й вЂ” дпина поспедоватепьности (период);
E — энергия последоватепьности, опредепяемая числом не нупевых эпементов поспедоватепьности на ее периоде.
Автокоррепяционная функция выходной
ПСП формируемой в известном устройст1 ве, при отображении ее уровнями (+1,-1, 0) имеет следующее значение
Й(а) = И +К-1
1(в) --(У+2) m=-О ео88
m$ О воЗК (1) а значение каждого символа многоуровневой поспедовате пьности опреде цяется по формупе
8 4 в) а„=-4-2 (hie>/z — встречается на период последоватепьности 2" 1 — 2(" /
per„
fJpH с(=2" t(или д «2"-2+3 с0= и н.о.д. (и, К ) — нечетное, а X
)41K
2. Пусть Р 2, простое, попучаем а) О, --1ФР— встречается на пе< +Е>/2 риоде многоуровневой поспедоватепьности
g((п- е,„(- е и б) 0 „ =-1 — встречается на периоде многоуровневой последоватепьности
- (раз. (н8)/2 с) O„ =-(-p — встречается на периоде многоуровневой поспедоватепьности (2(рй- -р(п-Е>/ раз, где 0- н.о.д. (C2,k) й( — нечетноер d=((2(p"-4) или d =р "-p +Ì, причем d ф р" mod р"- f q X >, = Уд ° .
Еспи на выходе коррепятора со сбросом каждому символу поставить в соответствие (6) Ъ„-О,если й„--<;
;Ь„=1,если а . +Р "+ >/
1 )
O g р (и+ КЦг (3) то пик-фактор выходной поспедоватепьности может определяться простой формулой (которая приближенно выпопняется и дпя ,многоуровневой псевдослучайной последовательности ) где X „и g „„- псевдослучайные поспедова4$ ! те пьности, генерируемые соответственно первым и вторым датчиками псевдоспучайных последовательностей.
Особый интерес представпяют образуемые на выходе устройства формирования последовательности(6 ), когда б < принимает только три уровня.
1. Пусть 9=2, тогда спедует, что уровни принимают спедукипие значения а) Q„ -342 )/ — встречается иа периоде 2" " 42(раз;
", е- (иЕ- )/ б) Ql„ -1- встречается на периоде последовательности 2 — 2 — 4 раз; и q-ß
Пик-фактор псевдослучайной поспедоватепьности, формируемой в известном устройстве имеет значение (6)
Впучшем c ae (g -1) пик фактор имеет значение = p.
ПСП, формируемые в известном устройстве, могут иметь минимапьное значение пик-фактора If =2 в случае, когда формируемые датчиками бинарные псевдоспучай-! ные последовательности имеют нечетную степень и = 3, 5, 7, .... Это значение
/ U(t) «(0 для непрерывных значений Х и Y„
При P — 2 коррелятор наналогичен коррелятору известного устройства. При 12 коррелятор осушествпят перемножение с весом по правилу Х„ . 1; „„1, если
Х Y,п,иХ„ Y =О, еслибы„ Ф (,, В общем случае коррелятор 4 имеет следующие узлы: весовой перемножитель; интегратор или сумматор.
Дешифратор 5 представляет собой и входную схему совпадения на определенное кодовое состояние псевдослучайной последовательности, генерируемой первым ,датчиком 3 псевдослучайной поспедова5 953 пик-фактора хуже значений, которые имеют псевдослучайные последовательности.
Недостатком известного устройства является также узкий класс формируемых последовательностей. Это объясняется тем, S что период последовательностей при р = 2 может иметь только одно иэ следующих значений:
N "-2 -1 - когда датчиками формируюти ся ПСП типа М-последовательностей; 10
N = 4(+ 2, Й - простое, Х = 1,2,...
Й = 4x 27, Ч вЂ” простое число, Х
1,2,...; х., Х< И Х< простые ñïà.
Цейь изобретения — уменьшение пик- 15 фактора формируемой псевдослучайной последовательности, что позволит повысить
его точность, и увеличение класса формируемых псевдослучайных последовательностей. 20
Поставленная цепь достигается тем, что в генератор псевдослучайных последовательностей, содержащий генератор тактовых импульсов, выход которого соединен с первым входом фазоврашатепя и с sxo- 25 дом первого генератора М-последовательности, выход которого соединен с первым входом коррелятора, второй вход которого подключен к выходу дешифратора и к второму входу фазоврашателя, выход которо- З0
ro соединен с входом второго генератора
М-пос ледовате пьности, разрядные выходы первого генератора М-последовательности соединены с входами дешифратора соответственно, введены компаратор, сумматор и блок задержки, входы которого подключены к разрядным выходам второго генератора M-последовательности соответственно, выход которого соединен с входом сумматора, выход которого соединен с третьим входом коррелятора, выход которого соединен с входом компаратора, выход которого являешься выходом генератора, выходы блока задержки соединены с соответствующими входами группы сумматора
На чертеже изображен генератор псевдослучайных последовательностей.
Устройство содержит генератор 1 тактовых импульсов, выход которого связан с входами фазовращателя 2 и перво50 го генератора 3 М-последовательности, один выход которого соединен с первым входом коррелятора 4, а другие выходы первого генератора 3 M-последовательности связаны с дешифратором 5, выход которого соединен с другим входом корSS релятора 4 и через фазоврашатель 2 связан с входом второго генератора 6
М-последовательности, выходы которого
638 6 через блок 7 задержки и сумматор 8 соединены с третьим входом коррелятора
4, причем второй вход сумматора 8 сое- динен с основным выходом второго генератора 6 М-последовательности, а выход коррелятора 4 подключен к входу компаратора 9.
Генератор 1 тактовых импульсов выполняет операцию генерирования импульсов заданной частоты, с помощью которых осуществляется синхронная работа всех элементов и блоков устройства формирования псевдоспучайных последовательностей.
Фазофращате пь 2 осуществляет изменение фазы (задержку фазы) по сигналу с дешифратора 5. Выходное значение напряжения фаэоврашателя подчйняется вы-. ражению где Y — значение выхода дешифратора;
U(t) - выходное напряжение генератора тактовой частоты.
Первый генератор 3 M-последовательности выполняет операцию генерирования псевдослучайной поспедовательности с основанием f êoòoðàÿ удовлетворяет некоторому полному значению задержки
Це1 С, Х, ее,е C, (ОЛ,",-3)
i 0
Коллектор 4 выполняет операцию следующего вида: (R(rn) = Z х„у„ для .,дискретных величин Х и Y u
R() = J x(t+t) Y(t+i ) dt
О. 953638 8 относитепьHO другой, поступают на сумматор 8, выпопняюший арифметическое сумми рова ни е.
Результат суммы сдвинутых псевдослучайных поспедоватепьностей поступает на коррелятор 4 со сбросом. на другой вход которого поступает ПСП, формируемая первым генератором 3 М-поспедоватепьности. За время N-,,«(„- длительность элементарного дискрета формируемых ПСП) вычисляется значение взаимокорреляционной функции между ПСП, генерируемой первым генератором 3 М-поспедоватепьности, и поспедовательностъю, образованной суммой (р«+1 ) копий ПСП . такой же формы, как ПСП, генерируемая вторым генератором 6 М-последовательности. В соответствии с избранным правилом в компараторе 9 происходит отображение значения ВКФ в уровни (1-1,0). Одновременно с отображением уровней происходит сброс коррелятора 4 в нулевое состояние, так как ровно через период ПСП на выходе дешифратора
5 появится логическая 1 ", которая производит сброс коррелятора 4 в нуль раз за период. Кроме того, погическая 1 производит изменение фазы ПСП, генерируемой вторым генератором 6 М-последовательности. jianee цикп работы усч ройства повторяется. Через П сдвигов фаза ПСП генерируемая другим датчиком псевдослучайной поспедоватепьности, примет исходное состояние и начнет вырабатываться второй период выходной псевдослучайной поспедоватепьности, состоящей иэ трех сивопов {+1, 1,0).
Сущность работы предлагаемого устройства основана на новом свойстве взаимокорреляционной функции между одной Мпоспедоватепьностью основания р и суммой N - копий другой М-поспедоватепьности такого же основания, тепьности. Еспи значение и †.разрядного слова ПСП совпадает с кодом схемы совпадения, на выходе дешифратора будет напряжение, которое соответствует погической 1 "°
Второй генератор 6 М-поспедоватепьности выполняет. операцию генерирования псевдослучайной поспедоватепьности с основанием р но попином задержки отпичен от попинома задержки первого датчи- 10 ка 3 псевдослучайн и поспедоватепьности.
Бпок 7 задержки осуществляет формирование ПСП, имеющих фазовый сдвиг относительно ПСП, генерируемой вторым датчиком 6 псевдоспучайной поспедова- 15 тельности. Число формируемых копий для каждого периода Н ПСП выбирается в соответствии с разложением на множители, hi=0, 1, 2... ° .
Су-мматор 8 осуществляет операцию 2«) сложения N +1 вепичин. Сложение может быть проведено аналоговым ипи дискретным методами.
Компаратор 9 осуществпяет преобразование уровней коррепятора 4 в три уров- 5 (1; О,— 1).
Генератор работает следующим образом. . В момент включения в первый 3 и второй 6 генераторы М-последовательности вводятся состояния, отличные от нупя, а дешифратор 5 настроен на комбинацию символов, которые вводятся в первый генератор 3 М-последовательности в на3S чапьный момент времени. Это позвопяет на выходе дешифратора 5 цопучить импульс, который осуществляет установку коррепятора 4 в нупевое состояние, а также производит задержку изменения
4«) фазы второго генератора 6 М-поспедоватепьности, за счет того, что логическая
"1 на выходе дешифратора 5 не пропус кает тактовый импульс через фазовращатель 2 на вход второго генератора 6 Mпоспедоватепьности. Затем происходит
45 формирование симво нов псевдослучайных последовательностей в первом 3 и втором 6 генераторах М-последовательности, а в бпоке 7 задержки осуществляется формирование % -копий псевдоспучайных последовательностей, которые имеют такую же форму, как и псевдослучайная по» спедоватепьность, генерируемая вторым генератором 6 М-последовательности, но имеющие фазовый сдвиг, кратный значе- 55 ниюЬ,««, )Ä. Символы с выхода второго
Ц
ps-4 генератора 6 М-последоватепьности и ее копии, сдвинутые на 5 симвопов одна
Если P" -1-(P ) -1, ) - нечетное, то ункция взаимной корреляции (ФВК) меж- ду псевдослучайной поспедоватепьностью и суммой p" -1 копий другой псевдослучайной М-поспедоватепьности «при нирсе « мает всего три значения на периоде —, Пусть -2, тогда
al — (2 -1 ) — встречается . (, <) t2" раз
«tl4 g)/ã a =-(-«)i2 — встречается л Е- < -Еа)
О;=-(2. -т) 2 -естречеетс» (ni8))2 ï-8- «и-8-2)I2 раз где =1= H,О.Э,tA,kj, п!  — нечетное;
J = 2 +1 „ g,,2к .,як+1
2, простое, тогда встречается раэ встречается вс тре чается раэ
Пусть Р Ф
Сд *- P 4 р1 „ (.Р - ) Р," 4=-(Р -М) Р "
1Рр.-e+<
>.. .„<.-еу „< -Е1:, <и-а)!г Г
953638 10 хОднм, что полином другой псевдослучайной последовательности должен быть
Х Х Ф Х Х+1=0. Форма этой псевдослучайной последовательности
-О
) j=62
1 =0
++ + «+» + -++»++++++»++++»
2"-1 2") -1 () --1
=21. дл дл
Эта псевдослучайная последователь- 45 ность может быть образована из М-последовательности основания 2 степени 6.
Пусть первый датчик 3 псевдослучайной последовательности генерирует М-последовательность периода Й = 63 генера- 50 торного полинома Х + Х + 1 О. Фор5 ма этой последовательности спедуюшая (х + —.+----++- — +-+-, "62 >=o
++++ + — +++ +++++++++++ + +», Учитывая формулу (7), находим 0= 2, 55
К=2, с) = 5, Я = 11. Ограничимся Д = 5.
Исходя иэ выражения = Х определяем что Y = Х5 Из этого выражения на- ) 2 1 где= 8= Cog (р") =i
1)= °, =1, 2, 3,4, 5, ..., О, 3, 5, 7, 9, 11, .(нечетное), й/0 - -нечетное;
Д=- р" a<) или d =- р"-р" i1) 2
Пик-фактор псевдослучайных поспедова-д5 тельностей, генерируемых в npeAaaraeMoM устройстве, определяется по выражению рn !
4i444l = <= p 444 ад вод -4)/p и
R(m)=Î m$0moa(-4„-4)(p
В случае <-=1 и p = 2 гл = О, т.е. сум-. мирование фаэ другого датчика псевдослучайной последовательности отсутствует и ПСП, генерируемые в предлагаемом устройстве, эквивалентны ПСП, генериру емым в известном. В случае < 1 и Рф 2, а также ф 1 и Р- любое простое в предлагаемом устройстве, формируемые Зя
ПСП имеют лучший пик-фактор, т.е. II l„ когда (P" -1) - Оо.
В таблице приведены сравнительные характеристики известного и предлагаемого устройства.
Рассмотрим процесс формирования псевдослучайной последовате пьности, обраэовываемой на выходе предлагаемого уст- ройства, если p= 2, i 2, тогда длина
I первой последовательности, удовлетворяюшей условию образования, равна
Если эту фазу последовательности генерирует другой датчик 6 псевдослучайной последовательности, тогда спедуюшие две псевдослучайные последовательности
+ + ++ ++ + ++ ++++++ =вэ
Я = " . «!!! 4. =444 + ++++++ + +++ ++ 44+4.+
++++ + + + + 1 ++4+ + +»+ генерируются .в блоке генерирования 1Tl дополнительных копий 7 другого датчика псевдослучайной последовательности. В сумматоре 8 происходит. сложение псевдо а ъ 1. случайных последовательностей Y, и
1 4Складовая по тактам символы этих
1ф последовательностей, получим следуюшие
1 значения символов суммы
i7 j 62 4; = o + Í-4-3+3444,3 3+, 3,44.44++Í.
3+3+й433++3+Н+44444-3+34.4-443 34+344-4
В корреляторе 4 эа каждый период всевдоспучайной последовательности будет- образован один символ выходной последовательности. Эта последовательность имеет вид 19д 134134 134 134 134 -, 194 13
-3, 13, -3, -19, 13, 3,3, -19, -3;
3, 13, -19, -3, -19, -19, 13, 13, 13, 13, ..., Преобразователь 9 уровней отображает выходную псевдослучайную последовательность на выходе коррелятора 4 в псевдослучайную последоватепьность со значениями символов+ l. О. Если выбрать правило преобразования — 19-4 -1, +13 +1.
-3- О, тогда на выходе образуется пери одическая псевдослучайная последовательность
-1 1, 1, 1, 1, 1, -l, 1, О, 1, О, -1, 1, 1, -1, О, О, +1, -1, О -1, -1, 1, 1, 1, 1, 1, -1, 1, 1, О, ..., Полученная последовательность имеет пик-фактор, равный l, 3, 3, 3, что соот- - ф
gnq ветствует табличному значению дпя >
Аналогично можно показать, что и при
Р 2 также на выходе устройства образуются псевдослучайные троичные последовательности с достаточно малым пикфактором.
953638
И
2 -1
2 -1 1,142
2 2-1
1,333
3 3-1
tl
3 -1 й
1,5
5 5-1
5 -1 1,008
Ь
4-124
5 5-1 .4
5 -1
4 24
1,041
1,16 7 -1
6.48
7 1 1,002
6.342
7 -1
7 7-1
1,020
1 1 -1 1,0007
t!
10. 1330
11-1
10. 120
11 11 -1
11 11 -1
1,008
13 13 -1
13 13 -1
1,006
1,08
12.143
17 17 -1
16 тт -1 1,0002
tl
16.4912.
1,107 17 -1
17 17 -1
1,003
16.255
1 9 -1 1,0001
1 8. 6858
19 -l
18.360
19 19 -1
19 19 -1
1,05
1,002
Увеличение класса формируемых псевдослучайных последовательностей происходит за счет того, что в предлагаемом устройстве образуется ряд псевдослучайных последовательностей не только периртт- 4 ода Р = -1, но и периода -:- .
Р -1
В рассматриваемом выше примере число дополнительных фаз, формируемых в блоке генерирования N — дополнительных копий 7 apyroro датчика псевдослучайной hatt последовательности, выбрано равным п1 = P" -2.Îäíàêo такое число формируемых койий является избыточным...йостатт .4 точно формировать acегоttt"-- о(1дополнительных копий. Суммирование суммато- 15 . ра 8 тогда осуществляется по правилу
Форму ла изобретения
Генератор псевдослучайных последовательностей, содержащий генератор тактовых импульсов„ выход которого соединен
Эти формулы следуют непосредственно иэ свойств М-последовательностей.
Таким образом, предлагаемое устройство формирования псевдослучайных последовательностей имеет преимущества перед известным, заключающиеся в увеличении класса формируемых псевдослучайных последовательностей и уменьшении пчк-фактора формируемых псевдослучайных последовате ль ностей.
Введение блок задержки, сумматора и компаратора позволяют существенно расширить ансабль псевдослучайных последовательностей с малым пик-фактором беэ существенного усложнения устройства.
1,125 3 -1 1,038
2 26 с первым входом фазоврашателя и с входом первого генератора М-последовательности, выход которого соединен с первым входом коррелятора, второй вход которого подключен к выходу дешифраторя и к
13 953638 14 второму входу фазоврашатепя, выход кото- выход которого явпяется выходом генерарого соединен с входом второго генерато- тора, выходы блока задержки соединены ра М-поспедоватепьности, разрядные выхо- с соответствуюшими разрядными входами ды первого генератора М-поспедоватепь- сумматора. ности соединены с входами дешифратора соответственно, о т и и ч а ю щ и и с si Источники информапии, тем, что, с- пепью повышения точности ге- принятые Во внимание при экспертизе нератора, он содержит компаратор, сум- 1. Патент США % 3700869, MBTop H блок задержки, входы которого кп. 235-152, 1972. подключены к разрядным выходам второго 1о 2. Яковлев В. B., Федоров P. Ф..Ста" генератора M-поспедоватепьности соответ- хостические вычиспительные машины. Л. ственно, выход которого соединен с вхо- Машиностроение", 1974, с. 253. дом сумматора, выход которого соединен 3. Авторское свидетепьство СССР с третьим входом коррепятора, выход ко- N 524174, кп. (06 F 1/02, "roporo соединен с входом компаратора, Н 03 В 29/00, 1974 (прототип).
Составитепь А. Kapacos
Редактор И. Никопайчук Техред А. Ач Корректор М, Шароши
Заказ 6279/77 Тираж 731 Подписное
ВНИИПИ Государственного комитета СССР по делам изобретений и открытий
113035, Москва, Ж-35, Раушская наб., д. 4/5
Филиал ППП Патент, г. Ужгород, уп. Проектная, 4






