Тема 8. Оптимальні методи кодування

План

1.    Код Шеннона-Фано

2.    Код Хаффмена

 

 

Оптимальним кодуванням називають процедуру перетворення символів первинного алфавіту А на кодові комбінації вторинного алфавіту В, при якій середня довжина повідомлення у вторинному алфавіті мінімальна.

Знайти код, який був би оптимальним з усіх точок зору, практично неможливо. Тому код може бути оптимальним тільки за певних умов (з точки зору швидкості передачі інформації, здатності виправляти помилки тощо). Існує кілька методик побудови оптимальних кодів з точки зору швидкості передачі інформації. До цих кодів належать оптимальні нерівномірні коди (ОНК), які передають повідомлення комбінаціями мінімальної середньої довжини.

 

1.    Код Шеннона-Фано

 

Алгоритм побудови ОНК даного методу має такі  кроки.

1.  Множину з N  повідомлень для кодування розміщують  у порядку спадання ймовірностей.

2.  Упорядковані за ймовірностями повідомлення розбивають  по можливості  на q рівноймовірних груп.

3.  Кожній  із груп завжди в одній і тій самій послідовності приписують символи алфавіту q (всім повідомленням першої групи – першу якісну ознаку цього алфавіту, всім повідомленням другої групи – другу якісну його ознаку тощо).

4.  Створені групи розбивають  по можливості  на рівноймовірні підгрупи, кількість яких дорівнює або  менша ніж q (якщо пісня розбивання у групі залишається одне повідомлення, то подальший поділ стає неможливим).

5. Кожнiй із утворених підгруп присвоюють якісні ознаки з алфавіту q, використовуючи крок алгоритму 3.

6. Розбивання та присвоєння ознак алфавіту q повторюють до того часу, поки після чергового поділу в утворених підгрупах залишиться не більш ніж одне повідомлення.

Приклад 6.1.1.  Закодувати 16 повідомлень за допомогою четвіркового ОНК алфавітом q = 4, якщо повідомлення на виході джерела з’являються з ймовірностями P(x1) = 0,22; P(x2)= = P(x3) = 0,1; P(x4) = 0,08; P(x5) =  P(x6) = 0,07; P(x7) = P(x8) =

= 0,06; P(x9) = P(x10) = 0,05; P(x11) = 0,04; P(x12) = 0,03; P(x13) = P(x14) = P(x15) = 0,02; P(x16) = 0,01.

Розв’язання. Використовуючи дані прикладу, кроки 1 і 2 алгоритму, будуємо таблицю для знаходження кодових комбінацій ОНК, табл.6.1.1.

 

 

 

 

 

 

 

 

 

 

 

   Таблиця 8.1

 

Згідно з другим алгоритмом визначаємо квант поділу повідомлень за ймовірностями, який буде дорівнювати   ,  і розбиваємо всі повідомлення по можливості на чотири рівномірні групи:            

 ;  ;  ;   .

Користуючись третім кроком алгоритму, завжди присвоюємо кожній із груп в одній і тій самій послідовності символи алфавіту q (першому повідомленню першої групи першу якісну ознаку 0 ; всім повідомленням другої групи – другу якісну ознаку 1 ; всім повідомленням третьої групи – третю якісну ознаку 2 ; всім повідомленням четвертої групи – четверту якісну ознаку 3. Дані про якісні ознаки заносимо в табл.6.1.1 як першу  цифру стовпчика комбінацій ОНК.

Використовуючи четвертий і п’ятий кроки алгоритму, присвоюємо кожній із утворених підгруп завжди в одній і тій самій послідовності   якісні ознаки з алфавіту  q  згідно з третім  кроком  алгоритму (0,1,2 – відповідні  повідомлення  першої  і другої груп; 0,1,2,3 – відповідні повідомлення  третьої і четвертої груп). Дані якісні ознаки заносимо в табл.6.1.1  як першу,  другу  і  третю  цифри стовпчика комбінації ОНК.

Користуючись кроками 4, 6 алгоритму, останнім чотирьом повідомленням присвоюємо якісні ознаки  0,  1,  2,  3  з алфавіту  q  згідно з третім  кроком  алгоритму. Дані якісні ознаки заносимо в таблицю 6.1.1  як третю цифру стовпчика комбінації ОНК.

Для перевірки оптимальності коду щодо довжини кодових комбінацій необхідно визначити середню довжину  nсер  кодової комбінації ОНК. У разі оптимальності ця довжина не повинна перевищувати довжини рівномірного четвіркового коду, яким можна закодувати 16 повідомлень, тобто qn =  42  =  16 (n = 2).

nсе р =(0,1 + 0,1 + 0,08 + 0,07 + 0,07 + 0,06 + 0,06 + 0,05 + +0,05 + 0,04 + 0,03) 2 + (0,02 +0,02+ 0,02+ 0,02+ 0,01) 3=0,22 +1,42 +0,21=1,85 < 2.  Таким чином, отриманий  ОНК є дійсно оптимальний, оскільки nсер <  n.

 

2.    Код Хаффмена

 

Дана методика, як і методика Шеннона - Фано, передбачає побудову ОНК у кодовому алфавіті з кількістю якісних значень  q. Згідно з цією методикою алгоритм побудови ОНК має такі кроки.

1.  Множину з N повідомлень, що кодують , розташовують у порядку   спадання ймовірностей.

2.  Останні  No  повідомлень  2      No      q  об’єднують у нове повідомлення з імовірністю, що дорівнює сумі ймовірності об’єднуваних повідомлень.

3.  Утворену множину (N - No +1) повідомлень розташовують у порядку спадання ймовірностей.

4.  Об’єднують останні  q  повідомлень і впорядковують множину повідомлень у порядку  спадання ймовірностей. Так діють до того часу, поки ймовірність чергового об’єднаного повідомлення не дорівнюватиме одиниці.

5.  Будують кодове дерево, починаючи з кореня, і гілкам цього дерева присвоюють якісні ознаки кодового алфавіту  q. Кодові комбінації ОНК – це послідовність якісних ознак, які зустрічаються на шляху від кореня до вершини кодового дерева.

Приклад 6.2.1. Закодувати 16 повідомлень комбінаціями четвіркового ОНК з ймовірностями появи посилань  коду: P(x1) = 0,22; P(x2) = P(x3) = 0,1; P(x4) = 0,08; P(x5) =  P(x6) = 0,07; P(x7) = P(x8) = 0,06; P(x9) = P(x10) = 0,05; P(x11) = 0,04; P(x12) = 0,03; P(x13) = P(x14) = P(x15) = 0,02; P(x16) = 0,01;

Розв’язання. Використовуючи дані прикладу і крок 1 алгоритму, будуємо таблицю для знаходження кодових комбінацій ОНК, табл.6.2.1.

 

       Таблиця 8.2

            Виконуючи крок  2 алгоритму, об’єднуємо останні чотири повідомлення (оскільки q = 4) й утворюємо нове умовне повідомлення. Користуючись третім кроком алгоритму, утворену множину розташовуємо в порядку спадання ймовірностей.    

Згідно з четвертим  кроком  алгоритму  знову об’єднуємо останні чотири повідомлення та впорядковуємо множину повідомлень  у порядку спадання ймовірностей. Цю процедуру повторюємо ще три рази, поки при останньому об’єднанні сумарна ймовірність не досягне значення одиниці.

     Використовуючи п’ятий крок алгоритму, будуємо кодове дерево, рис. 8.1.

 

Рисунок 8.1

 

Гілкам кадрового дерева присвоюємо якісні ознаки кодового алфавіту від 0 до 3. Кодові комбінації ОНК для кожного повідомлення заносимо до табл.6.2.1. Вони визначаються послідовністю якісних ознак, які зустрічаються на шляху від кореня до певної вершини кодового дерева.

Перевірку на оптимальність коду  щодо  довжини кодових комбінацій робимо аналогічно, як це   наведено у прикладі 6.1.1.

nсер=(0,1 + 0,1 + 0,08 + 0,07 +

+ 0,07+ 0,06 + 0,06 + 0,05 + 0,05 + 0,04 + 0,031) 2 + (0,02 +

+ 0,02 + 0,02 + 0,01)3 = 0,22 + 1,42 + 0,21 = 1,85 < 2.

    Таким чином, отриманий ОНК є дійсно оптимальним, оскільки  nсер<  n.

До недоліків алгоритму Хаффмена побудови ОНК слід віднести громіздкість (особливо зі збільшенням кількості повідомлень N та алфавіту q коду), що пояснюється необхідністю побудови кодового дерева.