Коды, исправляющие ошибки
Содержание | Назад | Вперед | Лабораторные | О курсе

  Содержание



 

1.3. Кодовое расстояние и исправление ошибок

Одним из важнейших параметров кода является кодовое расстояние. Кодовым расстоянием или просто расстоянием кода V называется минимальное расстояние между двумя различными кодовыми словами, т. е.

dV = min d(x, y), x y и x, y Î V.

Для двоичного кода V под расстоянием понимается расстояние Хэмминга.

Теорема 1.1. Код V исправляет все комбинации из t или менее ошибок, если и только если кодовое расстояние не меньше, чем 2t +1, т. е. dV ≥ 2t +1.

Доказательство теоремы основано на построении сфер с радиусом t вокруг каждого кодового слова. Для того чтобы каждая ошибка кратности t была исправлена, слово с такой ошибкой должно содержаться внутри сферы, описанной только вокруг одного кодового слова. Таким образом, расстояние между центрами двух сфер, т. е. различными кодовыми словами должно быть не меньше 2t +1. Геометрическая иллюстрация приведена на рис. 3.

Теорема 1.2. Код V обнаруживает все комбинации из t или менее ошибок, если и только если кодовое расстояние не меньше, чем t +1, т.е. dVt +1.

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

Рис 3. Сферы, центрами которых являются кодовые слова.

Например, код с расстоянием 3 исправляет все одиночные ошибки и обнаруживает все двукратные ошибки. Код с расстоянием 4 обнаруживает все ошибки кратности 3 и менее; однако такой код по-прежнему исправляет только одну ошибку.

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

Пример. В качестве примера попробуем построить код с кодовым словом длины 5, который имеет 3 информационных символа и исправляет одну ошибку. Так как информационных символов три, то различных кодовых слов должно быть 23 = 8. Согласно теореме 1.1 расстояние между двумя различными кодовыми словами должно быть не меньше 2×1 + 1 = 3. Включим в код V слово 00000. Тогда все остальные кодовые слова имеют вес не менее 3. После включения в код V любого слова веса 3, ни одно слова веса 3 в код добавлено быть не может, так как расстояние между любыми двумя словами веса 3 равно 2. По той же причине слово 11111 веса 5 также не принадлежит коду V. Остаются 5 слов веса 4, которых не достаточно, чтобы иметь 8 кодовых слов.