Коды Хемминга. 
Теория информационных процессов и систем + доп. 
Материалы в эбс

В отличие от канонического матричного кода, в коде Хемминга информационные и проверочные биты не разнесены в отдельные подматрицы, а чередуются. Если биты кодовой комбинации пронумеровать, начиная с 1, слева направо, то контрольными (проверочными) оказываются биты с номерами 1, 2, 4, 8 и т. д., все остальные являются информационными. Цель этих перестановок — сделать так, чтобы синдром ошибки непосредственно указывал на локализацию ошибок, минуя промежуточную таблицу соответствия синдромов и ошибок или исключая необходимость сравнения синдрома ошибки со столбцами проверочной матрицы. Код Хемминга начинают строить с проверочной матрицы Я, так как ее вид очевиден: столбцы проверочной матрицы представляют собой набор синдромов, соответствующих двоичному представлению номера столбца. Затем строят порождающую матрицу G, исходя из того, что матрицы Я и G ортогональны, т. е. скалярное произведение каждой строки матрицы G на каждую строку матрицы Я равно нулю, т. е.

Построим код Хемминга для (7,4)-кода. Чтобы синдром ошибки указывал на место ошибки, проверочная матрица должна иметь вид:

Обратите внимание, каждый столбец матрицы Н является двоичным представлением номера этого столбца.

В матрице Н на первом, втором и четвертом местах стоят столбцы матрицы, имеющей единицы на второстепенной диагонали, а на остальных — столбцы, соответствующие информационным разрядам кода. Выделим подматрицу, соответствующую информационным разрядам (т.е. третий, пятый, шестой и седьмой столбцы):

Повернем матрицу Н, по часовой стрелке и получим проверочную подматрицу порождающей матрицы:

Поставим столбцы матрицы Р на первое, второе и четвертое места, а остальные столбцы будут столбцами единичной матрицы. Получим порождающую матрицу кода Хемминга:

Закодируем по Хеммингу входную комбинацию т = [0 0 1 1].

Проверим разрешенное кодовое слово, вычислив синдром:

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

Предположим, что произошла ошибка в третьем разряде и принята кодовая комбинация й = [1 0 1 0 0 11]. Вычислим синдром:

Синдром представляет собой двоичное число 3, что локализует ошибку в третьем разряде.

8 Построить блочный систематический код для исправления двукратных ошибок Решение:

Порождающая матрица (8, 3)-кода уже была получена:

Представим ее в каноническом виде, переставив столбцы:

Выделим проверочную подматрицу: и транспонируем ее:

Составим проверочную матрицу (8, 3)-кода:

Код построен.

8 Как можно использовать полученный код для решения задачи о разведчиках?

Командир должен пронумеровать своих бойцов от 1 до 8. В соответствии с порождающей матрицей G бойцы с номерами 1,4, 5 должны отправиться по 1-й дороге, номера 2,6, 7 — по второй дороге, а разведчики с номерами 3 и 8 — по третьей дороге. Проверка результатов разведки может осуществляться следующим образом.

Первый случай. Допустим, объект находится на первой дороге, а шпионами являются бойцы № 1 и 5. Обнаружив объект, они солгут, и командир получит следующее сообщение: 0= (10 000). Умножив сообщение на проверочную матрицу, командир получит ненулевой синдром и обнаружит ложь:

Второй случай. Допустим, что объект находится на 1-й дороге, а шпионы — это бойцы № 2 и 8. С учетом искажений во 2-м и 8-м разрядах, командир получит следующее сообщение: U = (11 011 001). Проверка вновь осуществляется перемножением проверочной матрицы на сообщение:

Ненулевой синдром свидетельствует об ошибке.

Третий случай. Объект находится на 1-й дороге и в докладе разведгрупп нет искажений (шпионы воздержались от лжи). Тогда сообщение будет выглядеть так: 0 = (10 011 000). Умножение проверочной матрицы на эту кодовую комбинацию даст нулевой синдром, свидетельствующий об отсутствии искажений.

8 Можно ли не только обнаружить объект, но и установить, кто из бойцов является шпионами?

Ответ: Синдром полученного кода — 5-разрядный, следовательно, имеется 2⁵ -1 = 31 различный ненулевой синдром. В тоже время возможны 8−7/2 = 28 различных двукратных ошибок. Следовательно, каждой из двукратных ошибок можно однозначно сопоставить синдром. Таблицу соответствий ошибки и синдрома можно построить следующим образом. Берем вектор ошибки, например (11 000 000), умножаем на него проверочную матрицу и получаем синдром S = (11 110). Следующий вектор ошибки — (10 100 000), умножаем на него проверочную матрицу и получаем синдром S = (11 001), и т. д.

Однако заметим, что если наряду с двукратными ошибками учитывать однократные (т.е. один из шпионов солжет, а второй скажет правду), то всего возможны 28 + 8 = 36 различных ошибок. Это превышает количество возможных синдромов и, следовательно, не все такие ошибки могут быть локализованы.