Лекция №4 оптимальное и эффективное кодирование

1. Понятие кодирования. Кодовое дерево.

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

Если исходный алфавит содержит m букв, то для построения равномерного кода с использованием D кодовых букв необходимо обеспечить выполнение следующего условия:

,

где n- количество элементов кодовой последовательности.

Для построения равномерного кода достаточно пронумеровать буквы исходного алфавита и записать их в коды как n-разрядное число в D-ичной системе счисления.

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

.

При этом - энтропия кода одной буквы в n - разрядном D- ичном числе. Таким образом, информационные возможности кода используются не полностью.

Пример. Для двоичного 5-рарядного кода букв русского алфавита информационная емкость составляет 5 бит, =4,35 бит.

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

Если i-ая буква, вероятность которой p_i, получает кодовую комбинацию длины n_i, то средняя длинна кода или средняя длина кодового слова равна:

Введем понятие кодового дерева, которым часто пользуются при рассмотрении Известно, что любую букву или событие, содержащиеся в алфавите источника или в сообщении, можно разложить на последовательности двоичных решений с исходами «ДА»=1 и «НЕТ»=0, причем без потери информации. Таким образом, каждой букве исходного алфавита может быть поставлена в соответствие или, как говорят, приписана некоторая последовательность двоичных символов - 0 или 1.А такую последовательность называют кодовым деревом. При этом потери информации не происходит, так как каждое событие может быть восстановлено по соответствующему кодовому слову.

Корень

0

1

0

1

1

2

0

2

4

3

8

4

16

1

1

0

С₁

1

0

1

0

10

0

С₂

С₃

1

0

1

0

1

0

1

0

С₁₁

С₁₀

С₉

С₈

С₇

С₆

С₅

С₄

C₁,C₂,…,C₁₁-кодовые слова. Уровень кодового дерева определяет длину кодового слова.

2. Теорема кодирования источников, неравенство Крафта.

Префиксный код.

Теорема Шеннона о кодировании источников устанавливает связь между средней длинной кодового слова и энтропией источника.

Для любого дискретного источника без памяти X с конечным алфавитом и энтропией H(X) существует D- ичный префиксный код, в котором средняя длинна кодового слова , удовлетворяет неравенству:

В префиксном коде никакое кодовое дерево не является префиксом другого кодового дерева. Это значит, что поток кодовых слов может использоваться без специального разделения этих слов. Например, если код 101 является кодом какой-то буквы, то в качестве кодов других букв нельзя использовать следующие комбинации: 1,10,10101, …и т.д.

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

.

Если средняя длина кодового слова является минимально возможной, то код еще и оптимальный. Теорема кодирования источников доказывается с использованием неравенства Крафта и формулируется следующим образом.

Для существования однозначно декодируемого D- ичного кода, содержащего k кодовых слов с длинами n₁,n₂,…,n_k, необходимо и достаточно, чтобы выполнялось неравенство Крафта:

3. Методы оптимального кодирования. Сжатие данных.

Процедуру оптимального кодирования часто называют сжатием данных. Тогда задача сжатия данных есть минимизация технических затрат на хранение или передачу информации путем оптимального кодирования. На практике используют два вида сжатия данных:

1.Сжатие без потерь - устранение избыточности информации, не связанное с ее изменением, принципиально существенным для пользователя.

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

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

Методы сжатия данных были разработаны как математическая теория, которая до первой половины 80-х годов 20 века мало использовалась в компьютерной технике.

Методы или алгоритмы сжатия данных без потерь можно разделить на:

1.Статистические методы или алгоритмы. Например, методы Шеннона - Фано, Хаффмана и др.

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

2.Адаптивные методы или алгоритмы. Например, модифицированные коды Хаффмана, арифметическое кодирование и др.

Здесь распределение вероятностей символов сначала считается равномерным на заданном интервале, а потом оно меняется по мере накопления статистики.

3.Динамические методы или алгоритмы. Они являются универсальными и не нуждаются в априорной статистике. Например, метод Лемпела- Зива.

1. Метод кодирования Шеннона - Фано.

Буквы исходного алфавита записываются в порядке убывания их вероятностей. Это множество разбивается так, чтобы вероятности двух подмножеств были примерно равны. Все буквы верхнего подмножества в качестве первого символа кода получают 1, а буквы нижнего подмножества-0. Затем последнее подмножество снова разбивается на два подмножества с соблюдением того же условия и проводят то же самое присвоение кодовым элементам второго символа. Процесс продолжается до тех пор, пока во всех подмножествах не останется по одной букве кодового алфавита.

Пример.

Буква xi	Вероятности pi	Кодовая последовательность				Длина кодового слова ni	pini	-pilog2pi
		Номер разбиения
		1	2	3	4
x1	0,25	1	1			2	0,5	0,5
x2	0,25	1	0			2	0,5	0,5
x3	0,15	0	1	1		3	0,45	0,4
x4	0,15	0	1	0		3	0,45	0,4
x5	0,05	0	0	1	1	4	0,2	0,2
x6	0,05	0	0	1	0	4	0,2	0,2
x7	0,05	0	0	0	1	4	0,2	0,2
x8	0,05	0	0	0	0	4	0,2	0,2

== (0,25*2+0,25*2+0,15*3+0,15*3+0,05*4+0,05*4+0,05*4+0,15*4)=2,7 бит

= - (2*0,25*log₂ 0,25 + 2*0,15*log₂ 0,15 + 4*0,05*log₂0,05) = 2,7 бит

= 1

Метод Шеннона - Фано не всегда приводит к однозначному построению кода, так как при разбиении на подмножества можно сделать большей по вероятности как верхнюю, так и нижнюю часть, следовательно, такое кодирование хотя и является эффективным, но не всегда будет оптимальным.

2. Метод кодирования Хаффмана.

Этот метод всегда дает оптимальное кодирование в отличие от предыдущего, так как получаемая средняя длина кодового слова является минимальной.

Буквы алфавита сообщения располагают в порядке убывания вероятностей. Две последние буквы объединяют в один составной символ, которому приписывают суммарную вероятность. Далее заново переупорядочивают символы и снова объединяют пару с наименьшими вероятностями. Продолжают эту процедуру до тех пор, пока все значения не будут объединены. Это называется редукцией. Затем строится кодовое дерево из точки, соответствующей вероятности 1 (это корень дерева), причем ребрам с большей вероятностью присваивают 1,а с меньшей-0. Двигаясь по кодовому дереву от корня к оконечному узлу, можно записать кодовое слово для каждой буквы исходного алфавита.

Пример.

Буква xi	a	b	c	d	e	f
Вероятности pi	0,05	0,15	0,05	0,4	0,2	0,15
Кодовое слово	1001	110	1000	0	111	101
Длина кодового слова ni	4	3	4	1	3	3

0,4

0,2

0,15

0,05

0,15

0,35

0,05

1

0,1

0,6

1

0,25

0

1

1

0

0

1

0

0

1

== (4*0,05 +3*0,15+4*0,05+0,4+3*0,2+3*0,15)= 2,3 бит

= - (0,4log₂ 0,4+0,2 log₂ 0,2+2* 0,15 log₂0,15 +2*0,05 log₂0,05)= - (0,52 + 0,46+ 2*0,4+2*0,2)= 2,18

= 1,05

Из рассмотренного примера видно, что чем больше разница между вероятностями букв исходного алфавита, тем больше выигрыш кода Хаффмана по сравнению с простым блоковым кодированием.

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

Недостатки кода:

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

2.Сжатие снижает избыточность, что соответственно повышает предрасположенность к распространению ошибок, т.е. один ошибочно принятый бит может привести к тому, что все последующие символы будут декодироваться неверно.

3.Предполагаются априорные знания вероятности букв, которые на практике не известны, а их оценки часто бывают затруднительны.