Коды, обнаруживающие и исправляющие ошибки

Помехоустойчивыми (корректирующими) называются коды, позволяющие обнаружить и исправить ошибки в кодовых комбинациях. Отсюда и деление кодов на две большие группы: 1) коды с обнаружением ошибок; 2) коды с обнаружением и исправлением ошибок.

1)Если использовать двоичный код с длиной кодовой комбинации равной 3на все сочетания, получается восемь кодовых комбинаций. Такой код является непомехоустойчивым. Если же уменьшить число используемых комбинаций с восьми до четырех, то появиться возможность обнаружения одиночных ошибок. Для этого выберем только такие комбинации, которые отстоят друг от друга на расстояние d = 2, например, 000, 110, 011 и 101. Остальные кодовые комбинации не используются. Если будет принята комбинация 100, то очевидно, что при ее приеме произошла одиночная ошибка. Представленные комбинации построены по определенному правилу, а именно содержат четное число единиц, а принятая комбинация 100 – нечетное. Можно утверждать, что комбинация 100 образовалась при искажении разряда одной из разрешенных комбинаций, но определить, какая именно комбинация искажена, невозможно. Поэтому такие или подобные им коды называют кодами с обнаружением ошибок.

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

2)Если кодовые комбинации составлены так, что отличаются друг от друга на кодовое расстояние d > =3, то они образуют корректирующий код, который позволяет по имеющейся в кодовой комбинации избыточности не только обнаруживать, но и исправлять ошибки.

Составление корректирующих кодов производится примерно по следующему правилу. Сначала определяется количество контрольных символов r, которое следует добавить к данной кодовой комбинации, состоящей из k информационных символов. Далее устанавливается место, где эти контрольные символы должны быть расставлены в комбинации, и их состав, то есть является ли данный контрольный символ 1 или 0. На приеме обычно применяется проверка на четность определенной части разрядов.

Как пример рассмотрим код Хемминга:

Данный код относится к числу систематических кодов. По существу, это целая группа кодов, при d _min = 3 исправляющая все одиночные или обнаруживающая двойные ошибки, а при d _min = 4 исправляющая одиночные и обнаруживающая двойные ошибки.

Рассмотрим Код Хэмминга, исправляющий все одиночные ошибки.

В качестве исходного кода берется двоичный код на все сочетания с числом информационных символов k, к которому добавляется m контрольных символов. Таким образом, общая длина закодированной комбинации n=k+r.

1)Кодирование.

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

С помощью m контрольных символов можно описать 2^r событий. Значит, должно быть выполнено условие

2^r ≥ n+1=k+r+1

-Размещение контрольных символов.Для удобства обнаружения искаженного символа целесообразно размещать их на местах, кратных степени 2, т.е. на позициях 1, 2, 4, 8 и т.д. Информационные символы располагаются на оставшихся местах. Поэтому, например, для девятиэлементной закодированной комбинации можно записать: r 1, r 2, k 5, r 3, k 4, k 3, k 2, r 4, k 1

-Далее определяют состав контрольных символов

- Затем составляются проверки

2)Декодирование.

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