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) длина кодовых слов не меняется,
Сколько информационных и проверочных символов содержится в каждом из описанных здесь кодов?