Коды и математика (рассказы о кодировании) - Аршинов М.Н.
Скачать (прямая ссылка):
Продемонстрированное в этом примере сочетание проверок на четность по строкам и столбцам допускает широкие обобщения. О простейшем из них говорится в дополнении 3,
Задачи и дополнения
1. Для разобранного в данном параграфе примера найти число необнаруживаемых тройных ошибок. Какую часть они составляют от общего числа тройных ошибок?
2. Кодовые слова в примере на стр. 42 содержат 9 информационных символов и 7 проверочных, так что общая длина кодового слова равна 16. Такого числа символов достаточно, чтобы исправлять любые одиночные и обнаруживать любые двойные ошибки. Чтобы достичь того же эффекта для кода с повторением, нужно каждый информационный символ повторить 4 раза, так что общая длина кодового слова будет равна 36. Сравнение явно не в пользу кода с повторением. Справедливости ради надо все же отметить, что код с повторением обладает по сравнению с использованным в примере кодом некоторыми преимуществами в смысле обнаружения ошибок более высокой кратности. Предлагаем читателю найти, например, долю необнаруживаемых тройных ошибок для указанного кода с повторением и сравнить ответ с результатом задачи 1. Интересно найти также долю исправимых (!) тройных ошибок для этого кода.
3. Пример из данного параграфа обобщается следующим образом (смотри также дополнение 12 к § 11). Пусть каждое сообщение кодируется двоичным словом длины тп. Расположим все символы в прямоугольную таблицу (матрицу) с т строками и п столбцами:
Таблица 17
«11 otI 2 «in ai, П + І
аг1 <*22 «2 n «2, П+І
<*mn am, n + 1
а.7!+1. І am + t, г і ®ra + t, n I aBi-Hl n + 1 ! I
44 KaiC и ррежде, добавим к каждой строке и к каждому столбцу по одному прQpepочному символу, так чтобы во всех строках и столбцах получились четные суммы. Аналогично прежнему выбираем символ сеи + 1, „+1. Полученное множество слов образует код, исправляющий любые одиночные и обнаруживающий любые двойные ошибки.
9. КОД ХЕММИНГА
Пусть количество сообщений, которые требуется передавать абоненту, равно 16. Для их безубыточного кодирования можно использовать двоичные слота Длины 4, но тогда код не будет корректировать ошибки. При использовании слов длины 5, как мы уже знаем, можно обнаружить, но не исправить любую одиночную ошибку. Впрочем, из дополнения 3 предыдущего параграфа вытекает, что если добавить 5 проверочных символов, то код сможет не только исправлять одиночные, но и обнаруживать двойные ошибки. Возникает вопрос: нельз я ли для этой дели обойтись меньшим количеством проверочных символов?
Вычислим сначала, каково минимальное число проверочных символов, необходимое для исправления любых одиночных ошибок. Нетрудно убедиться, что двух добавочных символов для этого недостаточно (предлагаем читателю проверить это самостоятельно).
Попробуем обойтись тремя проверочными символами, т. е. будем использовать для кодирования сообщений двоичные слова а^газ^а^ва, длины 7. Наша задача — определить, произошла ли ошибка, и если произошла, то в каком месте. Но это то же самое, что указать одно из восьми чисел от 0 до 7 (0 соответствует отсутствию ошибки).
Пусть требуется передать сообщение, кодируемое словом CX1CX2CXsOC4. Добавим к этому слову три символа сс6, а6, ос7, определяемые равенствами (здесь и до конца параграфа все равенства берутся по модулю 2):
а6=ос2+сс3+а4>
ab = cxj+ cx3+jx4, (1)
a7=cxj+a2+a4.
Если теперь нужно выяснить, допущена ли при передаче слова a1a2a3a4a5a6a7 одиночная ошибка в одном из символов сх4, «5, ос6, ос., то для этого достаточно вычислить сумму:
Sj=a4+a6+ae+a7. (2)
Ее значение, равное J, соответствует ответу «да», значение О — ответу «нет» (почему?).
45 В случае «да» проверим, нет ли ошибки в символах а„, а7, в случае «нет» — не содержится ли ошибка в символах ct2, а3. В каждом из этих случаев ответ дает значение
суммы:
s2=a2+a3-fae-f а7. (3)
Если, например, значения обеих сумм (2) и (3) равны 1, то ошибка содержится либо в ос,, либо в а7. Всего имеется четыре комбинации значений сумм S1-, s2; они приведены в следующей таблице:
Таблица 18
Si S. Место ошибки
1 1 ae или а7
1 0 а4 или а5
0 I а2 или а3
0 0 нет ошибки ИЛИ Ct1
Наконец в каждом из четырех случаев нужно выбрать одну из двух возможностей. Это позволит сделать значение суммы
S3=ai+a3+a5+a7. (4)
Итак, мы имеем три проверочных соотношения: Si=a4+a5+ae+a7 = 0, s2=aa+a3+ae+a7=0, (5)
S3=ai+a3+a5+a7=0,
которые позволяют либо установить, что ошибки нет, либо однозначно указать ее место.
Отметим особо, что если произошла одиночная ошибка, то ее положение указывается числом с двоичной записью S1S2S3. Пусть, например, S1=I, s2=0, S3=I. Согласно таблице 18 ошибка допущена в четвертом или пятом разрядах; поскольку S3 = ], она — в пятом разряде, но S1S2S3=IOl как раз и есть двоичная запись числа 5.
Изученный здесь код — это код Хемминга длины 7 с четырьмя информационными символами.
В общем случае кодовые слова двоичного кода Хемминга, позволяющего исправить одиночную ошибку, имеют длину 2m—1 (т. — натуральное). Для определения положения ошибки тогда уж« нужно т проверок, т. е. т прове-
