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

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


 

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

75636. Особенности коммуникативной активности дошкольников с общим недоразвитием речи 24.56 KB
  Необходимость поиска адекватных и эффективных способов коррекции нарушений коммуникативной деятельности детей с ОНР отмечаемое рядом авторов О. Анализ специальной литературы позволил нам сделать выводы о том что недостатки коммуникативной деятельности детей с речевыми нарушениями имеют комплексный характер. Павлова отмечают низкий уровень личностной активности детей...
75637. Осознание фонетических явлений родного языка детьми в норме и при патологии речи 25.12 KB
  Принципиального определения возраста, в котором ребёнок может продемонстрировать осознанное отношение к языку и речи; уточнения позиции о взаимосвязи речеязыковых и когнитивных механизмов, определяющих ориентировочные действия в языке
75638. Своеобразие употребления, понимания и интерпретации невербальных средств общения дошкольниками с общим недоразвитием речи 46.76 KB
  Умение правильно понимать невербальные средства общения и адекватно выражать с их помощью смысл и значение играют исключительную роль в развитии детей в формировании предпосылок речи в становлении языковой личности ребёнка. На протяжении многих лет основное внимание логопедов было сосредоточено исключительно на языковом развитии детей с ОНР выявлении специфики и особенностей их речи по сравнению с нормой. Причём нередко невербальные компоненты коммуникации воспринимались как средства тормозящие речевое развитие детей и мешающие...
75639. Невербальные проявления интенциональных направленностей в поведении дошкольников с общим недоразвитием речи 32.72 KB
  Невербальные проявления интенциональных направленностей в поведении дошкольников с общим недоразвитием речи О. Сопоставив полученные исследователями результаты с нашими данными мы смогли выделить вербальные и невербальные проявления интенциональных направленностей и их выраженность в поведении дошкольников с нормальной и нарушенной речью см. Таблица Выраженность вербальных и невербальных проявлений интенциональных направленностей в поведении дошкольников Форма проявления Форма выражения интенциональной направленности...
75640. Особенности интерпретации невербальных средств общения дошкольниками с тяжёлыми нарушениями 52.22 KB
  Психические и физические недостатки вызывают отклонения в развитии детей замедляя и затрудняя процесс освоения знаковой действительности. При достаточной разработанности вопроса о языковом развитии детей с общим недоразвитием речи сведений об особенностях понимания и употребления ими других видов знаков недостаточно. В настоящее время общепризнано что помимо недостатков фонетического лексико-грамматического и синтаксического оформления высказываний речевая деятельность детей с ОНР характеризуется когнитивной слабостью...
75641. Использование невербальных средств общения в коррекционно-развивающей работе с дошкольниками с общим недоразвитием речи 56.67 KB
  Использование невербальных средств общения в коррекционно-развивающей работе с дошкольниками с общим недоразвитием речи Вестник Ленинградского государственного университета им. Изучение невербального общения детей с недоразвитием речи и определение коррекционно-развивающего эффекта невербальных средств общения является одной из актуальных проблем современной логопедии. Исследование было посвящёно определению значения невербальных средств общения в формировании базовых предпосылок речи у дошкольников с ОНР и разработке содержания научно...
75642. Цветообозначение в работе по развитию семантической стороны речи и обогащению эмоционального словаря детей с ОНР 1.12 MB
  Общечеловеческий родовой национально-культурный и индивидуально-психологический. Общечеловеческое значение цвета напрямую связано с его физическими характеристиками и определено способностью цвета оказывать воздействие на эмоции человека его состояние. Так выявлено что синий и зеленый цвета и их оттенки расслабляют успокаивают человека. Выявлено что светлые цвета максимально удалённые от чёрного преимущественно связаны с позитивными эмоциями; тёмные...
75643. Как понять себя и другого 7.47 MB
  Особое внимание следует обратить на подбираемую к текстам наглядность: она должна отражать мимику и пантомимику персонажей. Педагог обращает внимание детей на выражении лица и позу персонажей. Аналитичность просмотра подразумевает детальный разбор мимики позы жестов персонажей мультфильма. Используются разнообразные невербальные средства: экспрессивные выражающие эмоции и чувства персонажей; изобразительные имитирующие определённые действия персонажей; указательные и символические.
75644. Особенности невербального кодирования информации детьми с общим недоразвитием речи 25.54 KB
  Выраженность вариантов невербального кодирования информации Категория детей Варианты невербального кодирования Дети с нормальным х развитием речи в Дети с общим х недоразвитием речи в 4 г. В целом в ходе выполнения диагностического задания дети с общим недоразвитием речи гораздо реже чем их нормально развивающиеся сверстники могли правильно воспроизвести невербальный знак чаще отказывались от выполнения задания. Дети с ОНР могли справиться с заданием лучше если экспериментатор задавал наводящие вопросы подсказывал...