Обнаруживающие и корректирующие коды.

Понятие помехоустойчивого кодирования

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

Понятие избыточности

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

Абсолютная избыточность сообщения (D_абс) характеризуется разностью между максимально возможным количеством информации (Н_max) и энтропией реального сообщения:

D_абс = Н_max – H,                                                                   (1-39)

а относительная избыточность соответственно равна:

Избыточность сообщений приводит к увеличению времени переда­чи. Для уменьшения избыточности следует повышать информатив­ность элементов сообщения. В реальных системах для повышения помехоустойчивости передаваемых сообщений избыточность вводят преднамеренно.

Обнаруживающие коды

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

Обнаружение ошибок при декодировании производится путем проверки принятых комбинаций на четность. Нарушение четности произойдет при появлении ошибок нечетной кратности. Это позволяет обнаружить такие ошибки при проверке. Появление четных ошибок не приводит к изменению четности, поэтому такие ошибки не обнару­живаются. Проверка на четность сводится к определению суммы всех символов кодовой комбинации по модулю 2:

 Корректирующие коды

Корректирующими называются коды позволяющие обнаруживать и исправлять ошибки. Идею представления корректирующих кодов можно представить с помощью N-мерного куба. Возьмем трехмерный куб (рис.5.3), длина ребер, в котором равна одной единице. Вершины такого куба отображают двоичные коды. Минимальное расстояние между вершинами определяется минимальным количеством ребер, находящихся между вершинами. Это расстояние называется кодовым (или хэмминговым) и обозначается буквой d.

Влияние кодового расстояния на возможности кода

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

Пример

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