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. Нагрев осуществляется переменным источником ...