1.3. Целесообразность применения корректирующих кодов

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

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

(1.2)

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

1.4. Обнаружение и исправление ошибок корректирующими кодами

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

. (1.3)

где для простого кода , так как.

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

(1.4)

где , , () - априорная вероятность передачи кодового слова (),() - переходная вероятность приема кодового словапри условии передачи слова().

Вектор ошибок определяет различие между принятым словоми переданным:

(1.5)

Если нет ошибок при передаче двоичного кодового слова , принятое кодовое словосовпадает с, и вектор ошибокво всех разрядах содержит. Число ненулевых символов в векторе ошибок дает еговес .

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

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

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

Пример 1.4.2. Пусть число , перешедших вв каждом кодовом слове из-за действия помех, не равно числу, перешедших в. Тогда двоичные коды с постоянным весомобнаруживают все ошибки кратности. В полностью асимметричном канале связи возможен лишь один вид ошибок - преобразованиевилив. В нем такой код находит все ошибки. В симметричном канале с вероятностью искажения символавероятность пропуска ошибкив первом приближении определяется как вероятность одновременного искажения однойи одного. Для телеграфного кода № 3, где- число сочетаний изэлементов по,.

Пример 1.4.3. Каждое кодовое слово наиболее простого из линейных систематических двоичных кодов содержитпроверочный символ, равный сумме повсех информационных символов. Это - код спроверкой на четность. Для него кодовое расстояние , что позволяет гарантированно обнаружить лишь однократные ошибки. Слова такого кода имеют только четные веса. Вероятность пропуска ошибки вом приближении равна вероятности искажениях символов:.

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

Контроль на четность делается по строкам и по столбцам. Если, например, нарушение четности обнаружено для -ой строки и-ого столбца, то символматрицы - ошибочный. Исправление обнаруженной ошибки достигается заменой этого символа (- наили- на).

Контроль по методу четности (или нечетности) применяют при записи-считывании информации в запоминающих устройствах и при выполнении арифметических операций на ЭВМ (см. Приложение).

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