Код Хаффмана - раздел Образование, Основы теории информации и криптографии Алгоритм Хаффмана Дает Эффективный Способ Поиска Оптимального Вектора Крафта....
Алгоритм Хаффмана дает эффективный способ поиска оптимального вектора Крафта. Код, получаемый с использованием этого оптимального вектора, называется кодом Хаффмана[1].
Далее приведен алгоритм построения кодового дерева Хаффмана:
Инициализация. Список подлежащих обработки узлов состоит из узлов, где – мощность алфавита входных сообщений.
Каждому из узлов приписывается вероятность появления буквы.
Цикл. Пока в списке необработанных узлов находим два узла с наименьшими вероятностями. Они исключаются из списка, и вместо них вводится новый узел, которому приписывается суммарная вероятность двух исключенных узлов. Новый узел связывается ребрами с исключенными узлами. .
Теорема 2.2
Код Хаффмана является оптимальным.
Пример
Дан ансамбль: .
Энтропия ансамбля: .
На рис. 6 приведено кодовое дерево. Движение при кодировании и декодировании идет справа налево.
Рис. 6. Кодовое дерево Хаффмана
Таким образом:
буква
код
а
b
c
d
e
f
Найдены и кодовые слова, и вектор Крафта: . Проверим неравенство (2.1): , значит найденный код оптимальный. Длина двоичной последовательности: . Эта длина не меньше энтропии.
Найдем избыточность данного неравномерного кода: . Это показывает, что при данном кодировании тратится на 0.05 бит больше, чем могло бы быть затрачено в принципе при теоретически лучшем принципе кодирования. ●
Для декодирования выходной последовательности используется тоже двоичное кодовое дерево; если в потоке встречается -ой бит, то берется верхняя ветвь, иначе – нижняя. Так продолжается до тех пор, пока не получен лист дерева, соответствующий исходному символу последовательности.
Средняя длина кодовых слов для данного алгоритма: , что и было видно выше в примере.
Если Вам нужно дополнительный материал на эту тему, или Вы не нашли то, что искали, рекомендуем воспользоваться поиском по нашей базе работ:
Код Хаффмана
Что будем делать с полученным материалом:
Если этот материал оказался полезным ля Вас, Вы можете сохранить его на свою страничку в социальных сетях:
Задачи, решаемые в рамках теории информации
Теория информации – наука, появившаяся в 1948 г. в результате публикации работы Клода Шеннона «Математическая теория связи».
Ниже представлена структурная схема типичной системы передачи и
И их вероятностные модели
Пусть рассматривается произвольный источник сообщений. Каждое сообщение – это последовательность символов (например, букв русского алфавита, точек и тире в телеграфии, 0 и 1 в компьют
Собственная информация
Очевидно, что задача количественного измерения информации возникла при решении конкретных практических задач. Например, можно стремиться уменьшить количество электрических сигналов, необходимых для
Взаимная информация
Рассмотрим два ансамбля сообщений: . – ансамбль сообщений на входе
Энтропия
Пусть ИДС описывается некоторым дискретным ансамблем: . Тогда энтропия ИДС (или энтропия случайног
Условная энтропия
Пусть имеются два статистически независимых конечных ансамбля символов . Пары символов
Избыточность
Считают, что имеется избыточность, если количество информации, содержащейся в сигнале (энтропия сигнала), меньше того количества, которое этот сигнал мог бы содержать по своей физической природе.
Сжатие без потерь информации
В системах неразрушающего сжатия декодер восстанавливает данные источника абсолютно без потерь (рис. 4).
Сжатие с потерями информации.
Далее приведена система разрушающего сжатия (рис.5):
Рис. 5. Схема сжатия с потерями
&nbs
Без потерь информации
В данном случае кодирующие устройство должно удовлетворять следующим условиям:
1. Обеспечивать безошибочную передачу информации, то есть взаимно однозначное соответствие между
Основные методы побуквенного кодирования
Простейшими кодами, с помощью которых можно выполнять сжатие информации, являются коды без памяти. Наилучшим из кодов, обладающих свойствами, перечисленными выше, является код Хаффмана.
Ко
Код Шеннона
Далее приведен алгоритм кодирования по Шеннону:
Инициализации. Все буквы из алфавита записываются по убыванию вероятностей встречаемости в сообщениях. Каждой букве ставится в
Код Шеннона-Фано
Ниже приведен алгоритм кодирования по методу Шеннона-Фано:
Инициализации. Все буквы алфавита записываются в порядке убывания вероятностей.
Цикл. Всю совокупно
Код Гильбера-Мура
Далее приведен алгоритм кодирования по методу Гильбера-Мура.
Инициализация. Сопоставим каждой букве кумулятивную вероятность
Помехоустойчивое кодирование
Помехоустойчивые коды – это коды, позволяющие обнаружить и (или) исправить ошибки в кодовых словах, которые возникают при передачи по каналам связи. Эти коды строятся таким образом, что для
Коды с обнаружением ошибок
Рассмотрим простейший метод, принадлежащий к этой группе кодов и основанный на проверке на четность.
Схема кодирования: , то
Линейные блоковые коды
Линейным блоковым (n, k) кодом называется множество последовательностей длины
Коды Хэмминга
Код Хэмминга представляет собой один из важнейших классов линейных кодов, нашедших широкое применение на практике и имеющих простой и удобный для технической реализации алгоритм обнаружения и испра
Циклические коды
В отличие от кода Хемминга в циклическом коде используют математические операции не над векторами, а над многочленами. (Напомним, что произвольному вектору
Основные аспекты криптографии
Криптография – (до 70-ых годов) область научной и практической деятельности, связанной с разработкой, применением и анализом шифросистем; (в настоящее время) область науки, техники, практиче
Основные аспекты криптоанализа
Попытка криптоанализа называется вскрытием. Основное предположение криптоанализа, впервые сформулированное в XIX веке Д. А. Керкхофсом, состоит в том, что безопасность полностью опред
Шеноновские модели криптографии
На рис. 12 представлена общая схема симметричной криптосистемы.
Рис. 12. Схема симметричной крипто
Псевдослучайные последовательности
Случайные числа и их генераторы являются неотъемлемыми элементами современных криптосистем. Ниже приводятся конкретные примеры использования случайных чисел в криптологии:
1. Сеансовые и д
Система шифрования RSA
Данная криптосистема является шифрованием с открытым ключом. Алгоритм RSA[7] опирается на тот факт, что найти большие простые числа вычислительно легко, но разложить большое число на произведение д
Система шифрования Диффи-Хеллмана
Данный алгоритм[8] также является алгоритмом секретного обмена между абонентами ключом. Он основан на трудности вычисления дискретного логарифма.
Рассмотрим простейшую схему создания общег
Разложение на множители (факторизация)
Разложение на множители числа (например, ) является одной из древнейших проблем теории чисел. Приступая к факторизации числа, следует снача
Вычисление в поле Галуа
Напомним некоторые определения из алгебраических основ:
Поле – это множество
БИБЛИОГРАФИЧЕСКИЙ СПИСОК
Шеннон К. Теория связи в секретных системах. / В кн. Лекции по теории информации и кибернетике.–М.: ИЛ, 1963. Харин Ю.С., Берник В.И., Матвеев Г.В., Агиевич С.В. Матем
Хотите получать на электронную почту самые свежие новости?
Подпишитесь на Нашу рассылку
Наша политика приватности обеспечивает 100% безопасность и анонимность Ваших E-Mail
Новости и инфо для студентов