Коды, исправляющие ошибки

Особое значение имеют помехозащитные коды, которые могут исправлять ошибки определенной кратности. Соотношение между максимальной кратностью исправляемой ошибки q и кодовым расстоянием d определяется по формуле:

d ≥2q + 1.

В основу исправления ошибок положена следующая идея: определяется множество кодовых комбинаций, включающее все разрешенные и те запрещенные, которые получены при искажении ошибкой кратности не более q. Это множество разбивается на m+1 подмножеств, где m – число исходных кодируемых символов. В каждое из m подмножество входят: разрешенная кодовая комбинация и ближайшие к ней запрещенные, которые отстоят от разрешенной на расстояние не больше q. Еще одно подмножество составляют те кодовые комбинации, которые отстоят от исходной на расстояние больше q.

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

Пример 1. Построить помехозащитный код, исправляющий ошибку кратности 1, для передачи двух символов: a и b.

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

a 0,

b 1.

В силу приведенной выше формулы для расчета кодового расстояния для исправления ошибки и поскольку по заданию q = 1, имеем d = 3, таким образом, для исправления ошибки кратности 1 кодовое расстояние должно быть равно по меньшей мере 3.

Поскольку в первичном коде обеспечено расстояние между кодовыми комбинациями, равное 1, для выполнения условия d = 3 необходимо, чтобы проверочные разряды обеспечивали расстояние между кодовыми комбинациями, по меньшей мере, равным 2.

Очевидно, для этого число проверочных разрядов должно быть не меньше 2. Тогда разрешенные кодовые комбинации могут иметь вид:

Из таблицы видно, что кодовое расстояние равно 3, а построенные кодовые комбинации являются разрешенными.

Определим общее число всевозможных комбинаций, если число разрядов кода равно 3:

разрешенные кодовые комбинации = {000, 111};

запрещенные кодовые комбинации = {001, 010, 011, 100, 101, 110}.

Определим подмножества кодовых комбинаций, которые отстояли бы от каждой разрешенной на минимальное расстояние, равное 1: