Кодирование информации. Шикина В.Е. - 6 стр.

UptoLike

ВУЗ: 

УлГТУ | Ульяновск

Составители: 

Рубрика: 

3
РАЗДЕЛ 1. ЭФФЕКТИВНОЕ КОДИРОВАНИЕ
1.1. Общая характеристика эффективного кодирования
Учитывая статистические свойства источника сообщения, можно
минимизировать среднее число двоичных символов, требующихся для
выражения одной буквы сообщения, что при отсутствии шума позволяет
уменьшить время передачи или объем запоминающего устройства.
Такое эффективное кодирование базируется на основной теореме Шеннона
для каналов без шума.
Шеннон доказал, что сообщения, составленные из букв некоторого
алфавита, можно закодировать так, что среднее число двоичных символов на
букву будет сколь угодно близко к энтропии источника этих сообщений, но не
меньше этой величины.
1.2. Методика Шеннона – Фэно
При отсутствии статистической взаимосвязи между буквами
конструктивные методы построения эффективных кодов были даны впервые
Шенноном и Фэно. Их методики существенно не различаются, поэтому
соответствующий код получил название кода Шеннона – Фэно.
Код строится следующим образом: буквы алфавита сообщений
выписываются в таблицу в порядке убывания вероятностей. Затем они
разделяются на две группы так, чтобы суммы вероятностей в каждой из групп
были по возможности одинаковы. Всем буквам верхней половины в качестве
первого символа приписывается 1, а всем нижним 0. Каждая из полученных
групп в свою очередь разбивается на две подгруппы с одинаковыми
суммарными вероятностями и т. д. Процесс повторяется до тех пор, пока в
каждой подгруппе останется по одной букве.
Рассмотрим алфавит из восьми букв. Ясно, что при обычном (не
учитывающем статистических характеристик) кодировании для представления
каждой буквы требуется три символа.
Наибольший эффект сжатия получается в случае, когда вероятности букв
представляют собой целочисленные отрицательные степени двойки. Среднее
число символов на букву в этом случае точно равно энтропии. Убедимся в
этом, вычислив энтропию
64
63
1
8
1i
)logp(z)p(zH(z)
ii
=
∑
=
⋅−=
(1.1)
и среднее число символов на букву
64
63
1
8
1i
)n(z)p(zl
ii
ср
=
∑
=
⋅
, (1.2)

Страницы