15. Итеративные и каскадные коды

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

Нужно передать, к примеру, девять информационных символов m = ( m₀ , m₁ , ..., m₈ ). Эти символы можно расположить в виде квадратной матрицы, как это показано в табл. 1, и добавить к каждой строке и каждому столбцу этой таблицы по проверочному символу (проверка на четность).

Таблица 1

m0	m1	m2	P1 = m0 +m1 +m2
m3	m4	m5	P2 = m3 +m4 +m5
m6	m7	m8	P3 = m6  + m7 + m8
m0 +m3+m6	m1+ m4+m7	m2 +m5+m8	m0 + m0 + m1 + m1 +…. + m8 + m8

Таким образом, по строкам и по столбцам этой таблицы будет выполняться правило четности единиц. 

Если в процессе передачи по каналу с помехами в этой таблице произойдет одна ошибка (например  в символе m₄), то проверка на четность в соответствующей строке  и  столбце (в нашем примере - P₂ и P₅) не будет выполняться.

Иными словами,  координаты ошибки однозначно определяются  номерами столбца и строки, в которых не выполняются проверки на четность. Таким образом, этот код, используя различные проверки на четность (по строкам и по столбцам), способен не только обнаруживать, но и исправлять ошибки (если известны координаты ошибки, то ее исправление состоит просто в замене символа на противоположный: если 0, то на 1, если 1 – то на 0 ).  

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

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

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

Структура системы каскадного кодирования

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

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

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

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

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

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