9. КОД ХЕММИНГА

Пусть количество сообщений, которые тре­буется передавать абоненту, равно 16. Для их безызбыточ­ного кодирования можно использовать двоичные слова дли­ны 4, но тогда код не будет корректировать ошибки. При использовании слов длины 5, как мы уже знаем, можно об­наружить, но не исправить любую одиночную ошибку. Впрочем, из дополнения 3 предыдущего параграфа вытекает, что если добавить 5 проверочных символов, то код сможет не только исправлять одиночные, но и обнаруживать двойные ошибки. Возникает вопрос: нельзя ли для этой цели обойтись меньшим количеством проверочных символов?

Вычислим сначала, каково минимальное число прове­рочных символов, необходимое для исправления любых одиночных ошибок. Нетрудно убедиться, что двух добавоч­ных символов для этого недостаточно (предлагаем читате­лю проверить это самостоятельно).

Попробуем обойтись тремя проверочными символами, т. е. будем использовать для кодирования сообщений двоич­ные слова а1а2аэ^а5аеа_ длины 7. Наша задача — опреде­лить, произошла ли ошибка, и если произошла, то в каком месте. Но это то же самое, что указать одно из восьми чисел от 0 до 7 (О соответствует отсутствию ошибки).

 

 

 

Если теперь нужно выяснить, допущена ли при передаче слова а1а2а3агаъаГ)а7 одиночная ошибка в одном из симво­лов а4, аь, ас, а., то для этого достаточно вычислить сумму:

 

Ее значение, равное 1, соответствует ответу «да», значение О — ответу «нет» (почему?).

Пусть требуется передать сообщение, кодируемое словом а1а2ааа4. Добавим к этому слову три символа а5, а,;, а7, определяемые равенствами (здесь и до конца параграфа все равенства берутся по модуло 2):В случае «да» проверим, нет ли ошибки в символах а„, а . в случае «нет» — не содержится ли ошибка в символах а2, «.-!• В каждом из этих случаев ответ дает значение

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

 

Итак, мы имеем три проверочных соотношения:

 

 

 

суммы:

 

 

Если, например, значения обеих сумм (2) и (3) равны I, то ошибка содержится либо в ав, либо в а7. Всего имеется четыре комбинации значений сумм 5,, 52; они приведены в следующей таблице:

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

Отметим особо, что если произошла одиночная ошибка, то ее положение указывается числом с двоичной записью 5!525з- Пусть, например, 5Х=1, 5а=0, 5э=1. Согласно табли­це 18 ошибка допущена в четвертом или пятом разрядах; поскольку 53=1, она — в пятом разряде, но 5^53= 101 как раз и есть двоичная запись числа 5.

Изученный здесь код — это код Хемминга длины 7 с четырьмя информационными символами.

В общем случае кодовые слова двоичного кода Хеммин­га, позволяющего исправить одиночную ошибку, имеют длину 2т— 1 (т — натуральное). Для определения поло­жения ош ;бки тогда уже нужно т проверок, т. е. т прове­рочных символов. Оставшиеся 2т—1—т символов явля­ются информационными. Проверки строятся по аналогии с рассмотренным случаем. Значения т проверок, как ч вы­ше, образуют номер положения ошибки.

Вернемся, однако, к вопросу, поставленному в начале этого параграфа. Добавим к кодовым словам кода Хемгуин- га длины 7 еще один проверочный символ а0, а к проверочным соотношениям (5) еще одно (общую проверку на четность):

 

 

Новый код по-прежнему будет содержать 16 кодовых слог, потому что, как и раньше, символы а,, а2, аэ, а4 могут быть взяты какими угодно; по ним из соотношений (1) опреде­ляются символы а5, а„, а7, а из равенства (6) и символ а0. В случае одиночной ошибки добавленное соотношение (6) нарушается, а значения 5,, 52, 53 образуют номер положения ошибки. Если же произошла двойная ошибка, то соотно­шение (6) будет выполнено, а хотя бы одно из равенств (5) нарушится (почему?). Это и позволяет обнаружить любую двойную ошибку. Итак, для исправления одиночных и об­наружения двойных ошибок к четырем информационным символам достаточно добавить четыре проверочных симво­ла. Можно показать, что обойтись меньшим числом прове­рочных символов невозможно.

Построенное множество кодовых слов аса1а2аза4аЕ,айа,, удовлетворяющих соотношениям (5) и (6),— пример рас­ширенного кода Хемминга (длины 8 с четырьмя информаци­онными символами).

Задачи и дополнения

1. Определить положение одиночной ошибки в иска­женном слове 1100011 кода Хемминга длины 7.

Пусть 11010011 и 11001111—искаженные слова расширенного кода Хемминга длины 8. Какое из этих слов содержит одиночную, а

какое  двойную ошибку? В случае одиночной ошибки определить ее

положение.

К проверкам кода Хемминга длины 7 добавим (не меняя длины кода) общую проверку на четность:

а1+а2+аэ+а4+а6+а6+о!7=0.         (7)

Сколько слов удовлетворяет соотношениям (5) и (7)?

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

Построить систему проверок для кода Хемминга длины 15. Сколько кодовых слов содержит этот код? Сколько информационных и сколько проверочных символов имеется в кодовом слове?

 

то существуют два

 

6. Если задан код Хемминга длины

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

 

но добавляется общая проверка на четность:

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

 

Во втором способе (см. задачу 3) длина кодовых слов не меняется,

Сколько информационных и проверочных символов содержится в каждом из описанных здесь кодов?