Декодирование

Кодирование

Кодовое слово v и информационное слово u связаны соотношением:

v = u × G,

где G — порождающая матрица, структура которой была описана выше.

Например, информационный вектор u = (1010) отобразится в кодовый вектор следующим образом:

Легко заметить, что последние четыре разряда кодового вектора совпадают с информационным вектором. Это свойство называется систематичностью кода.

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

G_k×n = (P_k×(n−k) I_k),

где I_k — единичная матрица размерности k×k.

Таким образом, в кодовом векторе систематического кода всегда можно выделить информационные и проверочные символы.

v = (	v0 … vn−k−1	vn−k … vn−1	).
	n − k проверочных символов	k информационных символов

Роль проверочных символов и их использование будут подробно разъяснены ниже.

Задача декодера заключается в том, чтобы, используя структуру кода, по принятому слову r, восстановить переданный информационный вектор. Для рассмотренного выше (7, 4)-кода Хэмминга можно предложить следующий алгоритм обнаружения ошибок. Так как рассматриваемый код является систематическим, выразим каждый из трех проверочных символов через символы информационного вектора:

v₀ = v₃ ⊕ v₅ ⊕ v₆
v₁ = v₃ ⊕ v₄ ⊕ v₅
v₂ = v₄ ⊕ v₅ ⊕ v₆

Если в канале произошла ошибка, то в принятом векторе r хотя бы одно из равенств не будет выполняться. Запишем полученные проверочные соотношения в виде системы уравнений для компонент вектора r:

r₀ ⊕ r₃ ⊕ r₅ ⊕ r₆ = s₀
r₁ ⊕ r₃ ⊕ r₄ ⊕ r₅ = s₁
r₂ ⊕ r₄ ⊕ r₅ ⊕ r₆ = s₂

Таким образом, из первых трех столбцов порождающей матрицы G мы получили систему трех проверочных уравнений. Если в полученной системе уравнений хотя бы одна из компонент {s₀, s₁, s₂} не равна нулю, то в канале произошла ошибка.

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

H_(n−k)×n = (I_n−k P^T_k×(n−k)).

Тогда систему проверочных уравнений можно записать в виде

s = r × H^T

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

В качестве примера рассмотрим синдромное декодирование (7, 4)-кода Хэмминга. При передаче информационного слова u = (1010) по каналу без шума r = v = (0011010). Можем убедиться, что в этом случае синдром равен 0.

Если, например, в кодовом слове произошла одиночная ошибка на четвертой позиции (r = (0010010)), то синдромом является четвертая строка транспонированной проверочной матрицы.

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

Ошибочный разряд	r0	r1	r2	r3	r4	r5	r6
Синдром s

Можно заметить, что ошибке в i-ой позиции кодового слова соответствует синдром, образованный i-ым столбцом матрицы Н. Так как все столбцы матрицы различны, мы можем с помощью таблицы синдромов исправлять одиночную ошибку, вносимую каналом.

Дата добавления: 2015-05-09