Зразки розв'язування задач до розділу 3

 

Приклад 1  Для ансамблю повідомлень, заданого таким розподілом ймовірностей: 0,18; 0,17; 0,16; 0,15; 0,1; 0,08; 0,05; 0,05; 0,04; 0,02, побудувати двійкові коди Шеннона-Фано і Хаффмена. Визначити основні характеристики кодів.

Розв'язання

                Верхня границя компактності кодування повідомлень дискретної випадкової величини (д. в. в.) визначається її ентропією

(біт/сим).

                Обчислимо середню довжину оптимальних кодів Шеннона-Фано і Хаффмена для кодування даної д. в. в.

 

I              Метод Шеннона-Фано:

Побудуємо таблицю кодів Шеннона-Фано (табл. 1):

                Таблиця 1

Імовірність

 pi            Код Code(xi)          Довжина

коду li     pili

0,18         00            2              0,36

0,17         010          3              0,51

0,16         011          3              0,48

0,15         100          3              0,45

0,1           101          3              0,3

0,08         1100        4              0,32

0,05         1101        4              0,2

0,05         1110        4              0,2

0,04         11110      5              0,2

0,02         11111      5              0,1

 pili = 3,12

 

                Середня довжина даного коду: (біт/сим).

                Отже, ефективність коду,

                надлишковість коду.

 

                II             Метод Хаффмена:

Побудуємо кодове дерево за алгоритмом Хаффмена, використовуючи ймовірності заданої д. в. в. (рис.1), і  відповідно до кодового дерева побудуємо таблицю кодів (табл. 2):

 

 

 

 

                Таблиця 2

Імовірність pi        Код Code(xi)          Довжина коду li    pili

0,18         11            2              0,36

0,17         000          3              0,51

0,16         001          3              0,48

0,15         010          3              0,45

0,1           100          3              0,3

0,08         0110        4              0,32

0,05         1010        4              0,2

0,05         1011        4              0,2

0,04         01110      5              0,2

0,02         01111      5              0,1

 pili  = 3,12

                Середня довжина коду   (біт/сим).

                Отже, ефективність коду =0,98, надлишковість к0,02.

Для порівняння: при кодуванні даної д. в. в. рівномірним двійковим кодом середня довжина коду  (біт/сим), ефективність коду , надлишковість к=1-  0,23 .