Лабораторна робота №11-12

Тема: Методи кодування інформації Шеннона-Фано і Хаффмена

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

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

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

Повідомлення розбиваються на дві по можливості рівноймовірні підгрупи. Всім повідомленням першої підгрупи присвоюють 1 в якості кодового символу, а всім повідомленням другої підгрупи – 0. Аналогічне ділення на підгрупи робиться до тих пір, доки в кожну підгрупу не попаде одне повідомлення. Знайдений код по Шеннону-Фано дуже близький до оптимального.

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

Для того, щоб отримати код Хаффмана, дві найменші ймовірності об’єднуються дужкою і одній з них присвоюється символ 1, іншій – 0. Потім ці ймовірності додаються, результат записується в проміжку між найближчими йому ймовірностями. Процес об’єднання повідомлень для найменших ймовірностей продовжується до тих пір, поки сумарна ймовірність повідмлення не стане рівною 1. Код для кожного повідомлення будується при записі двійкового числа справа-наліво шляхом обходу по лініях вверх-направо, починаючи з ймовірності повідомлення, для якого будується код.

            Жоден з отриманих кодів не співпав з початком довшого коду. Тобто знайдені коди є префіксними.

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

Приклад_1. Задано 8 повідомлень та ймовірності їх появи. Побудувати код Шеннона-Фано та код Хаффмана. Виконати порівняння характеристик щодо ефективності кодування.

, , , , , ,

, .

Розв'язання

Код Шеннона-Фано:

Для побудови коду Шеннона-Фано всі повідомлення  записуються в порядку спадання їх ймовірностей.

 

Поділ

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

на підгрупи

Код

0.27

1

1

 

 

11

2

0.54

0.23

1

0

 

 

10

2

0.46

0.14

0

1

1

 

011

3

0.42

0.12

0

1

0

 

010

3

0.36

0.07

0

0

1

1

0011

4

0.28

0.06

0

0

1

0

0010

4

0.24

0.06

0

0

0

1

0001

4

0.24

0.05

0

0

0

0

0000

4

0.20

 

 

 

Код Хаффмена

 

Об’єднання повідомлень

Код

0.27

 

 

0.27

 

 

0.27

 

 

0.27

 

 

0.27

 

 

0.46

 

 

0.54

1

 

1

10

 

 

 

 

 

 

0.23

 

 

0.23

 

 

0.23

 

 

0.23

 

 

0.27

 

 

0.27

1

 

0.46

0

 

 

00

 

 

 

 

 

0.14

 

 

0.14

 

 

0.14

 

 

0.23

 

 

0.23

1

 

0.27

0

 

 

 

 

 

111

 

 

 

 

 

0.12

 

 

0.12

 

 

0.13

 

 

0.14

1

 

0.23

0

 

 

 

 

 

 

 

 

011

 

 

 

 

 

0.07

 

 

0.11

 

 

0.12

1

 

0.13

0

 

 

 

 

 

 

 

 

 

 

 

1101

 

 

 

 

 

0.06

 

 

0.07

1

 

0.11

0

 

 

 

 

 

 

 

 

 

 

 

 

 

 

1100

 

 

 

0.06

1

 

0.06

0

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

0101

 

 

 

0.05

0

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

0100

 

 

 

Приклад_2. Задано ймовірності появи символів:

А

Б

В

Г

Д

Е

Ж

З

0,6

0,2

0,1

0,04

0,025

0,015

0,01

0,01

 

Ентропія джерела при цьому буде менше: Н(Х)»1,781 (біт/сим).

Середнє число символів на одне повідомлення при використовуванні рівномірного трирозрядного коду  (біт/сим).

Надлишковість коду , тобто має досить велику величину (в середньому 3 символи з 10 не несуть ніякої інформації).

 

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

Завдання 1

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

Завдання 2

Побудувати код Шеннона-Фано для ансамблю повідомлень, заданого розподілом ймовірностей: 0,25; 0,25; 0,125; 0,125; 0,0625; 0,0625; 0,0625; 0,0625. Визначити середню довжину та ефективність коду.

Завдання 3

Сім рівноімовірних повідомлень кодуються кодом Шеннона-Фано. Визначити надлишковість коду.

Завдання 4

Побудувати коди Шеннона-Фано і Хаффмена для  повідомлень джерела, заданого таким розподілом: P(x1)=0,3; P(x2)=0,2; P(x3)=0,15; P(x4)=0,12; P(x5)=0,1; P(x6)=0,08; P(x7)=0,03; P(x8)=0,02. Обчислити середню довжину і надлишковість отриманих кодів. 

Завдання 5

Побудувати коди Шеннона-Фано і Хаффмена для дискретної випадкової величини (д. в. в.) Х, заданої розподілом ймовірностей: 

X

1

2

3

4

5

P

7/18

1/6

1/6

1/6

1/9

Обчислити середню довжину отриманих кодів та ентропію д. в. в. X.

Завдання 6

Побудувати коди Хаффмена і обчислити середню довжину кодів для ансамблів повідомлень, заданих такими розподілами ймовірностей:

а) 0,16; 0,2; 0,14; 0,4; 0,02; 0,03; 0,05; б) 0,16; 0,11; 0,04; 0,12; 0,07; 0,07; 0,09; 0,03; 0,1; 0,02; 0,02; 0,01; 0,06; 0,04; 0,01; 0,05; в) 0,15; 0,35; 0,2; 0,03; 0,02; 0,05; 0,1; 0,04; 0,06; г) 0,07; 0,1; 0,03; 0,05; 0,05; 0,16; 0,08; 0,14; 0,1; 0,1; 0,04; 0,01; 0,03; 0,02; 0,02.

Завдання 7

Побудувати коди Шеннона-Фано і Хаффмена, обчислити їх середню довжину для ансамблів повідомлень, заданих такими розподілами ймовірностей: а) 0,06; 0,25; 0,1; 0,05; 0,2; 0,04; 0,3; б) 0,5; 0,3; 0,1; 0,025; 0,025; 0,02; 0,015; 0,015;  в) 0,15; 0,1; 0,05; 0,25; 0,02; 0,03; 0,4.

 

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