ГУАП

КАФЕДРА № 62

ОТЧЕТ

ЗАВЕРШЕН С ОЦЕНКОЙ

ПРЕПОДАВАТЕЛЬ

старший преподаватель Соколовская М.В.

должность,уч.степень,звание подпись, дата инициалы, фамилия

ОТЧЕТ О ЛАБОРАТОРНОЙ РАБОТЕ

Кодирование дискретных источников информации методом шеннона-фано

по курсу: ИНФОРМАТИКА

РАБОТУ ВЫПОЛНИЛ

СТУДЕНТ ГР. 6231К Леонова Е.В.

подпись,дата инициалы,фамилия

Санкт-Петербург, 2012

Цель работы: освоить метод построения кодов дискретного источника информации, используя конструктивный метод, предложенный К.Шенноном и Н.Фано и методику Д.Хаффмана. На примере показать однозначность раскодирования имеющегося сообщения.

При кодировании дискретных источников информации нужно уменьшить избыточность, то есть количество символов для передачи сообщения по каналу связи. Тогда информация будет передаваться быстрее. Потребуется меньше памяти для хранения этой информации.

Любое сообщения можно передать, используя ноль и единицу. Тогда кодовое слово будет состоять из последовательностей нулей и единиц.

Если алфавит A состоит из N символов, то для такого кодирования необходимо слово разрядностью n, которая определяется

n = log₂ N .

Это справедливо для стандартных кодовых таблиц.

В нашей работе было 50 символов. Это меньше, чем 256. Удобнее будет другая таблица кодирования, которая позволит сжать информацию. В ней любой символ будет кодироваться меньшим количеством нулей и единиц. При кодировании не будет передаваться избыточная информация. У более вероятных символов кодовое слово будет короче, чем у менее вероятных символов. Такое кодирование называется эффективным.

Оно создано на основной теореме Шеннона, которая гласит, что сообщения, составленные из букв некоторого алфавита, можно закодировать так, что среднее число двоичных символов на букву будет сколь угодно близко к энтропии источника этих сообщений, но не меньше этой величины.

К.Шеннон и Н.Фано показали, как это можно сделать на практике и то, что получилось, назвали кодом Шеннона-Фано.

Символы	Вероятности P(a)	Кодовые комбинации	1 ступень	2 ступень	3 ступень	4 ступень	5 ступень
а1	0,4	0100
а2	0,044	0010100
а3	0,019	0010011
а4	0,015	001111
а5	0,005	000101
а6	0,002	00010
а7	0,004	000100
а8	0,02	0010

Сначала копируются символы из лабораторной работы №3 и значения их вероятностей. Они сортируются от самого большого к самому маленькому. Сумма всех вероятностей равна одному. Вероятности делятся на две группы, чтобы суммы вероятностей в каждой были приблизительно равны. Символам верхней группы приписывается единица, символам нижней – ноль. Всё повторяется нужное количество раз, пока в каждой подгруппе не останется по одному символу.

При разбиении на подгруппы можно сделать большей по вероятности как верхнюю, так и нижнюю подгруппу.

	№	Символ	Вероятность	Код	1	2	3	4	5	6		p(a)*log2(p(a))	n(a)	p(a)*n(a)
	1	о	0,089388	111111								-0,311407682	6	0,536328
	2	е	0,084365	111110								-0,300947806	5	0,50619
	3	и	0,078442	111101								-0,288057055	6	0,470652
	4	а	0,070907	111100								-0,27071783	4	0,425442
	5	н	0,067127	111011								-0,261591437	6	0,402762
	6	т	0,054115	111010								-0,227706593	5	0,32469
	7	р	0,05198	111001								-0,221741459	6	0,31188
	8	с	0,044351	111000								-0,199352847	3	0,266106
	9	в	0,040468	110111								-0,187248457	6	0,242808
	10	м	0,036336	110110								-0,173775342	6	0,218016
	11	л	0,034013	11010								-0,165907589	4	0,170065
	12	.	0,030722	11001								-0,154365271	5	0,15361
	13	к	0,028965	11000								-0,147997986	2	0,144825
	14	д	0,028819	101111								-0,147462094	6	0,172914
	15	п	0,02743	101110								-0,142309626	5	0,16458
	16	ы	0,020958	10110								-0,116869251	4	0,10479
	17	у	0,019913	10101								-0,112511349	5	0,099565
	18	я	0,02	101001								-0,112511349	6	0,119478
	19	з	0,016021	101000								-0,095547514	3	0,096126
	20	ч	0,015361	100111								-0,092543636	6	0,092166
	21	ь	0,013801	100110								-0,08527753	5	0,082806
	22	,	0,012618	10010								-0,07959905	4	0,06309
	23	г	0,012044	100011								-0,076787023	6	0,072264
	24	й	0,010518	100010								-0,069113734	5	0,063108
	25	б	0,009918	10000								-0,06601158	1	0,04959
	26	х	0,009121	011111								-0,061809298	6	0,054726
	27	1	0,007218	011110								-0,051350188	5	0,043308
	28	3	0,006472	01110								-0,047061618	4	0,03236
	29	ц	0,006386	011011								-0,046559507	6	0,038316
	30	2	0,006155	011010								-0,045202477	5	0,03693
	31	ю	0,005889	01100								-0,043624308	3	0,029445
	32	ш	0,005717	010111								-0,042594657	6	0,034302
	33	э	0,004637	010110								-0,035948772	5	0,027822
	34	ж	0,004389	01010								-0,034374174	4	0,021945
	35	ф	0,004217	010011								-0,033270305	6	0,025302
	36	:	0,003369	010010								-0,02767116	5	0,020214
	37	щ	0,003163	01000								-0,026267104	2	0,015815
	38	(	0,002477	001111								-0,021443861	6	0,014862
	39	)	0,002477	001110								-0,021443861	5	0,014862
	40	4	0,002109	00110								-0,018747376	3	0,010545
	41	0	0,0018	001011								-0,016412017	6	0,0108
	42	5	0,001114	001010								-0,010928379	5	0,006684
	43	;	0,001071	00100								-0,01056737	3	0,005355
	44	6	0,000994	000111								-0,00991462	6	0,005964
	45	7	0,000686	000110								-0,00720952	5	0,004116
	46	8	0,000617	00010								-0,006578727	4	0,003085
	47	9	0,0006	000011								-0,00642165	6	0,0036
	48	-	0,000506	000010								-0,005539979	5	0,003036
	49	ъ	0,000326	000001								-0,003776006	6	0,001956
	50	ё	0	000000								?	6	0
												4,742078021		5,819201
												H		Ncp

₅₀

H=∑p(a_i)log₂p(a_i)= 4,573834146

¹

₅₀

I_ср =∑p(a_i)n(a_i)= 4,620954551

¹

H – энтропия

p(a_i) – вероятность символа

I_ср — среднее количество двоичных разрядов, используемых при кодировании символов по алгоритму Шеннона-Фано

n(a_i) — число двоичных разрядов в кодовой комбинации, соответствующей символу a_i