Лабораторна робота №13-14

Тема: Застосування статистичних алгоритмів стиснення до блоків повідомлення

Мета: розглянути алгоритми побудови оптимальних кодів для блокового коду Хаффмена 2-го порядку

Теоретичні відомості

Теоретичні границі стиснення інформації

Стиснення даних не може бути більше деякої теоретичної границі. Сформульована раніше теорема Шеннона про кодування каналу без шуму встановлює верхню границю стиснення інформації як ентропію джерела H(X).

Позначимо через L(X) функцію, що повертає довжину коду повідомлень

L(X)=len(code(X)),

де code(X) кожному значенню X ставить у відповідність деякий бітовий код; len( ) - повертає довжину цього коду.

Оскільки L(X) - функція від д. в. в. X, тобто також є д. в. в., то її середнє значення обчислюється як математичне сподівання:

 

.                                                     (14.1)

 

Наслідком теореми Шеннона про кодування джерела у відсутності шуму є те, що середня кількість бітів коду, що припадає на одне значення д. в. в., не може бути менше її ентропії, тобто

           

                                                               (14.2)

 

для будь-якої д. в. в. X і будь-якого її коду.

Метод блокування повідомлення

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

Блоковий код розділяє вектор даних на блоки певної довжини, і потім кожний блок замінює кодовим словом з префіксної множини кодових слів. Отриману послідовність кодових слів об'єднують в остаточну двійкову послідовність на виході кодера.

Блоковий код називається блоковим кодом k-го порядку, якщо всі його блоки мають довжину k символів.

Метод блокування повідомлень полягає в такому.

За заданим e>0 можемо знайти таке k, що якщо розбити повідомлення на блоки завдовжки k (всього буде n/k блоків), то, використовуючи оптимальне статистичне кодування таких блоків, що розглядаються як одиниці повідомлень, можна досягти середньої довжини коду більше ентропії менш ніж на e.

Приклади виконання завдань

Приклад_1. Згрупувати по два і по три повідомлення в групі. Побудувати код Хаффмана. Виконати порівняльну характеристику щодо ефективності коду, швидкості передачі та похибки коду. Значення ймовірностей наступні: , .

 

Розв'язання

Код Хаффмана для двох повідомлень в групі:

Знайдемо ентропію для заданих повідомлень:

.

 

 

Код

0.64

 

 

0.64

 

 

0.64

1

 

1

1

1

 

 

 

 

0.16

 

 

0.20

1

 

0.36

0

 

 

00

2

 

 

 

 

0.16

1

 

0.16

0

 

 

 

 

 

011

3

 

 

 

0.04

0

 

 

 

 

 

 

 

 

010

3

 

 

 

Середня довжина кодового слова, яка припадає на одне повідомлення:

.

Швидкість передачі повідомлення:

 

.

 

Щоб знайти похибку коду, обчислимо ймовірність появи нулів і одиниць:

 

, .

 

Тоді ентропія коду рівна:

 

.

 

Похибка коду наступна:

 

.

 

 

 

 

 

 

 

 

 

 

 

 

 

Код Хаффмана для трьох повідомлень в групі:

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Код

0.512

 

 

0.512

 

 

0.512

 

 

0.512

 

 

0.512

 

 

0.512

 

 

0.512

1

 

1

1

1

 

 

 

 

 

 

0.128

 

 

0.128

 

 

0.128

 

 

0.128

 

 

0.232

 

 

0.256

1

 

0.488

0

 

 

110

3

 

 

 

 

 

 

 

 

 

0.128

 

 

0.128

 

 

0.128

 

 

0.128

 

 

0.128

1

 

0.232

0

 

 

 

 

 

111

3

 

 

 

0.128

 

 

0.128

 

 

0.128

 

 

0.128

1

 

0.128

0

 

 

 

 

 

 

 

 

101

3

 

 

 

0.032

 

 

0.040

 

 

0.064

1

 

0.104

0

 

 

 

 

 

 

 

 

 

 

 

10010

5

 

 

 

 

 

 

 

 

0.032

 

 

0.032

1

 

0.040

0

 

 

 

 

 

 

 

 

 

 

 

 

 

 

10011

5

 

 

 

0.032

1

 

0.032

0

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

10001

5

 

 

 

0.008

0

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

10000

5

 

 

 

 

Середня довжина кодового слова, яка припадає на одне повідомлення:

.

Швидкість передачі повідомлення:

 

.

 

Щоб знайти похибку коду, обчислимо ймовірність появи нулів і одиниць:

 

, .

 

Тоді ентропія коду рівна:

 

.

 

Похибка коду наступна:

 

.

 

Результати кодування по два і по три повідомлення в групі методом Хаффмана наведені в наступній таблиці:

 

 

 

Обчислювані величини

Число повідомлень в групі

Граничні значення обчислюваних величин

2

3

0.780

0.728

925641

991758

0.359

0.374

0.641

0.626

, %

5.8

4.6

 

Приклад_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

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

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 (біт).

Завдання на лабораторну роботу

Завдання 1

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

Завдання 2

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

Завдання 3

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

Завдання 4

Для кодування двійкового джерела з імовірністю одиниці 0,4 використовується блоковий код Хаффмена. Побудувати таблиці кодів для блокових кодів Хаффмена 2-го й 3-го порядків. Обчислити середню довжину отриманих кодів. Якою буде мінімальна середня довжина коду, необхідного для кодування цього джерела?

Завдання 5

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

Завдання 6

Закодувати повідомлення 0101110110 блоковим кодом Хаффмена 2-го порядку. Обчислити довжину коду й швидкість стиснення даних.

Завдання 7  

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

Завдання 8

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

 

Після виконання завдань оформити та здати звіт викладачу.