1.7. КОДЫ ХЭММИНГА

Важным семейством кодов, которые легко кодировать и декодировать, являются коды Хэмминга, исправляющие одну ошибку. В этом параграфе мы обсудим только двоичные коды Хэмминга.

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

Если должна иметь строк (код имеет проверочных символов), то существует только допустимых столбцов, а именно ненулевых двоичных векторов длины Например, если то имеются следующие допустимых столбцов:

являющихся двоичными представлениями чисел от 1 до 7. Для кода Хэмминга мы используем их все и получим код длины

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

Пример. Код представляет собой [7, 4, 3]-код Хэмминга с

Здесь, как и в (1.36), мы разместили столбцы в порядке возрастания чисел, двоичными представлениями которых они являются. Для того чтобы представить в стандартной форме (1.2), переставим столбцы:

В общем случае

где матрица А состоит из всех столбцов с двумя или более единицами.

Ясно, что перестановка столбцов не влияет на число ошибок, исправляемое кодом, или на вероятность ошибки этого кода.

Определение. Два кода называются эквивалентными, если они отличаются только перестановкой символов. Так, например, коды

являются эквивалентными -кодами. Поэтому матрицы задают эквивалентные коды.

Упражнения. (26). Показать, что матрицы

порождают эквивалентные коды.

(27). Показать, что матрицы

порождают эквивалентные коды.

(28). Показать, что код Хэмминга единствен в том смысле, что любой линейный код с параметрами эквивалентен

По разным причинам (как инженерным, так и эстетическим) предпочтение может быть отдано одному из эквивалентных кодов. Например, третьей проверочной матрицей для кода является матрица

содержащая те же самые столбцы, но уже в другом порядке. Эта матрица задает циклический код, т. е. циклический сдвиг любого кодового слова снова является кодовым словом. Далее мы увидим что двоичные коды Хэмминга могут быть всегда сделаны циклическими.

Упражнение. (29). Код представляет собой -код Хэмминга Выписать для кодз три формы матрицы соответствующие выражениям (1.37), (1.38) и (1.40). Используя форму вида (1.38), закодировать сообщение и декодировать принятый вектор 111000111000111.

Декодирование. Предположим, что мы используем матрицу вида (1-37), когда столбец равен двоичному представлению числа Если произошла ошибка в 1-й символе, то из (1.22) следует, что синдром т. е. равен двоичному представлению числа Очень простое декодирование! (Никогда больше нам не встретится столь простое декодирование.)

Так как код может исправлять любую одиночную ошибку, то его минимальное расстояние (по теореме 2). На самом деле равно 3, так как легко найти кодовые слова веса 3 (например, слово если вида (см. также теорему 10).

Теорема 8. Коды Хэмминга являются совершенными кодами, исправляющими одиночные ошибки.

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

Рис. 1.10. Свойства кода Хэмминга

Упражнения. (30). Выписать порождающую матрицу для кода и, используя ее, показать, что каждое ненулевое кодовое слово имеет вес не менее 3. [Указание. Предположить противное; тогда это кодовое слово должно быть суммой двух или менее строк

(31). Показать, что для кода Хэмминга распределение лидеров смежных классов таково: Найти вероятность ошибки