41678

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

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

Информатика, кибернетика и программирование

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

Русский

2013-10-24

165.5 KB

11 чел.

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

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

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

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

Лабораторная работа № 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 раз.

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


 

А также другие работы, которые могут Вас заинтересовать

67353. Шаблони. Узагальнені функції 96.5 KB
  Поняття про шаблони Поняття про узагальнені функції Шаблонна функція з одним узагальненим типом Безпосередньо задане перевантаження узагальненої функції Шаблонна функція з двома узагальненими типами Поняття про шаблони Шаблон – це один із складних і потужних засобів мови програмування C.
67354. Ресурси підприємства 41.32 KB
  Для здійснення будь-якого виробничого процесу, крім самої праці як доцільної діяльності людей, потрібні предмети праці, тобто матеріально-технічні ресурси та засоби праці. Сукупність засобів праці, якими розпоряджається підприємство, складає його основні фонди.
67355. ЮРИДИЧЕСКАЯ ПРАКТИКА 115.5 KB
  В правоведении существуют различные мнения о понятии юридической практики. Ошибочность первых двух позиций на наш взгляд состоит в том что в первом случае из практики исключается такой важный ее элемент как юридический опыт во втором допускается другая крайность: результаты деятельности...
67356. Перевантаження шаблонної функції 70 KB
  Окрім створення безпосередньо перевизначених версій узагальненої функції, можна також перевизначати саму специфікацію шаблону функції. Для цього достатньо створити ще одну версію шаблону, яка відрізнятиметься від інших переліком параметрів. Розглянемо такий приклад...
67357. ПРАВОВЫЕ ОТНОШЕНИЯ 258 KB
  Их участники наделяются правосубъектностью юридическими правами и обязанностями. Любые отношения приобретают характер правоотношений лишь в том случае если они возникают на ос 472 нове и в соответствии с нормами права и не противоречат воле государства. 473 Правоотношения следствие действия...
67358. Узагальнені класи 142.5 KB
  Окрім визначення узагальнених функцій, можна також визначити узагальнений клас. Для цього створюється клас, у якому визначаються всі використовувані ним алгоритми. При цьому реальний тип оброблюваних у ньому даних задається як параметр при побудові об’єктів цього класу.
67359. Обробка виняткових ситуацій 101 KB
  Розглянемо механізми оброблення різних виняткових ситуацій. Виняткова ситуація (або виняток) – це помилка, яка виникає у процесі виконання програми. Використовуючи С++-підсистему оброблення виняткових ситуацій, такі помилки легко можна виправляти. Їх виникнення під час роботи коду програми автоматично...
67360. ПРАВОМЕРНОЕ ПОВЕДЕНИЕ И ПРАВОНАРУШЕНИЯ 123.5 KB
  Нарушение предписаний правовых норм в любом обществе носит массовый характер и создает ему весьма ощутимый моральный и материальный вред. Все без исключения правонарушения представляют собой деяния людей а не воздействие сил природы или предметов не действия животных.
67361. Перехоплення винятків класового типу 71 KB
  Виняток може мати будь-який тип, у тому числі і класового типу, створенного програмістом. У реальних програмах більшість винятків мають саме класовий тип, а не вбудований тип. Ймовірно, тип класу найбільше підходить для опису помилки, яка потенційно...