Префиксные коды

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

Если код префиксный, то, читая принятую последовательность подряд с начала до конца, можно установить, где кончается одно кодовое слово и начинается следующее. Например, если код префиксный и в последовательности встретился код 110, то, очевидно, в коде не должно содержаться слов (1), (11). Закодировано префиксным кодом с а₁ = (00), а₂ =(01), а₃ = (101), а₄ = (100). На рис. 1 представлен граф (кодовое дерево) префиксного кода с сообщениема₁ = (0), а₂ =(1), а₃ = (11), а₄ = (111). Из рис. 1 следует, что если свойство префикса не выполняется, то некоторые промежуточные вершины дерева могут соответствовать кодовым словам.

Рис. Кодовое слово непрефиксного кода

Примерами префиксных кодов являются коды Шеннона-Фано и Хаффмана. Код Шеннона-Фано

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

Пример:

Р(а₁)=0,1 Р(а₂)=0,15 Р(а₃)=0,15 Р(а₄)=0,1 Р(а₅)=0,05

Р(а₆)=0,05 Р(а₇)=0,2 Р(а₈)=0,07 Р(а₉)=0,09 Р(а₁₀)=0,04

Рис. Кодовое дерево кода Шеннона – Фано

Методика Шеннона – Фано не всегда приводит к однозначному построе­нию кода, поскольку при разбиении на части можно сделать больше по веро­ятности как верхнюю, так и нижнюю части. Кроме того, методика не обеспе­чивает отыскания оптимального множества кодовых слов для кодирования данного множества сообщений. (Под оптимальностью подразумевается то, что никакое другое однозначно декодируемое множество кодовых слов не имеет меньшую среднюю длину кодового слова, чем заданное множество.) Предложенная Хаффманом конструктивная методика свободна от отмечен­ных недостатков.

Код Хаффмана

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

Для нахождения кодовой комбинации необходимо проследить путь перехода знака по строкам и столбцам таблицы. Это наиболее наглядно осуществимо по кодовому дереву. Из точки, соответ­ствующей вероятности 1, направляются две ветви, причем ветви с большей вероятностью присваиваем символ 1, а с меньшей – 0. Такое последователь­ное ветвление продолжается до тех пор, пока не дойдем до вероятности каж­дой буквы. Двигаясь по кодовому дереву сверху вниз, можно записать для каждого сообщения соответствующие ему кодовые комбинации.

Пример:

Р(а₁)=0,1 Р(а₂)=0,15 Р(а₃)=0,15 Р(а₄)=0,1 Р(а₅)=0,05

Р(а₆)=0,05 Р(а₇)=0,2 Р(а₈)=0,07 Р(а₉)=0,09 Р(а₁₀)=0,04

а₁=001 а₂=110 а₃=101 а₄=000 а₅=1000 а₆=11101 а₇=01 а₈=1001 а₉=1111 а₁₀=11100

Рис. Кодовое дерево кода Хаффмана