Новости    Библиотека    Энциклопедия    Биографии    Карта сайта    Ссылки    О проекте




предыдущая главасодержаниеследующая глава

9. Код Хемминга

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

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

Попробуем обойтись тремя проверочными символами, т. е. будем использовать для кодирования сообщений двоичные слова α1α2α3α4α5α6α7 длины 7. Наша задача - определить, произошла ли ошибка, и если произошла, то в каком месте. Но это то же самое, что указать одно из восьми чисел от 0 до 7 (0 соответствует отсутствию ошибки).

Пусть требуется передать сообщение, кодируемое словом α1α2α3α4. Добавим к этому слову три символа α5, α6, α7, определяемые равенствами (здесь и до конца параграфа все равенства берутся по модулю 2):

α5 = α2 + α3 + α4,
α6 = α1 + α3 + α4,
α7 = α1 + α2 + α4. (1)

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

s1 = α4 + α5 + α6 + α7. (2)

Ее значение, равное 1, соответствует ответу "да", значение 0 - ответу "нет" (почему?).

В случае "да" проверим, нет ли ошибки в символах α6, α7, в случае "нет" - не содержится ли ошибка в символах α2, α3. В каждом из этих случаев ответ дает значение суммы:

s2 = α2 + α3 + α6 + α7. (3)

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

Таблица 18
Таблица 18

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

s3 = α1 + α3 + α5 + α7. (4)

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

s1 = α4 + α5 + α6 + α7 = 0,
s2 = α2 + α3 + α6 + α7 = 0,
s3 = α1 + α3 + α5 + α7 = 0, (5)

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

Отметим особо, что если произошла одиночная ошибка, то ее положение указывается числом с двоичной записью s1s2s3. Пусть, например, s1 = 1, s2 = 0, s3 = 1. Согласно таблице 18 ошибка допущена в четвертом или пятом разрядах; поскольку s3 = 1, она - в пятом разряде, но s1s2s3 = 101 как раз и есть двоичная запись числа 5.

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

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

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

s0 = α0 + α1 + α2 + α3 + α4 + α5 + α6 + α7 = 0. (6)

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

Построенное множество кодовых слов α0α1α2α3α4α5α6α7, удовлетворяющих соотношениям (5) и (6), - пример расширенного кода Хемминга (длины 8 с четырьмя информационными символами).

предыдущая главасодержаниеследующая глава




ИНТЕРЕСНО:

Многомерный математический мир… в вашей голове

В школах Великобритании введут китайские учебники математики

Найдено самое длинное простое число Мерсенна, состоящее из 22 миллионов цифр

Как математик помог биологам совершить важное открытие

Математические модели помогут хирургам

Почему в математике чаще преуспевают юноши

Физики-практики откровенно не любят математику

В индийской рукописи нашли первое в истории упоминание ноля

Вавилонская глиняная табличка оказалась древнейшей «тригонометрической таблицей» в мире

Ученые рассказали о важной роли игр с пальцами в обучении детей математике
Пользовательского поиска

© Злыгостев Алексей Сергеевич, статьи, подборка материалов, оформление, разработка ПО 2001-2018
При копировании материалов проекта обязательно ставить ссылку на страницу источник:
http://mathemlib.ru/ 'MathemLib.ru: Математическая библиотека'
Рейтинг@Mail.ru