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

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


 

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

3215. РЕДУКТОР КОСОЗУБИЙ ОДНОСТУПІНЧАТИЙ 550 KB
  Редуктором називають механізм, який складається з зубчастих або черв\'ячних передач, виконаний у вигляді окремого агрегату і служить для передачі обертання від вала двигуна до вала робочої машини. Кінематична схема приводу може включати, окрім редуктора, відкриті зубчасті передачі, ланцюгові або пасові передачі.
3216. Проектирование привода ленточного транспортера для конвейера 1002 KB
  Задание на курсовой проект. Кинематический расчет привода. Выбор электродвигателя. Мощность на выходе. Требуемая мощность электродвигателя. Частота вращения приводного вала редуктора. Определение обще...
3217. Совершенствование организации оценки и аттестации персонала на примере районного отдела народного образования г. Данкова Липецкой области 1.64 MB
  Введение Глава 1. Теоретико – методологические основы организации оценки и аттестации персонала 1.1. Деловая оценка персонала: подходы, понятие, виды, этапы 1.2. Методы деловой оценки персонала 1.3. Организация процесса аттестации персонала в г...
3218. Проектирование детали Вал-шестерня и ее технологические характеристики 959 KB
  Введение. Машиностроение – важнейшая отрасль промышленности. Его продукция – машины различного назначения поставляются всем отраслям народного хозяйства. Рост промышленности в значительной степени зависит от уровня развития машиностроения....
3219. Монтаж санитарно-технических кабин. Кладка столбов и простенков. Сварка швов в нижнем положение. 696.22 KB
  Монтаж санитарно-технических кабин. 1. Общая характеристика санитарно-технической кабины. В настоящее время в связи с массовым строительством крупноблочных и крупнопанельных зданий решают по-новому вопросы индустриализации монтажа санитарно-технич...
3220. Проект девятиэтажного жилого дома с подвалом 48.34 KB
  Введение В данной курсовой работе разработан проект девятиэтажного жилого дома с подвалом. Проект разработан в соответствии с заданием на проектирование. Объемно-планировочное конструкционное решение здания соответствует требованиям нормативной доку...
3221. Технологические харатеристики детали 532 KB
  Данная деталь называется «вал-шестерня» и служит для установки сопрягаемых деталей и передачи вращающего момента. Вал устанавливается в корпусе редуктора с помощью двух подшипников. Вращение передается через шпонку.
3222. Проектирование кулисного механизма 306.5 KB
  Одной из ведущих отраслей современной техники является машиностроение. По уровню развития машиностроения судят о развитии производительных сил в целом. Прогресс машиностроения в свою очередь определяется созданием новых высокопроизвод...
3223. Теория информационных процессов и систем 393 KB
  Теория информационных процессов и систем : методические указания к лабораторным работам № 1–4 для студентов специальности 071900 «Информационные системы и технологии» сост. А. В. Левенец. – Хабаровск : Изд-во Тихоокеанского гос. ун-та, 2...