Приклад оформлення титульного аркушу
НАЦІОНАЛЬНИЙ АВІАЦІЙНИЙ УНІВЕРСИТЕТ
Інститут інформаційно − діагностичних систем
Кафедра комп’ютеризованих систем захисту інформації
Індивідуальна робота
із модуля № 4 шостого семестру
З дисципліни “Теорія інформації та кодування”
Для студентів спеціальностей
напряму підготовки 6.170101 “Безпека інформаційних й комунікаційних систем”
Виконав “____”__________ 20__р. студент групи 310 Інституту інформаційно – комунікаційних систем Іваненко О.І.
Перевірив: доцент кафедри Комп’ютеризованих засобів захисту інформації Василенко Вячеслав Сергійович
2010
Приклад реалізації стиснення за алгоритмом Хаффмена
Розглянемо наступний приклад реалізації стиснення. Хай повідомлення є текстом, який складається із дванадцяти символів із ймовірностями, які визначені і відображені в таблиці 1.
Таблиця 1
Символ |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
10 |
11 |
12 |
Імовірність |
0,01 |
0,01 |
0,01 |
0,01 |
0,02 |
0,02 |
0,02 |
0,1 |
0,1 |
0,1 |
0,2 |
0,4 |
Надалі будується “дерево” коду згідно із алгоритмом Хаффмена. Як відомо, на кожному кроці алгоритму здійснюється аналіз ймовірностей усіх символів (які на цьому кроці позначені зеленими колами), починаючи із пари символів, які мають найменші імовірності. Вразі наявності декількох символів із однаковою імовірністю, вибір пари здійснюється довільно. Нехай на першому кроці, в наслідок аналізу чотирьох найменших та однакових ймовірностей, вибрано перший та другий символи. Ці символи утворюють новий вузол (узагальнений символ), імовірність появи якого дорівнює сумі ймовірностей тих символів, які його утворили (0,01+ 0,01 = 0,02). Ребрам, які поєднують ці вузли привласнюють значення “1” чи “0” (довільно, за бажанням виконавця). Звернемо увагу, що на рисунках, які демонструють алгоритм, значення ребер привласнено (для спрощення рисунків!) лише на перших двох кроках алгоритму. Після цього розглянуті вузли (на першому кроці – перший та другий) із розгляду виключаються, що на рисунках показано виділенням таких вузлів червоним кольором.
На наступному кроці відбувається такий же аналіз ймовірностей, і, в наслідок аналізу двох найменших та однакових ймовірностей (третьої та четвертої), визначається наступний новий вузол (узагальнений символ) із відповідною ймовірністю (0,01+ 0,01 = 0,02).
На третьому кроці відбувається аналіз чотирьох вузлів із найменшими ймовірностями (по 0,02) і визначається наступний новий вузол (узагальнений символ) із відповідною ймовірністю (0,02+ 0,02 = 0,4).
Цей процес продовжується до повного перебору усіх вузлів, в наслідок чого утвориться корінь дерева із імовірністю, яка дорівнює 1 (одиниці).
Здійснивши тепер перехід по ребрам із кореня дерева до того вузла, яким позначено кожен із символів, і, послідовно записавши коди відповідних ребер, отримаємо коди кожного із символів.
Із рисунків видно, що коди перших шести символів будуть шестирозрядними, розрядність решти символів буде зменшуватися, аж до одного розряду для символу із найбільшою імовірністю.