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

Под корректирующей способностью кода понимается его свойство обнаруживать и/или исправлять ошибку максимальной кратности 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 000

b 01 011

c 10 101

d 11 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.

Однократная ошибка в любом разряде переводит кодовую комбинацию в запрещенную кодом.

s, r – кратность ошибки