3.6. Геометрический подход

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

Каждая вершина является возможным принятым сообщением; однако лишь некоторые выбранные вершины — это посылаемые сообщения. Одиночная ошибка в сообщении передвигает точку, соответствующую сообщению, вдоль ребра воображаемого куба в соседнюю вершину. Если потребовать, чтобы любое посылаемое сообщение находилось на расстоянии, по крайней мере, двух ребер от любого другого возможного сообщения, то ясно, что любая одиночная ошибка сдвинет сообщение вдоль ребра и принятое сообщение выйдет из множества посылаемых сообщений. Если минимальное расстояние между посылаемыми сообщениями равно трем ребрам куба, то любая одиночная ошибка оставит принятое сообщение ближе к посланному, чем к любому другому посылаемому сообщению, так что код будет исправлять одиночные ошибки.

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

1. Расстояние от любой точки до самой себя равно 0.

2. Расстояние от точки до отличной от нее точки у совпадает с расстоянием от точки у до точки и является положительным числом.

3. Выполнено неравенство треугольника, т. е. сумма длин двух сторон треугольника (расстояние от а до с плюс расстояние от с до не меньше длины третьей стороны (расстояние от а до

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

расстоянии от центра. Поверхность сферы радиуса 1 с центром это множество всех вершин пространства, находящихся на расстоянии 1, т. е. множество всех вершин, имеющих только один символ 1 в координатной записи (рис. 3.6.1). Число таких точек равно

Минимальное расстояние между вершинами множества посылаемых сообщений можно выразить в терминах корректирующих свойств. Для однозначности кода минимальное расстояние должно быть по меньшей мере равно 1 (табл. 3.6.1).

Таблица 3.6.1 (см. скан) Смысл минимального расстояния

Минимальное расстояние 2 дает обнаружение одиночных ошибок. Минимальное расстояние 3 дает исправление одиночных ошибок; каждая одиночная ошибка оставляет точку, расположенную ближе к первоначальному положению, чем к любому другому посылаемому сообщению. Ясно, что код с этим минимальным расстоянием может использоваться также для обнаружения двойных ошибок. Минимальное расстояние 4 дает исправление одиночных ошибок, а также обнаружение двойных ошибок. Минимальное расстояние 5 дает исправление двойных ошибок. Обратно, для того чтобы обнаруживать или исправлять ошибки соответствующей кратности, код должен иметь соответствующее минимальное расстояние.

Рис. 3.6.1. Трехмерные сферы с центрами (0, 0, 0) и (1, 1, 1) При исправлении одиночной ошибки (минимальное расстояние 3) каждое сообщение можно окружить единичной сферой, и эти сферы не перекрываются. Шар радиуса 1 состоит из центра и точек, по одной для каждой измененной координаты; таким образом, объем шара равен Объем всего -мерного пространства, т. е. число всех точек в нем, равен, очевидно,

Поскольку шары не пересекаются, максимальное число посылаемых сообщений должно удовлетворять условию

или

Поскольку то или Именно это неравенство было получено при использовании алгебраического подхода [см. (3.4.1)].

Получим теперь ограничения для кодов с исправлением ошибок более высокой кратности. Так, при исправлении двойных ошибок минимальное расстояние должно равняться пяти, и нужно расположить непересекающиеся шары радиуса 2 вокруг всех передаваемых сообщений. Этот шар состоит из центра точек, находящихся на расстоянии 1 от центра, а также тех точек, у которых изменены две координаты. Число таких точек равно биномиальному коэффициенту Деля объем всего пространства на объем такого шара, получаем верхнюю границу для числа возможных передаваемых сообщений в коде

Это неравенство не означает, что можно получить такое число сообщений в коде; оно дает лишь верхнюю границу этого числа. Аналогичные неравенства можно написать для больших шаров.

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

Задачи

3.6.1. Обобщите границы (3.6.1) и (3.6.2) на коды с исправлением большего числа ошибок.

3.6.2. Используя (3.6.2), вычислите и занесите в таблицу значения границы для кодов с исправлением двойных ошибок