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

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

где b_ik и b_jk – k-ые символы кодовых комбинаций B_i и B_j соответственно. Чтобы получить кодовое расстояние между двумя комбинациями двоичного кода достаточно подсчитать число единиц в сумме этих комбинаций по модулю 2.

 

Å 1100001010

--------------------

0101110111 d=7

 

Минимальное расстояние, взятое по всем парам кодовых разрешенных комбинаций, называют минимальным кодовым расстоянием d_min или просто кодовым расстоянием d. Существуют также d_max, d_cp. Набор всех значений d определяет спектр D расстояний кода. Код с одним значением d называется эквидистантным.

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

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

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

Разрешенные комбинации: 000 011 101 110

Запрещенные комбинации: 001 010 100 111

Код обнаруживает одиночные ошибки, а также другие ошибки нечетной кратности (при n=3 - тройные).

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

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

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

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

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

· единичных ошибок (они располагаются на сфере радиусом d=1, и их число равно C_n¹=n);

· двойных ошибок (они располагаются на сфере радиусом d=2, и их число равно C_n² = n! / (2!(n-2)!)) и т.д.

Внешняя среда подмножества имеет радиус d=s и содержит C_n^s запрещенных кодовых комбинаций.

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

 

 

 

Рис. 6.2. Расстояния между подмножествами:

а) корректирующий код; б) обнаруживающий и корректирующий код.

Поскольку указанные подмножества не должны пересекаться (рис. 1.30а), минимальное кодовое расстояние между разрешенными кодовыми комбинациями должно удовлетворять отношению:

Нетрудно убедиться, что для исправления всех ошибок кратности s и одновременно обнаружения всех ошибок кратности r (r≥s) (см. рис. 1.30б), минимальное кодовое расстояние нужно выбирать из условия:

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

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

Если, например, кодовая комбинация 00000000000000000 трансформировалась в комбинацию 01001000010101000 и ρ принято равным 3, то в комбинации имеется 2 пакета длиной 4 и 5 символов.

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

ИЗБЫТОЧНОСТЬ КОДА.

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

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

Одной из основных характеристик корректирующего кода является избыточность кода, которую можно рассчитать по общей формуле (1.26). Однако в случае блоковых кодов удобнее пользоваться более простыми формулами, указывающими степень удлинения кодовой комбинации для достижения определенной корректирующей способности. Если на каждые n символов выходной последовательности кодера приходится k информационных и (n-k) проверочных, то относительная избыточность кода может быть выражена:

В первом случае . Во втором выражении

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

Однако не всегда целесообразно стремиться к использованию кодов, близких к оптимальным. Необходимо учитывать другой не менее важный показатель качества корректирующего кода – сложность технической реализации процессов кодирования и декодирования. Так, в случае использования надежной и высокоскоростной линии связи для повышения общей надежности СПИ более целесообразно использовать коды с большой избыточностью, но зато требующих наиболее простую (и, следовательно, надежную) техническую реализацию кодирующих и декодирующих устройств.