Связь между корректирующей способностью кода и кодовым расстоянием

Важная характеристика помехоустойчивого кода – наименьшее расстояние между разрешенными кодовыми комбинациями d_min. Оно обеспечивает корректирующие свойства кода.

Проиллюстрируем этот подход для (3,2)-кода: количество информационных разрядов k = 2, следовательно, число разрешенных кодовых комбинаций S_р = 2² = 4; общее число кодов S=2³ =8. Число проверочных бит r = n – k = 1 и устанавливать их значение условимся таким образом, чтобы количество «единиц» во всех кодовых комбинациях было бы четным (по этой причине такой проверочный бит называется битом четности).

Будем обозначать разрешенные кодовые комбинации U_i. Их информационная часть может принимать значения 00, 01,10 и 11 (обозначим эти биты a₁и a₂); проверочный бит b принимает значения, приведенные в таблице. Последняя колонка содержит суммы (количество) бит со значением "1" в каждой кодовой комбинации. Любую из 8 существующих для n = 3 кодовых комбинаций можно считать вектором в пространстве, построенном на единичных векторах a₁, a₂, b – это иллюстрируется рисунком 5.3. Отметим разрешенные комбинации ноликами; остальные, очевидно, будут запрещенными - их отметим крестиками. Видно, что минимальное кодовое расстояние между разрешенными комбинациями равно 2 (расстояние между разрешенными вершинами по ребрам куба). На рисунке однократной ошибке соответствует переход из вершины куба в соседнюю вершину. Любая однократная ошибка переводит разрешенную комбинацию в запрещенную, следовательно, может быть обнаружена. Однако исправить такую ошибку нельзя, поскольку в любую из запрещенных вершин за один шаг можно попасть, по крайней мере, из двух разрешенных.

Рис. 5.3. К вопросу о связи кодового расстояния и корректирующей способности кода.

Обобщим рассуждения. Пусть необходимо построить код, обнаруживающий все ошибки кратности τ и меньше. Построить такой код – это значит из множества S возможных комбинаций выбрать S_p разрешенных комбинаций так, чтобы любая сумма по модулю 2 с любым вектором ошибок с весом ω ≤ τ не дала бы в результате никакой другой разрешенной комбинации. Для этого необходимо, чтобы наименьшее кодовое расстояние удовлетворяло условию

(5.2)