Побудувати код Хафмена

Для ансамблю символів джерела (таблиця 1.1). Побудувати код Хафмена а) m=2, б) m=3, визначення надмірності коду:

код інформаційний ентропія шенон.

Таблиця 1.1 — Статистична схема джерела

а) Формування додаткових допоміжних букв для випадку m=2 не потрібне, адже умова кодування 2 n₀2 є однозначна для визначення n₀

Отже за n₀=2 код можна формується так (результат наведено в таблиці 3.2):

0,61___1.

0,39 0,39 ___0.

а1= 0,37 0,37 0,37 0,37 0,37 0,37 ___1.

а2= 0,24 0,24 0,24 0,24 0,24 0,24 ___0.

0,21 ___1.

а4= 0,18 0,18 0,18 0,18 0,18 ___0.

0,13 ___1.

а5= 0,08 0,08 0,08 0,08 ___0.

0,08 ___1.

а3= 0,05 0,05 0,05 ___0.

а7= 0,04 0,04 ___1.

0,04 ___0.

а6= 0,03 ____1.

а8= 0,01 ____0.

Таблиця 3.2 — Код Хафмена для джерела m=2

Розрахунки аналогічні попередній задачі.

H_max= log2=1.

p (0)==.

p (0)= 1- p (1)=1- =.

H.

Знаходимо абсолютну та відносну надмірність:

%.

б) Формування додаткових допоміжних букв для випадку m=3 потрібне, умова кодування 2 n₀3, = j, jціле число, Mчисло символів повідомлення.

Отже, n₀=2, тоді умова (8−2)/(3−1)=6/2=3 виконується.

0,39___2.

а1= 0,37 0,37 0,37 0,37___1.

а2= 0,24 0,24 0,24 0,24 ___0.

а4= 0,18 0,18 0,18 ___2.

0,13 ___1.

а5= 0,08 0,08 0,08 ___0.

а3= 0,05 0,05 ___2.

а7= 0,04 0,04 ___1.

0,04 ___0.

а6= 0,03 ____1.

а8= 0,01 ____0.

Таблиця 3.3 — Код Хафмена для джерела m=3

H_max= log3=1,585.

p (2)==.

p (1)==.

p (0)= 1- =.

H.

Знаходимо абсолютну та відносну надмірність:

%.

Висновок

Кодуючи ансамбль символів джерела кодом Хаффмана, для значень алфавіту m=2 (таблиця 3.2), та m=3 (таблиця 3.3) знайшли надмірність коду, що складає:

Для m=2: D=2,764%.

Для m=3: D=2,069%.

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