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

14 чел.

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


 

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

30963. Государственные и муниципальные унитарные предприятия 234 KB
  Руководство унитарным предприятием (его администрация) наделено необходимыми полномочиями по организации его работы, обеспечению трудовой и государственной дисциплины. Оно реализует от имени предприятия, действующего в качестве юридического лица, его гражданскую и административную правосубъектность.
30964. Гражданское право. Понятие и предмет гражданского права 692.5 KB
  Гражданское право – это отрасль частного права регулирующая имущественные и связанные с ними личные неимущественные отношения основанные на равенстве автономии воли и имущественной самостоятельности их участников. Гражданское право представляет собой базовую отрасль частного права основанную на принципах частного права некоторые из которых сложились еще во времена римского частного права. Среди них: равенство участников правоотношений неприкосновенность права собственности свобода договора автономия воли участников ...
30965. Бизнес план ИП «Восточные Сладости» 261 KB
  Обычно анализируются оба показателя, характеризующие успешность экономической деятельности предприятия, так как по отдельности они не могут дать полной и всеобъемлющей оценки деятельности предприятия. Например, на предприятии может быть такая ситуация, когда достигнут значительный экономический эффект
30966. Внедрение нового продукта на рынок периодических изданий города Екатеринбурга 753.5 KB
  В 1й главе рассмотрены методические рекомендации по разработке бизнесплана проекта. В 3й главе представлен сам бизнесплан внедрения нового продукта на рынок периодических изданий г. СОДЕРЖАНИЕ ВВЕДЕНИЕ 6 1 Теоретические основы процесса бизнеспланирования 9 1.1 Бизнесплан.
30967. УПРАВЛЕНИЯ ЧЕЛОВЕЧЕСКИМИ РЕСУРСАМИ ОАО «СО–ЦДУ ЕЭС» 168.5 KB
  2 Проблемы обеспечения надежности профессиональной деятельности и сохранения здоровья персонала 8 2.3 Обеспечение полной профессиональной адаптации – ведущая проблема надёжности деятельности и сохранения здоровья персонала 9 2.4 Психофизиологическое сопровождение подготовки и переподготовки персонала 9 2.5 Аттестация персонала 9 2.
30969. Закрытое акционерное общество «ПОЛИСОРБ» г.Челябинск 645 KB
  Создаваемое Предприятие должно обеспечить выпуск нового лекарственного препарата – сорбента широкого спектра действия для удовлетворения потребностей всех групп населения в эффективной профилактике и лечении отравлений, аллергии, кишечных инфекций, кожных заболеваний, дисбактериоза, интоксикации различного происхождения
30970. ЗАО «Консорциум – Транспортно-модульные системы» 809 KB
  Рисунок 1 Комплекс по переработке бобов сои 8 Рисунок 2 Производство текстурированного соевого белка 26 Рисунок 3 График окупаемости NPV 73 Рисунок 4 Анализ чувствительности проекта 75 Перечень информационных и расчетных таблиц Таблица 1 Уровень среднедушевого потребления основных продуктов питания в России 16 Таблица 2 Динамика среднедушевого потребления белков за счет основных продуктов питания в РФ 17 Таблица 3 Выход основных продуктов переработки сырых соевых бобов 23 Таблица 4 Состав соевой муки 23 Таблица 5 Содержание в...
30971. Бизнес-план “Internet-провайдера ООО “Lucky Net” 493 KB
  Эти условия определяются положительным ответом на два вопроса: Что я получу от успешной реализации бизнесплана и Какова опасность риска потери вложенных в дело денег Резюме Фирма Lucky Net создаваемая в виде общества с ограниченной ответственностью планирует работать в сфере Internetпровайдинговых услуг которые будут заключаться в предоставлении неограниченного 24 часа в сутки доступа в Internet по телефонным линиям частным лицам Чернигова. Размер этой суммы планируется в будущем снижать чтобы сделать Internet еще более...