рефераты конспекты курсовые дипломные лекции шпоры

Реферат Курсовая Конспект

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

Метод кодирования Хаффмана. - раздел Философия, Дисциплина Теория информации Тема №4: Оптимальное эффективное кодирование источников Этот Метод Кодирования Всегда Дает Оптимальный Код, Т.е. Получаемая ...

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

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

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


Пример 1 (ПЗ№8):

 

Знаки(буквы) Вероятность Редукция Кодовое слово по кодовому дереву
x1 0,22 0,22 0,22 0,26 0,32 0,42 0,58
x2 0,20 0,20 0,20 0,22 0,26 0,32 0,42  
x3 0,16 0,16 0,16 0,20 0,22 0,26    
x4 0,16 0,16 0,16 0,16 0,20      
x5 0,1 0,1 0,16 0,16        
x6 0,1 0,1 0,1          
x7 0,04 0,06            
x8 0,02              

 

корень

 


Пример №2 :

 

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

 


 

II способ: Редукция по уровням.

 

 

xi x1 x2 x3 x4 x5 x6 x7 x8
pi 0,22 0,20 0,16 0,16 0,1 0,1 0,04 0,02
код
ni
nipi 0,44 0,4 0,48 0,48 0,3 0,4 0,2 0,1
-pilog2pi                

==2,8

 

=

=

 

Заметим:

1) Во втором способе при построении кодового дерева для присвоения ребрам его значений 1 и 0 необходимо использовать тот же принцип: 1 – ребру с большей вероятностью, 0 – ребру с меньшей вероятностью

2) В случае, когда в процедуре редукции несколько знаков имеют одинаковые вероятности, необходимо выбрать для очередного объединения те два из них, которые до этого имели наименьшее число объединений. Этим достигается выравнивание длин кодовых слов.

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

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

 

При всей простоте коды Хаффмана обладают недостатками:

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

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

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

 

– Конец работы –

Эта тема принадлежит разделу:

Дисциплина Теория информации Тема №4: Оптимальное эффективное кодирование источников

Тамбовский государственный технический университет... Кафедра Информационные системы... Дисциплина Теория информации...

Если Вам нужно дополнительный материал на эту тему, или Вы не нашли то, что искали, рекомендуем воспользоваться поиском по нашей базе работ: Метод кодирования Хаффмана.

Что будем делать с полученным материалом:

Если этот материал оказался полезным ля Вас, Вы можете сохранить его на свою страничку в социальных сетях:

Все темы данного раздела:

Тамбов 2010
Тема №4: Оптимальное (эффективное) кодирование источников. 4.1. Понятие кодирования. Кодовое дерево. В процессе кодирования каждая буква и

Теорема кодирования источников. Неравенство Крафта. Префиксный код.
Теорема Шеннона о кодировании источников устанавливает связь между средней длинной кодового слова и энтропией источника: Для любого дискретного источника без памяти X с конечным алфавитом

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

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

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

Алгоритм универсального кодирования методом Лемпела-Зива.
Этот метод относится к классу универсальных потому, что он не требует априорных знаний о статистике символов. Такой метод носит менее математически обоснованный, но более практический характер.

Особенности программ-архиваторов.
Если коды алгоритмов типа LZ передать для кодирования адаптивному алгоритму Хаффмана или арифметическому, то полученный двухшаговый алгоритм даст результат сжатия, подобный случайным программам: GZ

Сжатие с потерями.
Сжатие с потерями используется в основном для трех видов данных: 1.Полноцветная графика. 2. Звук. 3. Видеоинформация. Сжатие с потерями обычно происходит в два э

Хотите получать на электронную почту самые свежие новости?
Education Insider Sample
Подпишитесь на Нашу рассылку
Наша политика приватности обеспечивает 100% безопасность и анонимность Ваших E-Mail
Реклама
Соответствующий теме материал
  • Похожее
  • Популярное
  • Облако тегов
  • Здесь
  • Временно
  • Пусто
Теги