Коды, исправляющие ошибки
Содержание | Назад | Вперед | Лабораторные | О курсе

  Содержание



 

2. Исправление и обнаружение ошибок с помощью линейных кодов

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

2.1. Стандартное расположение

Пусть V - линейный код (n, k) - код, v - нулевой вектор и v1, v2, ..., vm-1 - остальные кодовые вектора. Тогда таблицу декодирования можно составить следующим образом. Кодовые вектора располагаются в виде строки с нулевым вектором слева. Затем один из оставшихся наборов длины n, например g1, помещается под нулевым вектором. Обычно это бывает один из наборов, которые наиболее вероятно получится на выходе, если по каналу передавался нулевой вектор. Далее строка заполняется так, чтобы под каждым кодовым словом vi помещался вектор g1 + vi. Аналогично в первый столбец второй строки помещается вектор g2, которого еще нет в таблице, и строка заполняется таким же способом. Процесс продолжается до тех пор, пока каждый двоичный набор длины n не появится в таблице. Это стандартное расположение, с одной стороны, в точности совпадает с таблицей декодирования, описанной в главе 1; с другой стороны, так как линейный код V является подгруппой группы (Bn,+), то построенное разложение есть разложение группы Bn по подгруппе V. Строки таблицы являются смежными классами, а векторы в первом столбце - образующими смежных классов.

Таким образом, стандартное расположение имеет следующий вид

,

где , .

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


В качестве примера рассмотрим код V = {10111, 01101, 00000, 11010} с порождающей матрицей

.

Стандартное расположение имеет следующий вид:

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

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

Доказательство. Пусть v и u - соответственно принятый и переданный векторы, тогда вектор ошибки e равен v + u. По правилу декодирования, если принятый вектор u находится в смежном классе с образующим g, то вектор u будет декодирован в кодовый вектор v' = u + g. Так как сложение по модулю 2 является групповой операцией, то v' = v, если и только если e = g.

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

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

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


Если V - (n,k)-код с проверочной матрицей H, то мы определяем синдром двоичного вектора u длины n как вектор s = uHT. Вектор s имеет длину n - k.

Теорема 2.3. Все векторы из одного смежного класса стандартного расположения имеют одинаковый синдром, присущий только этому смежному классу.

Доказательство. Векторы u и u' лежат в одном смежном классе, если и только если u + u' Î V, т.е. (u + u')HT = 0. Поскольку умножение матриц дистрибутивно относительно сложения, то (u + u')HT = uHT + u'HT. Таким образом, векторы u и u' лежат в одном смежном классе, если и только если uHT + u'HT = 0, т. е. если и только если uHT = u'HT.

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