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

 

Приклад 1  Обчислити середні довжини кодів за алгоритмами Шеннона-Фано, Хаффмена, арифметичним для дискретної випадкової величини Х, заданої таким розподілом ймовірностей:

X             1              2              5              6              7              .

P             0,2           0,1           0,3           0,25         0,15        

Розв'язання

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

Побудуємо таблицю кодів для дискретної випадкової величини (д. в. в.) X за алгоритмом Шеннона-Фано (табл. 1)

Таблиця 1

Значення

xi             Імовірність

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

коду li     pili

5              0,3           00            2              0,6

6              0,25         01            2              0,5

1              0,2           10            2              0,4

7              0,15         110          3              0,45

2              0,1           111          3              0,3

lipi= 2,25

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

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

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

 

Таблиця 2

Значення

xi             Імовірність

P(xi)        Код

Code(xi)  Довжина

коду li     pili

5              0,3           00            2              0,6

6              0,25         01            2              0,5

1              0,2           11            2              0,4

7              0,15         100          3              0,45

2              0,1           101          3              0,3

                lipi=2,25

 

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

Арифметичний метод

                Побудуємо таблицю інтервалів і кодів для даної д. в. в. X (табл. 3):

Таблиця 3

Значе-

ння xi      Імовір-

ність pi   Інтервал Число

інтервалу               Код         Довжи-на коду li   lipi

1              0,2           [0,8; 1)    7/8[0,8;1)             111          3              0,6

2              0,1           [0,7; 0,8) 3/4[0,7;0,8)          11            2              0,2

5              0,3           [0,4; 0,7) 1/2[0,4;0,7)          1              1              0,3

6              0,25         [0,15; 0,4)               1/4[0,15;0,4)        01            2              0,5

7              0,15         [0; 0,15)  1/8[0;0,15)           001          3              0,45

                lipi=2,05

 

                Обчислимо середню довжину арифметичного коду

                                (біт/сим).

Приклад 2  Закодувати за арифметичним алгоритмом  повідомлення BAABCB, отримане від дискретної випадкової величини X, заданої таким розподілом ймовірностей: P(X=A)=1/3; P(X=B)=7/15; P(X=C)=1/5.

Розв'язання

                Побудуємо таблицю символів і відповідних їм інтервалів:

 

Символ  Імовірність            Інтервал

A             1/3           [2/3; 1)

B             7/15         [1/5; 2/3)

C             1/5           [0; 1/5)

 

                Ця таблиця зберігається разом із кодом стисненого повідомлення і призначена для кодування й декодування за арифметичним алгоритмом.

                Процес кодування повідомлення BAABCB зручно подати у вигляді такої таблиці:

Повідомлення       Інтервал Ширина інтервалу

               

1

B            

 

 

A            

 

 

A            

 

 

B            

 

 

C            

 

 

B            

 

 

               

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

                Таке число   .

                Двійкове подання чисельника буде арифметичним кодом повідомлення. Розрядність коду визначається степенем 2.

                Отже, знайдемо двійковий 9-розрядний код числа 321: 32110=1010000012. Таким чином, арифметичний код заданого повідомлення 

                Code(BAABCB)=101000001.

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

Приклад 3  Декодувати повідомлення довжиною 5 символів за арифметичним алгоритмом. Код повідомлення 010001011.

                Таблиця символів і відповідних їм інтервалів така:

Символ  Імовірність            Інтервал

C             1/4           [3/4; 1)

B             1/2           [1/4; 3/4)

A             1/4           [0; 1/4)

Розв'язання

                Заданий арифметичний код повідомлення 010001011 – це 9-розрядна двійкова комбінація, що визначає число, яке належить відрізку закодованого повідомлення.

                Знайдемо це число:  0100010112 = 13910.

                Число  є поточним кодом повідомлення. Воно належить інтервалу, який визначає перший символ повідомлення 0,272  [1/4; 3/4) - це інтервал символу «В».

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

Процес розкодування повідомлення такий:

 

Поточний код повідомлення               Символ  Інтервал Ширина інтервалу

0,272       B             [1/4; 3/4) 1/2

=0,043

A             [0; 1/4)    1/4

=0,172

A             [0; 1/4)    1/4

=0,688

B             [1/4; 3/4) 1/2

=0,876

C             [3/4; 1)    1/4

               

                Розкодування повідомлення потрібно закінчити після отримання 5-го символу.

                Таким чином, закодовано повідомлення BAABC.