Обнаруживающая и исправляющая способность кодов

Рассмотрим возможность обнаружения и исправления ошибок на простейшем примере. Предположим, что информация передается одноразрядным двоичным кодом. То есть передается информация 0 или 1. Число возможных кодовых комбинаций N 0=2 n 0, где n 0=1, N 0=21=2. В каждой кодовой комбинации добавим еще один разряд: n = n 0+1=1+1=2. Число кодовых комбинаций N =2 n =22=4. Эти комбинации составляют множество, состоящее из 00, 01, 10, 11. Это множество разделим на два подмножества разрешенных и запрещенных комбинаций. К числу разрешенных отнесем те комбинации, у которых сумма единиц всегда четная. Разрешенными выберем такие комбинации, которые отличаются друг от друга двумя разрядами – это 00 и 11. При таком выделении разрешенных комбинаций любая одиночная (или нечетная) ошибка будет изменять число единиц на нечетное. Принятая кодовая комбинация в этом случае переходит в подмножество запрещенных и ошибка будет обнаружена.

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

Рассмотрим сказанное на геометрической модели трехразрядного двоичного кода при помощи которого можно получить 23=8 комбинаций. А именно: 000, 001, 010, 011, 100, 101, 110, 111. Каждую новую комбинацию можно представить точкой в трехмерном пространстве (рис. 3).

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

2 t s 1.

комбинации находятся в той же области, что и комбинация 000.

Рис. 3. Геометрическая модель помехоустойчивого кода

Рассмотренные примеры показывают, что для обнаружения одиночных ошибок кодовые комбинации должны различаться не менее чем двумя разрядами. Для исправления одиночной ошибки кодовые комбинации должны различаться не менее чем тремя разрядами. Это различие именуют кодовым (Хэминговым) расстоянием. Под кодовым расстоянием понимают минимальное число позиций, на которых символы данной кодовой комбинации отличаются от символов другой кодовой комбинации. Например, для показанных на рис. 4 комбинаций кодовое расстояние d равно 3.

Рис. 4. Кодовое расстояние между двумя кодовыми комбинациями

В общем случае кодовое расстояние между комбинациями выражается формулой:

		n
	d(a, b)	(аi bi),	(1)
		i 0
где	– операция сложения по модулю два;

а =(а 0, a 1,..., a n-1); b =(b 0, b 1,..., b n-1).

Пользуясь расстоянием Хэмминга как метрикой в множестве кодовых слов можно выделить зоны исправления и обнаружения ошибок.

Утверждение. Если код используется только для обнаружения ошибок, то, чтобы обнаружить в кодовом слове произвольную комбинацию из s ошибок, необходимо и достаточно, чтобы расстояние Хэмминга для любых двух разрешенных кодовых слов было на 1 больше, чем s (количество обнаруживаемых ошибок): d min a, b s 1

В соответствии с утверждением в данном примере могут быть обнаружены ошибки кратные s =1 и s =2. При s =3 передаваемая кодовая комбинация переходит в другую разрешенную комбинацию. Ошибка не обнаруживается.

Утверждение. Если код используется только для исправления ошибок, то, чтобы исправить t ошибок необходимо и достаточно, чтобы d min a, b 2 t 1.

Утверждение. Для того, чтобы исправить t и обнаружить s ошибок в кодовом слове, необходимо и достаточно, чтобы d min a, b

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