Построение оптимального неравномерного двоичного кода методом Шеннона-Фано

Реализуем алгоритм построения кода Шеннона-Фано по пунктам. Проиллюстрируем работу алгоритма построения кода Шеннона-Фано с помощью таблицы 2.

п.1. В столбце 1 (таблица 2) буквы первичного алфавита отсортированы в порядке убывания вероятностей их появления.

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

- первая группа – (a₁, a₅, a₆, a₁₁) с суммарной вероятностью

p(a₁)+p(a₅)+p(a₆)+p(a₁₁)=0,17+0,15+0,12+0,11=0,55;

- вторая группа – (a₁₀, a₄, a₇, a₁₂, a₃, a₂, a₈, a₉) с суммарной вероятностью

p(a₁₀)+p(a₄)+p(a₇)+p(a₁₂)+p(a₃)+p(a₂)+p(a₈)+p(a₉)=0,1+0,08+0,07+0,07+0,06+

+0,04+0,02+0,01=0,45.

Таблица 2 - Построение кода Шеннона Фано

Буква	р(аk)	Код 1		p()	– p(ak) log p(ak)
a1	0,17			0,51	0,4346
a5	0,15			0,45	0,4105
a6	0,12			0,36	0,3671
a11	0,11			0,33	0,3503
a10	0,1			0,3	0,3322
a4	0,08			0,32	0,2915
a7	0,07			0,28	0,2686
a12	0,07			0,28	0,2686
a3	0,06			0,24	0,2435
a2	0,04			0,16	0,1858
a8	0,02			0,1	0,1129
a9	0,01			0,05	0,0664
			=3,38	H(A)=3,3320

п.3. Первым символам кодовых слов букв a₁, a₅, a₆, a₁₁ присваиваем символ «0», а первым символам кодовых слов букв a₁₀, a₄, a₇, a₁₂, a₃, a₂, a₈, a₉ присваиваем символ «1» (столбец 3, таблица 2).

п.4. Повторяется п.2 для первой группы, которая разбивается на две подгруппы: (a₁, a₅) и (a₆, a₁₁). В соответствии с п. 3 второму символу букв a₁, a₅ присваивается символ «0». Вторым символам группы (a₆, a₁₁) присваивается символ «1».

Повторяется п.2 для группы (a₁, a₅), она разбивается на буквы a₁ и a₅.

В соответствии с п. 3 третьему символу буквы a₁ присваивается символ «0», а третьему символу буквы a₅ - символ «1», и на этом процесс кодирования букв a₁ и a₅ заканчивается:

Cod a₁ =000,

Cod a₅ =001.

Повторяется п.2 для группы (a₆, a₁₁), она разбивается на буквы a₆ и a₁₁.

В соответствии с п. 3 третьему символу буквы a₆ присваивается символ «0», а третьему символу буквы a₁₁ - символ «1», и на этом процесс кодирования букв a₆ и a₁₁ заканчивается:

Cod a₆ =010,

Cod a₁₁ =011.

Аналогично проводится кодирование остальных символов букв a₁₀, a₄, a₇, a₁₂, a₃, a₂, a₈, a₉, результаты которого представлены в столбце 3, таблица 2.

Оценим эффективность построенного кода.

Среднюю длину кодового слова вычислим по формуле (16), для чего для каждой буквы первичного алфавита воспользуемся данными из столбцов 4 и 2 таблицы 2, поместим полученные произведения в соответствующие ячейки столбца 5 и просуммируем их:

, (16)

где K – число букв первичного алфавита;

n_k – длина k-го кодового слова;

p(a_k) – вероятность появления k-го кодового слова.

=3,38.

Вычислим энтропию первичного алфавита по известной формуле (6). В столбце 6 таблицы 2 произведены соответствующие вычисления:

H(A)=3,3320 бит/символ.

Вычислим коэффициент относительной эффективности по формуле (17)

(17)

и коэффициент статистического сжатия – по формуле (18)

(18)

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

Дата добавления: 2015-11-30