Реферат: Энтропия сложных сообщений, избыточность источника. Цель сжатия данных и типы систем сжатия
4. Для совместной энтропии двух источников всегда справедливо соотношение
H ( X , Y ) ≤ H ( X ) + H ( Y ), (0)
при этом условие равенства выполняется только для независимых источников сообщений.
Следовательно, при наличии связи между элементарными сообщениями энтропия источника снижается , причем в тем большей степени, чем сильнее связь между элементами сообщения.
Таким образом, можно сделать следующие выводы относительно степени информативности источников сообщений:
1. Энтропия источника и количество информации тем больше, чем больше размер алфавита источника.
2. Энтропия источника зависит от статистических свойств сообщений. Энтропия максимальна, если сообщения источника равновероятны и статистически независимы.
3. Энтропия источника, вырабатывающего неравновероятные сообщения, всегда меньше максимально достижимой .
4. При наличии статистических связей между элементарными сообщениями (памяти источника) его энтропия уменьшается .
В качестве примера рассмотрим источник с алфавитом, состоящим из букв русского языка а ,б, в,.....,ю, я . Будем считать для простоты, что размер алфавита источника К = 25 = 32 .
Если бы все буквы русского алфавита имели одинаковую вероятность и были статистически независимы, то средняя энтропия, приходящаяся на один символ, составила бы
H ( λ )max = log2 32 = 5 бит/букву.
Если теперь учесть лишь различную вероятность букв в тексте (а нетрудно проверить, что так оно и есть), расчетная энтропия составит
H ( λ ) = 4,39 бит/букву.
С учетом корреляции (статистической связи) между двумя и тремя соседними буквами (после буквы “ϔ чаще встречается “A ” и почти никогда – “Ю ” и “Ц ”) энтропия уменьшится, соответственно, до
H ( λ ) = 3,52 бит/букву и H ( λ ) = 3,05 бит/букву .
Наконец, если учесть корреляцию между восемью и более символами, энтропия уменьшится до
H ( λ ) = 2,0 бит/букву
и далее остается без изменений.
В связи с тем, что реальные источники с одним и тем же размером алфавита могут иметь совершенно различную энтропию (а это не только тексты, но и речь, музыка, изображения и т.д.), вводят такую характеристику источника, как избыточность
ρи = 1 - H ( λ ) / H ( λ )max = 1 - H ( λ )/log K , (11)
где H (λ ) - энтропия реального источника, log K - максимально достижимая энтропия для источника с объемом алфавита в К символов.
Тогда, к примеру, избыточность литературного русского текста составит
ρи = 1 - ( 2 бита/букву )/( 5 бит/букву ) = 0,6 .
Другими словами, при передаче текста по каналу связи каждые шесть букв из десяти передаваемых не несут никакой информации и могут безо всяких потерь просто не передаваться.
Такой же, если не более высокой ( ρи = 0,9...0,95) избыточностью обладают и другие источники информации - речь, и особенно музыка, телевизионные изображения и т.д.
Возникает законный вопрос: нужно ли занимать носитель информации или канал связи передачей символов, практически не несущих информации, или же возможно такое преобразование исходного сообщения, при котором информация "втискивалась" бы в минимально необходимое для этого число символов?
Оказывается, не только можно, но и необходимо. Сегодня многие из существующих радиотехнических систем передачи информации и связи просто не смогли бы работать, если бы в них не производилось такого рода кодирование. Не было бы цифровой сотовой связи стандартов GSM и CDMA. Не работали бы системы цифрового спутникового телевидения, очень неэффективной была бы работа Internet, а уж о том, чтобы посмотреть видеофильм или послушать хорошую музыку с лазерного диска, не могло быть и речи. Все это обеспечивается эффективным или экономным кодированием информации в данных системах.
Изучению этого раздела современной радиотехники – основ теории и техники экономного, или безызбыточного, кодирования - и посвящена следующая часть нашего курса.