Адаптивний алгоритм хаффмена з упорядкованим деревом

На відміну від раніше розглянутих методів стиснення адаптивний (динамічний) алгоритм Хаффмена більш практичний, однопрохідний, не потребуючий передачі таблиці кодів. У процесі кодування залежно від значення поточного символу, що надходять на вхід алгоритму, кодове дерево постійно змінюється – коригується відповідно до зміни статистики вхідного потоку. При декодуванні відбувається той самий процес. Для однозначності декодування використовуєтьсяупорядкована структура кодового дерева.

Упорядкованим деревом Хаффменаназиваєтьсябінарне дерево, вузли якого можуть бути перелічені у порядку неубування їх ваги зліва-направо на кожному рівні і знизу-вверх за рівнями. Якщо дерево упорядковано таким чином, то при зміні ваги існуючого вузла в дереві достатньо поміняти місцями два вузли: вузол, що порушив упорядкованість, і останній з наступних за ним вузлів меншої ваги. Після обміну вузлів місцями необхідно перерахувати вагу всіх вузлів-предків.

На початку роботи алгоритму дерево містить тільки один спеціальний символ <ESC>, що завжди має частоту 0. Він необхідний для занесення в кодове дерево нового символу, що передається безпосередньо після <ESC>. При появі нового символу праворуч від вузла <ESC> додається лист і потім, якщо необхідно, дерево упорядковується. Ліві гілки кодового дерева позначаються 0, а праві - 1.

Наведемо приклад впорядкованоготаким чином дерева Хаффмена (рис. 2.8 а). Додамо в це дерево дві букви «А», тоді вузли «A» і «D» повинні помінятися місцями (рис. 2.8 б). Якщо додати ще дві букви «А», то потрібно поміняти місцями спочатку вузол «А» та вузол-батько «D» і «В», а потім вузол «Е» і вузол-брат «Е» (рис. 2.8 в-г).

а) б)

в) г)

Рисунок 2. 8

Розглянемо приклади кодування/ декодування повідомлень за адаптивним алгоритмом Хаффмена.

28.Які лінійні блокові коди називаються кодом Хеммінга? Як знаходиться кількість інформаційних і перевірних символів для коду Хеммінга? Як утворюються кодові слова коду Хеммінга?

Найпоширенішими систематичними лінійними блоковими кодами є коди Хеммінга, до яких належать коди з мінімальною кодовою відстанню d_min=3, здатні виправляти поодинокі помилки.

Синдром, що визначає систему перевірних рівнянь коду, знаходиться із рівняння u =0.

Наприклад, для r = 3 система перевірних рівнянь буде така:

Звідси визначають перевірні розряди (контрольні суми)

Щоб закодувати повідомлення m u, значеннями розрядів u_i, де i не дорівнює степеню двійки, будуть відповідні біти повідомлення у тому самому порядку, а перевірні розряди з індексами степеня двійки знаходяться з системи перевірних рівнянь. У кожне рівняння системи входить тільки одна контрольна сума.

29.Як складається перевірна та твірна матриці коду Хеммінга?

Характерною властивістю перевірної матриці лінійного блокового коду з d_min=3 є те, що її стовпці являють собою різні ненульові комбінації завдовжки r.

Хеммінгомзапропоновано розміщувати стовпці перевірної матриці так, щоб i-й стовпець матриці, що відповідає номеру i помилкового розряду кодової комбінації,був двійковим поданням цього номера. Тоді синдром виправлення однократних помилок кодом Хеммінгає двійковим поданням номера розряду, в якому виникла помилка. Для цього перевірні розряди, що відповідають стовпцям одиничної підматриці перевірної матриці коду, повинні знаходитися не в правій частині кодового слова, а у позиціях з номерами степеня двійки, тобто 2⁰, 2¹, 2²,…, .

Наприклад, для r=3 перевірна матриця Хеммінга має вигляд

.

Перевірна матриця (k, n)- коду Хеммінга складається із r рядків і стовпців, що є двійковими комбінаціями числа i, де i - номер стовпця.

Твірна матриця коду будується таким чином, щоб стовпці з номерами нестепеня 2 відповідали інформаційним елементам повідомлення, тобто утворювали одиничну підматрицю, а стовпці з номерами степеня 2 (перевірна частина матриці) визначалися рівняннями знаходження відповідних контрольних сум.