Оптимальное кодирование. Задача построения оптимального кода заключается в отыскании целых положительных чисел n1, n2, , nN

Задача построения оптимального кода заключается в отыскании целых положительных чисел n ₁, n ₂, …, n_N, минимизирующих среднюю длину кодового слова при условии выполнения неравенства Крафта:

При построении кодов в случае алфавита A = { a_i, i = 1, 2, …, N } с известным распределением вероятностей P = { p_i, i = 1, 2, …, N } без ограничения общности можно считать, что буквы алфавита A занумерованы в порядке убывания их вероятностей, т.е. p ₁ ≥ p ₂ ≥ … ≥ p_N. Кроме того, будем рассматривать только двоичные коды.

Известны два метода (Фано и Шеннона) построения кодов, близких к оптимальным. Метод Фано заключается в следующем. Упорядоченный в порядке убывания вероятностей список букв делится на две последовательные части так, чтобы суммы вероятностей входящих в них букв как можно меньше отличались друг от друга. Буквам из первой части приписывается символ 0, а буквам из второй части – символ 1. Далее точно также поступают с каждой из полученных частей, если она содержит, по крайней мере, две буквы. Процесс продолжается до тех пор, пока весь список не разобьется на части, содержащие по одной букве. Каждой букве ставится в соответствие последовательность символов, приписанных в результате этого процесса данной букве. Легко видеть, что полученный код является префиксным.

Метод Шеннона применим лишь в том случае, когда все вероятности положительны. Он состоит в том, что букве a_i, имеющей вероятность p_i > 0, ставится в соответствие последовательность из n_i = ]log(1/ p_i)[ первых после дробной точки цифр разложения числа в бесконечную дробь (для a ₁ полагаем, что q ₁ = 0). Поскольку при l > k (в силу того, что p_l ≤ p_k) n_l ≥ n_k и , то полученный таким образом код является префиксным. На основе полученного префиксного кода строится усеченный префиксный код, который и является результатом кодирования по методу Шеннона.

Пусть, например, имеется множество букв A = { a ₁, a ₂, a ₃, a ₄, a ₅, a ₆, a ₇} с распределением вероятностей P = {0.2, 0.2, 0.19, 0.12, 0.11, 0.09, 0.09}. Выполним кодирование букв по методу Фано.

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

A ₁ = { a ₁, a ₂, a ₃}, P ₁ = {0.2, 0.2, 0.19};

A ₂ = { a ₄, a ₅, a ₆, a ₇}, P ₂ = {0.12, 0.11, 0.09, 0.09}.

2. Припишем буквам из первой части символ 0, а буквам второй части символ 1:

A ₁ = { a ₁/0, a ₂/0, a ₃/0};

A ₂ = { a ₄/1, a ₅/1, a ₆/1, a ₇/1}.

3. Повторим последовательно указанные действия для каждой из частей по отдельности. В результате получим:

A ₁₁ = { a ₁/00};

A ₁₂₁ = { a ₂/010};

A ₁₂₂ = { a ₃/011};

A ₂₁₁ = { a ₄/100};

A ₂₁₂ = { a ₅/101};

A ₂₂₁ = { a ₆/110};

A ₂₂₂ = { a ₇/111}.

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

Процесс кодирования по методу Фано удобно оформлять в виде таблицы. Для рассматриваемого примера он приведен в таблице 5.3.

Таблица 5.3

Кодирование по методу Фано

Определим среднюю длину кодового слова:

.

Теперь выполним кодирование по методу Шеннона. Процесс кодирование приведено в таблице 5.4.

Таблица 5.4

Кодирование по методу Шеннона

Как и предыдущего случая найдем среднюю длину кодового слова:

.

Как можно видеть результаты кодирования по методам Фано и Шеннона с точки зрения минимизации средней длины кода практически совпали. Поэтому часто эти методы рассматривают как один (в формулировке Фано) и называют методом Шеннона-Фано.

В 1952 г. Давид Хаффмен предложил метод оптимального префиксного кодирования для дискретных источников, который в отличие от методов Шеннона и Фано до сих пор применяется на практике. Д.Хаффмен доказал, что средняя длина кодового слова, полученная с помощью его метода, будет минимальна. Кодирование Хаффмена производится за три шага.

1. Упорядочение: буквы располагаются в порядке убывания их вероятностей.

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

3. Кодирование: начиная с последнего объединения, последовательно приписываются одной компоненте составной буквы символ 0, а второй – символ 1; процесс продолжается до тех пор, пока все исходные буквы не будут закодированы.

Выполним кодирование по методу Хаффмена для множества, рассматривавшегося в примерах применения методов Фано и Шеннона.

1. Исходный список букв A = { a ₁, a ₂, a ₃, a ₄, a ₅, a ₆, a ₇} уже упорядочен, так как P = {0.2, 0.2, 0.19, 0.12, 0.11, 0.09, 0.09}.

2. Объединим буквы a ₆ и a ₇ в одну букву a ¹ с вероятностью 0.18 и переупорядочим список:

P ¹ = {0.2, 0.2, 0.19, 0.18, 0.12, 0.11}, A ¹ = { a ₁, a ₂, a ₃, a ¹, a ₄, a ₅}.

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

P ² = {0.23, 0.2, 0.2, 0.19, 0.18}, A ² = { a ², a ₁, a ₂, a ₃, a ¹};

P ³ = {0.37, 0.23, 0.2, 0.2}, A ³ = { a ³, a ², a ₁, a ₂};

P ⁴ = {0.4, 0.37, 0.23}, A ⁴ = { a ⁴, a ³, a ²};

P ⁵ = {0.6, 0.4}, A ⁵ = { a ⁵, a ⁴};

P ⁶ = {1}, A ⁶ = { a ⁶}.

4. Присвоим двоичные коды символам:

a ⁶: a ⁵ = 0, a ⁴ = 1;

a ⁵: a ³ = 00, a ² = 01;

a ⁴: a ₁ = 10, a ₂ = 11;

a ³: a ₃ = 000, a ¹ = 001;

a ²: a ₄ = 010, a ₅ = 011;

a ¹: a ₆ = 0010, a ₇ = 0011.

Таким образом, исходным буквам присвоены следующие двоичные коды: a ₁ = 10, a ₂ = 11, a ₃ = 000, a ₄ = 010, a ₅ = 011, a ₆ = 0010, a ₇ = 0011, что дает среднюю длину кода , меньшую, чем в случае кодирования Фано и Шеннона.

Определим избыточность полученных кодов. Для этого найдем энтропию источника сообщений:

.

Тогда коды имеют следующую избыточность:

код Фано: ;

код Шеннона: ;

код Хаффмена: .

Таким образом, избыточность кода Хаффмена минимальна.

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

Поиск по сайту: