4.5. Некоторые случаи и примеры

Довольно поучительным является рассмотрение ДСК и АБГШ канала с двоичным входом, которые представляют собой частные случаи каналов, рассмотренных выше. Ясно, что граница Бхаттачария для этих каналов справедлива со значениями параметров [см. (2.11.6), (2.11.7), (3.4.15) и (3.4.17)]

Заметим также, что если бы АБГШ канал сводился к ДСК путем жесткого квантования, то, как уже было показано в § 2.11, при следовательно,

т. е. величина уменьшилась бы в раз, что эквивалентно проигрышу приблизительно в отношении сигнал-шум.

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

Это выражение может быть использовано в средних частях неравенств (4.4.6) и (4.4.8) для получения более точных результатов, чем (4.4.7) и (4.4.12) (см. также задачу 4.10).

Аналогично для АБГШ канала из (2.3.10) следует, что попарная вероятность ошибки для кодовых векторов, находящихся друг от друга на расстоянии определяется равенством

Более элегантный и полезный результат получится, если не только подставить это равенство вместо в приведенные выше выражения, но и заметить (см. задачу 4.8), что

Так как то для (4.5.4) можно записать следующую верхнюю границу:

Она является более точной, чем граница Бхаттачария. Используя эту границу для оценки слагаемых в средних частях неравенств (4.4.5) и (4.4.8) и, далее, применяя равенства (4.4.6) и (4.4.10), получаем:

Последняя граница очень эффективна при получении точных верхних границ вероятности ошибки на бит для АБГШ канала с двоичным входом и различных сверточных кодов с длиной кодового ограничения, меньшей 10. При этом нахождение для кода с длиной кодового ограничения К связано с аналитическим решением системы алгебраических уравнений (см. § 4.3), а вычисление при фиксированных значениях сводится просто к численному обращению матрицы. Так как порождающая функция представляет собой многочлен от с неотрицательными коэффициентами и неубывающей при положительных значениях аргумента первой производной, то производная при может быть оценена сверху численными методами путем вычисления нормированной первой разности. Итак,

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

Рис. 4.12. Пример ошибочных событий: а) ; б) моделирование при квантовании на восемь уровней и хранении указателей путей длиной 32 бита; верхние границы для АБГШ канала без квантования. моделирование; верхняя граница (Приводятся с разрешения Хеллера и Джекобса [1971].)

ментами своих строк [ом. (4.3.1) и задачи 4.17 и 4.18]. В результате обращение может быть сведено к вычислению значений быстро сходящегося ряда степеней заданной матрицы (ом. задачу 4.18). Результаты вычислений для оптимальных сверточных кодов со скоростью 1/2 и длинами кодовых ограничений от 3 до 8 приведены на рис. 4.12. Для того чтобы оценить точность этих границ, на рисунке приведены результаты моделирования для тех же самых кодов при квантовании выходного сипнала на восемь уровней. В области малых вероятностей ошибок как видно из рисунка, верхняя граница лежит несколько ниже кривой, полученной при моделировании. Результаты моделирования в действительности и должны лежать выше расчетной кривой, так как потери из-за квантования имеют величину порядка Этот же порядок имеет расхождение между результатами моделирования и верхними границами, что говорит о точности последних.

Для всех кодов, рассматривавшихся до пор, предполагалось, что соответствующие им порождающие функции

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

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

порождающих последовательностей кода. Для кодов со скоростью Месси и Сайн [1968] получили такие условия — в терминах порсждаюших многочленов кода следующим образом, определяемых через порождающие последовательности

Рис. 4.13 Кодер, показывающий катастрофическое распространенно ошибок, и его диаграмма состояний

В терминах этих многочленов теорема Месси и Сайна утверждает, что фиксированный сверточный код является катастрофическнм, если и только если все порождающие многочлены имеют общий делитель (многочлен) степени, не меньшей Представляется также интересным вопрос о том, какую часть ансамбля всех сверточных кодов с заданной длиной кодового ограничения и заданной скоростью составляют катастрофические коды. Форни [1970] Розенберг [1971] показали, что для кодов со скоростью эта часть равна и не зависит от длины кодового ограничения (см. задачу 4.12). Таким образом, поиск хороших кодов не слишком затрудняется наличием катастрофических кодов, поскольку последних относительно мало и их легко отличить.

Один из подклассов некатастрофичесшх сверточных кодов образуют систематические сверточные коды. Как и систематические

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

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

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

Таблица 4.1. Максимальное свободное расстояние для некатастрофических кодов

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