Мир Знаний

Основы экономного кодирования (стр. 2 из 2)

- избыточность источника

;

- среднее число символов в коде

;

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

.

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

Пусть теперь вероятности появления в тексте различных букв будут разными (табл. 2).

Таблица 2

А Б В Г Д Е Ж З
Ра=0.6 Рб=0.2 Рв=0.1 Рг=0.04 Рд=0.025 Ре=0.015 Рж=0.01 Рз=0.01

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

в этом случае, естественно, будет меньшей и составит
= 1.781.

Среднее число символов на одно сообщение при использовании того же равномерного трехразрядного кода

Избыточность кода в этом случае будет

,

или довольно значительной величиной (в среднем 4 символа из 10 не несут никакой информации).

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

Такое кодирование называется статистическим.

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

Один из способов такого кодирования предложен Хаффменом. Построение кодового дерева неравномерного кода Хаффмена для передачи одного из восьми сообщений li с различными вероятностями иллюстрируется табл. 3.

Таблица 3

Буква Вероятность Рi Кодовое дерево Код ni ni × Pi
А Б В Г Д Е Ж З 0.6 0.2 0.1 0.04 0.025 0.015 0.01 0.01
1 01 001 0001 00001 000001 0000001 00000001 1 2 3 4 5 6 7 8 0.6 0.4 0.3 0.16 0.125 0.08 0.07 0.08

Среднее число символов для такого кода составит

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

т.е. на порядок меньше, чем при равномерном кодировании.

Другим простейшим способом статистического кодирования является кодирование по методу Шеннона-Фано. Кодирование в соответствии с этим алгоритмом производится так:

- сначала все буквы из алфавита сообщения записывают в порядке убывания их вероятностей;

- затем всю совокупность букв разбивают на две примерно равные по сумме вероятностей группы; одной из них (в группе может быть любое число символов, в том числе – один) присваивают символ “1”, другой - “0”;

- каждую из этих групп снова разбивают (если это возможно) на две части и каждой из частей присваивают “1” и “0” и т.д.

Процедура кодирования по методу Шеннона-Фано иллюстрируется табл. 4.

Таблица 4

Буква Р(li ) I II III IV V Kод ni× Pi
А 0.6 1 1 0.6
Б 0.2 0 1 1 011 0.6
В 0.1 0 010 0.3
Г 0.04 0 1 001 0.12
Д 0.025 0 1 0001 0.1
Е 0.015 0 00001 0.075
Ж 0.01 1 000001 0.06
З 0.01 0 000000 0.06

Для полученного таким образом кода среднее число двоичных символов, приходящихся на одну букву, равно

,

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

то есть также существенно меньшую величину, нежели для равномерного кода.

Обратим внимание на тот факт, что как для кода Хаффмена, так и для кода Шеннона-Фано среднее количество двоичных символов, приходящееся на символ источника, приближается к энтропии источника, но не равно ей. Данный результат представляет собой следствие теоремы кодирования без шума для источника (первой теоремы Шеннона), которая утверждает:

Любой источник можно закодировать двоичной последовательностью при среднем количестве двоичных символов на символ источника li, сколь угодно близком к энтропии, и невозможно добиться средней длины кода, меньшей, чем энтропия H(λ).

Значение этой теоремы для современной радиотехники трудно переоценить – она устанавливает те границы в компактности представления информации, которых можно достичь при правильном ее кодировании.


ЛИТЕРАТУРА

1. Лидовский В.И. Теория информации. - М., «Высшая школа», 2002г. – 120с.

2. Метрология и радиоизмерения в телекоммуникационных системах. Учебник для вузов. / В.И. Нефедов, В.И. Халкин, Е.В. Федоров и др. – М.: высшая школа, 2001 г. – 383с.

3. Цапенко М.П. измерительные информационные системы.– М.: Энергоатом издат, 2005. - 440с.

4. Зюко А.Г., Кловский Д.Д., Назаров М.В., Финк Л.М. Теория передачи сигналов. М: Радио и связь, 2001 г. –368 с.

5. Б. Скляр. Цифровая связь. Теоретические основы и практическое применение. Изд. 2-е, испр.: Пер. с англ. – М.: Издательский дом «Вильямс», 2003 г. – 1104 с.