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

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

Естественно возникает вопрос о том, а все ли ошибки могут быть обнаружены? Предположим, что алфавит входных и выходных символов одинаков, и его объем равен . Тогда объем кода, а значит и мощность множества , составляют величину , а число запрещенных комбинаций (или мощность множества ) определится как . При передаче по каналу связи M кодовых комбинаций возможны их переходов в принятые наблюдения , из которых только будут правильными, тогда как остальные переходов сопровождаются искажениями. Как уже указывалось, решение об обнаружение ошибок в принятой последовательности принимается всякий раз, когда она оказывается в области . Подобной ситуации отвечают переходов и, значит, общее число обнаруживаемых ошибок составляет величину , что еще раз свидетельствует о возможности обнаружения ошибок только при условии , т.е. при введении избыточных символов. Сравнение же общего количества ошибок с числом обнаруживаемых демонстрирует, что не все ошибки удается зафиксировать. Последнее объясняется тем, что переход одной кодовой комбинации в другую под действием канальных помех невозможно обнаружить, причем общее количество подобных переходов составит величину .

Аналогичным образом реализуется и процедура исправления ошибок. Отличие заключается лишь в том, что все множество разбивается теперь на (по числу передаваемых сообщений) решающих областей , причем и при не пересекаются, а в каждую область решения включается только одна кодовая последовательность. Если оказывается, что вектор наблюдений принадлежит j- й области, т.е. , то принимается решение о том, что было передано слово и, значит, канальные ошибки, вызвавшие трансформацию в , будут исправлены. Поскольку области решений не перекрываются, то общее число исправляемых ошибок определяется числом запрещенных комбинаций, распределяемых между M решающими областями. Следовательно, и, значит, как и в случае обнаружения ошибок, их исправление возможно лишь при , т.е. при введении избыточности.

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

,

или в другой записи

,

где индекс опущен без ущерба для понимания: – вероятность ошибки при условии передачи фиксированного кодового вектора , - решающая область, отвечающая кодовому вектору .

Поскольку такие вероятности ошибок составляют набор из M величин (по числу кодовых слов), для интегрального описания надежности передачи необходимо свести их к какому-либо единому показателю. Чаще всего это делается введением:

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

– средней (полной) вероятности ошибки декодирования, рассчитываемой, как видно, согласно обычной формуле полной вероятности.

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

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