Строим кодовое дерево
Сравнительный анализ двух методов
Вычисляемая величина |
Метод кодирования |
Предельное значение |
|
Шеннона-Фано |
Хаффмана |
||
lСР |
2,97 |
2,97 |
2,948 |
|
2,948 |
2,948 |
3 |
|
0,999 |
0,999 |
1 |
KОЭ 1 |
0,9925 |
0,9925 |
1 |
KСС 1 |
1,01 |
1,01 |
– |
KОЭ 2 |
0,337 |
0,335 |
– |
KСС 2 |
0,3367 |
0,3367 |
– |
D |
0,0004 |
0,0036 |
0 |
p(0) |
0,488 |
0,465 |
0,5 |
p(1) |
0,512 |
0,535 |
0,5 |
C, бит/с |
2701620 |
2692948 |
C=1/τ |
МЕТОД ШЕННОНА-ФАНО
БЛОЧНОЕ КОДИРОВАНИЕ
Процедура выполняется при помощи программы pti-ita.
Исходные данные: символы первичного алфавита и их вероятности:
;
;
Выходные данные: кодовые комбинации одно-, двух- и трёхсимвольных блоков
Расчёт односимвольных блоков
Блок |
pi |
|
Код |
|
|
p(0) |
p(1) |
|
|
|
D |
a1 |
0,83 |
0,223118 |
1 |
1 |
0,658 |
0,17 |
0,83 |
0,658 |
1 |
0,658 |
0,342 |
a2 |
0,17 |
0,434587 |
0 |
;
;
;
;
;
;
;
;
Расчёт двухсимвольных блоков
Блок |
pi |
|
Код |
|
|
p(0) |
p(1) |
|
|
|
D |
a1a1 |
0,6889 |
0,370376 |
1 |
1,481 |
1,315 |
0,344 |
0,656 |
0,929 |
0,675 |
0,627 |
0,071 |
a1a2 |
0,1411 |
0,398637 |
0 1 |
||||||||
a2a1 |
0,1411 |
0,398637 |
0 0 1 |
||||||||
a2a2 |
0,0289 |
0,14776 |
0 0 0 |
;
Расчёт трёхсимвольных блоков
Блок |
pi |
|
Код |
|
|
p(0) |
p(1) |
|
|
|
D |
a1a1a1 |
0,571787 |
0,461118 |
1 |
2,01 |
1,973 |
0,435 |
0,565 |
0,988 |
0,497 |
0,491 |
0,012 |
a1a1a2 |
0,117113 |
0,362351 |
0 1 1 |
||||||||
a1a2a1 |
0,117113 |
0,362351 |
0 1 0 |
||||||||
a2a1a1 |
0,117113 |
0,362351 |
0 0 1 |
||||||||
a1a2a2 |
0,023987 |
0,129089 |
0 0 0 1 1 |
||||||||
a2a1a2 |
0,023987 |
0,129089 |
0 0 0 1 0 |
||||||||
a2a2a1 |
0,023987 |
0,129089 |
0 0 0 0 1 |
||||||||
a2a2a2 |
0,004913 |
0,037679 |
0 0 0 0 0 |
Повторить все действия, используя метод Хаффмана. Сравнить результаты.
ВЫВОДЫ: С ростом длины блока эффективность кодирования растет.