Материал: Лекция 5

Построить код Хаффмена для кодирования заданного алфавита

Энтропия данного источника

_{Средняя длина кодовых слов}

.

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

.

Избыточность кода Хаффмена

Из теоремы 4.1 следует, что для построенных по алгоритму Хаффмана кодов средняя длина кодовых слов удовлетворяет неравенству

, (4.6)

где — энтропия ансамбля.

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

Итак, из (4.6) следует, что для кода Хаффмана избыточность г < 1. Хоте­лось бы получить более точную оценку средней длины кодовых слов. Гораздо бо­лее точную оценку избыточности получил Р. Галлагер, наложив ограничение на максимальную из вероятностей сообщений.

Теорема 4.3. Пусть — наибольшая из вероятностей сообщений конечно­го дискретного ансамбля. Тогда избыточность кода Хаффмана для этого ансамбля удовлетворяет неравенствам:

где — энтропия двоичного ансамбля; .

Код Шеннона-Фано

Алгоритм Шеннона-Фано заключается в следующем.

1. Символы алфавита источника (первичного или укрупненного) записываются в порядке не возрас­тающих вероятностей.

2. Затем они разделяются на две части так, чтобы суммы вероятностей символов, входящих в каждую из таких частей, были примерно одинаковыми. Всем символам первой части приписывается в качестве первого символа комбинации неравномерного кода ноль, а символам второй части — единица.

3. Затем каждая из этих частей (если она содержит более одного сооб­щения) делится в свою очередь на две, по возможности равновероятные части и к ним применяется то же самое правило кодирования.

4. Этот процесс повторя­ется до тех пор, пока в каждой из полученных частей не останется по одному сообщению.

Таблица 4.4

Пример. Пусть алфавит А источника состоит из 8 символов А, Б, В, Г, Д, Е, Ж, З с ве­роятностями р(А) = 0,6; р(Б) = 0,2; р(В) = 0,1; р(Г) = 0,04; р(Д)=0,025; р(Е) = 0,015, р(Ж)=0,01; р(З) = 0,01. Про­цедура построения неравномерного кода Шеннона-Фано задаётся в таблице 4.4.

На первом этапе производится деление на два множества А, и Б, В, Г, Д, Е, Ж, З, так как вероятность р(А)=0,6 и сумма вероятностей

примерно одинаковы. При этом символу А присваивается «1», а всем остальным Б, В, Г, Д, Е, Ж, З присваивается «0».

На втором этапе производится деление второго множества на два множества Б, В, и Г, Д, Е, Ж, З. Множеству Б, В присваивается «1», а множеству Г, Д, Е, Ж, З присваивается «0».

Hа третьем этапе производится деление множества Б, В, на два множества (уже символа) Б и В. Символу Б присваивается «1», а символу В присваивается «0». Множество Г, Д, Е, Ж, З делится на множества Г и Д, Е, Ж, З. Символу Г присваивается «1», а множеству Д, Е, Ж, З присваивается «0».

На четвёртом этапе производится деление множества Д, Е, Ж, З на два множества Д и Е, Ж, З. Символу Д присваивается «1», а множеству Е, Ж, З присваивается «0».

На пятом этапе производится деление множества Е, Ж, З на два множества Е и Ж, З. Символу Е присваивается «1», а множеству Ж, З присваивается «0».

На шестом этапе производится деление множества Ж, З на два множества Ж и З. Символу Ж присваивается «1», а символу З присваивается «0».

Легко проверить, что данный код оказывается префиксным и средняя длина кодовой комбинации 1,915, что менее чем на 7 % превышает энтропию данного источника, равную 1,7813. A избыточность кода составит

.

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

Пример. Источник дискретных сообщений для формирования сообщений использует алфавит из 7 знаков.

Построить код Шеннона-Фано для кодирования заданного алфавита

а₆ - 0

а₂ – 100

а₄ - 101

а₇ - 110

а₅ - 1110

а₁ - 11110

а₃ - 11111

4.3. Неравномерное кодирование для последовательности сообщений

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

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

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

бит/сообщение источника.

Подбирая длину блоков, при которой средняя длина кода будет наименьшей, получаем следующее определение для средней длины, кода на сообщение:

.

(Здесь пишем нижнюю грань вместо минимума, поскольку наименьшее значе­ние скорости может достигаться при .

Рассматриваемое кодирование называется -кодированием (fixed to variable), поскольку блоки из фиксированного числа сообщений и кодируются ко­довыми словами переменной длины. Наша задача — связать достижимые значе­ния средней скорости -кодирования с характеристиками источника, в частно­сти, с его энтропией . Начнем с обратной теоремы кодирования.

Теорема 4.3. Для дискретного стационарного источника с энтропией для любого -кодирования имеет место неравенство

.

Теорема 4.4 (прямая теорема кодирования). Для дискретного стационар­ного источника с энтропией и для любого существует такой способ не­равномерного -кодирования, для которого