Корректирующая способность кода.

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

Рассмотрим это на конкретных примерах.

Пусть нужно построить код, обнаруживающий все ошибки кратностью и ниже.

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

В качестве примера рассмотрим код со значностью . Все возможные комбинации такого кода представлены в табл. 2.1. Матрица расстояний между кодовыми комбинациями имеет вид (табл. 2.2).

Возможные комбинации кода.

Таблица 2.1

А1	А2	А3	А4	А5	А6	А7	А8
000	001	010	011	100	101	110	111

Матрица расстояний между кодовыми комбинациями.

Таблица 2.2

	А1	А2	А3	А4	А5	А6	А7	А8
А1	0	1	1	2	1	2	2	3
А2		0	2		2	1	3	2
А3			0	1	2	3	1	2
А4				0	3	2	2	1
А5					0	1	1	2
А6						0	2	1
А7							0	1
А8								0

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

А1=000

А4=011

А6=101

А7=110

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

А₁=000

А₈=111

Очевидна справедливость условия: .

Следовательно, в данном случае двукратные ошибки не могут быть обнаружены, так как в результате таких ошибок одни разрешенные комбинации переходят в другие со значностью . Пусть теперь необходимо построить код, обеспечивающий устранение однократных ошибок. Выбираем в качестве первой разрешенной комбинации А₁=000. При наличии однократных ошибок комбинация А₁ может перейти в одну из следующих запрещенных комбинаций: А₂=001, А₃=010, А₅=100. Комбинации А₂, А₃ и А₅ можно принять в качестве подмножества запрещенных комбинаций комбинации А₁. Последнее означает, что в случае приема одной из комбинаций этого подмножества выносится решение что передана комбинация А₁.

Пусть в качестве второй разрешенной комбинации выбирается комбинация, отстоящая от первой на расстоянии , например комбинации А₄=011. Ей должно соответствовать подмножество запрещенных комбинаций А₃=010, А₂=001 и А₈=111. Однако получилось пересечение подмножеств. При приеме запрещенных сигналов А₃ или А₂ нельзя однозначно установить, какой был передан сигнал — А₁ или А₄.

Если же в качестве второй разрешенной комбинации выбрать комбинацию, отстоящая от А₁ на расстоянии , т.е. комбинацию А₈=011, которой соответствует подмножество запрещенных комбинаций А₄=011, А₆=101 и А₇=110, то в этом случае подмножества не пересекаются. Следовательно, при обеспечивается устранение всех однократных подмножеств.

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

Аналогично рассуждая, можно установить, что для исправления всех ошибок кратности не более и одновременного обнаружения всех ошибок кратности не более (при ) кодовое расстояние должно удовлетворять условию: .

При этом нужно иметь в виду, что если обнаруженная кодом ошибка имеет кратность , то такая ошибка исправлена быть не может, т.е. в данном случае код только обнаруживает ошибку.

Дата добавления: 2015-07-08