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


 

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

1821. Развитие исторического образования в университетах России во второй половине XVIII – начале XX века 1.33 MB
  Влияние культуры классицизма на развитие русской исторической науки и образования. Эпоха Великих реформ и формирование принципов дальнейшего развития исторического образования в российских университетах. Реорганизация учебного процесса на историко-филологических факультетах в университетах России в конце 70-80-х гг. XIX в.
1822. Дидактическое структурирование процесса обучения студентов в педагогическом вузе 1.33 MB
  Структурирование процесса обучения в вузе как педагогическая проблема. Характеристики структур педагогических систем с позиции концепции структурно-количественного анализа. Дидактические оценки использования резюме как методологического компонента структуры процесса обучения математике в вузе. Взаимосвязь структурных характеристик умственной деятельности обучаемых с показателями эффективности решения математических задач и оценками качеств личности.
1823. МИГРАЦИОННАЯ ПОЛИТИКА ЕВРОПЕЙСКОГО СОЮЗА 1.33 MB
  Интеграционные процессы в Западной Европе во второй половине ХХ столетия и создание Европейских Сообществ. Возникновение и деятельность межправительственных групп по выработке основных направлений миграционной политики ЕС. Формирование единого европейского законодательства в области регулирования миграционных процессов.
1824. ГАРНИТУРА ШРИФТА КАК ФАКТОР РЕГУЛЯЦИИ ВОСПРИЯТИЯ ТЕКСТА 1.33 MB
  Научно-теоретические и практические аспекты проблемы исследования регулирующей функции гарнитуры шрифта. Функции гарнитуры шрифта с позиций прагматики и эстетики. Регулирующая функция гарнитуры шрифта в аспекте теории деятельности. Психолингвистическая интерпретация гарнитурно-шрифтовых регулирующих факторов.
1825. КОНСТИТУЦИОННЫЕ ГАРАНТИИ ЗАЩИТЫ ПРАВ И СВОБОД ГРАЖДАН ОТ НЕПРАВОМЕРНЫХ ДЕЙСТВИЙ (БЕЗДЕЙСТВИЙ) СУБЪЕКТОВ ПРАВООХРАНИТЕЛЬНОЙ СИСТЕМЫ РОССИЙСКОЙ ФЕДЕРАЦИИ 1.33 MB
  Конституционные гарантии прав и свобод человека и гражданина в Российской Федерации. Функции юридических гарантий обеспечения прав и свобод человека и гражданина. Персональная ответственность государственного служащего правоохранительного органа. Конституционно-правовой механизм защиты прав и свобод граждан от неправомерных действий (бездействий) должностных лиц правоохранительных органов.
1826. СОВЕРШЕНСТВОВАНИЕ ИНВЕСТИЦИОННЫХ ПРОЦЕССОВ В СТРУКТУРНОЙ ЭКОНОМИКЕ 1.33 MB
  СУЩНОСТЬ МЕТОДОЛОГИЧЕСКОЙ ОЦЕНКИ ИНВЕСТИЦИОННОГО ПОТЕНЦИАЛА РЕГИОНОВ СТРАНЫ. ОЦЕНКА СФЕРЫ ПРИЛОЖЕНИЯ ИНВЕСТИЦИОННОГО КАПИТАЛА В РОССИИ. ФОРМИРОВАНИЕ КОНЦЕПЦИИ И МЕТОДОЛОГИИ ИНВЕСТИЦИОННО-ФИНАНСОВОЙ ДЕЯТЕЛЬНОСТИ. ФОРМЫ ГОСУДАРСТВЕННОГО РЕГУЛИРОВАНИЯ ИНВЕСТИЦИОННОЙ ДЕЯТЕЛЬНОСТИ НА УРОВНЕ СУБЪЕКТОВ РОССИЙСКОЙ ФЕДЕРАЦИИ.
1827. Теорія складності екстремальних задач. Задача Комівояжора. 140 KB
  Зада́ча комівояже́ра (комівояжер — бродячий торговець, англ. Travelling Salesman Problem, TSP; нім. Problem des Handlungsreisenden) полягає у знаходженні найвигіднішого маршруту, що проходить через вказані міста хоча б по одному разу. В умовах завдання вказуються критерій вигідності маршруту (найкоротший, найдешевший, сукупний критерій тощо) і відповідні матриці відстаней, вартості тощо. Зазвичай задано, що маршрут повинен проходити через кожне місто тільки один раз, в такому випадку розв'язок знаходиться серед гамільтонових циклів.
1828. МЕХАНИЗМЫ ЭМОЦИОНАЛЬНОЙ ДЕТЕРМИНИРОВАННОСТИ ВНУТРЕННЕГО ОТСЧЕТА ВРЕМЕНИ СПОРТСМЕНОВ 1.32 MB
  Влияние эмоциональных факторов на механизмы аутохронометрии. Влияние двигательной активности на хронобиологическую оценку времени (на примере различных видов спорта). Исследование функционального состояния центральной нервной системы. Сравнительная характеристика аутохронометрических способностей представителей различных видов спорта