Кодовое дерево для множества кодовых слов.

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

Рисунок 1.-Пример двоичного кодового дерева

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

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

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

На рисунке 2 изображены кодовые деревья, соответствующие кодам 2 и 3 (см. таблицу 2).

Рисунок 2.- Кодовые деревья для кодов 2 (а) и 3(б)

Вернемся к рассмотренному ранее примеру 1. Пусть вероятность появления сообщения а₁ равна 0,2; сообщения а₂ – 0,3; а₃ – 0,5. Тогда среднее число двоичных символов , приходящихся на одно сообщение

для кода 3, составляет

а для кода 2 –

т.е. код 2 в среднем экономичнее кода 3.

Рассмотрим еще один код – код 4, который сообщению а₁ ставит в соответствие 10; а₂ – 11; а₃ – 0. Среднее число двоичных символов, приходящихся на одно сообщение этого кода: , т.е. код 4 экономичнее и кода 3, и кода 2. Спрашивается, можно ли предложить код, который будет экономичнее кода 4? Как построить самый экономичный код для данного источника сообщений? Ответы на эти и многие другие вопросы дает основная теорема кодирования, сформулированная и доказанная впервые К. Шенноном для дискретного канала связи без помех.

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

В [1] показано, что существует способ кодирования, при котором

где - сколь угодно малая величина.

Метод Хаффмана. Одним из часто используемых методов эффективного кодирования является так называемый метод Хаффмана. Пусть сообщения входного алфавита А={а₁, а₂,…, а_к} имеют соответственно вероятности их появления p₁, p₂,…, p_к.

Тогда алгоритм кодирования Хаффмана состоит в следующем:

1. Сообщения располагаются в столбец в порядке убывания вероятности их появления.

2. Два самых маловероятных сообщения а_к-1 и а_к объединяем в одно сообщение b, которое имеет вероятность, равную сумме вероятностей сообщений а_к-1 и а_к, т.е. p_к-1+p_к. В результате получим сообщения а₁, а₂,…, а_к=2,b, вероятности которых p₁, p₂,…, p_к-2, (p_к-1+p_к). Полученные сообщения вновь располагаем в порядке убывания вероятностей.

3. Повторяем шаги 1 и 2 до тех пор, пока не получим единственное сообщение, вероятность которого равна 1.

4. Проводя линии, объединяющие сообщения и образующие последовательные подмножества, получаем дерево, в котором отдельные сообщения являются концевыми узлами. Соответствующие им кодовые комбинации можно определить, приписывая левым ветвям объединения символ «1», а правым – «0». Впрочем, понятия «левые» и «правые» ветви в данном случае относительны.

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

Не нашли, что искали? Воспользуйтесь поиском по сайту: