Оптимальное кодирование

МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ

РОССИЙСКОЙ ФЕДЕРАЦИИ

ФЕДЕРАЛЬНОЕ ГОСУДАРСТВЕННОЕ БЮДЖЕТНОЕ ОБРАЗОВАТЕЛЬНОЕ УЧРЕЖДЕНИЕ ВЫСШЕГО ОБРАЗОВАНИЯ «ПОВОЛЖСКИЙ ГОСУДАРСТВЕННЫЙ ТЕХНОЛОГИЧЕСКИЙ УНИВЕРСИТЕТ»

Кафедра Пип ЭВС

ОТЧЕТ

по контрольной работе

ОПТИМАЛЬНОЕ КОДИРОВАНИЕ

по дисциплине «Основы теории информации»

Вариант 12

Выполнил: студент II курса

группы ИТС-21(зу)

Мальков Сергей Викторович

Подпись______________

Дата _________________

Проверил а:

к.т.н., доцент

Лежнина Т.А.

Подпись ______________

Дата _________________

Йошкар-Ола

1. Постановка задачи. Построить оптимальный неравномерный код вторичного алфавита для передачи сообщений, порождаемых дискретным источником, если известны вероятности появления букв первичного алфавита Р(ai) (см. таблицу с вариантами значений), по методу Шеннона-Фано и по методу Хаффмана. Оценить эффективность полученных кодов при помощи коэффициентов:

- статистического сжатия

- относительной эффективности

2. Вариант задания 12

Вероятности появления букв первичного алфавита

a1	a2	a3	a4	a5	a6	a7	a8	a9	a10	a11	a12	a13	a14	a15	a16
0,067	0,091	0,031	0,042	0,044	0,021	0,092	0,038	0,094	0,007	0,023	0,053	0,062	0,032	0,062	0,241

3. Результаты построения кода по методике Шеннона-Фано в виде таблицы.

Буква	P	Коды	Длина кода L	L*p	log(p)	log*p
a16	0,241						0,241	-2,05289	-0,49475
а9	0,094						0,282	-3,4112	-0,32065
а7	0,092						0,276	-3,44222	-0,31668
а2	0,091						0,273	-3,45799	-0,31468
а1	0,067						0,335	-3,8997	-0,26128
а13	0,062						0,31	-4,01159	-0,24872
а15	0,062						0,31	-4,01159	-0,24872
а12	0,053						0,265	-4,23786	-0,22461
а5	0,044						0,22	-4,50635	-0,19828
а4	0,042						0,21	-4,57347	-0,19209
а8	0,038						0,19	-4,71786	-0,17928
а14	0,032						0,192	-4,96578	-0,15891
а3	0,031						0,186	-5,01159	-0,15536
а11	0,023						0,161	-5,44222	-0,12517
а6	0,021						0,147	-5,57347	-0,11704
а10	0,007						0,049	-7,15843	-0,05011
							Lср.=	3,647		3,606316

Hmax = Log216 =

Kcc = Hmax/Lcp =

1,096791884

Kоэ = H/Lср =

0,988844464

4. Результаты построения кода по методике Хаффмана в виде таблицы.

Буква	P	Коды	P	Коды	P	Коды	P	Коды	P	Коды	P	Коды	P	Коды	P	Коды	P	Коды
a16	0,241		0,241		0,241		0,241		0,241		0,241		0,241		0,241		0,241
а9	0,094		0,094		0,094		0,094		0,094		0,095		0,115		0,125		0,147
а7	0,092		0,092		0,092		0,092		0,092		0,094		0,095		0,115		0,125
а2	0,091		0,091		0,091		0,091		0,091		0,092		0,094		0,095		0,115
а1	0,067		0,067		0,067		0,067		0,08		0,091		0,092		0,094		0,095
а13	0,062		0,062		0,062		0,063		0,067		0,08		0,091		0,092		0,094
а15	0,062		0,062		0,062		0,062		0,063		0,067		0,08		0,091		0,092
а12	0,053		0,053		0,053		0,062		0,062		0,063		0,067		0,08		0,091
а5	0,044		0,044		0,051		0,053		0,062		0,062		0,063		0,067
а4	0,042		0,042		0,044		0,051		0,053		0,062		0,062
а8	0,038		0,038		0,042		0,044		0,051		0,053
а14	0,032		0,032		0,038		0,042		0,044
а3	0,031		0,031		0,032		0,038
а11	0,023		0,028		0,031
а6	0,021		0,023
а10	0,007

P	Коды	P	Коды	P	Коды	P	Коды	P	Коды	P	Коды	P	Коды	Длина кода L	L*p		log(p)	log*p
0,241		0,241		0,241		0,33		0,429		0,571					0,482		-2,05289	-0,49475
0,183		0,189		0,24		0,241		0,33		0,429					0,282		-3,4112	-0,32065
0,147		0,183		0,189		0,24		0,241							0,368		-3,44222	-0,31668
0,125		0,147		0,183		0,189									0,364		-3,45799	-0,31468
0,115		0,125		0,147											0,268		-3,8997	-0,26128
0,095		0,115													0,248		-4,01159	-0,24872
0,094															0,248		-4,01159	-0,24872
															0,212		-4,23786	-0,22461
															0,176		-4,50635	-0,19828
															0,21		-4,57347	-0,19209
															0,19		-4,71786	-0,17928
															0,16		-4,96578	-0,15891
															0,155		-5,01159	-0,15536
															0,115		-5,44222	-0,12517
															0,147		-5,57347	-0,11704
															0,049		-7,15843	-0,05011
														L_ср=	3,674	бит	H=	3,60632