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 раз.

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


 

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

8731. Трудовая деятельность 40 KB
  Трудовая деятельность Вариант 1 Трудовая деятельность людей (процесс материального производства) - это одна из форм человеческой деятельности, направленная на преобразование природного мира и создание материальных благ. В структуре т...
8732. Свобода в деятельности людей 36.5 KB
  Свобода в деятельности людей Вариант 1 Свобода - это самостоятельность социальных и политических субъектов (в том числе и личности), выражающаяся в их способности и возможности делать собственный выбор и действовать в соответствии со своими инт...
8733. Исторический процесс и его участники 45 KB
  Исторический процесс и его участники Вариант 1 Исторический процесс - временная последовательность сменяющих друг друга событий, которые явились результатом деятельности многих поколений людей. Основу исторического процесса составляют исторические ф...
8734. Политика как деятельность, ее объекты, субъекты, цели и средства 54.5 KB
  Политика как деятельность, ее объекты, субъекты, цели и средства Вариант 1 Слово политика произошло от греческого слова politike, что означает в переводе на русский язык государственные дела. Среди причин - поляризация общества, появление соц...
8735. Политическая идеология 32.5 KB
  Политическая идеология Вариант 1 Политическая идеология - система идей и взглядов, выражающая коренные интересы, мировоззрение, какого-либо субъекта политики (класса, нации, общества, партии, общественного движения). Политическая идеология - те...
8736. Политическая система общества, ее структура 62.5 KB
  Политическая система общества, ее структура. Вариант 1 . Под политической системой общества понимают совокупность различных политических институтов, социально-политических общностей, форм взаимодействий и взаимоотношени...
8737. Политические партии. Многопартийность 58.5 KB
  Вариант 1 Политические партии. Многопартийность Политическая партия - это специализированная, организационно упорядоченная группа, объединяющая активных приверженцев тех или иных целей, идей, лидеров, служащая для борьбы за политическую власть....
8738. Общественный прогресс. Критерии прогресса 46.5 KB
  Общественный прогресс. Критерии прогресса 1 вариант. Прогресс - направление развития, для которого характерно поступательное движение общества от низших и простых форм общественной организации к более высоким и сложным. Регресс - обратное движение...
8739. Общество и научно-технический прогресс 37.5 KB
  Общество и научно-технический прогресс Вариант 1 Современное состояние научно - технического прогресса определяется понятием научно-технической революции. Научно-техническая революция (НТР)- это качественный скачок в развитии производительных с...