ID: 41678

Название работы: Исследование источника дискретной информации

Категория: Лабораторная работа

Предметная область: Информатика, кибернетика и программирование

Описание: А при изпользлвании кода Хаффмена избыточность уменьшилась до 0,51%, из этого следует что избыточность при кодировании этим методом уменьшилась в 16 раз. А при использовании кода Шеннона – Фано избыточность уменьшилась всего в 5,5 раз. Исходя из полученных значений, в нашем случае эффективнее использовать методику кодирования Хаффмена.

Язык: Русский

Дата добавления: 2013-10-24

Размер файла: 165.5 KB

Работу скачали: 19 чел.

Федеральное государственное бюджетное образовательное учреждение

Высшего профессионального образования

Уральский государственный университет путей сообщения

Кафедра «АТиС»

Лабораторная работа № 1

Исследование источника дискретной информации.

Проверил:                                                                                            Выполнил:

к.т.н., доцент                                                                                       студент  ИТ-310

Волынская А.В.                                                                                      Коробицын А.В.

Екатеринбург

2013 г.

Исходное сообщение на выходе источника:

КОРОБИЦЫН_АНАТОЛИЙ_ВАДИМОВИЧ

Определить:

Длину сообщения – Lа.

Объем алфавита – mа.

Вероятности символов – p(ai).

Энтропию источника – .

Количество информации, содержащееся в каждом символе I(ai) и во  всем сообщении Iсообщ.

Коэффициент избыточности источника информации – rист.

Закодировать сообщение эффективными двоичными кодами Шеннона-Фано и Хаффмена.

Определить коэффициент избыточности после кодирования сообщения равномерным кодом – rравн. и эффективными кодами – rШ-Ф и  rХаф.

Сделать выводы.

Определим длину сообщения: КОРОБИЦЫН_АНАТОЛИЙ_ВАДИМОВИЧ

La=28 символов

Определим объем алфавита:

Объем алфавита – количество различных символов, из которых состоит сообщение.

ma=17 символов

Определим вероятности символов, количество информации в символе и во всем сообщении:

По следующим формулам

                                               - вероятность символов

где  n(ai) – количество символов  ai  в сообщении;

          Lа – количество всех символов в сообщении;

Количество информации, содержащееся в символе, определяется по формуле Шеннона:

,  бит

где p(ai) – вероятности символов;

                         ,  бит. – количество информации во всем сообщении.

Результаты вычислений

ai	n(ai)	p(ai),	I(ai), бит
К	1	0,04	4,644
О	4	0,14	2,836
Р	1	0,04	4,644
Б	1	0,04	4,644
И	4	0,14	2,836
Ц	1	0,04	4,644
Ы	1	0,04	4,644
Н	2	0,07	3,936
_	2	0,07	3,936
А	3	0,11	3,184
Т	1	0,04	4,644
Л	1	0,04	4,644
Й	1	0,04	4,644
В	2	0,07	3,936
Д	1	0,04	4,644
М	1	0,04	4,644
Ч	1	0,04	4,644
17	26	1,04

Определим энтропию источника:

Энтропией называют среднее количество информации приходящееся на один произвольный символ.

,  бит/символ.

H(A)=3,75 бит/символ

Iсообщ=H(A)*La, ,бит

Iсообщ=105 бит

H max (A)=log 2 ma, бит/символ.

H max =4,0875 бит/символ

Коэффициент избыточности:

.

rист = 8,26 %

Закодируем сообщение кодом Шеннона – Фано:

ai	p(ai),	код	n(ai)	n(1)	n(0)
О	0,14	111	4	12	-
И	0,14	110	4	8	4
А	0,11	101	3	6	3
Н	0,07	1001	2	4	4
-	0,07	1000	2	2	6
В	0,07	0111	2	6	2
К	0,04	01101	1	3	2
Р	0,04	01100	1	2	3
Б	0,04	0101	1	2	2
Ц	0,04	01001	1	2	3
Ы	0,04	01000	1	1	4
Т	0,04	0011	1	2	2
Л	0,04	00101	1	2	3
Й	0,04	00100	1	1	4
Д	0,04	0001	1	1	3
М	0,04	00001	1	1	4
Ч	0,04	00000	1	-	5
				55	54	109

L ш-ф = n(0) + n(1)

L ш-ф – длина закодированного сообщения. 

L ш-ф =109

p(1) = 55/109 = 0,505

     p(0) = 54/109 = 0.495

Энтропия:

H ш-ф = 0.985 бит/символ

H ш-ф (K) = log 2 (m k) = = log 2 2 = 1 бит/символ

Избыточность:

r ш-ф = 1,5 %

Закодируем сообщение  кодом Хаффмена:

Кодовое дерево приведено на следующей странице.

ai	код	n(ai)	n(1)	n(0)
О	100	4	4	8
И	011	4	8	4
А	001	3	3	6
Н	1011	2	6	2
_	1010	2	4	4
В	0101	2	4	4
К	11111	1	5	-
Р	11110	1	4	1
Б	11101	1	4	1
Ц	11100	1	3	2
Ы	11011	1	4	1
Т	11010	1	3	2
Л	11001	1	3	2
Й	11000	1	2	3
Д	0100	1	1	3
М	0001	1	1	3
Ч	0000	1	-	4
			59	50	109

L х = n(0) + n(1).

L х – длина закодированного сообщения. 

L х =109

p(1) = 59/109 = 0.5413

     p(0) = 50/109 = 0.4587

Энтропия:

H x = 0.9949 бит/символ

H x (K) = log 2 (m k) = = log 2 2 = 1 бит/символ

Избыточность:

r x = 0,52 %

Вывод.

Избыточность источника без шифрования составила  rист = 8,26 %.

При  кодировании методом Шеннона – Фано избыточность уменьшилась до 1,5 %.

А при изпользлвании кода Хаффмена избыточность уменьшилась до 0,51%, из этого следует что избыточность при кодировании этим методом уменьшилась в 16 раз.

А при использовании кода Шеннона – Фано избыточность уменьшилась всего в 5,5 раз.

Исходя из полученных значений, в нашем случае эффективнее использовать методику кодирования Хаффмена.