Лекция 13. Совершенные и квазисовершенные коды.

Совершенные и квазисовершенные коды
Групповой (m, n)-код, исправляющий все ошибки веса, не большего k, и никаких других, называется совершенным.

Совершенный код — это лучший код, обеспечивающий максимум минимального расстояния между кодовыми словами при минимуме длины кодовых слов. Совершенный код легко декодировать: каждому полученному слову однозначно ставится в соответствие ближайшее кодовое.
Чисел m, n и k (1 < k < (n−1)/2 ), удовлетворяющих условию совершенности кода очень мало. Но и при подобранных m, n и k совершенный код можно построить только в исключительных случаях. Если m, n и k не удовлетворяют условию совершенности, то лучший групповой код, который им соответствует называется квазисовершенным, если он исправляет все ошибки кратности, не большей k, и некоторые ошибки кратности k + 1. Квазисовершенных кодов также очень мало.

Двоичный блочный (m, n)-код называется оптимальным, если он минимизирует вероятность ошибочного декодирования. Совершенный или квазисовершенный код — оптимален. Общий способ построения оптимальных кодов пока неизвестен.

Для любого целого положительного числа r существует совершенный (m, n)-код, исправляющий одну ошибку, называемый кодом Хэмминга (Hamming), в котором m = 2^r − r − 1 и n = 2^r − 1.
Действительно,

Порядок построения кода Хэмминга следующий:
1. Выбираем целое положительное число r. Сообщения будут словами длины m = 2r − r − 1, а кодовые слова — длины n = 2r − 1;
2. В каждом кодовом слове b = b₁b₂ . . . b_n r бит с индексами-степенями двойки (2⁰, 2¹, . . . , 2^r−1) — являются контрольными, остальные — в естественном порядке — битами сообщения. Например, если r = 4, то биты b₁, b₂, b₄, b₈ — контрольные, а b₃, b₅, b₆, b₇, b₉, b₁₀, b₁₁, b₁₂, b₁₃, b₁₄, b₁₅ — из исходного сообщения;
3. Строится матрица M из 2^r −1 строк и r столбцов. В i-ой строке стоят цифры двоичного представления числа i. Матрицы для r = 2, 3 и 4 таковы:

4. Записывается система уравнений bM = 0, где M — матрица из предыдущего пункта. Система состоит из r уравнений. Например, для r = 3:

5. Чтобы закодировать сообщение a, берутся в качестве b_j , j не равно степени двойки, соответствующие биты сообщения и отыскиваются, используя полученную систему уравнений, те b_j , для которых j — степень двойки. В каждое уравнение входит только одно b_j , j = 2ⁱ. В выписанной системе b4 входит в 1-е уравнение, b₂ — во второе и b₁ — в третье. В рассмотренном примере сообщение a = 0111 будет закодировано кодовым словом b = 0001111.

Декодирование кода Хэмминга проходит по следующей схеме.
Пусть принято слово b + e, где b — переданное кодовое слово, а e — строка ошибок. Так как bM = 0, то (b + e)M = bM + eM = eM. Если результат нулевой, как происходит при правильной передаче, считается, что ошибок не было. Если строка ошибок имеет единицу в i-й позиции, то результатом произведения eM будет i-я строка матрицы M или двоичное представление числа i. В этом случае следует изменить символ в i-й позиции слова b + e, считая позиции слева, с единицы.

Пример. (4, 7)-код Хэмминга имеет в качестве одного из кодовых слов b = 0001111. Матрица M_7×3 приведена на шаге 3 хода построения кода Хэмминга. Ясно, что bM = 0. Добавим к b строку ошибок e = 0010000. Тогда b + e = 0011111 и (b + e)M = 011 = 3₁₀, т. е. ошибка находится в третьей позиции. Если e = 0000001, то b + e = 0001110 и позиция ошибки — (b+e)M = 111 = 710 и т.п. Если ошибка допущена в более чем в одной позиции, то декодирование даст неверный результат.
Код Хэмминга — это групповой код.

Это следует из того, что (m, n)-код Хэмминга можно получить матричным кодированием, при помощи m×n-матрицы, в которой столбцы с номерами не степенями 2 образуют единичную подматрицу. Остальные столбцы соответствуют уравнениям шага 4 построения кода Хэмминга, т. е. 1-му столбцу соответствует уравнение для вычисления 1-го контрольного разряда, 2-му — для 2-го, 4-му — для 4-го и т.д. Такая матрица будет при кодировании копировать биты сообщения в позиции не степени 2 кода и заполнять другие позиции кода согласно схеме кодирования Хэмминга.

Пример. Кодирующая матрица для (4, 7)-кода Хэмминга —

Ее столбцы с номерами 3, 5, 6 и 7 образуют единичную подматрицу.
Столбцы с номерами 1, 2 и 4 соответствуют уравнениям для вычисления контрольных бит, например, уравнению b₁ = b₃ + b₅ + b₇ соответствует столбец 1101, т.е. для вычисления первого контрольного разряда берутся 1, 2 и 4 биты исходного сообщения или биты 3, 5 и 7 кода.
К (m, n)-коду Хэмминга можно добавить проверку четности. Получится (m, n + 1)-код с наименьшим весом ненулевого кодового слова 4, способный исправлять одну и обнаруживать две ошибки.
Коды Хэмминга накладывают ограничения на длину слов сообщения: эта длина может быть только числами вида 2^r − r − 1: 1, 4, 11, 26, 57, . . . Но в реальных системах информация передается байтам или машинными словами, т.е. порциями по 8, 16, 32 или 64 бита, что делает использование совершенных кодов не всегда подходящим. Поэтому в таких случаях часто используются квазисовершенные коды.
Квазисовершенные (m, n)-коды, исправляющие одну ошибку, строятся следующим образом. Выбирается минимальное n так, чтобы

Каждое кодовое слово такого кода будет содержать k = n−m контрольных разрядов. Из предыдущих соотношений следует, что
2^k = 2^n−m > n + 1 = C¹_n + C⁰_n = m + k + 1.
Каждому из n разрядов присваивается слева-направо номер от 1 до n. Для заданного слова сообщения составляются k контрольных сумм S₁, . . . , S_k по модулю 2 значений специально выбранных разрядов кодового слова, которые помещаются в позиции-степени 2 в нем: для S_i (1 ≤ i ≤ k) выбираются разряды, содержащие биты исходного сообщения, двоичные числа-номера которых имеют в i-м разряде единицу. Для суммы S₁ это будут, например, разряды 3, 5, 7 и т.д., для суммы S₂ — 3, 6, 7 и т.д. Таким образом, для слова сообщения a = a₁ . . . a_m будет построено кодовое слово b = S₁S₂a₁S₃a₂a₃a₄S₄a₅ . . . a_m. Обозначим S_i* сумму по модулю 2 разрядов полученного слова, соответствующих контрольной сумме S_i и самой этой контрольной суммы. Если S_k* . . . S₁* = 0, то считается, что передача прошла без ошибок. В случае одинарной ошибки S_k* . . . S₁* будет равно двоичному числу-номеру сбойного бита.
В случае ошибки, кратности большей 1, когда S_k* . . . S₁* > n, ее можно обнаружить. Подобная схема декодирования не позволяет исправлять некоторые двойные ошибки, чего можно было бы достичь, используя схему декодирования с лидерами, но последняя значительно сложнее в реализации и дает незначительное улучшение качества кода.

Пример построения кодового слова квазисовершенного (9, n)-кода, исправляющего все однократные ошибки, для сообщения 100011010.

Искомое кодовое слово имеет вид . Далее нужно вычислить контрольные суммы.

Таким образом, искомый код — 0011000111010. Если в процессе передачи этого кода будет испорчен его пятый бит, то приемник получит код 0011100111010. Для его декодирования опять вычисляются контрольные суммы:

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

Совершенный код Хэмминга также можно строить по рассмотренной схеме, т.к. для него 2n/(n + 1) = 2m.
Для исправление одинарной ошибки к 8-разрядному коду достаточно приписать 4 разряда (2¹²/13 > 2⁸), к 16-разрядному — 5, к 32-разрядному — 6, к 64-разрядному — 7.