41678

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

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

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

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

Русский

2013-10-24

165.5 KB

10 чел.

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

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

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

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

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

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


 

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

74577. СТРОЕНИЕ ЗЕМЛИ 4.66 MB
  В твердом теле Земли выделяют три внутренние оболочки: центральную ядро промежуточную мантию наружную земную кору рис. Как внутренние так и внешние оболочки объединяют под общим названием геосфер Земли. История изучения внутреннего строения Земли насчитывает несколько столетий и тесно связана с развитием представлений о происхождении Солнечной системы.
74578. ГЕОЛОГИЧЕСКОЕ ЛЕТОИСЧИСЛЕНИЕ (ГЕОХРОНОЛОГИЯ) 3.1 MB
  В первом случае определяют относительный возраст пород т. Во втором случае определяют абсолютный возраст пород который выражается в годах. Относительное летоисчисление При определении относительного возраста пород используют несколько методов.
74579. ВЕЩЕСТВЕННЫЙ СОСТАВ ЗЕМНОЙ КОРЫ 974.5 KB
  К физическим свойствам относят цвет блеск цвет черты плотность твердость спайность магнитность и некоторые другие. Твердость степень сопротивления минералов царапанию резанию. В полевой практике пользуются шкалой заменителей...
74580. ГЕОЛОГИЧЕСКАЯ ДЕЯТЕЛЬНОСТЬ МОРЯ 479 KB
  в океане заключено 86 общего количества воды гидросферы. Физические и химические свойства морской воды Температура морской воды. В поверхностном слое морей и океанов температура воды во многом зависит от климатических условий местности. Но начиная с некоторой глубины колебания температуры морской воды обусловленные климатическими условиями исчезают и далее с глубиной температура неуклонно понижается.
74581. Геологическая деятельность ветра 707 KB
  Во всех песчаных пустынях широко распространены продольногрядовые пески которые образуются при ветрах имеющих штопорообразный характер движения воздуха в горизонтальном направлении одного направления. Бугристые пески – песчаные холмы высотой до 810 м неправильной формы закрепленные растительностью.
74582. Геологическая деятельность снега, льда 902.5 KB
  Общий объем льда содержащегося в ледниках оценивается в 30 млн. Для возникновения ледника необходимы низкая среднегодовая температура большое количество осадков выпадающих в виде снега а также наличие пологих склонов и впадин защищенных от солнца и ветра. Это и определяет неравномерность накопления снега и масштабов образования глетчерного льда основная его часть 995 сосредоточена в полярных областях и только 05 связано с высокогорными ледниками. Накапливается он в виде масс значительной мощности составляющих тело ледника.
74583. Выветривание. Физическое выветривание 849.5 KB
  Факторами выветривания являются: Колебание температур суточное сезонное Химические агенты: O2 H2O CO2 Органические кислоты ульминовая гуминовая Жизнедеятельность организмов В зависимости от факторов вызывающих выветривание различают несколько видов...
74584. Геологическая деятельность поверхностных текучих вод 564 KB
  Такова схема выработки продольного профиля равновесия реки при условии однородного состава размываемых его пород. При чередовании мягких и твердых пород в русле реки образуются пороги. Перенос и отложения водотоков Реки переносят обломочный материал различной размерности от крупных валунов до мелких илистых частиц. Влекомые по дну обломки и взвешенные частицы называют твердым стоком реки.
74585. ГЕОЛОГИЧЕСКАЯ ДЕЯТЕЛЬНОСТЬ ОЗЕР И БОЛОТ 220.5 KB
  Источниками питания озер служат атмосферные воды поверхностный сток и подземная разгрузка водоносных горизонтов; Основную массу воды в озера поставляют реки. По величине озера сильно различаются площадь крупных озер-морей измеряется сотнями тысяч квадратных километров...