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 умови Сардінаса.


 

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

59266. Розцвіла верба – прийшла справжня весна 30 KB
  Ми чекаємо коли весна прижене холод устелить землю травичкою уквітчає квітами а пташки наповнять ліс веселими співами. Весела гарна кучерява маленька дівчинка Весна Біжить сміється сіє трави І пісня ллється голосна.
59267. Сценарій проведення спортивного свята 35 KB
  Дорога класна родино гості Сьогодні як і щорічно ми зібралися на наше улюблене фізкультурнохудожнє свято щоб позмагатись у силі спритності і просто відпочити. Вчитель фізкультури: Учасники змагань слухайте мою команду.
59268. A HAPPY NEW YEAR 49.5 KB
  Another popular way of celebrating the New Year is to go to a New Year’s dance. Most hotels and dance halls hold a special dance on New Year’s Eve. The hall is decorated, there are several different bands and the atmosphere is very gay.
59269. У гості до колобка 25.5 KB
  Вчити фіксувати характерні особливості персонажів: Колобок круглий він котиться Ведмедик клишоногий перевальцем ходить Лисичка руденька хитра; долати перешкоди: купи хмизу горбочки та пеньки у лісі.
59270. Ой єсть в лісі калина 33.5 KB
  З чим тебе порівняти Чи з весняним ранком чи з бездонним небом чи з веселим шумом червоної калини Гарна калина в усі пори року. Червона калина символ України. Галузочка до галузки зацвіла калина.
59271. Методрозробка практичного заняття з латинської мови 75 KB
  Навчальна мета: навчити студентів правильно читати латинські слова з вмінням вірного пояснення вимови голосних дифтонгів; правильно читати медичні терміни у склад яких входить буква –у і.
59272. Люблю рідну матусю 50 KB
  Непорочна як лілея біла Із ДитяткомНемовлятком Пречистая Діва. Друга мати це найкраща на світі країна Земля наша наша славна НенькаУкраїна. Третя мати що ж про неї гарного сказати Це ласкава люба мила рідна моя мати.
59273. Структура (Розробка) проведення уроку у добукварний період. Буква Р 27 KB
  Звуковий та звукобуквенний аналіз слів. Вдосконалювати навички звуко-буквенного аналізу слів творити різні форми слова складати речення з власними назвами моделювати ці речення.
59274. Сценарій урочистої шкільної лінійки 48.5 KB
  Що велике це свято, велике, бо ж глянь скільки народу зібралося. А радісне яке... Що й в двох словах не передаси. Як згадаю ті недоспані ночі, важкенні контрольні, незрозумілі приклади і задачі, каверзні формули і диктанти...