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

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

. (1.3)

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

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

(1.4)

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

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

(1.5)

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

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

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

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

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

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

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

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

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

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

Дата добавления: 2014-01-11