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

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


 

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

32423. Понятие Key Recovery 16.75 KB
  Key Recovery – технология восстановления ключей. Требование восстановления ключей является одним из важных для случая корпоративных сетей. В её качестве может служить центр перераспределения ключей который генерирует сеансовые ключи. Копии этих ключей могут сохраняться.
32424. Понятие ассиметричной криптографии, схемы её практического использования 103.05 KB
  2 При использовании АК каждый пользователь обладает парой ключей дополняющих друг друга ключей – открытым и личным. Каждый из входящих в пару ключей подходит для расшифровки сообщений зашифрованных с помощью другого ключа из пары.
32425. Алгоритм Диффи-Хэлмана, RSA 17.9 KB
  Основан на односторонней криптографической функции: P – простое число – тоже простое число. Пользователь А выбирает число Х B число Y. Число N опубликовывается P и Q держатся в тайне. Число целых чисел меньших N и взаимно простых по отношению к N.
32426. Контроль целостности, хэш-функции, российский стандарт хэш-функции 18.11 KB
  Поэтому на практике для контроля используется хэшфункция. Хэшфункция делится на 2 класса: с ключом и без ключа. Значение хэшфункции с ключом может вычислить лишь тот кто знает ключ.
32427. Понятие, стандарты, реализация электронной подписи 965.58 KB
  В симметричной криптографии существует проблема электронной подписи – необходимо чтобы получатель а в случае разбирательств и третья сторона могли убедиться в авторстве сообщения и его неизменности. Электронная подпись вводится так как необходимо: Предотвратить отказ от посланного сообщения Защититься от модификации присланного сообщения Предотвратить подделку сообщения Предотвратить отправку сообщения от чужого имени Предотвратить перехват сообщения с целью его модификации Предотвратить повтор сообщений Подпись создается с...
32428. Сертификаты, СА, SSL, аутентификация с помощью сертификатов 397.63 KB
  Структура сертификата: Оговаривается стандартом Х509 последняя3я версия которого появилась в 1996 году. Стандарт оговаривает следующие компоненты сертификата: Номер версии Уникальный порядковый номер Стандарты ЭЦП и хэшфункция используемые для подписи сертификата Имя субъекта и его организация. Для аннулирования сертификата необходимы следующие причины: потеря ЛК изменение места работы Внешнее коммерческое СА используется: Когда действительность ключа должна быть подтверждена доверенной 3й стороной Не хватает...
32429. Стеганография(СГ). Цифровые водяные знаки 18.79 KB
  форматы либо избыточность аудио графической информации. В первом случаем можно использовать для упрятывания информации зарезервированные поля компьютерного формата данных. : небольшое количество информации низкая степень скрытности. Виды стеганографии: Суррогатная – данные информации обычно шумят и необходимо заменять шумящие биты скрываемой информацией.
32430. Направления в области ЗИ от НСД , Показатели защищенности СВТ, порядок оценки класса защищенности СВТ, понятие и подсистемы АС , Классификация СВТ и АС по уровню защищенности от НСД 1.07 MB
  Первое связано с СВТ второе – с АС. СВТ – средства вычислительной техники. СВТ совокупность программ и технических элементов систем обработки данных способная функционировать как самостоятельно так и в составе других систем.
32431. Классификация СЗИ по уровню контроля отсутствия недекларируемых воздействий 20.5 KB
  Классификация распространяется на ПО предназначенное для защиты информации ограниченного доступа. Для ПО используемого при защите информации отнесенной к государственной тайне должен быть обеспечен уровень контроля не ниже третьего. Самый высокий уровень контроля первый достаточен для ПО используемого при защите информации с грифом ОВ. Второй уровень контроля достаточен для ПО используемого при защите информации с грифом CC.