Избыточность кодирования

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

Абсолютная недогруженность на символ сообщений такого источника

 бит/символ.

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

,

где  коэффициент сжатия (относительная энтропия).

Н и Н_макс берутся относительно одного и того же алфавита.

Кроме общего понятия избыточности существует частные виды избыточности Избыточность, обусловленная неравновероятным распределением символов в сообщении,

.

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

.

Полная информационная избыточность

. (48)

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

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

Фактически для передачи сообщения  достаточно иметь длину кодовой  комбинации

,

где N – общее количество передаваемых сообщений.

L можно представить и как  ,

где m₁ и m₂ – соответственно качественные признаки первичного и вторичного алфавитов. Поэтому для 5 в двоичном коде можно записать   дв. символа.

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

В общем случае избыточность от округления ,

где  , k – округлённое до ближайшего целого числа значение  . Для нашего примера .

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

максимальная нагрузка на символ может  быть лишь при равномерном появлении  символов). Так, в трёхзначном коде (всего комбинаций 8) в первых пяти общее число нулей в два  раза больше числа 1, для первых 11 комбинаций четырёхзначного двоичного кода соотношение нулей и единиц – 27 к 17, но уже в 1,58 раза больше…

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

Избыточность – не всегда нежелательное  явление. Для повышения помехоустойчивости кодов избыточность необходима и  её вводят искусственно в виде добавочных n_к символов (см. тему 6). Если в коде всего n разрядов и n_н из них несут информационную нагрузку, тоn_к= n- n_н характеризует абсолютную корректирующую избыточность, а величина  характеризирует относительную корректирующую избыточность.

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

Наиболее эффективным способом уменьшения избыточности сообщения  является построение оптимального кодов.

Оптимальные коды - коды с практически нулевой избыточностью. Оптимальные коды имеют минимальную среднюю длину кодовых слов – L. Верхняя и нижняя границы L определяются из неравенства

,

где H – энтропия первичного алфавита, m – число качественных признаков вторичного алфавита.

В случае поблочного кодирования, где  каждый из блоков состоит им M независимых буквa₁, a₂, …, a_м, минимальная средняя длина кодового блока лежит в пределах

.

Общее выражение среднего числа  элементарных символов в букву сообщения  при блочном кодировании

.

С точки информационной нагрузки на символ сообщения поблочное кодирования  всегда выгоднее, чем побуквенное.

Суть блочного кодирования можно  уяснить на примере представления  десятичных цифр в двоичном коде. Так, при передаче цифры 9 в двоичном коде необходимо затратить 4 символа, т. е. 1001. Для передачи цифры 99 при побуквенном кодировании – при поблочном – 7, так как 7 двоичных знаков достаточно для передачи любой цифры от 0 до 123; при передаче цифры 999 соотношение будет 12 – 10, при передаче цифры 9999 соотношение будет 16 – 13 и т. д. В общем случае «выгода» блочного кодирования получается и за счет того, что в блоках происходит выравнивание вероятностей отдельных символов, что ведёт к повышению информационной нагрузки на символ (см. задачу 5.11) .

При построении оптимальных кодов  наибольшее распространение нашли  методики Шеннона – Фано и Хаффмена [14,15].

Согласно методике Шеннона –  Фано построение оптимального ансамбля из сообщений сводится к следующему:

1-й шаг. Множество из сообщений  располагается в порядке убывания  вероятностей.

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

3-й шаг. Первой группе присваивается  символ 0, второй группе символ 1.

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

5-й шаг. Первым группам каждой  из подгрупп вновь присваивается  0, а вторым – 1. Таким образом,  мы получаем вторые цифры кода. Затем каждая из четырёх групп  вновь делится на равные(с точки зрения суммарной вероятности) части до тех пор, пока в каждой из подгрупп не останется по одной букве.

Согласно методике Хаффмена, для построения оптимального кода N символы первичного алфавита выписываются в порядке убывания вероятностей. Последние n₀ символов, где  1 и  целое число, объединяют в некоторый новый символ с вероятностью, равной сумме вероятностей объединенных символов. Последние символы с учетом образованного символа вновь объединяют, получают новый, вспомогательный символ, опять выписывают символы в порядке убывания вероятностей с учетом вспомогательного символа и т. д. до тех пор, пока сумма вероятностей m оставшихся символов после  го выписывания в порядке убывания вероятностей не даст сумме вероятность, равную 1. На практике обычно, не производят многократного выписывания вероятностей символов с учетом вероятности вспомогательного символа, а обходятся элементарным геометрическим построением, суть которых сводится к тому, что символы кодируемого алфавита попарно объединяются в новые символы, начиная с символов, имеющих наименьшую вероятность. Затем с учетом вновь образованных символов, которым присваивается значения суммарной вероятности двух предыдущих, строят кодовое дерево, в вершине которого стоит символ с вероятностью 1. При этом отпадает необходимость в упорядочивании символов кодируемого алфавита в порядке убывания вероятностей.

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

Максимально эффективными будут те ОНК, у которых  .

Для двоичных кодов

,

так как  . Очевидно, что равенство (52) удовлетворяется при условии, что длина кода во вторичном алфавите

.

Величена l_i точно равна H, если  , где n – любое целое число. Если n не является целым числом для всех значений букв первичного алфавита, то  и, согласно основной теории кодирования1, средняя длина кодового слова приближается к энтропии источника сообщений по мере укрупнения кодируемых блоков.

Эффективность ОНК оценивают при  помощи коэффициента статистического сжатия:

,

который характеризует уменьшение количества двоичных знаков на символ сообщения при ОНК по сравнению  с применением методов нестатистического  кодирования и коэффициента относительной эффективности

.

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

Для наиболее общего случая неравновероятных и взаимозависимых

Для случаев неравновероятных и взаимозависимых символов

 

 

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

m – число качественных признаков строящегося оптимального кода.