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


 

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

50337. Оценка финансового состояния войсковой части 3009 325.5 KB
  Определить суть анализа финансового состояния бюджетной организации, его задачи и методы; выявить основные направления финансовой деятельности организации; рассмотреть методику оценки финансовой деятельности организации и дать характеристику ее основным показателям; рассмотреть организационно-экономическую характеристику объекта исследования; провести анализ финансовой деятельности организации...
50340. Использование библиотеки элементов графического интерфейса Qt 111.5 KB
  План простейшее графическое приложение на Qt работа с компоновщиками создание приложения ColorViewer использование QFileDilog создание простейшего обозревателя текста Инструкция по выполнению лабораторной работы Простейшее GUIприложение на Qt Рассмотрим следующий фрагмент кода представляющий простейшее GUIприложение созданное с использованием элементов Qt. QWidget базовый класс для всех элементов графического интерфейса виджетов в Qt начиная с кнопок и кончая сложными диалогами. Попробуйте добавить в корневой...
50341. Постройка графа состояний P-схемы 166 KB
  Для СМО из задания 1 построить имитационную модель и исследовать ее (разработать алгоритм и написать имитирующую программу, предусматривающую сбор и статистическую обработку данных для получения оценок заданных характеристик СМО). Распределение интервалов времени между заявками во входном потоке и интервалов времени обслуживания – геометрическое с соответствующим параметром (ρ, π1, π2).
50342. Построение аналитической и имитационной моделей системы массового обслуживания 80 KB
  Если в свободную систему поступает заявка, то ее обслуживают совместно все каналы. Если во время обслуживания заявки поступает еще одна, то часть каналов переключается на ее обслуживание и т.д., пока все каналы не окажутся занятыми. Интенсивность совместного обслуживания заявки n каналами n . Каналы распределяются равномерно между заявками.
50343. Построение аналитической и имитационной моделей системы массового обслуживания 158.5 KB
  Значения A, Q зависят от числа пришедших заявок (величины модельного времени), а также от R0, при генерации случайных чисел, распределенных по экспоненциальному закону.
50344. Снятие кривой намагничивания ферромагнитного образца 68 KB
  Расчетные формулы: Индукция намагничивающего поля: где N1 число витков намагничивающей обмотки тороида; D длина осевой линии тороида. Магнитная индукция в образце: или B=cn где постоянная где R2 сопротивление вторичной цепи; kбаллистическая постоянная; S2 площадь поперечного сечения образца; nотброс.Результаты наблюдений: Снятие основной кривой намагничивания Намагни чивающий ток I1 мА Индукция B0 намагничивающего поля Тл Отброс 1 вправо дел. Индукция В...