3.3. М-последовательности. Основные свойства

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

1. М-последовательность является периодической с периодом, состоящим из импульсов (символов).

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

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

4. Формируются М-последовательности с помощью линейных переключательных схем на основе сдвигающих регистров. При этом, если применяется регистр с разрядами и в -последовательности используются различных видов импульсов (отличающихся, например фазами), то

Число разрядов регистра Следовательно, значитательное увеличение числа импульсов в периоде М-последова-вательности вызывает незначительное увеличение числа разрядов регистра, так как зависимость от является логарифмической.

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

Благодаря перечисленным свойствам М-последовательности широко применяют в радиотехнических системах. Для пояснения этих свойств рассмотрим пример.

Допустим, что сдвигающий регистр (рис. 3.14) состоит из трех триггерных ячеек которые выполняют роль

дискретных элементов задержек, и сумматора. На триггеры поступают сдвигающие импульсы, которые рис. 3.13 не доказаны. Они следуют с тактовой частотой Каждый тактовый импульс вызывает изменение состояния (напряжения на выходе) всех триггеров. При этом напряжение на выходе каждого триггера (символ) становится равным напряжению (символу) на его входе для предыдущего такта. Символы могут принимать два значения, которые условно обозначим 0 и 1. При суммировании любых комбинаций входных символов на выходе сумматора получаются только символы 0 и 1. Правило суммирования символов в двоичной системе счисления (с двумя (возможными значениями символов) по модулю определяется табл. 3.3.

Таблица 3.3. Суммирование по

Рис. 3.14. Генератор М-последовательности с

Выясним, в каких состояниях может находиться схема, представленная на рис. 3.14. Предположим, что в исходном состоянии символ на одном из выходов триггеров отличается от нуля, например символ на выходе триггера имеет значение 1, а на выходе и значение 0. Тогда исходное состояние сдвигающего регистра характеризуется комбинацией выходных символов 100. На входе 77 символ равен 0, так как согласно с табл. 3.3 символ на выходе сумматора равен С поступлением на вход схемы очередного сдвигающего импульса символы со входов триггеров «переходят» на их выходы. Новое установившееся состояние регистра описывается комбинацией выходных символов На входе появляется 1, так как в соответствии с табл. 3.3 выходной символ сумматора равен Аналогично определяются все состояния регистра, приведенные в табл. 3.4.

Из рассмотрения табл. 3.4 видно, что состояния регистра (символы на выходе различны для тактов 1—7, а для последующих тактов они повторяются. Так как число разрядов регистра а основание системы счисления (число используемых символов) то число возможных различных состояний регистра

В табл. 3.4 отсутствует нулевая комбинация 000, так как её наличие согласно табл. 3.3 приводит к обращению в нуль всех символов во всех остальных комбинациях. Поэтому в табл. 3.4 приведены только возможные для нормальной работы схемы (рис. 3.14) состояния регистра, число которых После

Таблица 3.4. Состояния регистра

семи тактов состояния регистра повторяются. Если символы непрерывно считывать со входа 77, то получим периодическую последовательность

с периодом, равным Отметим, что символы можно считывать с выхода любого триггера. В этом случае получаются последовательности, сдвинутые во времени (табл. 3.4).

Подчеркнем, что период последовательности (3.33) является максимально возможным для данного числа разрядов (триггеров) схемы рис. 3.14, и выбранного основания системы счисления. Это следует из того, что в регистре последовательно сменяются все возможные состояния, кроме нулевого. Период для последовательности (3.33) совпадает со значением, определяемым формулой (3.32),

Необходимо отметить, что при заданных период последовательностей вида (3.33) определяется схемой включения отводов сдвигающего регистра (выходов триггеров) в цепь обратной связи. Он может быть получен и меньше максимально возможного. Выбор соединений отводов сдвигающего регистра в цепи обратной связи для получения максимального периода последовательности при заданном числе разрядов регистра и основания системы счисления к настоящему моменту полностью определен и решается с помощью таблиц неприводимых многочленов.

При рассмотрении работы схемы рис. 3.14 было сделано допущение, что исходное состояние регистра характеризуется комбинацией 100. Из табл. 3.4 видно, что в качестве исходного можно взять любое состояние регистра. Это вызовет лишь сдвиг последовательности (3.33) во времени.

Число единиц и нулей в периоде последовательности (3.33) соответственно причем Отметим, что отличие между и на единицу в последовательностях вида (3.33) имеет общий характер. В общем случае при число единиц в последовательности равно а число нулей

Сумма двух Мчпоследователыюсгей, сдвинутых друг относительно друга, является М-последовательностью. В этом можно

убедиться, суммируя согласно правилам табл. 3.3 последовательность (3.33) и, например, М-тос ледоват ост с выхода на рис. 3.14, т. е.

Это является следствием того, что сдвинутые М-последова-тельности можно получить с помощью одной и той же схемы.

Фазоманипулированный сигнал с помощью М-последователь-ностей формируется следующим образом. Каждому символу последовательности ставится в соответствие радиоимпульс со своей начальной фазой. В двоичной системе счисления это соответствие можно определить как

где двойная стрелка означает соответствие.

Таблица 3.5. Умножение символов

В соответствии с (3.35) табл. 3.3 сложения символов 0 и 1 превращается в таблицу умножения символов 1 и —1 (табл. 3.5).

АКФ периодического ФМ сигнала определяется согласно (3.25), где Обозначая символы М-последовательности (3.33) через и сравнивая табл. 3.3 и 3.5, замечаем, что

Если для любого то сумма двух М-последовательностей является тоже М-последовательностью. Но в ней число единиц в периоде на единицу больше числа нулей. Поэтому сумма по всем при будет равна единице, выражении для АКФ (3.25) сумма будет равна согласно При для любого временной сдвиг между двумя -последовательностями равен нулю. При этом из (3.25) получаем, что

Объединяя полученные результаты, получаем

где

На рис. 3.15, а изображена М-последовательность с на рис. 3.15, б - периодическая АКФ, дискретные значения которой построены согласно (3.37), на рис. 3.15, в — апериодическая АКФ.

Рассмотренный пример подтвердил основные особенности М-последовательности.

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

обратимся к принципам формирования произвольных последовательностей с помощью цифровых автоматов.

Цифровые автоматы формирования кодовых последовательностей с заданным периодом. С помощью цифровых автоматов можно Сформировать кодовую последовательность с заранее заданным периодом

Рис. 3.15. М-гюследовательность с (а), периодическая АКФ (б), апериодическая АКФ (в)

Цифровой автомат [13], предназначенный для формирования двоичной кодовой последовательности (рис. 3.16), состоит из сдвигающего регистра с элементами задержки (на рис. 3.16 триггера дешифратора (ДШ) заданной кодовой комбинации из двоичных символов, сумматора по и триггера Т для дополнительной задержки на один такт. На рис. 3.16

Рис. 3.16. Цифровой автомат формирования двоичной последовательности с периодом

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

В табл. 3.6 [13] приведены параметры цифрового автомата, формирующего кодовые последовательности с заданным периодом, в том числе период номера отводов сдвигающего регистра, заданная кодовая комбинация. Для М-последовательностей нет необходимости в дешифраторе (см. рис. 3.14), поэтому в столбце «Кодовая последовательность» для оследовательностей кодовые комбинации не указаны. В табл. 3.6 приведены параметры цифровых автоматов для В работе ] приведены параметры 2047.

Цифровой автомат формирования М-последовательностей. Общая схема цифрового автомата, формирующего М-последовательность, приведена на рис. 3.17.

Рис. 3.17. Цифровой автомат формирования М-последова-тельности

Его основу составляет сдвигающий регистр с триггерами , которые осуществляют задержку входного символа на один такт длительностью . Допустим, что используются различных символов: которые образуют конечное множество символов Символы на выходах триггеров при такте обозначены через причем Символ на входе первого триггера обозначен Символ на выходе триггера на такте , так как с каждым тактом символ со входа «переходит» на выход. Символы с выходов триггеров поступают на умножители, с выходов которых снимают символы Множители Поэтому, если операция умножения в множителе производится по модулю то символы

(кликните для просмотра скана)

Окончание табл. 3.6 (см. скан)

Смысл умножения по модулю становится понятным гари рассмотрении сравнения двух чисел по третьему числу (модулю). Два целых числа а и называются сравнимыми по модулю если при делении обоих чисел на их остатки равны. Сравнение двух чисел обозначается как

Остаток от деления любого числа на всегда меньше и лежит в пределах от 0 до Например, если то , так как остатки от деления обоих чисел равны двум. Сравнение (3.39) означает, что разность делится на без остатка, что иногда записывается Сравнимость двух чисел по модулю позволяет записать их в следующем виде: где любые целые числа; остаток, . В приведенном ранее примере Таким образом, сравнение по модулю означает перевод произвольного целого числа в конечное множество состоящее из элементов.

Умножение двух чисел по модулю производится следующим образом. Два числа перемножаются обычным образом, а их произведение переводится в конечное множество с помощью сравнения по модулю Умножение двух чисел по модулю записывается как при . Например, если то и для , т. е. число 8, которого нет в множестве переводится в число 3. Правило умножения двух чисел по модулю 5 определяется табл. 3.7.

Отметим, что каждая строка и столбец таблицы состоят из всех возможных символов множества содержат, за исключением нулевого столбца и строки, одинаковых символов. Это - является следствием того, что в качестве модуля взято простое число 5. Если составное число, то при умножении в одной строке или столбце могут оказаться одинаковые числа, т. е. операция умножения не будет однозначной. Для сохранения однозначности в качестве модуля берут простые числа.

Таблица 3.7. Умножение по

Таблица 3.8. Сложение по

Отметим, что умножение любого числа на нуль означает, что символ на выходе умножителя всегда (равен нулю. Это эквивалентно разрыву цепи между выходом триггера и сумматором. Следовательно, умножитель может быть опущен. Например, при (символы 0 и 1) множитель может принимать значение или О, или 1, т. е. выходы триггеров или подсоединены к сумматорам, или нет. После умножения суммирование производится также по модулю Сумма двух целых чисел переводится с помощью сравнения в конечное множество т. е. для Для примера в табл. 3.8 приведено правило сложения по модулю 5. Следовательно, в результате операций умножения и сложения получаются только элементы множества

Возвращаясь к работе сдвигающего регистра (см. рис. 3.17), можно записать, что символ на входе такте равен

Выражение (3.40) является линейным рекуррентным уравнением. Оно позволяет по известным символам на выходах триггеров найти символ который в последующем такте перейдет на выход .

Для такта состояние регистра характеризуется переменными, которые можно записать как

Анализ работы цифрового автомата формирования последовательности на основе рекуррентного уравнения (3.40) показывает, что работа этого автомата полностью определяется характеристическим многочленом

коэффициенты которого связаны с множителями следующим соотношением:

Отрицательные значения можно свести с помощью сравнения по к положительному числу множества

Для двоичных М-последовательностей, состоящих из символов множители и коэффициенты согласно (3.43) равны, т. е. причем

Таким образом, для определения структуры цифрового автомата необходимо знать характеристический многочлен степени Из теории М-последовательностей известно, что характеристический многочлен степени во-первых, должен быть неприводимым, т. е. его нельзя представить в виде произведения многочленов меньших степеней, а во-вторых, он должен быть первообразным (примитивным) относительно двучлена т. е. характеристический многочлен должен делить без остатка. Поэтому характеристический многочлен является первообразным корнем уравнения Если характеристический многочлен является первообразным, то он является и неприводимым.

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

Поскольку двоичные М-последовательности играли и играют особо важную роль в радиотехнических системах, то их свойства были изучены достаточно глубоко, в том числе и характеристические многочлены. Известны таблицы (см., например, [14]), в которых приведены неприводимые многочлены до степени В табл. 3.9 приведены в двоичной форме коэффициенты характеристических многочленов [15] для т. е. совпадающие с множителями в схеме цифрового автомата (рис. 3.17), т. е. Характеристическому многочлену в табл. 3.9 соответствует последовательность , представленных в виде 1 или 0. В каждом столбце указана степень многочлена и его коэффициенты. В табл. 3.9 приведены только те характеристические многочлены, которые порождают М-последовательности. Соответственно, период М-последовательности Знание коэффициентов позволяет однозначно построить цифровой автомат формирования М-последо-вательностей. Если то выход триггера подключен к сумматору по если то выход триггера к сумматору по не подключен.

(кликните для просмотра скана)

Окончание табл. 3.9 (см. скан)

В табл. 3.9 приведены значения коэффициента Коэффициент всегда по определению. Для определения структуры цифрового автомата, изображенного на рис. 3.17, необходимо учитывать коэффициенты

Для примера на рис. 3.18 изображена схема цифрового автомата формирования М-последовательности с В качестве характеристического многочлена взят многочлен с коэффициентами 10000001001 (первый в столбце с табл. 3.9). В соответствии с коэффициентами многочлена на

Рис. 3.18. Цифровой автомат формирования М-последовательностн с периодом

Таблица 3.10. Число М-последователыгостей (см. скан)

сумматор по поступают символы с выходов 7-го и 10-го триггеров.

Число М-последовательностей определяется следующим выражением:

где функция Эйлера (число чисел в ряду взаимно простых с числом число разрядов в сдвигающем регистре. Если простое число, то Значения для различных приведены в табл. 3.10 [4, 15].

В табл. 3.11 приведены все периоды М-последовательностей для в виде разложения на простые множители [14], из которой следует, что не все периоды М-последовательностей являются простыми числами. Это и объясняет нелинейный характер числа от

Длительность М-последовательности где согласно (3.32), то — длительность одиночного импульса (символа). Для двоичных М-последовательностей Если тактовая

Таблица 3.11. (см. скан) Разложение на простые множители

Таблица 3.12. (см. скан) Периоды М-последовательностей различной длины стактовой частотой следования 1 МГц

частота в сдвигающем регистре то табл. 3.12 приведены длительности периода М-последовательности для с тактовой частотой [7].

Характеристики апериодических корреляционных функций. Периодическая АКФ последовательностей имеет характерный вид, представленный на рис. 3.15. Боковые пики ПАКФ равны Поскольку -последовательности достаточно просто формируются и обладают такими малыми боковыми пиками в периодическом режиме, то они с самого открытия до настоящего времени находятся под пристальным вниманием разработчиков радиотехнических систем. Одним из главных «направлений исследований является изучение свойств М-последовательностей в апериодичеоком режиме, что характерно для передачи информации в системах связи. К настоящему времени накоплены сведения по корреляционным свойствам М-последовательностей в апериодическом режиме — как по АКФ, так и по ВКФ. Имеются многочисленные данные по конкретным АКФ и ВКФ

Рис. 3.19. АКФ М-последовательности

М-последовательностей различной длины, а также обобщенные характеристики корреляционных функций. На рис. 3.19 изображен пример АКФ М-последовательности с Из рис. 3.19 видно, что боковые пики АКФ В апериодическом режиме существенно больше боковых пиков ПАКФ. Приведем лишь основные характеристики КФ М-последовательностей.

Таблица 3.13. Характеристики корреляционных функций -последовательностей и случайных последовательностей

В табл. 3.13 [16] приведены основные характеристики корреляционных функций (АКФ и ВКФ) М-последовательностей и случайных последовательностей. Последние приведены для сравнения их свойств со свойствами М-последовательностей. В качестве характеристик взяты следующие:

среднеквадратическое значение боковых пиков определяемое через дисперсию

среднее значение модулей боковых пиков

среднеквадратичное значение модулей боковых пиков, определяемое через дисперсию

а также значение максимального бокового пика . В табл. 3.13 все характеристики приведены в ненормированном виде, т. е. умножены на В результате цифры, приведенные в табл 3.13, характеризуют превышение уровня Отметим, что среднее значение боковых пиков Во второй строке табл. 3.13 приведены характеристики АКФ, а в третьей строке — характеристики ВКФ М-последовательностей [16]. Из сравнения цифровых данных второй и третьей строк следует, что ВКФ М-последовательностей имеет большие боковые пики по

сравнению с боковыми ликами АКФ. В четвертой строке приведены характеристики КФ (АКФ и ВКФ) случайных последовательностей, относительно которых было предположено, что их КФ распределены по нормальному закону

с дисперсией Соответственно Как видно из сравнения третьей и четвертой строк табл. 3.13, характеристики ВКФ М-последовательностей близки к статистическим характеристикам случайных последовательностей, что и является обоснованием названия «псевдослучайные последовательности» для М-последовательностей и им подобных. На рис. 3.20, а [16] приведен пример ВКФ двух М-последовательностей длиной Вместе с тем, некоторые пары М-последовательностей имеют периодические ВКФ, отличающиеся от случайных, так как такие ВКФ имеют всего три уровня (рис. 3.20, б):

Рис. 3.20. ВКФ и ПВКФ М-последовательностей

М-последовательности, имеющие трехуровневые ПВКФ, называются также последовательностями Голда [5, 16, 17]. Более подробно они будут рассмотрены в параграфе, посвященном системам сигналов. Отметим, что последовательности Голда имеют ПВКФ, максимальные значения которых близки к Вместе с тем, надо подчеркнуть, что последовательности Голда составляют только часть М-последовательностей, т. е. их число мало.

Функция неопределенности. Можно показать, что исходя из ограниченности объема тела неопределенности произвольного сигнала (2.34), среднеквадратичное значение ФН равно На рис. 3.21 приведена ФН М-последовательности с N=15.

Рис. 3.21. Функция неопределенности М-последовательности

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