14.9. Каскадные коды

Если прямое произведение кодов кодируется и декодируется каскадным образом, как показано на рис. 14.2, то такая система передачи является частным случаем системы, представленной на рис. 14.5 и исследованной впервые Форни [1966 b].

Рис. 14.5. Система с каскадным кодированием и декодированием.

Этот раздел представляет собой краткое введение в работу Форни.

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

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

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

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

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

Так как достаточно велико, то в качестве выходного кода можно выбрать код Рида — Соломона -код). Из результатов разд. 13.3 известно, что -код имеет наибольшее минимальное расстояние среди всех линейных кодов с той же скоростью и той же блоковой длиной. В гл. 10 было показано, что к -кодам, как и ко всем

БЧХ-кодам, применимы эффективные алгебраические методы кодирования и декодирования.

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

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

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

Форни [1966b] вычислил также характеристики системы, в которой внутренний декодер может передавать выходному декодеру некоторые дополнительные сведения. Улучшение экспоненты вероятности ошибки при каскадном декодировании можно получить, если позволить внутреннему декодеру передавать выходному декодеру, помимо каждого декодируемого блока, оценку вероятности его правильного декодирования. Если такую оценку не передавать, то максимальная экспонента каскадного декодирования уменьшается вдвое. Если внутренний декодер не передает оценки вероятности правильного декодирования, но стирает все неоднозначные внутренние блоки, то общая экспонента составляет две трети от максимально достижимой.

Читателя, заинтересованного в более подробном изучении каскадных кодов, мы отошлем к монографии Форни [1968].

Каскадные коды Форни и итеративные коды Элайеса не являются единственно известными методами построения реализуемых систем связи, сложность декодирования в которых растет сравнительно

медленно с ростом блоковой длины. Эпштейн [1958а] предложил такую систему для двоичного канала со стиранием; Хорстейн [1963], Берлекэмп [1964а] и Шелквик с Кейласом [1966] построили такие системы для каналов с бесшумной обратной связью. Возенкрафт и Рейффен [1961], Фано [1963], Галлагер [1963], Зив [1962, 1966, 1967], Пинскер [1968] и Фэлконер [1967] предложили такие системы для каналов без обратной связи и без стирания.