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

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

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

Метод кодирования Хафмана - раздел Философия, ТЕОРИЯ ИНФОРМАЦИИ   Правило Образования Кодов Состоит Из Следующих Пунктов. ...

 

Правило образования кодов состоит из следующих пунктов.

1. Все сообщения ансамбля ранжируются в порядке убывания вероятности реализаций сообщений.

2. Последние два сообщения объединяются в одно сообщение с вероятностью реализации, равной сумме вероятностей, объединяемых сообщений.

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

4. Процедура объединения и ранжирования сообщений продолжается до тех пор, пока не останется одно сообщение с вероятностью реализации, равной 1.

5. В результате процедуры объединения и ранжирования сообщений получается кодовое дерево. Каждому лучу, исходящему из узла, в котором объединяются сообщения, приписываются символы 1 и 0, ( скажем, верхнему лучу приписывается символ 1, нижнему – символ 0).

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

Процедура кодирования демонстрируется на примере.

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

 

Характеристики , , , , остаются неизменными.

Рассмотрим ансамбль . По формуле полной вероятности получим = 0.5303, = 0.4697.

Количество информации, содержащееся в каждом символе ансамбля Y равно соответственно

0.915119 , 1.09019 .

Энтропия ансамбля Y равна

0.997349.

Соответственно коэффициент сжатия и коэффициент избыточности будут равны

0.997349, 0.00265

 

Таблица 3.4  
X Вер. не префиксный код префиксный код Условн. вер.
0.2
0.2 1/2
0.19 1/3
0.15 2/3
0.10 1/3
0.08 1/4
0.06 1/5
0.01 1/6
0.01
             

 

На рисунке 3.5 приведено кодовое дерево, полученное при кодировании по методу Хафмена ансамбля X.

 

 
 

Сравнивая коэффициенты сжатия и коэффициенты избыточности ансамблей X и Y видно при кодировании по методу Хафмана, произошло увеличение коэффициента сжатия и уменьшение избыточности ансамбля Y по сравнению с равномерным кодом.

Средняя длина кода при кодировании по методу Хафмана уменьшилась также и равна

=1.34 .

Как видно из рисунка 3.5, ни одна кодовая комбинация не является началом другой кодовой комбинации, т.е. код является префиксным. Свойство префиксности кода позволяет однозначно декодировать последовательность кодовых комбинаций, что видно из таблицы 3.4 и рисунка 3.5.

Следует отметить, метод кодирования Хафмана позволяет получить показатели , , , более высокие, чем при кодировании по методу Шеннона. Это объясняется тем, что в методе кодирования по Шеннону допускается некоторый произвол при делении множества событий на группы.

 

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

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

ТЕОРИЯ ИНФОРМАЦИИ

Мера информации Мера информации по Шеннону Сообщения могут быть... Количество взаимной информации... Дискретный канал передачи информации Рассмотрим...

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

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

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

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

Теорема Котельникова
  Согласно теореме Котельникова, если спектр сигнала ограничен полосой

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

Мера информации по Шеннону
  Сообщения могут быть закодированы разными символами. Число разных символов, из которых образуются сообщения, составляет основание кода, (русский алфавит имеет 33 символа, двоичный к

Энтропия дискретного ансамбля сообщений
Среднее количество информации, содержащееся в ансамбле , определяется математическим ожиданием &nbs

Энтропия непрерывного ансамбля сообщений
  Выше мера информации была введена для дискретного ансамбля сообщений. Точно так же вводится мера информации на непрерывном ансамбле. Непрерывная случайная величина

Энтропия непрерывного ограниченного ансамбля
  Энтропия ансамбля после квантования была записана как

Дискретный канал передачи информации
  Рассмотрим модель канала передачи информации  

Непрерывный канал передачи информации
  Непрерывный канал передачи информации описывается одномерными и двумерными плотностями распределений вероятностей. Чтобы записать количество взаимной информации между входом и выход

Кодирование источника информации
  Источник информации может быть составлен из различных элементов. В частности это могут

Метод кодирования равномерным кодом
  Чтобы уменьшить избыточность, содержащуюся в ансамбле X источника информации, создается новый ансамбль Y символов, энтропия которой близка к максимальному значению. За

Метод кодирования Шеннона-Фано
  При кодировании по методу Шеннона следует придерживаться следующих правил. 1. Все сообщения

Независимых сообщений.
  При заданном ансамбле из N независимых сообщений с энтропией

Канал связи
Под каналом связи понимается среда, в которой перемещается сигнал. В зависимости от типа сигнала каналы разделяются на непрерывные и дискретные. Предполагается, что сигнал, передаваемый по

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

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

Канал с шумами
  Наличие шума в канале связи приводит к тому, что условная энтропия не равна нулю. Условную

Непрерывный канал связи
  Как и прежде, сигналы поступают в канал в дискретные моменты времени, но значения сигналов принимают непрерывные значения из некоторого множества. Примером такого канала является пе

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

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

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

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

Образование систематического кода
Обычно для построения кодов необходимо знать длину кодовой комбинации , кратность обнаруживаемых ошибок

Систематический код Хемминга
Соотношение между числом информационных символов , числом исправляемых ошибок

Циклические коды
  Циклические коды являются разновидностью систематических кодов. Они получили широкое распространение из-за простоты кодирования и декодирования. Все разрешённые кодовые комбинации п

Обнаружение однократной ошибки
  Циклический код относится к классу систематических кодов. Ранее было показано, что при обнаружении одиночной ошибки минимальное кодовое расстояние равно

Исправление однократной ошибки
Исправление одиночной ошибки связано с определением разряда, в котором произошла ошибка. Это производится на основании анализа остатков от деления многочленов ошибок

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