КОД ХЕММИНГА

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

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

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

Пусть требуется передать сообщение, кодируемое словом aia₂a₃a₄. Добавим к этому слову три символа а₅, а_й, а₇, определяемые равенствами (здесь и до конца параграфа все равенства берутся по модуле 2):

Если теперь нужно выяснить, допущена ли при передаче слова а_да₂а₈а4С1ба_га₇ одиночная ошибка в одном из симво­лов a_4> ct_f)l а₇, то для этого достаточно вычислить сумму:

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

В случае «да» проверим, нет ли ошибки в символах а_в, а , в случае «нет» — не содержится ли ошибка в символах а₂, а_я. В каждом из этих случаев ответ дает значение суммы:

Г.слп, например, значения обеих сумм (2) и (3) равны 1, то ошибка содержится либо в а„, либо в а₇. Всего имеется четыре комбинации значений сумм Si, s₂; они приведены в следующей таблице:

Таблица 18

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

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

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

Отметим особо, что если произошла одиночная ошибка, то ее положение указывается числом с двоичной записью SjSaSe. Пусть, например, = I, Sa=0, S₃=l. Согласно табли­це 18 ошибка допущена в четвертом или пятом разрядах; поскольку s₃=l, она — в пятом разряде, но как раз и есть двоичная запись числа 5.

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

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

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

Новый код по-прежнему будет содержать 16 кодовых слог, потому что, как и раньше, символы а_и а₂, а₃, а₄ могут быть взяты какими угодно; по ним из соотношений (1) опреде­ляются символы а₆, а₆» ^а7» ^a из равенства (6) и символ а₀. В случае одиночной ошибки добавленное соотношение (6) нарушается, а значения s_u s₂, s₃ образуют номер положения ошибки. Если же произошла двойная ошибка, то соотно­шение (6) будет выполнено, а хотя бы одно из равенств (5) нарушится (почему?). Это и позволяет обнаружить любую двойную ошибку. Итак, для исправления одиночных и об­наружения двойных ошибок к четырем информационным символам достаточно добавить четыре проверочных симво­ла. Можно показать, что обойтись меньшим числом прове­рочных символов невозможно.

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

Предлагаю ознакомиться с аналогичными статьями: