Побудувати код Хафмена
Формування додаткових допоміжних букв для випадку m=2 не потрібне, адже умова кодування 2 n02 є однозначна для визначення n0. Для ансамблю символів джерела (таблиця 1.1). Побудувати код Хафмена а) m=2, б) m=3, визначення надмірності коду: Отже за n0=2 код можна формується так (результат наведено в таблиці 3.2): Знаходимо абсолютну та відносну надмірність: Знаходимо абсолютну та відносну… Читать ещё >
Побудувати код Хафмена (реферат, курсовая, диплом, контрольная)
Для ансамблю символів джерела (таблиця 1.1). Побудувати код Хафмена а) m=2, б) m=3, визначення надмірності коду:
код інформаційний ентропія шенон.
Таблиця 1.1 — Статистична схема джерела
a1 | a2 | a3 | a4 | a5 | a6 | a7 | a8 |
0,37. | 0,24. | 0,05. | 0,18. | 0,08. | 0,03. | 0,04. | 0,01. |
а) Формування додаткових допоміжних букв для випадку m=2 не потрібне, адже умова кодування 2 n02 є однозначна для визначення n0
Отже за n0=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
a1 | a2 | a3 | a4 | a5 | a6 | a7 | a8 |
Розрахунки аналогічні попередній задачі.
Hmax= log2=1.
p (0)==.
p (0)= 1- p (1)=1- =.
H.
Знаходимо абсолютну та відносну надмірність:
%.
б) Формування додаткових допоміжних букв для випадку m=3 потрібне, умова кодування 2 n03, = j, jціле число, Mчисло символів повідомлення.
Отже, n0=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
a1 | a2 | a3 | a4 | a5 | a6 | a7 | a8 |
Hmax= 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%.
Збільшення букв алфавіту кодування призвело до зменшення надмірності коду, що свідчить про те що імовірності ближче до від'ємних ступенів трійки.