Основы экономного кодирования (стр. 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 с.