Васюков В.Н. - Введение в ТЭС (1275345), страница 4

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 4)

Итак, при оптимальном кодировании источника кодовые символы равновероятны; такое кодирование является безызбыточным. Источник вместе с кодером можно рассматривать, как новый источник с алфавитом, состоящим из кодовых символов; энтропия и избыточность этого источника – это энтропия и избыточность кода. Оптимальный код имеет максимальную энтропию и нулевую избыточность.

Кодирование источника по методу Хаффмена.

Другим широко известным методом кодирования источника является метод Хаффмена⁴. Процедура кодирования состоит из следующих шагов.

1. Все символы алфавита записываются в порядке убывания вероятностей.

2. Два нижних символа соединяются скобкой, из них верхнему приписывается символ 0, нижнему 1 (или наоборот).

3. Вычисляется сумма вероятностей, соответствующих этим символам алфавита.

4. Все символы алфавита снова записываются в порядке убывания вероятностей, при этом только что рассмотренные символы «склеиваются», т.е. учитываются, как единый символ с суммарной вероятностью.

5. Повторяются шаги 2, 3 и 4 до тех пор, пока не останется ни одного символа алфавита, не охваченного скобкой.

Скобки в совокупности образуют дерево. Код Хаффмена для некоторого символа алфавита находится путем последовательной записи нулей и единиц, встречающихся на пути от корня дерева (корню соответствует суммарная вероятность 1) до листа, соответствующего данному символу. Полученное дерево, очевидно, является деревом декодирования.

Для примера, приведённого в таблице 2, получаются следующие кодовые комбинации: 01; 11; 001: 000; 101; 1000; 10011; 10010.

Энтропия алфавита . Средняя длина кодового слова 0,32+0,22+0,153+0,153+0,13+0,044+0,035+0,035=2,66. Следовательно, код не оптимален, но очевидно, что он довольно близок к оптимальному. Для сравнения: равномерный код для этого случая имеет среднюю длину кодового слова 3 (совпадающую для равномерного кода с длиной каждого кодового слова).

Вероятность символа 1 в последовательности кодовых комбинаций находится как среднее количество единиц, отнесённое к средней длине кодового слова

.

Неоптимальность кода проявляется в неравенстве вероятностей кодовых символов (0,466 для «1» и 0,534 для «0»).

Таблица 2

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

: 0,3		: 0,3		: 0,3		: 0,3		0,4
: 0,2		: 0,2		: 0,2		0,3		: 0,3
: 0,15		: 0,15		0,2		: 0,2		0,3
: 0,15		: 0,15		: 0,15		0,2
: 0,1		: 0,1		: 0,15
: 0,04		0,06
: 0,03		: 0,04
: 0,03

Замечания

1. Из рассмотренных примеров не должно составиться ложное впечатление, будто код Шеннона – Фано оптимален, а код Хаффмена – нет. Оптимальность кода Шеннона – Фано в рассмотренном примере объясняется специально подобранными вероятностями символов.

2. В рассмотренных примерах предполагалось, что символы в сообщении являются независимыми (то есть вероятность появления в сообщении любых двух символов рядом равна произведению вероятностей каждого из символов). В реальных сообщениях на естественных языках символы не являются независимыми; в таких случаях следует кодировать не отдельные символы (буквы), а группы букв или слова. Это уменьшает зависимость и повышает эффективность кода.

3. Кодирование групп символов вместо отдельных символов также повышает эффективность кодирования в случае независимого источника с сильно различающимися вероятностями символов, как это видно из следующего примера.

Пример 5. Рассмотрим источник, вырабатывающий два независимых символа с вероятностями 0,1 и 0,9. В этом тривиальном случае методы кодирования Хаффмена и Шеннона – Фано приводят к одинаковому коду: символы алфавита кодируются символами «0» и «1». Пусть для определенности 0; 1. Энтропия источника равна =0,469; средняя длина кодового слова равна 1, избыточность источника и избыточность кода одинаковы и равны

.

Применим кодирование группами по 2 символа алфавита. Составим всевозможные пары и запишем их с соответствующими вероятностями (найденными как произведения вероятностей отдельных символов, так как они независимы)

Таблица 3

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

:0,81	____	:0,81
:0,09		___0,1___
:0,09		:0,09
:0,01

Согласно построенному дереву код Хаффмена для указанных групп содержит следующие кодовые комбинации

1; 00; 011; 010.

Средняя длина кодовой комбинации, приведённая к одному символу алфавита (для этого взвешенная сумма делится на 2), равна

.

Вероятность символа 1 в последовательности кодовых комбинаций находится как среднее количество единиц, отнесённое к средней длине кодового слова

.

Энтропия кода находится как энтропия случайной величины, принимающей два значения (0 и 1) с вероятностями 0,225 и 0,775:

.

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

.

Сравнение с кодированием одиночных символов показывает, что кодирование групп является более эффективным: уменьшаются избыточность кода и средняя длина кодового слова, вероятности символов 0 и 1 сближаются.

Ещё более эффективные коды для данного источника можно получить, объединяя символы алфавита в группы по три, четыре и т. д. В пределе, согласно теореме Шеннона, средняя длина кодовой комбинации, приведённая к одному символу алфавита, должна стремиться к значению 0,469, избыточность кода – к нулю, а вероятности кодовых символов 0 и 1 – к значению 0,5.

1. Помехоустойчивое кодирование

Кодирование источника, называемое также статистическим или экономным кодированием⁵, преследует цель повышения эффективности передачи информации, под которым понимается максимально быстрая передача. Экономное кодирование можно рассматривать как замену исходного источника другим источником с меньшей (в пределе нулевой) избыточностью. Если в канале действуют помехи, то при приёме сигналов возникают ошибки, приводящие к неправильному декодированию сообщений. В таких случаях выдвигается на передний план задача повышения верности передачи. Одним из путей ее решения является помехоустойчивое (канальное) кодирование. Помехоустойчивыми или корректирующими кодами называются коды, обеспечивающие автоматическое обнаружение и/или исправление ошибок в кодовых комбинациях. Такая возможность обеспечивается целенаправленным введением избыточности в передаваемые сообщения. Наиболее простой способ повышения помехоустойчивости путем введения избыточности состоит в многократной передаче каждого символа, например, вместо слова связь можно передавать слово сссвввяяязззььь, тогда одиночные ошибки могут быть исправлены путем «голосования» среди символов каждой тройки. На практике применяются более сложные и более эффективные методы кодирования.

Теоретическим обоснованием применения канального кодирования служит следующая основная теорема кодирования Шеннона для каналов с помехами (шумами) [1]:

ТЕОРЕМА. Если производительность источника меньше пропускной способности канала , то существует по крайней мере одна процедура кодирования/декодирования, при которой вероятность ошибочного декодирования и ненадежность могут быть сколь угодно малы. Если , то такой процедуры не существует.

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

Характеристики

Список файлов книги