Кодовое расстояние

Для оценки корректирующих свойств кода используют еще понятие минимального кодового расстояния dmin.

Кодовое расстояние d(A, В) для кодовых комбинаций А и В определяется числом символов, которыми они отличаются друг от друга.

Для определения d(A, В), которое называют еще расстоянием по Хэммингу, достаточно вычислить вес третьей кодовой комбинации, которая получается в результате сложения по mod2 исходных комбинаций А и В. Весом V(S) двоичной кодовой комбинации будем называть число единиц в ней.

Пример 1. Найти d(A, В) для кодовых комбинаций А и В:

А = 0110111002; В = 1001110012.

Для этого сложим их по mod2 и найдем вес суммарной двоичной комбинации

которая и определяет кодовое расстояние заданных комбинаций d(A, В).

Если коды рассматривать как некоторые геометрические (пространственные) фигуры (например, триаду можно представить в виде единичного куба, имеющего координаты вершин, которые отвечают двоичным символам (рис. 3.48)), то в этом случае кодовое расстояние воспринимается как сумма длин ребер между соответствующими вершинами куба (принято, что длина одного ребра равна единице). Тогда, например, d(D, С) = 3.

Геометрическое представление кодов

Рис. 3.48. Геометрическое представление кодов

Минимальное кодовое расстояние dmin — это минимальное расстояние, взятое по всем параметрам разрешенных кодовых комбинаций.

В теории кодирования показано, что систематический код способен обнаруживать ошибки только тогда, когда dmin > 2t, где t — кратность обнаруживаемых ошибок (для одиночных ошибок t = 1).

Действительно, при dmin > 2t никакой вариант t-кратной ошибки не может перевести одну разрешенную кодовую комбинацию в другую разрешенную.

Так, если d = 2, то при t = 1 ни одна из разрешенных 3-разрядных кодовых комбинаций не переходит в другую разрешенную. Множество тр может быть образовано по принципу четности в них числа 1. Так, КК 000,011,101,110 е {тр}; тогда 001,010,111,100 е {т3}. При таком

кодировании обнаружатся все одиночные ошибки (t = 1), а также другие ошибки нечетной кратности (тройные).

Если же dmin < 2t, то существует хотя бы одна пара кодовых комбинаций, отстоящих друг от друга на расстоянии, меньшем или равном 2t, и найдется такой вариант t-кратной ошибки, который трансформирует одну комбинацию в другую.

Пример 2. Для кодовых комбинаций А = 1011002 и В = 1000002 кодовое расстояние d (А, В) = 2, так как

Следовательно, 2-кратная ошибка вида S = 0011002 превратит кодовую комбинацию А в комбинацию В:

В случаях, когда необходимо не только обнаружить ошибку, но и исправить ее, минимальное кодовое расстояние должно удовлетворять условию dmin > 2t + 1.

Исправление ошибок. Общая идея исправления ошибок кратности не более t заключается в следующем. Число возможных кодовых комбинаций помехоустойчивого кода разбивается на классы по числу разрешенных кодовых комбинаций. Разбиение осуществляется таким образом, чтобы в каждый класс входили одна разрешенная кодовая комбинация и ближайшие к ней запрещенные. При декодировании определяется, какому классу принадлежит принятая кодовая комбинация. Если она принята с ошибкой, т.е. является запрещенной, то исправляется на разрешенную кодовую комбинацию, принадлежащую тому же классу.

Например, для исправления одиночной ошибки (t= 1) каждой разрешенной кодовой комбинации сопоставим подмножество запрещенных. Чтобы эти подмножества не пересекались, d между разрешенными КК должно быть не менее трех, т.е. dmin > 3 . Тогда за разрешенные кодовые комбинации можно принять А0 = 0002 и А7 = 1112 и приписать каждой из них подмножество тех запрещенных комбинаций, к которым может привести одиночная ошибка.

 
Посмотреть оригинал
< Пред   СОДЕРЖАНИЕ   ОРИГИНАЛ   След >