Ефективне кодування
Як відомо, більшість повідомлень, що формуються джерелом, містять надмірність. Видалення або зменшення надмірності є одним із завдань кодування.
Кодування, яке здійснює видалення чи зменшення надмірності із закодованих повідомлень, називається ефективним.
Можливість ефективного кодування заснована на теоремі Шеннона, згідно з якою:
Мінімальна середня кількість елементів на виході кодуючого пристрою, що відповідає одному символу дискретного повідомлення, можна зробити як завгодно близьким до максимальної ентропії джерела.
Ефективне кодування здійснюється із застосуванням нерівномірних кодів, у яких більш короткі кодові комбінації відповідають вірогіднішим символам повідомлення, а довші — менш ймовірним символам.
Основними вимогами до ефективного коду є:
- однозначність декодування, т. е. кожному символу повідомлення, що кодується, повинна відповідати своя кодова комбінація і для всіх символів комбінації повинні бути різні;
- в середньому на один символ повідомлення має бути мінімальна кількість елементів кодової комбінації ефективного коду;
- жодна більш коротка комбінація ефективного коду не повинна бути початком іншої, довшої комбінації.
Розглянемо побудову ефективного коду з прикладу коду Шеннона-Фано і коду Хаффмена.
Приклад 1. Джерело виробляє вісім повідомлень з ймовірностями Р(а1) = Р(а4) =0,25; Р(а5) = Р(а7) = 0,125; Р(а2) = Р(а3) = Р(а6) = Р(а8) = 0,0625. Здійснити ефективне кодування кодом Шеннона-Фано.
Для побудови коду потрібно скласти таблицю 1.
Заповнення таблиці здійснюється у три етапи.
1 етап.Записуються повідомлення ai у порядку зменшення їх ймовірностей (більш ймовірні вгорі, менш ймовірні внизу).
2 етап. Всі повідомлення поділяються на дві групи, таким чином, щоб у кожній групі сумарні ймовірності були приблизно рівними. Верхній групі надається нуль нижньої одиниці. Потім кожна група розбивається на дві підгрупи, також, наскільки можна, з рівними сумарними ймовірностями. Верхній підгрупі присвоюється нуль, нижній одиниця, і т. д. Розподіл підгруп проводиться до тих пір, поки в кожній підгрупі не виявиться по одному елементу ai.
3 етап. Записуються кодові комбінації, що відповідають кожному елементу повідомлення, при цьому 1-а група відповідає старшому розряду, 2-а наступному і т. д. по всіх стовпцях. Якщо в стовпці елемента ai немає символу «0» або «1», то у відповідному розряді кодової комбінації він не пишеться.
Як видно з таблиці, кожному елементу ai відповідає своя кодова комбінація, що ніде не повторюється. Жодна коротша кодова комбінація не є початком іншої довшою. При цьому вірогідніші символи повідомлення мають більш короткі комбінації, а менш ймовірні — довші.
Визначимо, чи видалено надмірність в результаті кодування.
Ентропія, що припадає на один символ повідомлення, визначається як
Максимальна ентропія джерела формує вісім повідомлень дорівнює
Надмірність повідомлення джерела, що виробляється, дорівнює
cс = (Нmax(A) – Н(А))/Нmax(А) = (3 – 2,75)/3 = 0,09
Для визначення надмірності повідомлення після кодування визначимо середню довжину кодової комбінації
Ентропія, що припадає на один розряд кодової комбінації, визначається як
Нр(А) = Н(А)/nср = 2,75/2,75 = 1 біт/розряд
Максимальна ентропія навиході двійкового дискретного джерела дорівнює
Нmax(А) = log22 = 1 біт/повідом.
Визначимо коефіцієнт надмірності джерела.
Таким чином, надмірність видалена.
Приклад 2. За наведеними у прикладі 1 даними необхідно здійснити ефективне кодування кодом Хаффмена.
Побудова цього коду також зручно оформити у вигляді таблиці 2.
Таблиця заповнюється в такий спосіб.
1 етап. Записуються повідомлення ai у порядку зменшення їх ймовірностей (більш ймовірні вгорі, менш ймовірні внизу).
2 етап. Будується дерево коду, для цього два повідомлення з найменшою ймовірністю (знизу таблиці) поєднуються в групу. Верхній гілки присвоюється одиниця, нижній? нуль. Якщо чотири символи мають однакову мінімальну ймовірність, організуються дві однакові групи. Потім формується наступна група: нижня гілка графа виходить із попередньої групи, а верхня? з наступного елемента, розташованого на одну позицію вище (цей елемент може мати більшу ймовірність, або таку ж, як і в попередній групі). Верхній гілки присвоюється одиниця, нижній? нуль. Така організація груп триває до того часу, доки утворюється остання група з елементом які мають найбільшу ймовірність ( у верхівці таблиці).
3 етап. Формуються кодові комбінації, при цьому записують значення гілок графа справа наліво.