Фетюхина Л.В.
ЛАБОРАТОРНАЯ РАБОТА 2 «Оптимальное кодирование»
Цель работы: ознакомление с методикой оптимального кодирования Шеннона - Фано и Хаффмана
Методика выполнения задания :
1.Выбор варианта.
j1 =ДАТА рождения – соответствует среднему времени выработки символа на выходе источника в мс;
j2= Порядковый номер по списку - соответствует из вариантов задания. Исходными являются символы первичного алфавита xi и их вероятности pi .
Необходимо произвести кодирование и рассчитать коэффициенты экономичности кода, скорость передачи. Сделать сравнительный анализ двух методов кодирования. Полученные результаты свести в таблицу.
Произвести процедуру блочного кодирования методом Шеннона-Фано для двух и трех символьных блоков.
Внимание! Все расчеты выполняются на компьютере.
2. Пример расчета
Используемые расчетные формулы:
Средняя число двоичных символов на букву (длина кода):
;
Энтропия первичного кода:
;
Вероятности появления единиц и нулей в коде:
; ;
Энтропия вторичного кода
;
Коэффициент статического сжатия и относительной эффективности первичного кода:
; ;
Коэффициент статического сжатия и относительной эффективности вторичного кода:
; ;
Избыточность
Кодирование по методу Шеннона-Фано
xi |
pi |
|
Код |
|
x1 |
0,26 |
0,505288 |
11 |
2,948 |
x2 |
0,14 |
0,39711 |
101 |
|
x3 |
0,13 |
0,382644 |
100 |
|
x4 |
0,13 |
0,382644 |
011 |
|
x5 |
0,11 |
0,350287 |
010 |
|
x6 |
0,09 |
0,312654 |
001 |
|
x7 |
0,07 |
0,268555 |
0001 |
|
x8 |
0,05 |
0,216096 |
00001 |
|
x9 |
0,01 |
0,066439 |
000001 |
|
x10 |
0,01 |
0,066439 |
000000 |
Кодирование по методу Хаффмана
xi |
pi |
|
Код |
||||||||
x1 |
0,26 |
0,26 |
0,26 |
0,26 |
0,26 |
0,26 |
0,28 |
0,46 |
0,54 |
1 |
10 |
x2 |
0,14 |
0,14 |
0,14 |
0,14 |
0,2 |
0,26 |
0,26 |
0,28 |
0,46 |
|
111 |
x3 |
0,13 |
0,13 |
0,13 |
0,14 |
0,14 |
0,2 |
0,26 |
0,26 |
|
|
011 |
x4 |
0,13 |
0,13 |
0,13 |
0,13 |
0,14 |
0,14 |
0,2 |
|
|
|
010 |
x5 |
0,11 |
0,11 |
0,11 |
0,13 |
0,13 |
0,14 |
|
|
|
|
001 |
x6 |
0,09 |
0,09 |
0,09 |
0,11 |
0,13 |
|
|
|
|
|
000 |
x7 |
0,07 |
0,07 |
0,07 |
0,09 |
|
|
|
|
|
|
1101 |
x8 |
0,05 |
0,05 |
0,07 |
|
|
|
|
|
|
|
11001 |
x9 |
0,01 |
0,02 |
|
|
|
|
|
|
|
|
110001 |
x10 |
0,01 |
|
|
|
|
|
|
|
|
|
110000 |