41973

ПОБУДОВА ОПТИМАЛЬНОГО НЕРІВНОМІРНОГО КОДУ ЗА МЕТОДИКОЮ ХАФФМАНА

Лабораторная работа

Информатика, кибернетика и программирование

0 проводиться перехід до побудови дерева коду за допомогою проміжних вузлів. 161 00074 3 В 893 00412 21 Х 156 00072 11 Л 745 00344 29 Ю 148 00068 16 Р 699 00322 22 Ц 126 00058 №п п Символ ni pi №п п Символ ni pi 12 М 656 00303 25 Щ 108 00050 10 К 574 00265 24 Ш 60 00028 5 Д 507 00234 28 Э 59 00027 26 Ы 467 00215 20 Ф 30 00014 19 У 399 00184 8 З 4 00002 Дерево коду за методикою Хаффмана: Визначаємо ентропію джерела за формулою: Визначаємо максимальний ступінь стиснення інформації: Середня довжина кодової комбінації:...

Украинкский

2013-10-26

53.47 KB

13 чел.

Лабораторна робота №3

ПОБУДОВА ОПТИМАЛЬНОГО НЕРІВНОМІРНОГО КОДУ ЗА МЕТОДИКОЮ ХАФФМАНА

Мета роботи:  

  1.  визначити принципи та умови побудови нерівномірних оптимальних кодів;
  2.  набути навичок побудови оптимального нерівномірного коду за методикою Хаффмана.

СТИСЛІ ТЕОРЕТИЧНІ ВІДОМОСТІ

Спроби знайти інші методики побудови оптимальних кодів, позбавлених недоліків методики Шеннона-Фано, призвели до того, що в 1974 р. Хаффман запропонував методику побудови ОНК від листя до кореня дерева. Запропонована методика включає наступні процедури:

1. упорядкувати масив у порядку зменшення ваги символів;

2. скласти ваги двох молодших символів, утворити фіктивний проміжний вузол, повернутися до п.1.

На кожному кроці алгоритму перевіряється сума вагів проміжних вузлів.

Коли сума виявиться рівною 1.0, проводиться перехід до побудови дерева коду за допомогою проміжних вузлів.

Виконання роботи:

Алфавіт джерела:

№п/п

Символ

n(i)

p(i)

№п/п

Символ

n(i)

p(i)

32

"ПРБ"

3101

0,1431

30

Я

373

0,0172

14

О

2087

0,0963

15

П

354

0,0163

6

Е

1914

0,0883

23

Ч

336

0,0155

9

И

1452

0,0670

27

Ь

334

0,0154

13

Н

1440

0,0664

4

Г

270

0,0125

18

Т

1326

0,0612

2

Б

267

0,0123

17

С

1287

0,0594

7

Ж

240

0,0111

1

А

1104

0,0509

31

.

161

0,0074

3

В

893

0,0412

21

Х

156

0,0072

11

Л

745

0,0344

29

Ю

148

0,0068

16

Р

699

0,0322

22

Ц

126

0,0058

№п/п

Символ

n(i)

p(i)

№п/п

Символ

n(i)

p(i)

12

М

656

0,0303

25

Щ

108

0,0050

10

К

574

0,0265

24

Ш

60

0,0028

5

Д

507

0,0234

28

Э

59

0,0027

26

Ы

467

0,0215

20

Ф

30

0,0014

19

У

399

0,0184

8

З

4

0,0002

Дерево коду за методикою Хаффмана:

Визначаємо ентропію джерела за формулою:


Визначаємо максимальний ступінь стиснення інформації:

Середня довжина кодової комбінації:

Коефіцієнт ефективності кода:

Коефіцієнт стискання:

Код символів алфавіту:

Символ

ПК

ЗК

Символ

ПК

ЗК

"ПРБ"

110

011

Я

101011

110101

О

001

100

П

101010

010101

Е

1111

1111

Ч

100001

100001

И

1011

1101

Ь

100000

000001

Н

1001

1001

Г

010000

000010

Т

0111

1110

Б

010001

100010

С

0110

0110

Ж

000001

100000

А

0001

1000

.

0101011

1101010

В

11101

10111

Х

0101010

0101010

Л

10100

00101

Ю

0101000

0001010

Р

10001

10001

Ц

0000001

1000000

М

01011

11010

Щ

0000000

0000000

К

01001

10010

Ш

01010010

01001010

Д

00001

10000

Э

010100110

011001010

Ы

111001

100111

Ф

0101001111

1111001010

У

111000

000111

З

0101001110

0111001010


Висновок:

На даній лабораторній роботі я створив оптимальний нерівномірний код за методикою Хаффмана, який за своєю ефективністю на 99.3% наблизився до ідеального. Розрахував середню довжину кодової комбінації, коефіцієнт ефективності коду, коефіцієнт стискання та провів порівняльний аналіз з аналогічним кодом за методом Шеннона-Фано.

Також ознайомився з поняттями:

Оптимальними нерівномірними кодами (ОНК) - називаються коди, в яких символи алфавіту кодуються кодовими словами мінімально середньої довжини.

Кодування за методом Хаффмана здійснюється наступним чином:

1. упорядкувати масив у порядку зменшення ваги символів;

2. скласти ваги двох молодших символів, утворити фіктивний проміжний вузол, повернутися до п.1.

На кожному кроці алгоритму перевіряється сума вагів проміжних вузлів.

  1.  Коли сума виявиться рівною 1.0, проводиться перехід до побудови дерева коду за допомогою проміжних вузлів. Всім символам верхньої групи приписується кодовий символ 1, а символам нижньої - 0. Можна, навпаки, тому що для кодової реалізації байдуже 0 або 1, але з точки зору потужності, краще, якщо в кодової комбінації менше одиниць.
  2.  Потім кожна підгрупа аналогічним чином розбивається на підгрупи по можливості з однаковими ймовірностями. Розбиття здійснюється до тих пір, поки в кожній підгрупі залишиться по одному символу.

Теорема Шеннона: Теорема доведена К. Шенноном (Claude Elwood Shannon) в (1948 р.), що завжди можна побудувати таку систему ефективного кодування дискретного джерела, при якій середня кількість двійкових знаків на символ джерела як завгодно близька, але не менша за ентропію джерела на повідомлення.

За методикою Шеннона-Фано ми отримали код з меншою максимальною довжиною кодової комбінації, проте за методом Хаффмана код виявився ефективнішим, що показують вищі показники ефективності коду та стикання.

Для оцінки ступеня досконалості коду вводиться показник - коефіцієнт ефективності код

Кєф=

Коефіцієнт стиснення інформації визначається за формулою:

Kсж=

Перша умова Сардінаса: жодна комбінація коду не повинна бути початком іншої, довшої комбінації, цього ж коду.

Друга умова Сардінаса - інверсний код не повинен бути префіксним.

ОНК - клас кодів, що самосинхронізуються, відновлюють синхронізацію самостійно та мають кінцевий трек помилки. Щоб код само синхронізувався потрібно щоб виконувались 2 умови Сардінаса.


 

А также другие работы, которые могут Вас заинтересовать

79270. Цели, функции, организационная структура системы управления персоналом 229.37 KB
  Традиционно в службы управления персоналом входят: отдел кадров отдел обучения отдел труда и заработной платы отдел социального развития и другие отделы социальной инфраструктуры отдел охраны труда и техники безопасности лаборатория социологии отдел охраны окружающей среды юридический отдел отдел организации труда производства и управления отдел научнотехнической информации патентнолицензионный отдел бюро рационализации и изобретательства. 1 Цели системы управления персоналом организации с точки зрения персонала Рис. 2 Цели...
79271. Анализ и описание работы и рабочего места 13.44 KB
  Анализ рабочего места представляет собой дифференцирование рабочего места с одной стороны через задачи деятельность которая на нем совершается а с другой через требования по отношению к образованию опыту и ответственности необходимым для успешного выполнения деятельности на этом месте. АРМ как правило состоит из двух частей: описание рабочего места перечисление видов деятельности задач трудовых условий средств оборудования и материалов которые используются на данном рабочем месте; спецификация рабочего места перечисление...
79272. Кадровое обеспечение системы управления персоналом 30.16 KB
  Под кадровым обеспечением системы управления персоналом понимается необходимый количественный и качественный состав работников кадровой службы организации. Работники службы управления персоналом должны: хорошо знать трудовое законодательство методические нормативные и другие материалы касающиеся работы с персоналом учета личного состава; основы педагогики социологии и психологии труда; передовой отечественный и зарубежный опыт в области управления персоналом; владеть современными методами оценки персонала профориентационной работы...
79273. Информационное и техническое обеспечение системы управления персоналом 18.5 KB
  Реализация кадровых задач напрямую зависит от качества и количества информации на основе которой будет принято то или иное решение. Информационное обеспечение включает в себя сбор анализ и хранение информации. Качество представленной информации зависит от критериев оценки информации т. Полпота информации заключается в том объеме который необходим и достаточен для принятия управленческого решения.
79274. Нормативно-методическое и правовое обеспечение системы управления персоналом 16.07 KB
  Нормативнометодическое обеспечение системы управления персоналом представляет собой обеспечение документами устанавливающими нормы управления правила и методы организации труда необходимыми для нормальной организации трудовых процессов ведения нормативного хозяйства системы управления. Нормативнометодические документы подразделяются на следующие группы: нормативносправочные определяют нормы времени управленческих действий задания на конкретный период времени инструкции вышестоящих организаций или органов власти;...
79275. Кадровая политика организации – основа формирования стратегии управления персоналом 20.81 KB
  Кадровая политика организации генеральное направление кадровой работы совокупность принципов методов форм организационного механизма по выработке целей и задач направленных на сохранение укрепление и развитие кадрового потенциала на создание квалифицированного и высокопроизводительного сплоченного коллектива способного своевременно реагировать на постоянно меняющиеся требования рынка с учетом стратегии развития организации. Назначение кадровой политики – своевременно формулировать цели в соответствии со стратегией развития...
79276. Система стратегического управления персоналом организации 23.23 KB
  Система стратегического управления персоналом организации Кадровая политика предусматривает в первую очередь формирование стратегии управления персоналом организации. Цель стратегического управления персоналом – обеспечить адекватное состоянию внешней и внутренней среды формирование человеческого капитала предприятия в расчете на долгосрочный период. Стратегическое управление персоналом направлено на решение следующих задач: 1 обеспечение организации необходимым трудовым потенциалом в соответствии со стратегией; 2 формирование внутренней...
79277. Стратегия управления персоналом организации и ее реализация 25.51 KB
  Стратегия управления персоналом организации и ее реализация Стратегическое управление – это система менеджмента ориентирующаяся на человеческий капитал как основу компании гибко реагирующая на динамику изменений внешней среды проводящая своевременные изменения в организации позволяющие добиться конкурентных преимуществ через приближение своей деятельности к запросам покупателей что обеспечивает долгосрочное устойчивое развитие и достижение поставленных целей. Стратегическое управление персоналом – это управление формированием...