1110 0 10 0 10 110 0 1

Очевидно, что ценность стандартного расположения относительна. Для больших пик составлять такую таблицу было бы не практично.

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

Для любого принятого вектора v определим синдром равенством

S = vH.

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

Доказательство. Если v и v лежат в одном смежном классе, то V = Сг -Ь у, v = c + у для некоторого у и кодовых слов Cj и Cj Для любого кодового слова с выполняется равенство сН = 0. Отсюда получаем

S = vH = уН\

s = vнт = yн

и, следовательно, s = s. Обратно, допустим, что s = s, тогда (v - v) Hf = О, и поэтому разность v - v является кодовым словом. Следовательно, v и v принадлежат одному смежному классу. □

Любые два вектора из одного смежного класса имеют одинаковый синдром. Следовательно, нам необходимо только свести в таблицу синдромы и лидеры смежных классов. Затем мы можем производить декодирование следующим образом. По принятому вектору V вычисляем синдром и находим соответствующий этому синдрому лидер смежного класса. Этот лидер является разностью между принятым словом и кодовым словом, которое одновременно является центром сферы кодирования. Таким образом, мы исправим ошибку, вычтя из слова v лидер смежного класса.

В примере, приведенном выше, проверочной матрицей будет

й новая таблица запишется в виде

i.i. коды ХЭММИНГА 71

Эта таблица проще, чем стандартное расположение. Предположим, что принят вектор v = 10010. Тогда s = vH = 101. Лидер смежного класса будет равен 01000. Отсюда получим, что переданное слово равно 10010 -01000 = 11010, а информационное слово равно 11.

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

Код, у которого минимальное расстояние не менее трех, в силу следствия 3.2.3 имеет проверочную матрицу, в которой все столбцы ненулевые и различные. Если проверочная матрица двоичного кода имеет т строк, то каждый столбец оказывается двоичным числом длины т. Существует всего 2™ - 1 возможных столбцов. Следовательно, если Н -матрица двоичного кода с d* 3- имеет /п строк, то она может иметь не более 2" - 1 столбцов. В результате получается (2" - 1, 2" - 1 -т)-код. Простейший нетривиальный пример соответствует m = 3. В этом случае матрицы Н и G в систематическом виде запишутся следующим образом:

110 110 0 10 110 10 0 1110 0 1

1 0 0 0 1 1 0

0 10 0 10 1

0 0 1 0 0 11

0 0 0 1 1 1 1

Например (13,10)-код Хэмминга над GF (3) задается проверочной матрицей

1 1 1 1 1 1 I 1 О О 1 О о 00111222110 10 .1201201212001

Такие (2" - 1, 2" - 1 - т)-коды называются кодами Хэм» минга.

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

Определение кодов Хэмминга легко обобщить на случай больших алфавитов. Достаточно просто заметить, что главная идея построения таких кодов состоит в определении матрицы Н, любая пара столбцов которой линейно независима. Для задания проверочной матрицы нельзя использовать все ненулевые т-последо-вательности над GF (q), q Ф 2, поскольку некоторые из них попарно линейно зависимы. Чтобы обеспечить линейную независимость, выберем в качестве столбцов матрицы все т-последовательности, у которых первая ненулевая компонента равна единице. Тогда все столбцы будут попарно линейно независимыми, а некоторые тройки столбцов могут оказаться линейно зависимыми, и минимальный вес в коде будет равен трем.

Всего существует (q" -\)l{q - 1) таких различных столбцов. Следовательно, .получившийся код будет {{q" - \)l{q-1), (qin - lyiq - 1)~ т)-кодом. Код Хэмминга, исправляющий одиночные ошибки, существует для каждого q, для которого существует поле GF (q), и для любого т. Для примера в табл. 3.1 приведены параметры нескольких кодов Хэмминга.

Таблица 3.1

Параметры (я, ft) некоторых кодов Хэмминга