Файл: 1. информационная мера шеннона. Количество информации и избыточность.doc

, , ,

, , ,

, , .

4. КОДИРОВАНИЕ ИНФОРМАЦИИ

4.1. Общие сведения Кодом называется:

- правило, описывающее отображение одного набора знаков в другой набор знаков или в набор слов без знаков;

- множество образов, получающихся при таком отображении.

В технических кодах буквы, цифры и другие знаки почти всегда кодируются двоичными последовательностями, называемыми двоичными кодовыми словами. У многих кодов слова имеют оди­наковую длину (равномерные коды).

Выбор кодов для кодирования конкретных типов сообщений определяется многими факторами:

- удобством получения исходных сообщений из источника;

- быстротой передачи сообщений через канал связи;

- объёмом памяти, необходимым дня хранения сообщений;

- удобством обработки данных;

- удобством декодирования сообщений приемником.

Закодированные сообщения передаются по каналам связи, хра­нятся в ЗУ, обрабатываются процессором. Объемы кодируемых данных велики, и поэтому во многих случаях важно обеспечить таксе кодирование данны:'., которое характеризуется минимальной длиной получающихся сообщений, Это проблема сжатия данных. Существуют два подхода сжатия данных:

- сжатие, основанное на анализе статистических свойств коди­руемых сообщений.

Сжатие на основе статистических свойств данных называется так же теорией экономного или эффективного кодирования. Эко­номное кодирование основано на использовании кодов с перемен­ной длиной кодового слова, например, код Шеннона-Фано, код Хафмана /31. Идея использования кодов переменной длины для сжа­тия данных состоит в том, чтобы сообщения с большей вероят­ностью появления ставить в соответствие кодовые комбинации мень­шей длины и, наоборот, сообщения с малой вероятностью появле­ния кодировать словами большей длины. Средняя длина кодового слова определяется с.о.:

---

где /, - длина кодового слова для кодирования i - го сообщения; p_t - вероятность появления i - го сообщения.

4.2. Задания

4.2.1. Из табл.4 выбрать дня последующего кодирования ис­ходный алфавит, содержащий 10 символов, начиная с N-ro (N -порядковый номер студента в журнале группы). Пронормировать вероятности символов.

4.2.2. Пронормировать выбранный в п.4.2.1. исходный алфавит равномерным двоичным кодом, кодом Шеннона-Фано, кодом Хафмана. Для каждого варианта кодирования рассчитать мини­мальное, максимальное, среднее значение длины кодового слова. Проанализировать результаты.

4.2.3. Проделать задание 4.2.2. для троичного кода.

Таблица 4

N	сим­вол	Р	N	сим­вол	Р	N	сим­вол	Р	N	сим­вол	Р
1	А	0,062	10	К	0,028	19	у	0,021	28	Э	0,003
2	Б	0,014	11	Л	0,035	20	ф	0,002	29	Ю	0.018
3	В	0,038	12	м	0,026	21	X	0,009	30	Ъ	0,009
4	Г	0,013	13	н	0,053	22	Ц	0,004	31
5	д	0,025	14	о	0,090	23	ч	0,012
6	Е	0,072	15	п	0,023	24	ш	0,006
7	Ж	0,007	16	Р	0,040	25	Щ	0,003
8	3	0,016	17	с	0,053	26	ь	(M¥L
9	И	0,062	18	т	0,053	27	ъ	одй1

---

4.3. Указания к выполнению отдельных заданий К заданию 4.2.1. Нормирование вероятностей производится по формуле:

/W-HO / *Рк ' JC=AT

где Pi - вероятности появления символов, приведенные в табл.4.

К заданию 4.2.2. Правила построения двоичных кодов изло­жены в /4,6/.

К заданию 4.2.3. При построении троичного кода в качестве кодовых слов берутся слова, записанные в троичной системе счис­ления. Оптимальный троичный код строится с помощью процедуры Хафмана (с помощью процедуры Шеннона-Фано строится субоп-тимальный код). При этом разбиение алфавита ведется на три груп­пы, первой группе приписывается "О", второй - "1", третьей - "2".
ПРИЛОЖЕНИЕ 1

ЗНАЧЕНИЕ ФУНКЦИИ –P^. log₂( P)

Таблица

P	-P.log2P	P	-P.log2P	P	-P.log2P	P	-P.log2P
0.00	0.000000	0.26	0.505288	0.52	0.490577	0.78	0.279594
0.01	0.066439	0.27	0.510022	0.53	0.485446	0.79	0.268660
0.02	0.112877	0.28	0.514220	0.54	0.480043	0.80	0.257542
0.03	0.151767	0.29	0.517904	0.55	0.474373	0.81	0.246245
0.04	0.185754	0.30	0.521090	0.56	0.468441	0.82	0.234769
0.05	0.216096	0.31	0.523795	0.57	0.462251	0.83	0.223118
0.06	0.243534	0.32	0.526034	0.58	0.455808	0.84	0.211293
0.07	0.268555	0.33	0.527822	0.59	0.449116	0.85	0.199295
0.08	0.291508	0.34	0.529174	0.60	0.442179	0.86	0.187129
0.09	0.312654	0.35	0.530101	0.61	0.435002	0.87	0.174794
0.10	0.332193	0.36	0.530615	0.62	0.427589	0.88	0.162294
0.11	0.350287	0.37	0.530729	0.63	0.419943	0.89	0.149629
0.12	0.367067	0.38	0.530453	0.64	0.412068	0.90	0.136803
0.13	0.382644	0.39	0.529797	0.65	0.403967	0.91	0.123816
0.14	0.397110	0.40	0.528771	0.66	0.395645	0.92	0.110671
0.15	0.410545	0.41	0.527385	0.67	0.387104	0.93	0.097369
0.16	0.423017	0.42	0.525646	0.68	0.378347	0.94	0.083911
0.17	0.434587	0.43	0.523564	0.69	0.369379	0.95	0.070301
0.18	0.445308	0.44	0.521147	0.70	0.360201	0.96	0.056538
0.19	0.455226	0.45	0.518401	0.71	0.350817	0.97	0.042625
0.20	0.464386	0.46	0.515335	0.72	0.341230	0.98	0.028563
0.21	0.472823	0.47	0.511956	0.73	0.331443	0.99	0.014355
0.22	0.480573	0.48	0.508269	0.74	0.321458	1.00	0.000000
0.23	0.487668	0.49	0.504282	0.75	0.311278
0.24	0.494134	0.50	0.500000	0.76	0.300906
0.25	0.500000	0.51	0.495430	0.77	0.290344

---

ПРИЛОЖЕНИЕ 2

ЗНАЧЕНИЕ ФУНКЦИИ log₂( 1/P)

Таблица

P	log2(1/P)	P	log2(1/P)	P	log2(1/P)	P	log2(1/P)
.00	-	.26	1.94342	.52	.943416	.78	.358454
.01	6.64386	.27	1.88897	.53	.915936	.79	.340075
.02	5.64386	.28	1.83650	.54	.888969	.80	.321928
.03	5.05889	.29	1.78588	.55	.862496	.81	.304006
.04	4.64386	.30	1.73697	.56	.836501	.82	.286304
.05	4.32193	.31	1.68966	.57	.810966	.83	.268817
.06	4.05889	.32	1.64386	.58	.785875	.84	.251539
.07	3.83650	.33	1.59946	.59	.761213	.85	.234465
.08	3.64386	.34	1.55639	.60	.736966	.86	.217591
.09	3.47393	.35	1.51457	.61	.713119	.87	.200913
.10	3.32193	.36	1.47393	.62	.689660	.88	.184425
.11	3.18442	.37	1.43440	.63	.666576	.89	.168123
.12	3.05889	.38	1.39593	.64	.643856	.90	.152003
.13	2.94342	.39	1.35845	.65	.621488	.91	.136062
.14	2.83650	.40	1.32193	.66	.599462	.92	.120294
.15	2.73697	.41	1.28630	.67	.577767	.93	.104697
.16	2.64386	.42	1.25154	.68	.556393	.94	.089267
.17	2.55639	.43	1.21759	.69	.535332	.95	.074001
.18	2.47393	.44	1.18442	.70	.514573	.96	.058894
.19	2.39593	.45	1.15200	.71	.494109	.97	.043943
.20	2.32193	.46	1.12029	.72	.473931	.98	.029146
.21	2.25154	.47	1.08927	.73	.454032	.99	.014500
.22	2.18442	.48	1.05889	.74	.434403	1.0	.000000
.23	2.12029	.49	1.02915	.75	.415037
.24	2.05889	.50	1.00000	.76	.395929
.25	2.00000	.51	.971431	.77	.377070

---

---