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

Из предыдущего следует, что при взаимно независимых ошибках наиболее вероятен переход в кодовую комбинацию, отличающуюся от данной в наименьшем числе символов.

Степень отличия любых двух кодовых комбинаций характеризуется расстоянием между ними в смысле Хэмминга или просто кодовым расстоянием. Оно выражается числом символов, в которых комбинации отличаются одна от другой, и обозначается через d.

Чтобы получить кодовое расстояние между двумя комбинациями двоичного кода, достаточно подсчитать число единиц в сумме этих комбинаций по модулю 2. Например:

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

Декодирование после приема может производиться таким образом, что принятая кодовая комбинация отождествляется с той разрешенной, которая находится от нее на наименьшем кодовом расстоянии.

Такое декодирование называется декодированием по методу максимального правдоподобия.

Очевидно, что при d = 1 все кодовые комбинации являются разрешенными. Например, при n = 3 разрешенные комбинации образуют следующее множество: 000, 001, 010, 011, 100, 101, 110, 111.

Любая одиночная ошибка трансформирует данную комбинацию в другую разрешенную комбинацию. Это случай безызбыточного кода, не обладающего корректирующей способностью.

Если d = 2, то ни одна из разрешенных кодовых комбинаций при одиночной ошибке не переходит в другую разрешенную комбинацию. Например, подмножество разрешенных кодовых комбинаций может быть образовано по принципу четности в них числа единиц, как это приведено ниже для n = 3:

Код обнаруживает одиночные ошибки, а также другие ошибки нечетной кратности. В общем случае при необходимости обнаруживать ошибки кратности до r включительно минимальное хэммингово расстояние между разрешенными кодовыми комбинациями должно быть по крайней мере на единицу больше r, т.е. d ≥ r + 1.

Действительно, в этом случае ошибка, кратность которой не превышает r, не в состоянии перевести одну разрешенную кодовую комбинацию в другую.

Для исправления одиночной ошибки каждой разрешенной кодовой комбинации необходимо сопоставить подмножество запрещенных кодовых комбинаций. Чтобы эти подмножества не пересекались, хэммингово расстояние между разрешенными кодовыми комбинациями должно быть не менее трех. При n = 3 за разрешенные комбинации можно, например, принять 000 или 111. Тогда разрешенной комбинации 000 необходимо приписать подмножество запрещенных кодовых комбинаций 001, 010, 100, образующихся в результате возникновения единичной ошибки в комбинации 000.

Подобным же образом разрешенной комбинации 111 необходимо приписать подмножество запрещенных кодовых комбинаций: 110, 011, 101, образующихся в результате возникновения единичной ошибки в комбинации 111:

В общем случае для исправления ошибок кратности S d между РКК должно удовлетворять соотношению:

d ≥ 2S + 1.

Для исправления всех ошибок кратности S и одновременного обнаружения всех ошибок кратности r d должно удовлетворять условию:

d ≥ r + S + 1.

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

В реальных каналах связи длительность импульсов помехи часто превышает длительность символа. При этом одновременно искажаются несколько расположенных рядом символов комбинации. Ошибки такого рода получили название пачек ошибок или пакетов ошибок. Длиной пачки ошибок называют число следующих друг за другом символов, начиная с первого искаженного символа и кончая последним искаженным символом, за которым следует не менее ρ неискаженных символов. Основой для выбора служат статистические данные об ошибках. Если, например, кодовая комбинация 00000000000000000 трансформировалась в комбинацию

и ρ принято равным трем, то в комбинации имеется два пакета длиной 4 и 5 символов.

Пример

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

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

Если характер и уровень помехи отличаются от предполагаемых, эффективность применения кода резко снизится. http://peredacha-informacii.ru/ Применение корректирующего кода не может гарантировать безошибочного приема, но дает возможность повысить вероятность получения на выходе правильного результата.