41678
Исследование источника дискретной информации
Лабораторная работа
Информатика, кибернетика и программирование
А при изпользлвании кода Хаффмена избыточность уменьшилась до 0,51%, из этого следует что избыточность при кодировании этим методом уменьшилась в 16 раз. А при использовании кода Шеннона – Фано избыточность уменьшилась всего в 5,5 раз. Исходя из полученных значений, в нашем случае эффективнее использовать методику кодирования Хаффмена.
Русский
2013-10-24
165.5 KB
14 чел.
Федеральное государственное бюджетное образовательное учреждение
Высшего профессионального образования
Уральский государственный университет путей сообщения
Кафедра «АТиС»
Лабораторная работа № 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 раз.
Исходя из полученных значений, в нашем случае эффективнее использовать методику кодирования Хаффмена.
А также другие работы, которые могут Вас заинтересовать | |||
| 10592. | Философия Возрождения: антропоцентризм (XV –XVI вв.) | 50 KB | |
| Философия Возрождения: антропоцентризм XV XVI вв. С XV века происходят изменения в социально-экономической и духовной жизни Западной Европы. Она характеризуется возникновением мануфактур техническими открытиями и нововведениями самопрялка ткацкий станок водяное к... | |||
| 10593. | Немецкая классическая философия во второй половине XVIII века | 56 KB | |
| Немецкая классическая философия В Германии во второй половине XVIII века сформировалось новое направление немецкая классическая философия. Ее представители: Кант дуалист Фихте субъективный идеалист Шеллинг объективный идеалист Гегель объективный идеали | |||
| 10594. | Отечественная философия XIX - начала XX веков | 82.5 KB | |
| Отечественная философия XIX начала XX веков Русская философия начинает свое существование с XIX века. Основная тема которая на протяжении почти целого столетия занимала умы русской интеллигенции историческая судьба России ее прошлое настоящее и будущее ее историче... | |||
| 10595. | Предмет и цель математического моделирования | 19.24 KB | |
| Предмет и цель математического моделирования. В развитии различных областей человеческой деятельности математика оказывала и оказывает существенное влияние. Ее роль складывалась исторически и зависела от двух факторов: степени развития математических понятий и ма | |||
| 10596. | Математическое моделирование системы индукционного нагрева | 32.53 KB | |
| Математическое моделирование системы индукционного нагрева. Система индукционного нагрева представляет собой в общем случае источник питания индуктор нагреваемое тело и окружающую среду. Источник питания будь то генератор повышенной частоты тиристорный п... | |||
| 10597. | Тепловая задача. Основные положения. Критерии и числа подобия | 67.46 KB | |
| Тепловая задача. Основные положения. Критерии и числа подобия В настоящее время существует немало как аналитических так и численных методов решения тепловых задач для тел цилиндрической и прямоугольной формы. В случае нагрева тел более сложной формы для решения п... | |||
| 10598. | Методы решения краевых задач. Метод разделения переменных (Метод Фурье) | 119.66 KB | |
| Методы решения краевых задач. Метод разделения переменных Метод Фурье. Метод разделения переменных относится к классическим методам решения линейного дифференциального уравнения теплопроводности. При его применении вначале находится совокупность частных решений... | |||
| 10599. | Методы интегрального преобразования | 76.24 KB | |
| Методы интегрального преобразования. Операционные методы. Для многих задач теплопроводности использование классических методов оказывается неэффективным например применение метода разделения переменных для задач с внутренними источниками тепла. Основные пра | |||
| 10600. | Нагрев неограниченной пластины. Решение методом преобразования Фурье | 73.38 KB | |
| Нагрев неограниченной пластины. Решение методом преобразования Фурье Дана неограниченная пластина толщиной 2R при температуре. Теплообмен с окружающей средой происходит при ГУ2. Нагрев осуществляется переменным источником ... | |||
