5.3. Верхняя граница с выбрасыванием для симметричного по выходу канала с двоичным входом

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

Для каналов с двоичным входом это выражение сводится к следующему:

где

Таким образом, показатель экспоненты сверточного кодирования, полученный выше, при малых скоростях меньше показателя экспоненты блочного кодирования. Как уже указывалось в § 3.10, нельзя осуществить вычеркивание кодовых векторов из линейного кода, не нарушив его линейности. Для сверточных кодов вычеркивание привело бы не только к нарушению линейности, но и в равной степени нарушило бы важную топологическую структуру решетки. Однако для класса симметричных по выходу каналов с двоичным входом в § 2.9 было установлено, что для линейных кодов вероятность ошибки одна и та же, независимо от того, какое кодовое слово передается. Следовательно, для этого класса каналов необходимости в проведении вычеркивания нет, поскольку граница для вероятности ошибки на бит для любого переданного пути является границей для вероятности ошибки кода в целом (не зависящей от переданного пути).

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

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

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

Тогда для среднего по ансамблю значения имеем

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

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

где Наконец, полагая получаем

где, как и в § 3.3,

Подставляя (5.3.6) в (5.3.3), имеем

где нат/символ канала.

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

Выберем таким образом, что

Наконец, проводя максимизацию по получаем следующую теорему.

Теорема 5.3.1. (Витерби и Оденвальдер [1969].) Для симметричного по выходу канала с двоичным входом существует изменяющийся во времени сверточный код с длиной кодового ограничения К и скоростью бит/символ, для которого вероятность ошибки на бит при декодировании по максимуму правдоподобия удовлетворяет неравенству

Можно выразить показатель экспоненты непосредственно через скорость, так как для симметричных по выходу каналов с двоичным входом, как это было установлено в § 3.3,

где

Из (5.3.11) и (3.3.29) находим, что следовательно,

Если первое из уравнений (5.3.11) разделить на второе и воспользоваться формулой (5.3.12), то получим Следствие 5.3.1. Показатель экспоненты в (5.3.11) может быть представлен в виде

Рис. 5.5. Ансамбль с выбрасыванием и границы сферической упаковки для сверточных и блочных кодов в канале с двоичным входом и симметричным выходом

Отсюда, в свою очередь, следует, что

Отметим, что выражение в правой части последнего равенства точно совпадает с выражением для показателя экспоненты блочных кодов (3.3.31) при нулевой скорости передачи.

График показателя экспоненты (5.3.13) приведен на рис. 5.5, на котором для сравнения дан также соответствующий график показателя экспоненты для блочных кодов.