Кодовое расстояние и корректирующая способность кода

Под корректирующей способностью кода понимается его свойство обнаруживать и/или исправлять ошибку максимальной кратности q. Корректирующая способность кода связана с его кодовым расстоянием.

Расстоянием d_ij между кодами (кодовыми комбинациями) i и j называется число различных разрядов в кодовых комбинациях i и j. Например, если есть коды 01 и 10, расстояние между ними равно 2: они различаются в двух разрядах.

Кодовым расстоянием d для кода, содержащего m кодовых комбинаций, является минимальное расстояние между всеми парами кодовых комбинаций, т.е.

,

где i≠j, i=1,m; j=1,m.

Пусть есть кодовая таблица:

Исходные символы	Двоичные коды
a	00
b	01
c	10
d	11

Тогда расстояния между кодовыми комбинациями имеют значения:

d_ab = 1;        d_ad  = 2;        d_bd = 1;        d_ac  = 1;        d_bc = 2;        d_cd = 1.

Отсюда следует:

d = min{1, 2, 1, 1, 2, 1} = 1.

Это означает, что всякая ошибка кратности 1 (и более) переводит исходную кодовую комбинацию в другую кодовую комбинацию, которая также принадлежит коду.

Увеличить кодовое расстояние можно, введя в кодовые комбинации дополнительный разряд (или разряды). Тогда исходные разряды называют информационными, а дополнительный (или дополнительные) – проверочным (проверочными).

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

Для кодов из приведенной выше таблицы введем дополнительный разряд и сформируем его значение. Результат показан ниже:

Исходные символы	Информационные разряды кода	Проверочный разряд кода	Результирующий код
a	00	0	000
b	01	1	011
c	10	1	101
d	11	0	110

                               

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

Определим кодовое расстояние полученного кода. Для этого вначале выясним расстояния между кодовыми комбинациями:

d_ab = 2;        d_ad  = 2;        d_bd = 2;        d_ac  = 2;        d_bc = 2;        d_cd = 2.

Тогда d = min{2, 2, 2, 2, 2, 2} = 2.

Пусть передается кодовая комбинация, соответствующая символу c, – 101. Пусть на нее накладывается ошибка кратности 1. Возможные результаты искажения приведены в таблице:

Передаваемая кодовая комбинация	Ошибка	Принимаемая кодовая комбинация	Результат декодирования
101	001	100	Невозможно декодировать
101	010	111	То же
101	100	001	"-"

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