Принципы построения каскадных кодов

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

Каскадные коды строятся по принципу поэтапного применения двух или более процедур кодирования к последовательности передаваемых информационных символов. При этом символами кода последующего этапа (ступени) кодирования являются слова кода предыдущей ступени. Процедура кодирования двоичным каскадным кодом сводится к следующему. Последовательность двоичных символов передаваемого сообщения разбивается на K k -элементных блоков. Каждый k -элементный блок рассматривается как символ нового (q -ичного) алфавита и подлежит кодированию (N, K) q -ичным кодом. В результате реализации процедуры кодирования (N, K)-кодом к k -элементным блокам добавляется N – K избыточных k -элементных блоков или символов q -ичного алфавита. Предполагается, что эти избыточные символы имеют представление в виде k -элементных двоичных последовательностей. (N, K)-код получил название кода второй ступени или внешнего кода. Каждый из N k -элементных символов внешнего кода кодируется двоичным (n, k)-кодом первой ступени.

Код первой ступени называют также внутренним кодом. Процедура каскадного кодирования поясняется рис. 9.2. В результате кодирования получается двоичный блок длиной N × n, являющийся кодовой комбинацией каскадного кода.

В теории кодирования доказано, что построенный указанным способом каскадный код является линейным и его кодовое расстояние D_k не меньше, чем произведение кодовых расстояний внешнего (D) и внутреннего (d) кодов:

D_k ≥ D ∙ d.

Двоичная информационная последовательность, подлежащая кодированию каскадным кодом, поступает во внешний кодер, где разбивается на k -элементные блоки, каждый из которых рассматривается внешним кодером как q -ичный символ в двоичном представлении. Для каждых K таких q -ичных символов внешний кодер формирует N – K избыточных q -ичных символов, т. е. k -элементных блоков. Информационные и избыточные k -элемент­ные блоки затем поступают во внутренний кодер, где преобразуются в кодовые комбинации двоичного (n, k)-кода. Структура системы каскадного кодирования представлена на рис.9.3.

Блок длины n передается по каналу и поступает во внутренний декодер. Поток данных, поступающий на выход внутреннего декодера, состоит из k -элементных блоков, которые рассматриваются внешним декодером как символы (N, K)-кода. На выходе внешнего декодера формируются K k -элементных блоков, поступающих к потребителю информации.

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

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

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

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

Эффективность использования каскадных кодов повышается за счет некоторой декорреляции ошибок, появляющихся в k -эле­ментных блоках в результате поэтапной процедуры декодирования.

2. Режимы использования каскадных кодов

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

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

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

Таким образом, возможны следующие режимы использования каскадных кодов:

- исправление ошибок внутренним и внешним кодами;

- обнаружение ошибок внутренним и исправление стираний внешним кодами;

- обнаружение ошибок внутренним и исправление стираний и ошибок внешним кодами;

- частичное исправление и обнаружение ошибок внутренним и исправление стираний внешним кодами;

- частичное исправление и обнаружение ошибок внутренним и исправление стираний и ошибок внешним кодами.

Наиболее прост в реализации второй алгоритм. Он требует минимальной избыточности, особенно в случае формирования стираний элементов по оценке надежности их приема, т. е. при применении косвенных методов повышения достоверности. Исправление стираний q -ичным кодом реализуется значительно проще, чем исправление ошибок и сводится к решению линейной однородной системы уравнений над полем GF (q). При использовании в качестве внешнего кода РС-кода с D = N – K +1 возможно исправление всех стираний кратности Δ= N – K. Ошибочное декодирование блока при этом происходит в двух случаях: при необнаружении ошибок внутренним кодом и при обнаружении ошибок более чем в Δ комбинациях внутреннего кода.

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

Один из таких методов описан в [5] применительно к системе с обратной связью. По прямому каналу передаются блоки внутреннего (n, k)-кода, которые на приемной стороне проверяются на наличие ошибок и при их обнаружении стираются. Первые K блоков (n, k)-кода рассматриваются как информационные элементы PC-кода (N, K), и по ним генерируются проверочные элементы этого кода, которые сравниваются с поступающими от передатчика избыточными элементами PC-кода, а при их несовпадении стираются. Как только приемником будет принято всего K нестертых блоков, восстанавливаются стертые информационные элементы (N, K)-кода и по обратному каналу посылается команда прекращения передачи. В этом случае избыточность сокращается за счет неполной передачи избыточных элементов PC-кода. При отсутствии ошибок они вообще не передаются. Назовем этот метод методом ограничения избыточности.

Возможен другой метод – метод запроса дополнительной избыточности. Он предполагает применение укороченных PC-кодов. В этом случае для каждого набора K информационных блоков передатчик формирует несколько наборов избыточных элементов различной длительности: N₁ – K, …, N_i – K. Передача начинается с (N ₁, K) PC-кода. Если приемник из N ₁ элементов PC-кода принял K нестертых элементов, то методом исправления стираний восстанавливаются K информационных элементов. Если при длине N ₁, число нестертых элементов меньше K, то приемник запрашивает следующий по длительности набор избыточных элементов и т. д. до тех пор, пока на длине информационной и избыточной части не будет принято нестертыми K элементов PC-кода.

В этом случае избыточность сокращается за счет повторной передачи только избыточности PC-кода без повторной передачи информационных элементов.

Указанные достоинства каскадных кодов делают их перспективными для использования в аппаратуре передачи данных.

3. Построение двоичных каскадных кодов на основе кодов Рида–Соломона и Боуза–Чоудхури–Хоквингема

Двоичный каскадный код может быть построен на основе PC-кода следующим образом:

1. Двоичные информационные элементы сообщения разбиваются на K подблоков по k элементов в каждом. Каждый подблок из k элементов записывается как элемент поля GF (2 ^k), в результате чего получаем последовательность из K элементов GF (2 ^k).

2. K -элементная последовательность элементов GF (2 ^k) кодируется (N, K) PC-кодом над GF (2 ^k). В результате получаем кодовую комбинацию внешнего кода.

3. Каждый из N элементов внешнего кода, являющийся двоичной последовательностью длины k, кодируется двоичным (n, k)-кодом с минимальным расстоянием d – внутренним кодом.

Полученный таким образом двоичный каскадный код имеет следующие параметры: N_k = N ∙ n, K_k = K × k, D_k ≥ D ∙ d.