14.5. ГРАНИЦЫ МИНИМАЛЬНОГО РАССТОЯНИЯ ДЛЯ СВЕРТОЧНЫХ КОДОВ

Минимальное 1-е расстояние для сверточного кода с длиной блока определяется как минимальное расстояние Хэмминга среди всех пар начальных сегментов кодовых слов длины кадров, у которых первые кадры различны. Минимальное расстояние сверточного кода равно а свободное расстояние определяется соотношением

В этом параграфе мы найдем границы типа границ Гилберта и Элайса для

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

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

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

Пусть объем алфавита фиксирован; определим

где максимум берется по всем сверточным кодам с длиной блока и скоростью означает минимальное расстояние для кода Функция определяет наибольшее минимальное расстояние по всем сверточным кодам над со скоростью и длиной блока Обозначим, далее,

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

Аналогичные определения можно дать и для свободного расстояния. В зависимости от того, что рассматривается: отношение свободного расстояния к длине блока или к свободной длине, можно получить различные функции. Определим

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

Обозначим, далее,

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

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

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

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

Теорема 14.5.1 (граница Элайса). Для двоичного сверточного кода со скоростью функция удовлетворяет условию

при любом таком, что

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

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

Прежде чем доказывать границу Гилберта, необходимо доказать лемму. Лемма касается начального сегмента кодового слова

сверточного кода, т. е. сегмента кодового слова, состоящего из первых символов.

Лемма 14.5.2. Ничальный сегмент кодового слови, начинающийся с ненулевого кодра, входит точно в различных систематических сверточных -кодов с длиной слова

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

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

Теорема 14.5.3. Пусть при заданной скорости и длине блока величина удовлетворяет условию

Тогда существует хотя бы один систематический сверточный код над минимальное расстояние которого больше

Доказательство. Минимальное расстояние сверточного кода больше если код не содержит начального сегмента кодового слова длины и веса не больше у которого некоторый информационный символ первого кадра отличен от нуля. В множестве

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

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

Ненулевые -последовательности веса, не превышающего можно выбрать

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

то должен существовать хотя бы один код с минимальным расстоянием, большим Теорема доказана.

Следствие 14.5.4 (граница Гилберта). Для двоичных сверточных кодов

Доказательство. При теорема утверждает, что

Следовательно,

Отсюда, используя теорему 14.4.1 и переходя к пределу, получаем утверждение следствия.

ЗАДАЧИ

(см. скан)

(см. скан)

ЗАМЕЧАНИЯ

Распределение весов кода с максимальным расстоянием было найдено независимо Ассыусом, Мэттсоном и Турином [1965]. Форни [1966], Касами, Лином и Питерсоноы [1966]. Тождество Мак-Вильямс было выведено ею в 1963 г. В этой же статье она дала свою трактовку связи между распределением весов и

вероятностью ошибки декодировании. Иная трактовки принадлежит Форни [1966] и Хунгуну и Михельсону [1977]. Использование диаграммы состояний для нахождения распределения весов сверточного кода предложил Витерби [1971] Нижняя граница минимального расстояния блоковых кодов опубликована Гилбертом [1952]. Элайс никогда не публиковал свою верхнюю границу; впервые она появилась в его лекциях в 1960 г. Известны и лучшие верхние границы, но они доказываются гораздо сложнее Наилучшая известная верхняя граница найдена Мак-Элисом, Родемичем. Рамсеем и Велчем [1977]. В недавно выполненной в СССР работе показано, что в граница Гилберта может быть улучшена.