БЕЛОРУССКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ ИНФОРМАТИКИ И РАДИОЭЛЕКТРОНИКИ

Кафедра РЭС

Реферат на тему:

«Энтропия сложных сообщений, избыточность источника. Цель сжатия данных и типы систем сжатия»

МИНСК, 2009

Энтропия сложных сообщений, избыточность источника

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

Однако в реальных условиях независимость элементарных сообщений, вырабатываемых источником, - явление довольно редкое. Чаще бывает как раз обратное - сильная детерминированная или статистическая связь между элементами сообщения одного или нескольких источников.

Например, при передаче текста вероятности появления отдельных букв зависят от того, какие буквы им предшествовали. Для русского текста, например, если передана буква "П", вероятность того, что следующей будет "А", гораздо выше, чем "Н", после буквы "Ъ" никогда не встречается "H" и т.д. Подобная же картина наблюдается при передаче изображений - соседние элементы изображения имеют обычно почти одинаковые яркость и цвет.

При передаче и хранении данных часто также имеют дело с несколькими источниками, формирующими статистически связанные друг с другом сообщения. Сообщения, вырабатываемые такими источниками, называются сложными сообщениями, а сами источники - источниками с памятью.

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

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

Пусть сообщения первого источника принимают значения x1, x2, x3,....xk с вероятностями, соответственно, P(x1 ), P(x2 ),..... P(xk ), сообщения второго - y1, y2,.....ym с вероятностями P(y1 ), P(y2 ),..... P(ym ).

Совместную энтропию двух источников X и Y можно определить следующим образом:

, (1)

где P(xi,yj ) - вероятность совместного появления сообщений xi и yj . Поскольку совместная вероятность P(xi,yj ) по формуле Байеса определяется как

,                  (2)

то выражение для совместной энтропии можно записать в следующем виде:

 (3)

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

  (4)

и совместная энтропия H(X,Y) определится как

,                                  (5)

где H ( Y/xi ) - так называемая частная условная энтропия, отражающая энтропию сообщения Y при условии, что имело место сообщение xi. Второе слагаемое в последнем выражении представляет собой усреднение H ( Y/xi ) по всем сообщениям xi и называется средней условной энтропией источника Y при условии передачи сообщения X. И окончательно:

H (X,Y ) = H (X) + H (Y/X) .                     (6)

Таким образом, совместная энтропия двух сообщений равна сумме безусловной энтропии одного из них и условной энтропии второго.

Можно отметить следующие основные свойства энтропии сложных сообщений:

1. ............