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

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

Иллюстрации

Показать все

Реферат

 

Союз Советскик

Социалистическмк

Республик

ОП ИСАЙИ Е

ИЗОБРЕТЕН ИЯ

К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ (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