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

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


 

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

62171. «Планета заболела!» (Я и Украина) 22.71 KB
  Учитель в начале урока даёт установку на предстоящую деятельность. Учитель говорит вступительное слово и тем самым приковывает к себе всё внимание детей. Учитель умеет распределять своё внимание на уроке.
62177. Снятие мерок для построения чертежа юбки 15.76 KB
  Структура урока соответствовала комбинированному уроку. В ней выделены следующие этапы: организационный момент актуализация опорных знаний и опыта целеполагание и мотивация изучение нового материала практическая работа...