При кодировании сообщений считается, что символы сообщения порождаются некоторым источником информации. Источник считается заданным полностью, если дано вероятностное описание процесса появления сообщений на выходе источника. Это означает, что в любой момент времени определена вероятность порождения источником любой последовательности символов . Такой источник называется дискретным вероятностным источником.
Определение. Если вероятностный источник с алфавитом порождает символы алфавита независимо друг от друга, т.е. знание предшествующих символов не влияет на вероятность последующих, то такой источник называется бернуллиевским. Тогда для любого сообщения
,
, порождаемого источником, выполняется равенство:
где P(x) – вероятность появления символа x, – вероятность появления последовательности
.
Для другого класса источников (марковских) существует статистическая взаимосвязь между порождаемыми символами. В дальнейшем будем рассматривать кодирование стационарных (с неизменным распределением вероятностей) бернуллиевских дискретных источников без памяти.
Пусть имеется дискретный вероятностный источник без памяти, порождающий символы алфавита с вероятностями
. Основной характеристикой источникаявляется энтропия, которая представляет собой среднее значение количества информации в сообщении источника и определяется выражением (для двоичного случая)
.
Энтропия характеризует меру неопределенности выбора для данного источника.
Пример 4.1.1. Если , т.е. источник может породить только символ
, то неопределенности нет, энтропия
.
Источник с равновероятными символами , будет иметь максимальную энтропию
.
Определение. Величина называется энтропией на символ последовательности длины L, где
- множество всех сообщений источника длины L в алфавите A.
Определение. Обозначим через предел энтропии
при
. Эту величину называют предельной энтропией источника. Показано, что для стационарного бернуллиевского источника
Для практических применений важно, чтобы коды сообщений имели по возможности наименьшую длину. Основной характеристикой неравномерного кода является количество символов, затрачиваемых на кодирование одного сообщения.
Определение. Пусть имеется разделимый двоичный побуквенный код для источника, порождающего символы алфавита с вероятностями
, состоящий из n кодовых слов с длинами
. Средней длиной кодового слова называется величина
, которая показывает среднее число кодовых букв на одну букву источника.
Пример 4.1.2. Пусть имеются два источника с одним и тем же алфавитом и разными вероятностными распределениями
и
, которые кодируются одним и тем же кодом
.
Средняя длина кодового слова для разных источников будет различной
Определение. Побуквенный разделимый код называется оптимальным, если средняя длина кодового слова минимальна среди всех побуквенных разделимых кодов для данного распределения вероятностей символов.
Определение. Избыточностью кода называется разность между средней длиной кодового слова и предельной энтропией источника сообщений
Избыточность кода является показателем качества кода, оптимальный код обладает минимальной избыточностью. Задача эффективного неискажающего сжатия заключается в построении кодов с наименьшей избыточностью, у которых средняя длина кодового слова близка к энтропии источника. К таким кодам относятся классические коды Хаффмана, Шеннона, Фано, Гилберта-Мура и арифметический код.
Взаимосвязь между средней длиной кодового слова и энтропией дискретного вероятностного источника при побуквенном кодировании выражает следующая теорема.
Теорема 1 (Шеннон). Для бернуллиевкого источника с алфавитом и вероятностями
,
и любого разделимого побуквенного кода средняя длина кодового слова всегда не меньше энтропии
и можно построить разделимый побуквенный код, у которого средняя длина кодового слова превосходит энтропию не больше, чем на единицу:
Можно получить более сильные результаты, если кодовые слова приписывать не отдельным буквам, а сообщениям (блокам из L букв) источника. Так, для неравномерных блоковых кодов справедлива следующая теорема.
Теорема 2. Пусть - энтропия на букву в блоке длины L дискретного источник. Тогда существует префиксный код для кодирования блоков длины L, такой, что средняя длина кодового слова
будет удовлетворять неравенствам:
Кроме того, в случае бернуллиевского стационарного источника для любого можно выбрать достаточно большое L, чтобы величина
удовлетворяла неравенствам:
и левое неравенство для никогда не нарушается для разделимого кода.
Приведем некоторые свойства, которыми обладает любой оптимальный побуквенный код.
Лемма 1. Для оптимального кода с длинами кодовых слов верно соотношение
, если
.
Доказательство (от противного). Пусть есть индексы и
такие, что
при
. Тогда
т.е. если поменяем местами и
, то получим код, имеющий меньшую среднюю длину кодового слова, что противоречит с оптимальности кода. Лемма 1 доказана.
Лемма 2 Пусть – схема оптимального префиксного кодирования для распределения вероятностей P,
. Тогда среди элементарных кодов, имеющих максимальную длину, существуют два, которые различаются только в последнем разряде.
Доказательство. Покажем, что в оптимальной схеме кодирования всегда найдется два кодовых слова максимальной длины. Предположим обратное. Пусть кодовое слово максимальной длины одно и имеет вид . Тогда длина любого элементарного кода не больше длины b, т.е.
,
. Поскольку схема кодирования префиксная, то кодовые слова
не являются префиксом b. С другой стороны, b не является префиксом кодовых слов
. Таким образом, новая схема кодирования
также является префиксной, причем с меньшей средней длиной кодового слова
, что противоречит оптимальности исходной схемы кодирования. Пусть теперь два кодовых слова
и
максимальной длины отличаются не в последнем разряде, т.е.
. Причем
не являются префиксами для других кодовых слов
и наоборот. Тогда новая схема
также является префиксной, причем
, что противоречит оптимальности исходной схемы кодирования. Лемма 2 доказана.
Метод оптимального побуквенного кодирования был разработан в 1952 г. Д. Хаффманом. Оптимальный двоичный код Хаффмана обладает минимальной средней длиной кодового слова среди всех побуквенных кодов для данного источника с алфавитом и вероятностями
.
Алгоритм построения оптимального кода Хаффмана основывается на утверждениях лемм предыдущего параграфа и заключается в следующем:
1. Упорядочим символы исходного алфавита по убыванию их вероятностей
.
2. Если , то
.
3. Если и известны коды
,
, то для алфавита
с новыми символами
вместо
, и вероятностями
, код символа
заменяется на коды
и
.
Пример 4.4.1. Пусть источник имеет алфавит с вероятностями
Здесь символы источника уже упорядочены в соответствии с их вероятностями. Будем складывать две наименьшие вероятности и включать суммарную вероятность на соответствующее место в упорядоченном списке вероятностей до тех пор, пока в списке не останется два символа. Тогда закодируем эти два символа 0 и 1. Далее кодовые слова достраиваются, как показано на рисунке 4.
Рисунок 4 Процесс построения кода Хаффмана
Таблица 5 Код Хаффмана
Посчитаем среднюю длину, построенного кода Хаффмана
при этом энтропия данного источника
Рисунок 5 Кодовое дерево для кода Хаффмана
Код Хаффмана обычно строится и хранится в виде двоичного дерева, в листьях которого находятся символы алфавита, а на «ветвях» – 0 или 1. Тогда уникальным кодом символа a является последовательность 0 и 1, которая получается при прохождении пути от корня дерева к вершине с символом a (такой путь в дереве единственный) (рис. 5).
Алгоритм на псевдокоде
Построение оптимального кода Хаффмана (n,P)
Обозначим
n – количество символов исходного алфавита
P – массив вероятностей, упорядоченных по убыванию
C – матрица элементарных кодов
L – массив длин кодовых слов
Huffman (n,P)
Функция Up (n,q) находит в массиве P место, куда вставить число q, и вставляет его, сдвигая вниз остальные элементы.
Процедура Down (n,j) формирует кодовые слова.