Фетюхина Л.В.

ЛАБОРАТОРНАЯ РАБОТА 2 «Оптимальное кодирование»

Цель работы: ознакомление с методикой оптимального кодирования Шеннона - Фано и Хаффмана

Методика выполнения задания :

1.Выбор варианта.

j₁ =ДАТА рождения – соответствует среднему времени выработки символа на выходе источника в мс;

j₂= Порядковый номер по списку - соответствует из вариантов задания. Исходными являются символы первичного алфавита x_i и их вероятности p_i .

• Необходимо произвести кодирование и рассчитать коэффициенты экономичности кода, скорость передачи. Сделать сравнительный анализ двух методов кодирования. Полученные результаты свести в таблицу.

• Произвести процедуру блочного кодирования методом Шеннона-Фано для двух и трех символьных блоков.

• Внимание! Все расчеты выполняются на компьютере.

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