Студопедия  
Главная страница | Контакты | Случайная страница

АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатика
ИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханика
ОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторика
СоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансы
ХимияЧерчениеЭкологияЭкономикаЭлектроника

САНКТ-ПЕТЕРБУРГСКАЯ АКАДЕМИЯ

Читайте также:
  1. АЗАҚ БАС СӘУЛЕТ-ҚҰРЫЛЫС АКАДЕМИЯСЫ
  2. Академия Гражданской Авиации
  3. Академия Гражданской Авиации
  4. АКАДЕМИЯ ГРАЖДАНСКОЙ ЗАЩИТЫ МЧС РОССИИ
  5. АКАДЕМИЯ МАРКЕТИНГА И СОЦИАЛЬНО-ИНФОРМАЦИОННЫХ
  6. Академия наук Республики Казахстан и специализированные Академии
  7. АКАДЕМИЯ ТРУДА И СОЦИАЛЬНЫХ ОТНОШЕНИЙ
  8. АКАДЕМИЯ ФОГЕЛЬЗАНГ
  9. АНО ВПО РОССИЙСКАЯ АКАДЕМИЯ ПРЕДПРИНИМАТЕЛЬСТВА
  10. Виват, академия

Разработать код с использованием метода Хаффмена для входного алфавита Х = {x1,...x8} и выходного алфавита В = {0,1}, если р(х1)= 0,19; р(х2)= 0,17; р(х3)= р(х4)= 0,15; р(х5)= 0,12; р(х6)= 0,11; р(х7)= 0,09; р(х8)= 0,02, и определить коэффициент избыточности полученного кода.

Решение:

Методика Хаффмена для построения двоичных эффективных кодов:

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

Составим таблицу:

Знаки Вероятность
x1 0,19
x2 0,17
x3 0,15
x4 0,15
x5 0,12
x6 0,11
x7 0,09
x8 0,02

 

Теперь применим методику Хаффмена:

Знаки Вероятность  
x1 0,19  
x2 0,17  
x3 0,15  
x4 0,15  
x5 0,12  
x6 0,11  
x7 0,09  
x8 0,02  

 

Знаки Вероятность  
x1 0,19  
x2 0,17  
x3 0,15  
x4 0,15  
x5 0,12  
x6 0,11  
x78 0,11  

 

Знаки Вероятность  
х678 0,22  
x1 0,19  
x2 0,17  
x3 0,15  
x4 0,15  
x5 0,12  

 

Знаки Вероятность  
х45 0,27  
х678 0,22  
x1 0,19  
x2 0,17  
x3 0,15  

 


 

Знаки Вероятность  
х32 0,32  
х45 0,27  
х678 0,22  
x1 0,19  

 

Знаки Вероятность  
х1678 0,41  
х32 0,32  
х45 0,27  

 

Знаки Вероятность  
х2345 0,59  
х1678 0,41  

Теперь запишем полученные коды для всех знаков алфавита:

Знаки Вероятность Код
x1 0,19  
x2 0,17  
x3 0,15  
x4 0,15  
x5 0,12  
x6 0,11  
x7 0,09  
x8 0,02  

 

 

Среднее число символов на знак сообщения считается по следующей формуле:

,

где p(zi) – вероятность использования знака zi

n(zi) – число символов в кодовой комбинации, соответствующей знаку zi

Избыточность кода определяется по формуле:

,

где

Hmax(z) – максимально возможная энтропия, равная log L, где L – количество знаков в алфавите сообщений. Рассчитывается по формуле Хартли;

H(Z) – энтропия кода. Рассчитывается по формуле Шеннона

Произведем расчет:

 


 

Задача 3. Алфавит сообщений состоит всего из двух знаков Z1 и Z2 с вероятностями появления соответственно p(z1) = 0,9 и p(z2) = 0,1.
Рассчитать и сравнить эффективность кодов, полученных при побуквенном кодировании, при кодировании блоков, содержащих по две буквы, при кодировании блоков, содержащих по три буквы. Так как знаки статистически не связаны, вероятности блоков определяются как произведение вероятностей составляющих знаков.

Решение:

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

1. Побуквенное кодирование:

Знаки Вероятность
z1 0,9
z2 0,1

 

Рассчитаем энтропию:

 

2. Кодирование блоков, содержащих по две буквы:

Знаки Вероятность
z1z1 0,81
z1z2 0,09
z2z1 0,09
z2z2 0,01

 

Рассчитаем энтропию:

3. Кодирование блоков, содержащих по три буквы:

Знаки Вероятность
z1z1z1 0,729
z1z1z2 0,081
z1z2z1 0,081
z1z2z2 0,009
z2z1z1 0,081
z2z1z2 0,009
z2z2z1 0,009
z2z2z2 0,001

Рассчитаем энтропию:

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


 

Список использованной литературы:

1. А.В.Власенко, В.И.Ключко «Теория информации». Краснодар Издательство КубГТУ 2003.

2. Игнатов В. А. «Теория информации и передачи сигналов», 1979.

3. Лидовский В. В. Учебное пособие по курсу «Теория информации», 2004.

4. Кавчук С. В. Сборник примеров и задач по теории информации, 2002.

5. Ломакин Д. В., Туркин А. И. Прикладная теория информации и кодирования, 1988.

 

САНКТ-ПЕТЕРБУРГСКАЯ АКАДЕМИЯ




Дата добавления: 2014-12-20; просмотров: 20 | Поможем написать вашу работу | Нарушение авторских прав




lektsii.net - Лекции.Нет - 2014-2024 год. (0.01 сек.) Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав