Мы говорили о корректирующих свойствах кодов с избыточностью

Рассмотрим теперь простые примеры, которые связывают кодовое расстояние d с корректируюшими свойствами кода.

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

Например, при n=3 разрешенные комбинации образуют следующее множество:

000,001,010,011, 100, 101, 110, 111 с кодовым расстоянием d=1.

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

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

011, 101, 110 -разрешенные комбинации;

010, 100, 111 - запрещенные комбинации.

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

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

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

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

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

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

Разрешенной комбинации 000 соответствуют запрещенные комбинации 001 010 100.

Если принято любое кодовое слово из этого набора, то по принципу максимального правдоподобия можно предположить, что передавалось кодовое слово 000.

Разрешенной комбинации 111 соответствуют запрещенные комбинации 011 101 110.

Если принято любое кодовое слово из этого набора, то по принципу максимального правдоподобия передавалось кодовое слово 111.

Таким образом для кода 000 и 111 с d = 3 может быть исправлена одна ошибка.

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

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

d>=2S+1;

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

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

Это условие будет выполнено, если кодовые комбинации выбраны так, что среди них нет таких, которые находятся на расстоянии, меньше чем r+1. Если такой код использован для кодировки сообщения, тогда принятое кодовое слово Y, которого нет в списке разрешенных слов, является признаком обнаружением ошибки. Рассмотренные ранее 4 комбинации - 000, 011, 101, 110,- представляют код с обнаружением одиночной ошибки, потому что для них кодовое расстояние d = 2. Для того, чтобы код исправлял все ошибки, кратность которых не превосходит s,.векторы каждой пары Xi, Xj должны находиться один от другого на расстоянии, не меньшем чем 2s + 1.

В общем случае для выявления ошибок кратности r, одновременного исправления ошибок кратности s необходимо и достаточно выполнение условия

d>=r+s+1.

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

Дата добавления: 2014-01-04