Избыточность кодов

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

Понятие избыточности легко пояснить следующим примером.

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

Действительно, по теореме Котельникова (§ 1.7), непрерывное сообщение (сигнал) можно передать последовательностью мгновенных отсчетов его значений с промежутками между ними :

где f _max – верхняя граничная частота в спектре сигнала.

При наличии помех промежутки между отсчетами (Δ t_n) необходимо уменьшать, т.е.

В этом случае мы увеличиваем число отсчетов и, следовательно, увеличиваем избыточность сообщения и тем самым повышаем его помехозащищенность.

Пусть сообщение из n символов содержит количество информации I. Если сообщение обладает избыточностью, то его (при отсутствии шума) можно передать меньшим числом символов n₀ (n₀ < n). При этом, количества информации (I ₁и I _1max), приходящиеся на один символ сообщения, будут связаны соотношением:

I₁ = I/n < I _1max = I/n₀

и, следовательно,

n ∙ I ₁ = n₀ ∙ I _1max.

За меру избыточности принимается величина R:

(2.3)

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

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

По наличию избыточности коды также делятся на избыточные и неизбыточные. Для неизбыточных кодов характерно то, что они позволяют просто определить различные символы сообщения. Переход от неизбыточного кода к избыточному осуществляется путем добавления позиций в кодовых символах, которые можно получить либо путем различных логических операций, выполняемых над основными информационными позициями, либо путем использования алгоритмов, связывающих неизбыточный и избыточный коды. Например, если есть символы сообщения А₁; А₂; А₃; А₄, то их можно закодировать в двоичном неизбыточном коде:

А₁ = 00; А₂ = 01; А₃ = 10; А₄ = 11.

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

А₁ = 000; А₂ = 011; А₃ = 101; А₄ = 110.

Особенностью такого кода является то, что он позволяет обнаружить любую единичную ошибку (ошибку в одной из позиций кода), выявившуюся в процессе передачи кода.