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

 

Приклад 1  Дискретна випадкова величина (д. в. в.) X задана таким розподілом ймовірностей: P(X=A)=1/3; P(X=B)=7/15; P(X=C)=1/5. Побудувати таблицю кодів для блокового коду Хаффмена 2-го порядку. Визначити середню довжину коду.

Розв'язання

Побудуємо розподіл ймовірностей векторної д. в. в. , що являє собою блок повідомлення довжиною в два символи (табл.1).

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

Таблиця 1

 

BB          BA          AB          AA          BC          CB          AC          CA          CC

 

49/225     7/45         7/45         1/9           7/75         7/75         1/15         1/15         1/25

 

10            001          010          011          111          0000        0001        1100        1101

 

2              3              3              3              3              4              4              4              4

PiLi      98/225     7/15         7/15         1/3           7/25         28/75       4/15         4/15         4/25

 

 

Середня довжина коду для блокового коду Хаффмена 2-го порядку (біт/сим).

Для порівняння: наведемо кодове дерево (рис. 2) і відповідну таблицю кодів (табл.2) для одновимірної д. в. в.:

Таблиця 2

xi             B             A             C             

pi             7/15         1/3           1/5           1

Code(xi)  1              00            01           

li              1              2              2             

pili           7/15         2/3           2/5           23/15

 

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

Мінімальна середня довжина коду для кодування даної д. в. в. визначається її ентропією:

 

(біт/сим).

                Отже, надлишковість блокового коду , а надлишковість неблокового коду .

Для рівномірного коду надлишковість  істотно більше.

Приклад 2  Закодувати повідомлення ABAAABBA за алгоритмом Хаффмена і блоковим алгоритмом Хаффмена 2-го порядку, обчислити довжини отриманих кодів. Приблизний закон розподілу ймовірностей визначити з аналізу повідомлення.

Розв'язання

                За частотами символів у повідомленні побудуємо приблизний закон розподілу їх ймовірностей (табл. 1).

Таблиця 1

Символ xi              A             B

Імовірність pi        5/8           3/8

               

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

Таблиця 2

Символ xi              A             B

Імовірність pi        5/8           3/8

Код         0              1

Скориставшись таблицею кодів (табл. 2), закодуємо повідомлення  

Code(ABAAABBA )=01000110.

Довжина коду L(X)=8 (бітів).

Повідомлення ABAAABBA можна розбити на 4 блоки довжиною 2 символи.

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

Таблиця 3

Блок повідомлення

AВ          AA          BA

Імовірність pi        1/2           1/4           1/4

 

Побудуємо таблицю кодів за алгоритмом Хаффмена для блоків повідомлення (табл. 4).

                Таблиця 4

Блок повідомлення

AB          AA          BA

Імовірність pi        1/2           1/4           1/4

Код         0              10            11

 

                Блоковий код повідомлення

                               Code(ABAAABBA)=010011.

Довжина коду L(X)=6 (біт).