Линейные блочные коды. Коды Хэмминга

В показанном на рис. 1 случае не все слова размерности n принадлежат областям декодирования. Таких кодов большинство. Коды, в которых непересекающиеся области декодирования охватывают все пространство слов размерности n, называются совершенными или плотноупакованными. При использовании совершенных кодов всегда возможна коррекция ошибок (не всегда правильная). Декодер такого кода не может определить ошибку декодирования. Он работает либо в режиме определения ошибок, либо в режиме исправления ошибок. Основными совершенными кодами являются коды Хэмминга и коды Голея.

Код Хэмминга можно построить для любого натурального числа r ≥3. Этот код будет обладать рядом свойств
Далее будем рассматривать процессы кодирования и декодирования линейных блочных кодов на примере кодов Хэмминга.

Кодирование линейных блочных кодов.

Поскольку между информационными и кодовыми словами существует взаимно однозначное соответствие, процесс кодирования может быть осуществлен с использованием таблицы соответствий, хранящейся в памяти кодера. Однако, для длинных кодов такой метод неприемлем, так как требует большой объем памяти для хранения таблицы.
Вместо этого вводится понятие так называемой порождающей матрицы G. Оно основано на том, что подпространство всех кодовых слов линейного блочного (n,k)-кода имеет некоторый базис(v0,v1,…,vk-1), через который может быть выражено любое кодовое слово этого кода.
Векторы базиса образуют порождающую матрицу G размера k*n

Тогда уравнение (34) принимает вид
Фактически, формула (36) описывает процедуру кодирования линейного блочного кода посредством образующей матрицы.
Для пространства кодовых слов линейного (n,k)-кода существует дуальное ему пространство кода (n,n-k), порождаемое матрицей H размера (n-k)*n. Такая матрица получила название проверочной для кода (n,k) и обладает следующими свойствами:
на основе которых реализована операция декодирования линейных блочных кодов.

Как правило рассматривают так называемые систематические или канонические формы матриц G и H, использующиеся для процедуры систематического кодирования. На практике, любая порождающая матрица G линейного блочного (n, k)-кода может быть преобразована к систематическому виду посредством элементарных операций и перестановок столбцов матрицы.
Матрица G в систематической форме состоит из двух подматриц: единичной матрицы Ik размера k*k и проверочной подматрицы P размера k*(n-k).

Соответственно, исходя из свойства (37), следует, что проверочная матрица H состоит из единичной матрицы In-k и транспонированной проверочной под матрицы P.
В качестве примера приведем порождающую(40) и проверочную(41) матрицы для кода Хэмминга (7; 4).

Для примера также рассмотрим процедуру кодирования с использованием порождающей матрицы G (40). В качестве информационного слова возьмем вектор u = [1 0 1 1].

Декодирование линейных блочных кодов

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

В связи с этим используют механизм синдромного декодирования, основанный на использовании проверочной матрицы H.
Для понимания принципа декодирования рассмотрим как выражаются проверочные символы кодового слова через информационные на примере систематического кода Хэмминга (7; 4).
Если в канале произошла ошибка, то для принятого вектора r хотя бы одно из равенств выполняться не будет. Эти проверочные соотношения можно записать для принятого вектора в виде системы уравнений (43).

Соответственно, если хотя бы один из компонент вектора s = {s0; s1; s2} не равен нулю, то в принятом слове есть ошибка.
Уравнения (43) можно записать через проверочную матрицу H.
Вектор s принято называть синдромом. Таким образом, ошибка в принятом слове будет обнаружена, если хоть один компонент синдрома принятого слова не равен нулю.
Для исправления ошибки используется тот факт, что каждый синдром соответствует своей позиции одиночной ошибки (код Хэмминга). Таким образом, перебрав все возможные варианты одиночной ошибки можно получить таблицу соответствия синдром-ошибка. В табл. 5.1 приведены соответствия позиций ошибки и синдромов для кода Хэмминга (7; 4)

Если сравнить табл. 5.1 и проверочную матрицу (41), то можно увидеть, что ошибке в i-й позиции кодового слова соответствует синдром,образованный i-м столбцом матрицы H.
Для примера рассмотрим декодирование полученной ранее кодовой комбинации v = [1 0 0 1 0 1 1] без ошибок и с ошибкой в позиции v4.
При отсутствии ошибки синдром будет равен:
что доказывает отсутствие ошибки.

Если наложить на вектор v ошибку в позиции v4 будет получен вектор r = [1 0 0 1 1 1 1]. Теперь синдром будет равен:
что, во-первых, показывает наличие ошибки, а во-вторых, согласно табл. 5.1, указывает, что она произошла в позиции r4. Таким образом, ошибка может быть исправлена.

Расширенные коды Хэмминга.

Расширение кода Хэмминга заключается в дополнении кодового слова дополнительным двоичным разрядом так, чтобы оно содержало четное число единиц. Такое расширение дает ряд преимуществ:
Длина кода увеличивается до n = 2r, что удобнее для хранения и передачи информации.
Минимальное расстояние dmin = 4, следовательно tобн = 3.
Также, дополнительный разряд позволяет использовать декодер в гибридном режиме обнаружения и коррекции ошибок

Для примера рассмотрим расширение кода Хэмминга (7,4) - расширенный код Хэмминга (8,4).
Кодовый вектор
расширенного кода (8,4) получается из вектора
кода (7,4) путем добавления разряда проверки на четность, то есть
где

Проверочная матрица кода (8,4) получается из проверочной матрицы кода (7,4) в два приема.
1.Слева к матрице H(7;4) дописывается нулевой столбец.
2.Полученная матрица дополняется сверху строкой из единиц.
При синдромном декодировании
вектор синдрома имеет вид
где компонента равна сумме всех элементов кодового слова и, следовательно, равна нулю.

Рассмотрим процесс коррекции и обнаружения ошибок.
Процедура исправления одиночных ошибок совпадает с таковой для обычных кодов Хэмминга. Компонента при этом всегда равна единице, а синдром s соответствует синдрому обычного кода Хэмминга. Если же ошибка в дополнительном разряде , то будет равно 1, а s = (0 0 0). При двукратной же ошибке компонента всегда будет равна нулю. Таким образом можно представить гибридный алгоритм коррекции ошибок.
1.Если = 1, то исправление одиночной ошибки.
2.Если = 0 и s≠0, то обнаружена неисправляемая ошибка