5.7.2. Симплексные коды и m-последовательности

Симплексным кодом называется линейный код, порождающая матрица которого равна проверочной матрице кода Хэмминга, т.е. симплексный код дуален к коду Хэмминга [30]. Свое название код получил потому, что его слова, рассматриваемые как многомерные векторы, образуют правильную многомерную фигуру, называемую симплексом.

Так как существует много эквивалентных друг другу кодов Хэмминга, отличающихся перестановкой столбцов проверочной матрицы, то имеется и много эквивалентных симплексных кодов. Среди них есть и код с порождающей матрицей, столбцами которой являются целые числа, записанные в двоичной системе счисления.

Подобная матрица уже рассматривалась в 5.7.1 как часть порождающей матрицы кода Рида-Маллера. Действительно, если в матрице (5.34) исключить первую строку и первый столбец, то получим все  ненулевых различных столбцов, т.е. порождающую матрицу симплексного кода. Исключение первой строки, состоящей из единиц, можно трактовать как формирование слов кода Рида-Маллера при , а исключение первого столбца означает исключение первого (нулевого) символа из слов Рида-Маллера. Таким образом, симплексный код получается из кода Рида-Маллера путем отбрасывания при  первого символа, равного 0 для всех  слов (см. левую часть табл. 5.8).

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

В технических приложениях большое значение имеет циклический симплексный код, столбцы порождающей матрицы которого являются степенями примитивного элемента поля Галуа :

.

(5.37)

Порождающая матрица вида (5.37) указывает простой способ формирования базисных векторов кода путем последовательного умножения элементов поля  на . Устройства умножения на  представляют собой сдвигающий регистр, охваченный линейной обратной связью [10].

Отметим, что помехоустойчивость симплексного кода всегда выше, чем ортогонального, так как при равных кодовых расстояниях слово симплексного кода на 1 элемент короче и, следовательно, энергия, приходящаяся на один символ, больше. Правда, при увеличении  выигрыш уменьшается, стремясь к 0.

На первый взгляд каждая комбинация симплексного кода похожа на случайную последовательность единиц и нулей, из-за чего слова этого кода часто называют псевдослучайными последовательностями (ПСП), -последовательностями (отмечая связь с параметром кода ), линейными рекуррентными последовательностями, последовательностями максимальной длины. Все эти названия отражают специфические свойства слов симплексного кода.

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

Перечислим основные структурные свойства -последовательностей. Рассмотрим бесконечную -последовательность, получаемую, например, в результате бесконечного умножения элементов поля на  или с выхода генератора -последовательности.

1. Последовательность  удовлетворяет рекуррентному соотношению для всех :

,

(5.38)

где    – известные двоичные числа (коэффициенты минимального многочлена примитивного элемента поля).

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

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

Это объясняется тем, что степени примитивного элемента  пробегают все  ненулевых элементов поля, т.е. все различные -разрядные векторы.

3. В -последовательности число единиц равно , а число нулей , что очевидно, так как слово симплексного кода может быть получено путем исключения первого нулевого символа из слов кода Рида-Маллера, у которых число единиц и нулей одинаково и равно . Приблизительно равное соотношение символов 0 и 1 имеет место для отрезка из  символов, взятого в любом месте бесконечной последовательности. Для наблюдателя, не знающего закона формирования последовательности (5.5), появление 0 и 1 происходит примерно с равными вероятностями. Если же рекуррентное соотношение (5.5) известно, то по любому отрезку из  символов можно восстановить все оставшиеся символы последовательности. Этим и объясняется название «псевдослучайная» последовательность.

4. Сумма -последовательности и ее циклического сдвига есть -последовательность, удовлетворяющая тому же рекуррентному соотношению, но с другим сдвигом.

Это следует из того, что циклический сдвиг ПСП принадлежит симплексному коду, а сумма кодовых слов линейного кода есть слово данного кода (см. 5.4.1).

Таким образом, симплексный циклический код содержит один нулевой вектор, а остальные  являются циклическими сдвигами одной -последовательности, заданной (5.38). Эти сдвиги, называемые также фазами ПСП, можно пронумеровать различными -разрядными векторами и сопоставить их с состояниями сдвигающего регистра. Отсюда понятен способ получения ПСП с заданной фазой: в сдвигающий регистр генератора записывается номер фазы, и за и тактов работы генератора формируется требуемая ПСП.

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

Так как корреляционная функция определена для последовательностей с действительными компонентами, то далее предполагается, что двоичные символы -последовательности заменены на +1 и –1 с помощью отображения (5.36). По определению, нормированная ПАКФ бесконечной последовательности  с периодом

,

где    – число тактов сдвига.

После несложных преобразований можно получить

,

где    и  – соответственно числа совпадений и несовпадений символов последовательности  и ее циклического сдвига, причем . Тогда

,

т.е. боковые лепестки ПАКФ -последовательности постоянны и равны .

Вид ПВКФ -последовательностей зависит от многих факторов, в том числе и от соотношения между периодами ПСП: периоды равны, взаимно просты или произвольны. Для частных случаев получены или точные, или верхние границы значений взаимно-корреляционных функций. Например, нормированная ПАКФ -последовательностей с взаимно простыми периодами имеет при любых сдвигах одинаковые значения, равные , где  и  – соответственно вероятности совпадения и несовпадения символов двух ПСП.

Корреляционные свойства одиночных (непериодических) ПСП также зависят от многих факторов. Многочисленные исследования показывают, что можно подобрать несколько ПСП или отрезков одной ПСП с удовлетворительными АКФ и ВКФ. Относительно боковых лепестков АКФ одиночных ПСП известно, что их максимальный уровень не превышает .

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

Существование разных ПСП одного периода объясняется наличием в конечном поле Галуа нескольких примитивных элементов.