русс | укр

Языки программирования

ПаскальСиАссемблерJavaMatlabPhpHtmlJavaScriptCSSC#DelphiТурбо Пролог

Компьютерные сетиСистемное программное обеспечениеИнформационные технологииПрограммирование

Все о программировании


Linux Unix Алгоритмические языки Аналоговые и гибридные вычислительные устройства Архитектура микроконтроллеров Введение в разработку распределенных информационных систем Введение в численные методы Дискретная математика Информационное обслуживание пользователей Информация и моделирование в управлении производством Компьютерная графика Математическое и компьютерное моделирование Моделирование Нейрокомпьютеры Проектирование программ диагностики компьютерных систем и сетей Проектирование системных программ Системы счисления Теория статистики Теория оптимизации Уроки AutoCAD 3D Уроки базы данных Access Уроки Orcad Цифровые автоматы Шпаргалки по компьютеру Шпаргалки по программированию Экспертные системы Элементы теории информации

Пример № 2.


Дата добавления: 2013-12-23; просмотров: 1426; Нарушение авторских прав


Пример № 1.

, .

, .

Средняя длина двоичной последовательности на выходе кодера – это . Лучший код без памяти – это код, для которого средняя длина минимальна. Для того чтобы это выполнялось, необходимо найти соответствующий вектор Крафта . Простым перебором такую задачу при больших k осуществить трудно.

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

Далее приведен алгоритм построения кодового дерева Хаффмана (H-дерева):

Шаг 1. Инициализация. Список подлежащих обработки узлов состоит из узлов, где – мощность алфавита входных сообщений (количество букв в этом алфавите). Каждому из узлов приписывается вероятность появления буквы.

Шаг 2. Цикл. Пока в списке необработанных узлов находим два узла с наименьшими вероятностями. Они исключаются из списка, и вместо них вводится новый узел, которому приписывается суммарная вероятность двух исключенных узлов. Новый узел связывается ребрами с исключенными узлами. .

Теорема 2.Код Хаффмана является оптимальным.

Пусть дан ансамбль сообщений (алфавит): .

Энтропия ансамбля (алфавита): бит.

На рисунке 11.4 приведено кодовое дерево для ансамбля X. Движение при кодировании и декодировании происходит справа налево.

 

Рисунок 11.4 –Кодовое дерево Хаффмана

Таким образом, имеем:

Буква Код l – длина кодового слова k – номер кодового слова
а
b
c
d
e
f

 

Найдены кодовые слова и вектор Крафта: .

Проверим выполнение неравенства Крафта (11.4):

,

значит найденный код оптимальный.

Средняя длина двоичной последовательности, вычисленная по формуле (11.3) составляет



бит.

Очевидно, эта длина не меньше энтропии ( бит).

Найдем избыточность данного неравномерного кода:

бит.

Вычисленная избыточность показывает, что при данном кодировании тратится на 0,05 бит больше, чем могло бы быть затрачено в принципе при теоретически лучшем принципе кодирования.

Для декодирования выходной последовательности используется тоже двоичное кодовое дерево (дерево просматривается справа налево); если в потоке встречается нулевой бит, то берется верхняя ветвь, иначе – нижняя. Так продолжается до тех пор, пока не получен лист дерева, соответствующий исходному символу последовательности.

Средняя длина кодовых слов для данного алгоритма удовлетворяет неравенству

бит,

что и было показано ранее в примере № 2.

Закодируем при помощи построенного кода Хаффмана сообщение «abba»:

a b b a

Видно, что длина кодовой цепочки символов составляет 8 бит = 1 байт.

Если бы сообщение «abba» кодировалось при помощи кодой таблицы ASCII (American Standard Code of Information Interchange – американский стандартный код информационного обмена), то длина кодовой цепочки символов составляет 4 байт (каждая буква кодируется одним байтом). Следовательно, в данном случае коэффициент сжатия, рассчитанный по формуле (11.1), составит

.

Выводы

1. Построенный в примере № 2 код Хаффмана действительно является оптимальным.

2. Средняя длина двоичной последовательности построенного кода Хаффмана составляет 2,45 бит.

3. Избыточность данного неравномерного кода составляет 0,05 бит.

4. Коэффициент сжатия сообщение «abba» кода Хаффмана составляет 4 для случая, когда размер источника сообщений определялся на основе кодой таблицы ASCII.

 



<== предыдущая лекция | следующая лекция ==>
Основные методы побуквенного кодирования. Код Хаффмана | Функции группы администраторов БД


Карта сайта Карта сайта укр


Уроки php mysql Программирование

Онлайн система счисления Калькулятор онлайн обычный Инженерный калькулятор онлайн Замена русских букв на английские для вебмастеров Замена русских букв на английские

Аппаратное и программное обеспечение Графика и компьютерная сфера Интегрированная геоинформационная система Интернет Компьютер Комплектующие компьютера Лекции Методы и средства измерений неэлектрических величин Обслуживание компьютерных и периферийных устройств Операционные системы Параллельное программирование Проектирование электронных средств Периферийные устройства Полезные ресурсы для программистов Программы для программистов Статьи для программистов Cтруктура и организация данных


 


Не нашли то, что искали? Google вам в помощь!

 
 

© life-prog.ru При использовании материалов прямая ссылка на сайт обязательна.

Генерация страницы за: 0.004 сек.