6.9. Структура расстояний сверточных кодов

Исследование расстояний между кодовыми словами является важным при анализе свойств кодов. Следуя Месси [17, 18], получим сначала аналоги верхней границы Плоткина и нижней границы Варшамова — Гилберта для минимального расстояния систематических сверточных кодов. Далее остановимся на введенном Костелло [19] понятии свободного расстояния, которым удобно пользоваться для описания расстояния кодов, используемых при последовательном декодировании, и в заключение рассмотрим несколько алгоритмов построения сверточных кодов со скоростью

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

то систематический сверточный код можно задать с помощью порождающих многочленов следующим образом:

При рассмотрении декодирования с обратной связью всегда будем считать, что при

6.9.1. Верхняя граница Плоткина при декодировании с обратной связью

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

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

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

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

Из равенства (6.160) непосредственно следует, что максимальное значение в классе всех сверточных кодов со скоростью порождаемых кодерами с -разрядными регистрами сдвига, является верхней границей для Это максимальное значение обозначим через Для Месси была получена следующая верхняя граница:

Для доказательства этого неравенства нам понадобятся следующие свойства величины как функции

Свойство 1.

Так как минимум в (6 160) берется по всем кодовым последовательностям, каждый подблок из символов которых содержит информационных символов, то естественно, что минимум в (6.162) берется и по всем кодовым последовательностям, порождаемым информационными подблоками последние символов которых равны нулю. Минимизация только по таким кодовым последовательностям эквивалентна нахождению минимального расстояния сверточного кода, на вход кодера которого в каждый момент времени подается один информационный

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

Свойство 2. Для любого нечетного

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

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

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

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

Далее, произвольный подблок представим в следующем виде:

Второе слагаемое в правой части (6.164) представляет собой вектор длины не зависящий от Следовательно, векторы соответствующие являются дополнительными. Так как по предположению нечетное число, то, выбрав равным 0 или 1, можно добиться того, что вес -мерного вектора не будет превышать Поскольку вышеизложенное справедливо при любом то в любом коде с всегда существует кодовое слово, вес которого не превосходит Это доказывает свойство 2.

Свойство 3. При любом четном

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

где — матрицы, все элементы которых равны 0. Обозначим через

и

векторы соответственно из информационных и проверочных двоичных символов нового кода в момент времени По определению

Блоки кодовых слов нового кода, как легко видеть, являются также блокам и кодовых слов исходного кода, порождаемого матрицами и могут быть найдены с помощью равенства (6.159). Согласно равенству (6.160), минимальное расстояние нового кода определяется равенством

Можно показать, что правая часть равенства (6.170) к тому же является минимальным расстоянием исходного кода. Действительно, минимум по всем информационным последовательностям, для которых (в этом случае равен минимальному расстоянию по определению. Так как при вектор не может иметь вес, меньший то, очевидно, что вес вектора также не меньше Следовательно, правая часть равенства (6.170) равна Отсюда следует неравенство (6.162).

Свойство 4.

Это свойство очевидно.

Используя приведенные выше свойства, докажем следующую теорему.

Теорема 6.6 (Месси.) Величина удовлетворяет следующему неравенству.

Доказательство. Сначала рассмотрим случай, когда нечетно. Из свойств 1, 3, 4 непосредственно следует, что

Отсюда и из свойств 1 и 2 получаем

Предположим, что четное. Тогда, согласно свойствам 1 и 2,

Подставляя в (6.172), получаем следующее асимптотическое неравенство: