<< Предыдущая

стр. 5
(из 50 стр.)

ОГЛАВЛЕНИЕ

Следующая >>

•••
••
•• 0,0257 0 0,0229
В
••
••
••
•• Р
0,0284 0,0094
С
••••
••
• 0,0541 0,0007
D Q'
• ••

R 0,0654
Е 0,1669
••
•• ••

0,0204
F S 0,0678

••
• т
0,0365 0,0674
G
••
•• и ••

0,0406 0,0370
Н
••
••
•• 0,0782 V
I 0,0107
••

•••• W
J 0,0019 0,0140
••
••
••
• X
К 0,0188 0,0002
••••
Y
•Ш»
L 0,0283 0,0003
•• ' ••
••
Z
М 0,0301 0,0100



Замечание. Коды Хаффмана играют важнейшую роль в кодиро-
вании изображений. Они являются основной частью стандартов
JPEG, MPEG и H.261 J19]. Кроме этого, они так же используются
при оцифровке аудио сигналов. В литературе, в качестве примеров
энтропийного кодирования, упоминаются коды Шеннона и Фано, но
они не во всех случаях являются оптимальными и мы пропустим
их описание.

Кодирование Хаффмана производится за три шага. Мы наглядно
поясним этот процесс на маленьком примере.
Кодирование Хаффмана.

1. Упорядочение. Расположить знаки в порядке убывания их
вероятностей.

2. Редукция. Объединить два знака с наименьшими вероятно-
3.2. Коды Хаффмана
Таблица 3.2. Вероятности и энтропия двух символов.

Ь f
d
а с е

02
,
0,05 0,15 0,05 04
, 0,15
Pi

I(pi)
4,32 бит 2,74 бит 4,32 бит 1,32 бит 2,32 бит 2,74 бит
бит
Н(Х)
« 2,25
бит




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

3. Кодирование. Начать с последнего объединения. Приписать пер-
вой компоненте составного знака символ «0», а второй - сим-
вол «1». Продолжать этот процесс до тех пор, пока все простые
знаки не будут закодированы.

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




Рис. 3.3. Кодирование Хаффмана п = 4.

Пример:
Кодирование Хаффмана наглядно показано на примере источни-
ка, заданного табл. 3.2. При этом мы немного упростим кодирование,
Глава 3. Кодирование для дискретных источников без памяти

Таблица 3.3. Кодирование кодом Хаффмана к рис. 3.3.

f b
d е а с
Xi


0,4 0,2 0,15 0,15 0,05 0,05
р.
ПО
Кодовое слово 100 101 1110 1111
0
4 4
1 3 3
Длина кодового слова 3




отказавшись от наглядных переупорядочений знаков на втором ша-
ге, т.к. в таком маленьком примере это можно сделать сделать «в
уме». В соответствии с первым шагом, расположим все знаки в по-
рядке убывания их вероятностей (рис.3.3).
На втором шаге объединим символы «а» и «с», обладающие наи-
меньшими вероятностями, в составной символ «ас». Далее объеди-
ним «е» с «ас» в составной символ «еас» с вероятностью 0.25. Теперь
наименьшими вероятностями уже обладают символы «f» и «Ь». Объ-
единив их, получим символ «fb». Следующая редукция дает состав-
ной символ «fbeac» с вероятностью 0,6. И, наконец, объединив все
символы, получим составной символ «dfbeac», вероятность которого
равна 1.
На третьем шаге будем идти справа налево, приписывая верхним
компонентам объединений символ «0», а нижним «1». Полученные
кодовые слова всех простых знаков с их длинами приведены в табл. 3.3.
Данный код обладает минимальной средней длиной кодового слова.
Средняя длина кодового слова определяется длинами всех слов щ,
«взвешенными» с соответствующими вероятностями р;

N
(3.21)
П =




В рассмотренном выше примере средняя длина кодового слова
п = 2,3 бит близка к энтропии Н(Х) = 2,25 бит. Важнейшей ве-
личиной, называемой эффективностью кода или фактором сжатия,
является отношение средней длины к энтропии. В нашем примере
эффективность кода равна г\ = 0,976.

Эффективность кода или фактор сжатия


(3.22)
3.2. Коды Хаффмана

Из примера отчетливо видно, что чем больше разница между
вероятностями символов, тем больше выигрыш кода Хаффмана по
сравнению с простым блоковым кодированием.
Теорема Шеннона о кодировании источников показывает, насколь-
ко эффективным может быть такое кодирование. Но теория инфор-
мации также указывает на то обстоятельство, что при кодировании
могут появляться кодовые слова очень большой длины. Это обстоя-
тельство может препятствовать практическому использованию тео-
ремы кодирования источников.
Реализация декодера кода Хаффмана следует непосредственно
из рис. 3.3. На рис. 3.4 представлено дерево, называемое кодовым
деревом декодера.
Декодирование каждого нового слова начинается с исходного уз-
ла (корня) кодового дерева. Если мы принимаем «О», то идем по
ребру, соответствующему нулю (по верхнему ребру). В нашем при-
мере при этом мы достигаем оконечного узла d. Следовательно, был
нередан символ d и мы начинаем декодирование нового символа с,
корня.
Оконечный узел




Узел




Рис. 3.4. Кодовая конструкция для D = 2 и п = 4.

Если мы принимаем «1», то идем по нижнему ребру и попадаем
в узел, из которого выходят два ребра. Следующий принятый бит
указывает, какое из этих двух ребер нужно выбрать. Мы продолжаем
эту процедуру до тех пор, пока не достигнем оконечного узла. В
этом случае мы принимаем решение о переданном символе и опять
переходим к корню кодового дерева.
При всей простоте построения и декодирования, коды Хаффмана
обладают тремя недостатками:
• Различные длины кодовых слов приводят к неравномерным за-
Глава 3. Кодирование для дискретных источников без памяти

держкам декодирования.

• Сжатие данных снижает избыточность и поэтому повышает
предрасположенность к распространению ошибок. В случае ко-
дирования Хаффмана это означает, что один, ошибочно рас-
познанный бит, может привести к тому, что все последующие
символы будут декодированы неверно.

• Кодирование Хаффмана предполагает знание вероятностей со-
бытий (знаков), или, по крайней мере, подходящих оценок этих
вероятностей. На практике очень часто вероятности событий
неизвестны, а их оценки весьма затруднены.

Именно поэтому для сжатия больших массивов данных часто ис-
пользуют универсальный алгоритм кодирования, известный как алт
горитм Лемпеля-Зива. Описание этого алгоритма приведено в раз-
деле 6.3. Универсальный' алгоритм сжатия не требует априорного
знания статистики источника.
ГЛАВА 4
ЭНТРОПИЯ
СВЯЗАННЫХ
источников
До сих пор в своих рассуждениях мы исходили из предположе-
ния независимости последовательных событий. Однако, стоит лишь
только открыть немецкий орфографический словарь, мы сразу же
обнаружим зависимость между рядом стоящими буквами, напримерг
«qu», «ch», «ck», «tz» и «sch». Читая немецкий текст, мы видим, что
после «q» за редким исключением следует «и». В этом случае «и»,
как почти неизбежное событие, практически не несет в себе никакой
информации. Поэтому, при определении информации подобного ро-
да источников, мы должны принимать во внимание взаимную связь
между событиями.


4.1. Взаимная и условная информация
При аксиоматическом построении теории информации использова-
лось такое понятие, как информация пары событий. Напомним и
обобщим эти рассуждения. Рассмотрим два дискретных источника
X и У. Объединим их события в пары событий (х{,Уг). Мы получим
простейшую модель связанных источников (рис.4.1).




Символы




Связанные источники


<< Предыдущая

стр. 5
(из 50 стр.)

ОГЛАВЛЕНИЕ

Следующая >>