Коды, исправляющие ошибки

Основная задача теории кодирования

Пусть есть набор сообщений 1 ^? ^ п, которые нужно передавать по каналу связи. Сообщения будем кодировать нулями и единицами, т. е. каждому сообщению будем сопоставлять его код — слово из нулей и единиц (бинарный набор), который обычно называется кодовым словом. Мы ограничимся только случаем, когда все сообщения кодируются словами одинаковой длины. Будем считать, что ошибки при передаче могут только изменять значения некоторых битов. Вообще говоря, это не единственный вид ошибок. Возможны, например, выпадения и вставки — какой-то из битов может не дойти до приемника или, наоборот, из-за помех может произойти ложное срабатывание приемника и получится бит, которого никто не посылал. Мы такие ситуации рассматривать не будем.

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

Более удобно рассматривать другую задачу: даны п — длина кода, г — максимально допустимое число ошибок. Требуется найти максимальное число сообщений к. которое можно передать. Решив задачу про максимальное число сообщений, нетрудно получить и решение предыдущей задачи про код минимальной длины.

Мы приближенно решим эту задачу для произвольных п и г. Точное решение будет дано лишь для случая п — 2^m — 1 и г = 1, а также для п = 23, г = 3 (см. раздел 4.5). Введем расстояние между бинарными наборами.

где а = (ai,…, а"), 0 = (А,а_и&? {0,1}- (Это расстояние часто называется метрикой Хэмминга.)

Говоря попросту, р (а, р) — это число координат, по которым различаются наборы а и /3.

Введем еще одно определение: норма Ц7Ц — это число единичных координат в 7.

Читателю предлагается самостоятельно проверить справедливость следующего простого утверждения.

Утверждение 4.1. р (аД) = ||аф/3||, где

Пример 4.2. а = (101 011), р = (110), р (а, Р) = 4, =

= (101 101), ||аф#|| = 4.

Большая часть теории кодирования построена на так называемых групповых кодах, т. е. кодах, образующих группу (их также называют линейными кодами). Другими словами, множество кодовых слов {а¹,…, а⁹} образует группу относительно операции ф: для любых кодовых слов а¹, а³ выполняется а^гфо^ = а*, 1 ^ t, ^ q (достаточно проверить это утверждение, так как наличие обратного здесь очевидно — это сам элемент).

Теорема 4.3. Предположим, что мы имеем групповой код {а¹,…, а⁹} относительно операции ф (здесь и далее рассматриваются группы только относительно операции 0). Для минимального расстояния. между различными кодовыми словами выполняется соотношение:

Доказательство. р (а^г, а?) = а^% ф а³ = ||d^w||, причем а^и ф (0,…, 0) при а^г ф а³. Отсюда получаем оценку.

Ясно, что эта оценка достигается: набор (0,…, 0) обязательно принадлежит групповому коду, a ||d^w|| = ||&^иФ0|| = p (d^u, 6). Пусть передавалось сообщение.

а получено сообщение.

Мы предположили, что число ошибок не больше г. Поэтому />(<*',/3') < г. ?

Определение 4.4. Минимальное расстояние между кодовыми словами кода С называется кодовым расстоянием С.

Совокупность таких /З¹, что p (a^t,$^t) ^ г назовем шаром Хэмминга S_r(a^l) с центром в а^г и радиусом г.

Утверждение 4.5. Множество {d¹,…, а⁹} образует код с исправлением ошибок, если S_r(a^l) П S_r(&³) = 0 при i ф j.

Доказательство. Если при передаче сообщения а^г сделано не более г ошибок, то набор останется в шаре 5_г(о^г). Если шары не пересекаются, то мы можем однозначно восстановить центр шара по любой точке из этого шара. ?

Отсюда следует, что у кода, исправляющего г ошибок, кодовое расстояние не меньше 2г + 1.

Итак, чтобы построить код максимального размера, исправляющий г ошибок, нужно вложить в множество всех бинарных наборов Е" (булев куб) максимальное число неиересекающихся шаров Хэмминга радиуса г. В случае п = 2^т — 1, г = 1 можно так расположить шары, чтобы они покрывали куб Е^п и не пересекались. Ясно, что такой код имеет самый большой размер. Интересен вопрос, при каких других п и г можно разбиение Е^п на шары радиуса г. Оказывается, такое возможно лишь еще при одной паре п и г: п = 23, г = 3 (см. раздел 4.5).

Теорема 4.6 (теорема Хэмминга). При2г < п максимальное число сообщений к находится в следующих пределах

Доказательство. Подсчитаем, сколько точек попадает в шар радиуса г — это сам центр, все точки с одной измененной координатой (которую можно выбрать («) способами), все точки с двумя измененными координатами (которые можно выбрать («) способами), …, все точки с г измененными координатами (их можно выбрать («) способами). Так как шары не пересекаются, получаем верхнюю оценку.

Для оценки снизу построим пример кода (негруппового). Берем произвольную точку о¹ и строим вокруг нее шар радиуса 2 г. В качестве следующей точки берем произвольную точку вне этого шара а² и строим снова около нее шар радиуса 2 г. Третью точку выберем вне этих двух шаров. Далее аналогично. Заметьте, что каждый новый шар занимает не более, чем.

точек. Значит, число таких шаров будет не меньше.

Очевидно, что шары радиуса г с центрами в построенных точках не пересекаются, так как в построении использовались шары радиуса 2 г. ?

Теперь разберем случай п = 2^т — 1, г = 1.

Покажем, что.

т. е. при таких значениях параметров верхняя оценка в теореме Хэмминга достигается.

Вначале построим код, а потом определим его кодовое расстояние.

Справа выписываются вес бинарные наборы длины га, содержащие более одной единичной координаты. Слева — единичная матрица размера (2^т—(га+1))х (2^т—(га+1)). Рассмотрим множество наборов (оно называется кодом Хэмминга), которые получаются при суммировании строчек этой таблицы всеми возможными способами. В этом множестве 2²" ^-(^w+B наборов (результаты сложения различны для любого множества строчек). Заметим, что.

Найдем минимальное р{а^г, дР). Легко видеть, что р ^ 3, так как норма любого ненулевого набора, получаемого суммированием строчек таблицы, не меньше трех: если суммируем не менее трех строчек, то в левой части будет не менее трех единиц; если суммируем две строчки, то в левой части будет две единицы, а в правой (наборы разные) — хотя бы одна; в любой строчке таблицы также содержится не менее трех единиц.

Раз расстояния между кодовыми наборами нс меньше трех, шары радиуса 1 с центрами в этих наборах не пересекаются.

Пример 4.7. Составим таблиц}' для кода Хэмминга длины 7:

Складываем строчки произвольным образом и получаем 16 возможных комбинаций. Ими можно закодировать 16 сообщений, например, все 10 цифр и знаки операций. При передаче с помощью кода Хэмминга можно исправить одну ошибку, возникающую при передаче.