Принципы обнаружения и исправления ошибок

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

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

Рис.7.1 К пояснению принципа кодирования

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

При построении кодов, исправляющих ошибки, все множество кодовых комбинаций разбивается на ряд непересекающихся подмножеств (Рис 7.1 б).

В каждом подмножестве одна разрешенная комбинация. При приеме любой комбинации из данного подмножества потребителю выдается разрешенная комбинация этого подмножества.

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

Кодовое расстояние между i-ю и j-ю кодовыми комбинациями определяется по формуле

,

где - значение символов -й позиции i-й и j-й кодовых комбинаций.

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

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

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

Обозначим число информационных разрядов в передаваемом сообщенни . К ним добавятся проверочных разрядов.

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

ошибка отсутствует - 1 случай;

одиночная ошибка - случаев; двукратная ошибка - случаев;

ошибка кратности - случаев

где - число соединений с по , .

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

откуда

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

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