20. Составной код. Итеративные коды

Итеративные коды, иногда называемые прямоугольными (rectangular code), либо композиционными (product code), являются одними из самых простых (с точки зрения аппаратной реализации) избыточных кодов, позволяющих исправлять ошибки в кодовых словах.

Простейшим из них является двумерный линейный итеративный код, при использовании которого кодовые слова записываются в виде таблицы. Основной является форма записи, при которой строки и столбцы содержат четное (нечетное) число единиц. Например, при кодировании информационного слова Х_k = 011101111 с помощью таблицы с четностью по строкам и столбцам получим избыточные символы Х_r = X_h, X_v = 0010011, как показано на рис. 3.3 (информационные символы выделены жирным шрифтом, а проверочные – курсивом).

Горизонтальные проверки

k₂

k1 0 1 1	0
1 0 1	0
1 1 1	1
0 0 1	1

Вертикальные проверки

Рис. 3.3. Схематичное представление (в виде таблицы) двумерного линейного итеративного кода

Кодовое слово имеет вид: X_n = 0111011110010011.

Порождающая матрица для двумерного линейного итеративного кода (4, 3, 4, 3) с d_min = 4, приведенного на рис. 3.3, будет иметь следующий вид:

(3.16)

Число проверочных символов определяется следующей зависимостью:

(3.17)

где k = k₁  k₂ .

Местоположение ошибки находится на пересечении строки и столбца с нарушенной четностью. Кодовое расстояние итеративного кода равно произведению минимальных расстояний составляющих его подкодов (свертки по модулю 2, d = 2). Следовательно, двумерный линейный итеративный код (d_min=4) позволяет корректировать все одиночные ошибки с одновременным обнаружением двукратных.

Увеличить корректирующие возможности двумерных итеративных кодов можно, дополнив проверочную матрицу избыточными символами (на четность) по диагонали, как показано на рис. 3.4 (информационные символы выделены жирным шрифтом, а проверочные – курсивом).

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

В общем случае линейный двумерный итеративный код с диагональными проверками (ЛИКД) (по основанию 2) можно определить как блоковый (n₁, k₁, n₂, k₂) код, формирующий кодовые последовательности длиной k (k = k₁ ∙ k₂) информационных и 2∙(k₁ + k₂) проверочных разрядов (в приведенном примере k₁ = k₂ = 3).

Порождающая матрица для двумерного линейного итеративного кода с проверочными символами по диагонали, приведенного на рис. 3.4, будет следующей:

(3.18)

Рассмотрим некоторые основные параметры таких кодов.

Избыточность двумерного линейного итеративного кода (r) будет равна (k = k₁ ∙k₂ ):

(3.19)

Минимальное кодовое расстояние двумерного линейного итеративного кода с диагональными проверками равно пяти (d_min = 5). Следовательно, такой код позволяет обнаруживать и корректировать все ошибки, кратность которых не превышает двух.

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

Для определенного набора k двоичных информационных символов кодовое слово можно представить в виде k₁ n₂-разрядных кодовых слов строк, k₂ n₁-разрядных кодовых слов столбцов и k₁ + k₂  – 1 кодовых слов первых и вторых диагоналей, размерность которых не превышает меньшего из k₁ или k₂ (n₁ =  k₁ + 1, n₂ = k₂ + 1).

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

В соответствии с этим, код, приведенный на рис. 3.5, можно представить в виде кодовых слов строк, столбцов и диагоналей (таблица).

Таблица