6.7. Кодирование в каналах с памятью

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

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

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

6.8. Сверточные (решетчатые) коды

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

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

Двоичный сверточный кодер показан на рис. 6.6. Он состоит из сдвигового регистра с ячейками памяти и блока сумматоров по . Длина регистра - длина кодового ограничения. Входы сумматоров связаны с выходами ячеек памяти регистра в зависимости от значений коэффициентов . На каждом такте в регистр последовательно поступает очередной блок из информационных символов, а его крайних правых ячеек освобождаются. Из сумматоров выходные символы числом последовательно считываются через коммутатор в канал. Растущих задержек во времени нет, если скорость передачи символов по каналу , - скорость поступления символов в кодер. Более общее представление сверточного кодера - регистрами сдвига с кодовыми ограничениями , . В каждый из них приходит информационный символ за такт.

Рис. 6.6. Структура двоичного сверточного кодера

Пример 6.8.1. На рис. 6.7 показан сверточный кодер ( и ). Информационная последовательность из дает кодовую последовательность из . Табл. 6.2 - пример получения кодовой последовательности.

Рис. 6.7. Двоичный сверточный кодер для кода со скоростью

Таблица 6.2. Получение кодовой последовательности в кодере рис. 6.7

Вход	0	0	1	0	0	0	1	1	0	0	0
Выход			11	10	11	00	11	01	01	11	00

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

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

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

Сверточные коды – линейная реализация решетчатых кодов. Решетка удобна для описания кодов. Решеткой называют ориентированный граф с периодической структурой ячеек. Каждая ячейка содержит колонки из одинакового числа вершин (узлов), соединенных ребрами. Процедура кодирования взаимно однозначно соответствует решетке:

а) каждый узел соответствует внутреннему состоянию кодера;

б) каждое ребро соответствует одному из возможных символов источника; в частности, для двоичного источника из каждой вершины исходит два ребра: верхнее – для и нижнее – для ;

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

г) последовательности ребер (пути на решетке) соответствует последовательность символов, которые может выдать источник.

Пример 6.8.2. Состояние кодера рис. 6.7 задано содержимым ячеек и регистра сдвига. Этих состояний на решетке кодера - (см. рис. 6.8).

Рис. 6.8. Решетка кодера, показанного на рис. 6.7

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

а) они не требуют синхронизации по блокам, а лишь синхронизации коммутаторов при передаче и приеме;

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

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

г) сверточные коды допускают простое объединение операций кодирования и модуляции (кодированная модуляция, см. п. 6.9).

Рекуррентный алгоритм декодирования Витерби (АВ) оптимален для сверточных кодов в каналах без памяти. Применим его для мягкого декодирования в постоянном канале с аддитивным белым гауссовским шумом. Пусть известен сигнал длительности , принимаемый на ом тактовом интервале. Евклидовы (или гильбертовы) расстояния между ним и всеми сигналами , ожидаемыми для ого символа в месте приема, , , . Ребрам решетки последовательно припишем на ых ее звеньях значения . В двоичном коде . Оптимальное по максимуму правдоподобия декодирование означает выбор пути на решетке (последовательности непрерывно следующих ребер), где минимальна. Чтобы найти минимум на решетке (последовательности передаваемых символов) длины , не надо перебирать возможных вариантов. Для каждой вершины на данном шаге (такте) есть ряд метрик (расстояний), соответствующих соединенным с ней ребрами вершинам на предыдущем шаге. Из этих ребер оставим одно, дающее минимум суммы метрик на всех предыдущих шагах.

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

Пример 6.8.3. Алгоритм выбора возможных путей для решетки с мя состояниями поясняет рис. 6.9. Над ребрами отмечены их метрики.

Рис. 6.9. Решетка с метриками

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

0

0

0,3

0

0,8

0,5

Рис. 6.10 Построение выжившего пути по АВ

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

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

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