Курсовая работа по «Основам сбора, передачи и обработки информации»

Энтропия этого источника  при кодировании его первичного ансамбля сообщений A определенным кодом рассчитывается по формуле:

, (6)

где l_ср   –   средняя длина кодовой комбинации закодированного ансамбля сообщений (см. формулу (5)),

H(B) – энтропия источника вторичного ансамбля сообщений B.

Рассчитаем энтропию источника сообщений вторичного алфавита B - H(B). Для этого необходимо найти вероятность появления символов этого алфавита. Положим, что длина текста

.

Для данного текста, закодированного  кодом Шеннона-Фано, найдем вероятность  появления в нем двоичных символов “0” и “1” – элементов вторичного ансамбля сообщений B. Для этого необходимо подсчитать количество “0” и “1” в закодированном тексте.

 

Таблица 3

Подсчет количества “0” и “1” в закодированном тексте (исходный текст длиной L = 10 000 символов)

Символ первичного алфавита	Вероятность появления символа первичного алфавита	Закодированный кодом Шеннона-Фано символ	Количество символов в кодовой комбинации		Количество символов в тексте
			0	1	0	1
о	0,1067	000	3	0	3201	0
а	0,1067	001	2	1	2134	1067
и	0,0933	0100	3	1	2799	933
в	0,0933	0101	2	2	1866	1866
к	0,08	0110	2	2	1600	1600
н	0,08	0111	1	3	800	2400
с	0,08	1000	3	1	2400	800
е	0,08	1001	2	2	1600	1600
л	0,0667	1010	2	2	1334	1334
я	0,0667	1011	1	3	667	2001
ч	0,0533	1100	2	2	1066	1066
й	0,0267	1101	1	3	267	801
т	0,0267	1110	3	1	801	267
ь	0,0133	111100	4	2	532	266
р	0,0133	111101	5	1	665	133
г	0,0133	11111	0	5	0	665
Количество каждого  из двоичных символов в закодированном тексте					21732	16799
Длина закодированного  текста					38 531

 

 

Зная количество “0”  и “1” в тексте, а также длину  текста, подсчитаем вероятность появления  двоичных символов в закодированном тексте:

По формуле (3) рассчитаем энтропию источника вторичного ансамбля сообщений B - H(B) (количество символов алфавита n = 2):

Теперь по формуле (6) найдем энтропию источника при кодировании  его первичного ансамбля сообщений A кодом Шеннона-Фано:

.

Энтропия источника  первичного ансамбля сообщений A:

.

Следовательно:

≈ .

Вывод: из двух пунктов доказательства следует, что код Шеннона-Фано является оптимальным.

3.3. Код Хаффмана

Краткие теоретические сведения

Все кодируемые сообщения  источника располагаются в столбец  по убывающим вероятностям. Затем  два наименее вероятных сообщения (расположенных в последних строках  столбца) объединяются в одно, которому приписывается суммарная вероятность. Затем составляется первая вспомогательная группа элементов, отличающаяся от исходной тем, что объединенный элемент занимает в колонке положение, соответствующее его вероятности. Далее процесс объединения пары наименее вероятных элементов и создания второй и последующих вспомогательных групп повторяется до получения единственного элемента с вероятностью 1.

Для образования кодовых  сообщений необходимо построить  кодовое дерево. Отмечают вершину  кодового дерева и приписывают ей вероятность 1,000. Из вершины проводят две ветви, оканчивающиеся узлами. Узлам приписывают вероятности, которые при суммировании дают единицу. Вертикальной ветви (с меньшей вероятностью) приписывают символ "0", а горизонтальной (с большей) – символ "1". Если вероятность при некотором узле равна вероятности какого-либо сообщения, узлу приписывают символ этого сообщения и переходят к анализу следующего узла. Если вероятность при некотором узле образована суммированием двух меньших вероятностей, то из него опять проводят две разнонаправленные ветви, оканчивающиеся узлами. Узлам приписывают вероятности с учетом принятой ориентации. Ветвям приписывают символы: вертикальной – "0", горизонтальной – "1". Процесс построения кодового дерева продолжается, пока все символы сообщений источника не будут приписаны корневым узлам.

Кодовые комбинации, соответствующие  сообщениям источника, записываются следующим  образом. На полученном кодовом дереве необходимо проследить по ветвям путь от корневого узла (узла с вероятностью 1,000), до узла, соответствующего заданному сообщению, записывая последовательно слева направо символы 1 или 0, соответствующие прослеживаемым ветвям. Полученные кодовые комбинации и представляют собой оптимальный код Хаффмана.

Кодирование

Закодируем полученный в п. 3.3.1. алфавит кодом Шеннона-Фано. Для чего сначала составим таблицу вспомогательных групп.

 

Таблица 4

Иллюстрация получения  вспомогательных групп для построения кодового дерева для кодирования  нашего алфавита кодом Хаффмана

Буквы	pi	Вспомогательные группы
		1		2		3		4		5		6		7		8		9		10		11		12		13		14		15
о	0,1067	0,1067		0,1067		0,1067		0,1067		0,12		0,147		0,147		0,173		0,187		0,213		0,267		0,333		0,4		0,6		1
а	0,107	0,107		0,107		0,107		0,107		0,107		0,12		0,16		0,16		0,173		0,187		0,213		0,267		0,333		0,4
и	0,093	0,093		0,093		0,093		0,093		0,107		0,107		0,12		0,147		0,16		0,173		0,187		0,213		0,267
в	0,093	0,093		0,093		0,093		0,093		0,093		0,107		0,107		0,12		0,147		0,16		0,173		0,187
к	0,08	0,08		0,08		0,08		0,093		0,0933		0,0933		0,1067		0,1067		0,1201		0,147		0,16
н	0,08	0,08		0,08		0,08		0,08		0,093		0,093		0,093		0,107		0,107		0,12
с	0,08	0,08		0,08		0,08		0,08		0,08		0,093		0,093		0,093		0,107
е	0,08	0,08		0,08		0,08		0,08		0,08		0,08		0,093		0,093
л	0,067	0,067		0,067		0,067		0,08		0,08		0,08		0,08
я	0,067	0,067		0,067		0,067		0,067		0,08		0,08
ч	0,0533	0,0533		0,0533		0,053		0,0667		0,0667
й	0,0267	0,0267		0,04		0,0533		0,0534
т	0,027	0,027		0,027		0,04
Буквы	pi		Вспомогательные группы
			1		2		3		4		5		6		7		8		9	10	11		12		13		14		15
ь	0,0133		0,027		0,0267
р	0,013		0,013
г	0,013

 

 

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

Рис. 1. Кодовое дерево для кодирования нашего алфавита кодом Хаффмана

 

С помощью построенного дерева переходов выпишем кодовые комбинации для элементов нашего алфавита.

Таблица 5

Буквы нашего алфавита, закодированные кодом Хаффмана

Буква	Кодовая комбинация
о	010
а	011
и	001
в	000
к	1011
н	1100
с	1110
е	1101
л	1001
я	1010
ч	11111
й	10000
т	10001
ь	111100
р	1111010
г	1111011

Кодирование ФИО

Закодируем в данном алфавите мое ФИО кодом Хаффмана.

Исходный текст:

ОИВ;

кодовые комбинации для  букв:

О – 010,

И – 001;

В - 000

тогда закодированное ФИО:

010001000.

Кодовая комбинация ФИО, закодированная кодом Хаффмана, имеет длину 9 бит, а закодированная цифровым кодом – длину 24 бита, то есть ФИО в коде Хаффмана в 2,5 раз короче ФИО в цифровом коде.

Доказательство оптимальности  кода

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

1. Код Хаффмана - неравномерный код. Чтобы он был оптимальным, необходимо, чтобы средняя длина кодовой комбинации для определенного алфавита, закодированного этим кодом, была меньше длины кодовой комбинации равномерного двоичного кода, которым можно закодировать этот алфавит.

По формуле (5) найдем среднюю  длину кодовой комбинации для  нашего алфавита (количество символов алфавита n = 16), закодированного кодом Хаффмана, и получим следующее значение:

,

то есть в среднем  на один символ нашего алфавита приходится 3,8131 двоичных символов.

Длина кодовой комбинации равномерного двоичного кода, которым можно закодировать наш алфавит, будет равняться 4, поскольку таким кодом можно закодировать алфавит, максимальное количество символов которого будет равняться 2⁴ = 16.

Это означает, что необходимая  длина кодовой комбинации равномерного двоичного кода больше средней длины кодовой комбинации Хаффмана.

2. Сравним энтропию источника первичного ансамбля сообщений A (нашего алфавита) с энтропией этого же источника при кодировании его ансамбля сообщений кодом Хаффмана.

Рассчитаем энтропию источника сообщений вторичного алфавита B - H(B). Для этого необходимо найти вероятность появления символов этого алфавита. Положим, что длина текста

.

Таблица 6

Подсчет количества “0” и “1” в закодированном тексте (исходный текст длиной L = 10 000 символов)

Символ первичного алфавита	Вероятность появления символа первичного алфавита	Закодированный кодом Хаффмена символ	Количество символов в кодовой комбинации		Количество символов в тексте
			0	1	0	1
о	0,1067	010	2	1	2134	1067
а	0,1067	011	1	2	1067	2134
и	0,0933	001	2	1	1866	933
в	0,0933	000	3	0	2799	0
к	0,08	1011	1	3	800	2400
н	0,08	1100	2	2	1600	1600
с	0,08	1110	1	3	800	2400
е	0,08	1101	1	3	800	2400
л	0,0667	1001	2	2	1334	1334
я	0,0667	1010	2	2	1334	1334
ч	0,0533	11111	0	5	0	2665
й	0,0267	10000	4	1	1068	267
т	0,0267	10001	3	2	801	534
ь	0,0133	111100	2	4	266	532
р	0,0133	1111010	2	5	266	665
г	0,0133	1111011	1	6	133	798
Количество каждого  из двоичных символов в закодированном тексте					21732	16799
Длина закодированного  текста					38131