3.9 Комбинирование кодов

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

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

В итоге после прохождения цепочки из р кодеров на выходе имеем комбинацию линейного блочного кода, содержащую те же k информационных символов и r = r₁ +…+ r_p проверочных символов. Возрастают избыточность кода и его корректирующая способность.

Пример 1. Двумерный композиционный код получается следующим образом. Прямоугольная таблица, содержащая n₁ столбцов и n₂ строк, делится на четыре блока. Левый верхний б

1 0 0 1 1 0 1 0 0 0 1 1 1 0 1 1 0 0 1 1 0	0 1 0
0 1 0 0 1 0 1	1

Рис. 3.9. Пример кодирования двумерным композиционным кодом (32,21)

лок (k₁ столбцов и k₂ строк) заполняется информационными символами от источника. Затем каждая строка отдельно кодируется (n₁,k₁) линейным блочным кодом, при этом r₁ = n₁ – k₁ проверочных символов каждой строки помещают в правый верхний блок. Далее каждый столбец кодируется (n₂,k₂)-кодом. В итоге получим новый (n,k)-код, где n = n₁n₂, k = k₁k₂. На рис. 3.9 приведен пример кодирования, когда на обоих этапах используется код с проверкой на четность.

Одиночная ошибка нарушает условие четности в соответствующих строке и столбце, поэтому ее положение может быть определено, но две ошибки код уже исправить не может. Однократное кодирование кодом с проверкой на четность позволяет лишь обнаруживать одиночные ошибки, но не исправлять их. Итак, применение двукратного кодирования позволило повысить коррек­тирую­щую способность кода. При этом интересно посмотреть, велика ли цена. Из Приложения 1 мы видим, что примерно те же значения параметров имеет (31,21)-код БЧХ, но он способен исправлять и любые двукратные ошибки.

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

Декодирование кода также проводится в два этапа. На первом этапе принятая комбинация подвергается общей проверке на четность, в результате которой получают ответ на вопрос, четной или нечетной является кратность ошибок. Затем последний проверочный символ отбрасывается, и по оставшимся символам вычисляется синдром по правилам декодирования кода Хэмминга. Сопоставление результатов на обоих этапах позволяет даже определить кратность ошибки (сам по себе код Хэмминга на это не способен) и в зависимости от этого предпринять нужные действия (если ошибка однократная, код Хэмминга ее может исправить; если двукратная или трехкратная, нужно сделать запрос на повторную передачу комбинации). Снова отметим, что такими же характеристиками обладает код Рида-Малера с кодовым расстоянием, равным четырем.

Множество примеров показывает, что всегда можно найти такой код, который при тех же значениях n и k при использовании одноэтапной процедуры кодирования обеспечивает лучшую (или не худшую) помехоустойчивость, чем каскадный код, формируемый в несколько этапов. Зачем же тогда применяются каскадные коды? Лишь потому, что на каждом этапе можно использовать относительно простые и короткие коды и менее трудоемкие методы кодирования и декодирования. В частности, при записи на компакт-диск требуется применять код, способный исправлять пакеты, содержащие тысячи ошибок. И он реализуется путем многократного последовательного выполнения операций перемежения и кодирования кодом Рида-Соломона.

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