Вернер М. Основы кодирования

Подождите немного. Документ загружается.

3.2.

Коды

Хаффмана

Из

примера отчетливо видно, что чем больше разница

между

вероятностями символов, тем больше выигрыш кода Хаффмана по

сравнению с простым блоковым кодированием.

Теорема Шеннона о кодировании источников показывает, насколь-

ко

эффективным может быть такое кодирование. Но теория

инфор-

мации

также указывает на то обстоятельство, что при кодировании

могут

появляться кодовые слова очень большой длины. Это обстоя-

тельство может препятствовать практическому использованию тео-

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

Реализация

декодера кода Хаффмана

следует

непосредственно

из

рис. 3.3. На рис. 3.4 представлено дерево, называемое кодовым

деревом декодера.

Декодирование каждого нового слова начинается с исходного уз-

ла (корня) кодового дерева. Если мы принимаем «О», то идем по

ребру,

соответствующему нулю (по верхнему ребру). В нашем при-

мере при этом мы достигаем оконечного

узла

d. Следовательно, был

нередан символ d и мы начинаем декодирование нового символа с,

корня.

Оконечный

узел

Узел

Рис.

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

Если мы принимаем «1», то идем по нижнему

ребру

и попадаем

узел,

из которого

выходят

два ребра. Следующий принятый бит

указывает, какое из этих

двух

ребер нужно выбрать. Мы продолжаем

эту процедуру до тех пор, пока не достигнем оконечного

узла.

этом

случае

мы принимаем решение о переданном символе и опять

переходим к корню кодового дерева.

При

всей простоте построения и декодирования, коды Хаффмана

обладают

тремя недостатками:

• Различные длины кодовых слов приводят к неравномерным за-

Глава

Кодирование

для

дискретных

источников

без

памяти

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

• Сжатие данных снижает избыточность и поэтому повышает

предрасположенность к распространению ошибок. В

случае

ко-

дирования Хаффмана это означает, что один, ошибочно рас-

познанный

бит, может привести к

тому,

что все последующие

символы

будут

декодированы неверно.

• Кодирование Хаффмана предполагает знание вероятностей со-

бытий (знаков), или, по крайней мере, подходящих оценок этих

вероятностей. На практике очень часто вероятности событий

неизвестны, а их оценки весьма затруднены.

Именно

поэтому для сжатия больших массивов данных часто ис-

пользуют

универсальный

алгоритм

кодирования,

известный как алт

горитм Лемпеля-Зива. Описание этого алгоритма приведено в раз-

деле

6.3. Универсальный' алгоритм сжатия не

требует

априорного

знания

статистики источника.

ГЛАВА 4

ЭНТРОПИЯ

СВЯЗАННЫХ

источников

До сих пор в своих рассуждениях мы исходили из предположе-

ния

независимости последовательных событий. Однако, стоит лишь

только открыть немецкий орфографический словарь, мы сразу же

обнаружим зависимость

между

рядом стоящими буквами, напримерг

«qu»,

«ch»,

«ck»,

«tz»

«sch».

Читая немецкий текст, мы видим, что

после «q» за редким исключением

следует

«и». В этом

случае

«и»,

как

почти неизбежное событие, практически не несет в себе никакой

информации.

Поэтому, при определении информации подобного ро-

да источников, мы должны принимать во внимание взаимную связь

между

событиями.

4.1.

Взаимная

и условная информация

При

аксиоматическом построении теории информации использова-

лось такое понятие, как информация пары событий. Напомним и

обобщим эти рассуждения. Рассмотрим два дискретных источника

X и У. Объединим их события в пары событий

(х{,Уг).

Мы получим

простейшую модель связанных источников (рис.4.1).

Символы

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

Рис.

4.1.

Модель

двух

связанных

источников.

Глава

Энтропия

связанных

источников

Если

оба

источника каким-то образом связаны

между

собой,

то

следует

ожидать,

что

событие одного источника позволяет делать

некоторое предположение

событии другого.

терминах теории

информации

это

означает,

что

неопределенность второго источника

снижается,

т.е.

источники обмениваются взаимной информацией.

Введем условную вероятность р(х/у)

вероятность события

при

условии,

что

произошло событие

у.

Выразим совместную веро-

ятность

p(xi,

г/г)

двух

событий Х{

и j/j

через

их

априорные

условные

вероятности

p{xi,yi)=p(xi/yi)p(yi)=p(yi/xi)p{Xi).

(4.1)

Используя логарифмическую функцию, сразу

же

получаем инфор-

мации

Событий

{Xi,yi),

(Xi)

(у)

-Цим)

бит i(

) бит

то есть

I{xi,Vi)

I(Vi)

ld(ii/3/j) бит

= 1(ц) -

\og

p{yi/xi) бит.

(4.3)

Прибавляя

одновременно вычитая

I(xi) в

первой части

(4.3) и,

соответственно,

I{yi) во

второй, получаем

'l(

, у

) = (

) + 1(у

) -

log

бит

Таким

образом, информация пары событий (xi,yi) определяется

суммой информации этих событий

за

вычетом некоторой неотрица-

тельной величины, которая снижает неопределенность,

т.е.

сама

свою очередь является информацией. Поэтому, назовем

ее

взаимной

информацией

нары событий.

Взаимная

информация

нары событий определяется

как

апостериорная вероятность

log

( I.

априорная вероятность

4-1-

Взаимная

условном информация

-Обратите внимание

на

то,

что

взаимная информация /(ж,;

у,) все-

гда положительна. Важным свойством также является симметрия

взаимной информации относительно источников,

т.к.

Р(Уг)

Симметрия относительно источников

в (4.5)

позволяет сделать

вывод,

что

обмен информацией между источниками является

вза-

имным,

а не

односторонним.

Для того, чтобы лучше представлять себе смысл взаимной

ин-

формации,

рассмотрим

два

граничных случая.

1. Источники независимы. Тогда

для

пары независимых событий

имеем

p(*i,Vi)

P{xi)p(yi),

' (4.7)

то есть источники

не

обмениваются информацией

1{Хг;

г)=0.

(4.8)

2. Источники жестко связаны,

то

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

однозначно определяет событие

другого

)

= 1. • (4.9)

В этом случае происходит полный обмен информацией

ЦХГМ)

= 1(ъ) = /(w).

(4.10)

Из

(4.4)

следует,

что

информацию пары событий

{xi,yi)

можно

ин-

терпретировать,

как

разность между информацией пары независи-

мых событий

l{xi) + I(yi) и

заранее предсказанной взаимной инфор-

мацией I(xi;yi), обусловленной связанностью источников

X и Y

Цхит)

= I(

) +

1{УГ)

1{ХГ,1Н).

(4.11)

Рассмотрим

еще раз (4.3) и

введем понятие условной информации.

Условная

информация

(апостериорная неопределенность)

Iixilm)

-logapfo/и)

бит.

(4.12)

Из

(4.3)

следует

/(*<;»)

= 1{

г) +

I(Xi/

)

= Цц) +

НУг/Xi),

(4.13)

,38

Глава

Энтропия

связанных

источников

то есть информацию пары событий можно определить

как

сумму

информации события

у\

информации события

ж,

при условии,

что

событие

уже

известно, или, наоборот,

как

сумму

информации

со-

бытия

информации события ;(/, при условии,

что

событие

уже

известно.

4.2.

Совместная

условная энтропия

После рассмотрения отдельных нар событий

предыдущем разделе,

перейдем

средним оценкам источника.

На

рис.

4.2

показана исходная ситуация.

Алфавит

Х={х,,...,х

1^(Ж I

Вероятность

р(х,) Ш^^^ШШ"^ЖЖ I

^Символы

Условная

вероятность

р(у

}

Xj)

Д^Д

ИСТОЧНИК

„,_^_^_

- I

Вероятность

пары

Алфавит

К=(^

Уд

,) ЯНи^иЛ

символов

р^,,

у>

)

Вероятность

р(у*)

Связанные

источники

Рис.

4.2. Два

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

Совместная энтропия

двух

источников определяется

как

матема-

тическое ожидание информации

всех

пар

событий.

Совместная

энтропия

двух

дискретных источников

без

памяти

^т

(4.14)

Замечание.

Здесь

подразумевается,

что

рассматриваются

все

па-

ры

совместных

событий,

то

есть

Y t=i j=i

Усредняя условные информации

всех

нар

событий, получим услов-

ную энтропию.

4-2. Совместная

условная энтропия

Таблица

4.1.

Оценка совместной вероятности

пар

символов

p(xi,yj)

вероятность отдельных символов

хз

v(Vj)

2/1

0,10

0,05

0,15

0,05

0,15

0,10

0,05

0,35

№

0,05

0,15

0,10

0,05

0,35

0,10

0,05

0,15

0,20

0,35

0,30

0,15

Условная

энтропия

двух

дискретных источников без памяти

X и У

(4.15)

ЩХ/Y)

бит

p{Xty)log2p{x/y)

Заменяя

(4.14)

\og

p{x,y)

ua.\og

(p(x/y)p(y))

на Iog

(p(y/x)p{y)),

получим

Н(Х,

Y) =

H{Y)

H{X/Y)

= Н{Х) +

H(Y/X).

(4.16)

Таким

образом, совместная энтропия может быть представлена

виде суммы энтропии одного источника

некоторой части эн-

тропии

другого

источника. Для независимых источников энтропия

второго источника входит

сумму целиком, т.к. H(X/Y) —

Н(Х)

H(Y/X)

= H(Y).

Для связанных источников всегда H(X/Y)

Н(Х)

H{Y/X)

< H(Y).

Поэтому,

общем случае, всегда имеет

место

H{X,Y)<H{Y)

H(X).

(4.17)

Пример:

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

Сейчас самое время подробно разобрать числовой пример,

на-

глядно поясняющий приведенные выше определения

формулы. Для

этой

цели была подобрана задача, методика решения которой может

непосредственно использоваться на практике.

Пусть мы имеем выборку

100000

пар совместных событий (xi,yi)

дискретных источников

X и У и

алфавит каждого источника

со-

держит четыре события. Пусть пара (xi,yi) встретилась

10000

раз.

Г40

Глава

Энтропия

связанных

источников

Тогда оценка вероятности пары

(xi,2/i)

равна

10000/10000

= 0,1.

Оценки

остальных пар событий также получены подсчетами их от-

носительной частоты и сведены в таблицу 4.1. Будем считаем, что

полученные оценки близки к вероятностям пар событий и в даль-

нейшем будем говорить уже о вероятностях. Вероятности событий

Xi, yi получены суммированием строк и столбцов. Контрольная сум-

ма Y2i=i

X/i=i 2/г

1 приведена в правом нижнем

углу.

Теперь, когда нам известны все вероятности, необходимые для

подсчета энтропии, определим:

1. Энтропии источников X и У;

2. Совместную энтропию источников;

3. Обе условные энтропии;

Для контроля мы также вычислим:

4. Условные вероятности P(y

/xi);

5. Определим условную энтропию H(Y/X).

Замечание. Для

простоты

проведем

расчеты

точностью

до 4

знаков

после

запятой.

Решение.

н(х) _ А _

бит ^—*

i=i

-2[0,15

•

log

(0,15)

+ 0,35 • lo

(0,35)] =

1,9261,

(4.18)

_ >(

№

) =

1,8813;

j=i

4 4

?~р-

Е Е

-p(

УЗ)

4464

;

(

)

i=i j=\

3. Без длинных вычислений из (4.16) получаем

H(X/Y) = H(X,Y) - H(Y) =

3,4464

1,8813

1,5651

бит,

H(Y/X) = H{X,Y) - H{X) =

3,4464

1,19261

1,5203

бит;

4-3.

Выводы

Таблица

4.2.

Условная

вероятность

p(y,/Xj).

хз

У1

1/2

1/7

г/2

1/4

3/7

1/3

Уз

1/4

3/7

1/3

2/4

1/3

4. В таблице 4.2 приведены условные вероятности, подсчитанные ис-

ходя

из таблицы 4.1. Заметим, что при этом мы получили так назы-

ваемую

стохастическую матрицу. Сумма условных вероятностей для

каждой строки равна 1.

1,5496.

(4.20)

г=1

j=l

4.3.

Выводы

Все приведенные в предыдущих

разделах

рассуждения в математи-

ческой форме сведены в табл. 4.3. Напомним, что основной идеей

теории информации является представление информации источни-

ка

как меры неопределенности. Эта неопределенность раскрывается

посредством экспериментов со случайными событиями из алфавита

этого источника. Такой

подход

поясняют три столбца таблицы.

Так

как информация исходит из случайности событий, в первом

столбце вводится понятие вероятности событий и совместной веро-

ятности пары событий как основополагающих величин. Для пары

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

столбце дается определение информации события и нары событий,

а также условной и взаимной информации. И, наконец, в третьем

столбце, вводится понятие энтропии как меры неопределенности ис-

точника.

Энтропия

источника, совместная и условная энтропии

двух

ис-

точников трактуются как математические ожидания соответствую-

щих информации событий. Условная вероятность - это вероятность

одного события при условии, что

другое

событие уже произошло, по-

(42

Глава 4- Энтропия связанных источников

Таблица

4.3.

Дискретные источники

без

памяти

X и У с

сим-

волами

х S X =

{xi,xa,

• • •

,1м} и ;(/ 6 У —

{г/1.

№,•••,

1/JV}-

Информации

Энтропия

Вероятность

отдельного

сим-

вола

(априорная

вероятность)

р(х)

Информация

отдельного

символа

I(x)

-log

p(x)

бит

Энтропия

Совместная

ве-

роятность

двух

символов

Р(х, У)

Информация

пары

сим-

волов

1(х,у)

= -

log

р(х,

у) бит

H(X,Y)

Условная веро-

ятность

(апо-

стериорная

вероятность)

Условная информация

Цх/у)

= -

\<щ

р{х/у)

бит

Цу/х)

= - log

p(y/x) бит

H(X/Y)

р(х/у)

Р(у/х)

Р(.х,у)

р(у)

Р(х,у)

р{х)

H(Y/X)

log

бит

Взаимная информация

ч _,

апостериорная вероятность

'У/ - &2

априорная информация

иJ