89067

Алгоритмы решения задач на определение среднего количества информации

Контрольная

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

Провести кодирование по одной и блоками по две буквы, используя метод Шеннона-Фано. Сравнить эффективности кодов (величина энтропии). Данные взять из задачи 1. Алфавит передаваемых сообщений состоит из независимых букв Si. Вероятности появления каждой буквы в сообщении заданы.

Русский

2015-05-09

120.96 KB

39 чел.

МИНОБРНАУКИ РОССИИ

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

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

«Пензенский государственный технологический университет»

(ПензГТУ)

Факультет «Информационных и образовательных технологий»

Кафедра «Информационные технологии и системы»

Дисциплина «Основы теории информации»

КОНТРОЛЬНАЯ РАБОТА №1

Выполнил: студент группы 13ИС2Б

Чинков М.Ю.

Проверил: ст. преподаватель каф. ИТС

Пискаев К.Ю.

Пенза 2015

СОДЕРЖАНИЕ

ВВЕДЕНИЕ 3

1. ОПРЕДЕЛЕНИЕ СРЕДНЕГО КОЛИЧЕСТВА ИНФОРМАЦИИ 4

2. ЗАВИСИМОСТЬ МЕЖДУ СИМВОЛАМИ МАТРИЦЫ УСЛОВНЫХ ВЕРОЯТНОСТЕЙ 5

3. КОДИРОВАНИЕ МЕТОДОМ ШЕННОНА-ФАНО 6

4. КОДИРОВАНИЕ АЛГОРИТМОМ ХАФФМАНА 8

5. ПРОПУСКНАЯ СПОСОБНОСТЬ КАНАЛА СВЯЗИ 11

заключение 12

список литературы 13


ВВЕДЕНИЕ

Цель данной контрольной работы – актуализация знаний в предмете «Основы теории информации».

В рамках контрольной работы было выполнено 5 заданий в соответствии с моим вариантом (вариант №23):

  1.  Определить среднее количество информации, содержащееся в сообщении, используемом три независимых символа S1, S2, S3. Известны вероятности появления символов p(S1)=p1, p(S2)=p2, p(S3)=p3. Оценить избыточность сообщения.
  2.  В условии предыдущей задачи учесть зависимость между символами, которая задана матрицей условных вероятностей P(Si / Sj).

3.  Провести кодирование по одной и блоками по две буквы, используя метод Шеннона – Фано. Сравнить эффективности кодов (величина энтропии). Данные взять из задачи 1.

4.  Алфавит передаваемых сообщений состоит из независимых букв Si. Вероятности появления каждой буквы в сообщении заданы. Определить и сравнить эффективность кодирования сообщений методом Хаффмана при побуквенном кодировании и при кодировании блоками по две буквы.

5.  Определить пропускную способность канала связи, по которому передаются сигналы Si. Помехи в канале определяются матрицей условных вероятностей P(Si / Sj). За секунду может быть передано N = 10 сигналов.

Простые вычисления и кодирования сообщений в заданиях были сделаны вручную, более сложные были сделаны с помощью среды разработки MATLAB R2014a. Формулы и решения задач были введены с помощью программы MathType.


  1.  ОПРЕДЕЛЕНИЕ СРЕДНЕГО КОЛИЧЕСТВА ИНФОРМАЦИИ

Энтропия источника – среднее количество информации в одном сообщении. Не следует путать энтропию с количеством информации в одном конкретном сообщении. Если в источнике есть множество сообщений, точно знать о каждом из них необязательно. В этом заключается преимущество среднего значения количества информации. Усреднение позволило Шеннону оценить как редкие, так и частые сообщения. Энтропия характеризует источник сообщения. Аналогично можно получить и “энтропийную характеристику сигнала”.

Задание: определить среднее количество информации, содержащееся в сообщении, используемом три независимых символа S1, S2, S3. Известны вероятности появления символов p(S1)=p1, p(S2)=p2, p(S3)=p3. Оценить избыточность сообщения. Вариант №23: p1=0.12; p2=0.13; p3=0.75.

Решение. Максимальное среднее количество информации на символ сообщения имеет место при равновероятном распределении и равно, согласно формуле.

Рассчитаем среднее количество информации на символ сообщения при заданных вероятностях по формуле, где n – число символов в алфавите, p – вероятность появления события.

Оценим избыточность сообщения по формуле.

Максимальная энтропия.

Реальная энтропия.

Избыточность сообщения.


  1.  ЗАВИСИМОСТЬ МЕЖДУ СИМВОЛАМИ МАТРИЦЫ УСЛОВНЫХ ВЕРОЯТНОСТЕЙ

В большинстве реальных случаев появление элемента хi в сообщении зависит от того, какой элемент хj был предшествующим. Взаимосвязь элементов в сообщении характеризуется матрицей условных вероятностей.

Задание: в условии предыдущей задачи учесть зависимость между символами, которая задана матрицей условных вероятностей P(Si / Sj).

Вариант №23.

 

Решение. Рассчитаем энтропию источника по формуле.

Подставим числовые данные, используя задание 1.

Вычисление энтропии в программе MATLAB.

H2=p1*((0.7*log2(0.7)+0.3*log2(0.3)))+p2*((0.5*log2(0.5)+0.5*log2(0.5))++p3*(-(0.1*log2(0.1)+0.5*log2(0.5)+0.4*log2(0.4)));


  1.  КОДИРОВАНИЕ МЕТОДОМ ШЕННОНА-ФАНО

Кодирование Шеннона — Фано (англ. Shannon–Fano coding) — алгоритм префиксного неоднородного кодирования. Относится к вероятностным методам сжатия (точнее, методам контекстного моделирования нулевого порядка). Алгоритм Шеннона — Фано использует избыточность сообщения, заключённую в неоднородном распределении частот символов его (первичного) алфавита, то есть заменяет коды более частых символов короткими двоичными последовательностями, а коды более редких символов — более длинными двоичными последовательностями. Алгоритм был независимо друг от друга разработан Шенноном (публикация «Математическая теория связи», 1948 год) и, позже, Фано (опубликовано как технический отчёт).

Задание: провести кодирование по одной и блоками по две буквы, используя метод Шеннона – Фано. Сравнить эффективности кодов (величина энтропии). Данные взять из задачи 1.

Решение. Проведем кодирование методом Шеннона–Фэно и рассчитаем характеристики кода. Пусть исходный алфавит состоит из трех (по одной букве) и девяти (по две буквы) букв и заданы их вероятности. Проведем разбиения по алгоритму Шеннона–Фэно и составим кодовые комбинации.

xi

P(xi)

1

2

3

4

P3

0.75

0

0

1

P2

0.13

0

0

0

1

P1

0.12

0

0

0

0

Кодовые комбинации по одной букве.


xi

P(xi)

1

2

3

4

5

p3p3

0.5625

1

1

p3p2

0.0975

1

0

p2p3

0.0975

0

1

1

p3p1

0.09

0

1

0

p1p3

0.09

0

0

1

1

p2p2

0.0169

0

0

1

0

p2p1

0.0156

0

0

0

1

p1p2

0.0156

0

0

0

0

1

p1p1

0.0144

0

0

0

0

0

Кодовые комбинации по две буквы.

Рассчитаем энтропию по формуле.

Рассчитаем среднюю длину кодовой комбинации по формуле.

Рассчитаем эффективность кода, согласно формуле. 

Энтропия источника. По одной букве:

По две буквы:

 Средняя длина кодовой комбинации источника. По одной букве:

По две буквы:

Эффективность кода. По одной букве:

По две буквы:

  1.  КОДИРОВАНИЕ АЛГОРИТМОМ ХАФФМАНА

Один из первых алгоритмов эффективного кодирования информации был предложен Д. А. Хаффманом в 1952 году. Идея алгоритма состоит в следующем: зная вероятности символов в сообщении, можно описать процедуру построения кодов переменной длины, состоящих из целого количества битов. Символам с большей вероятностью ставятся в соответствие более короткие коды. Коды Хаффмана обладают свойством префиксности (то есть ни одно кодовое слово не является префиксом другого), что позволяет однозначно их декодировать. Классический алгоритм Хаффмана на входе получает таблицу частот встречаемости символов в сообщении. Далее на основании этой таблицы строится дерево кодирования Хаффмана (Н-дерево).

Задание: алфавит передаваемых сообщений состоит из независимых букв Si. Вероятности появления каждой буквы в сообщении заданы. Определить и сравнить эффективность кодирования сообщений методом Хаффмена при побуквенном кодировании и при кодировании блоками по две буквы. Вариант №23: (0,8;0,0;0,08;0,12).

Решение. Проведем кодирование методом Шеннона–Фэно.

xi

P(xi)

1

2

3

p1

0.8

1

p4

0.12

0

1

p3

0.08

0

0

1

p2

0

0

0

0

По одной букве.

xi

P(xi)

P1p1

0.64

P4p1

0.096

P1p4

0.096

P3p1

0.064

P1p3

0.064

P4p4

0.0144

P4p3

0.0096

P3p4

0.0096

P3p3

0.0064

P4p2

0

P2p4

0

P3p2

0

P2p3

0

P2p1

0

P1p2

0

P2p2

0

По две буквы.

Проведем кодирование по методу Хаффмена. Исходный алфавит состоит из нескольких букв с заданными вероятностями. Составим таблицу.

xi

P(xi)

Вспомогательный столбец

p1

0.8

0.8

p4

0.12

0.2

p3

0.08

p2

0

По одной букве.

xi

P(xi)

Вспомогательные столбцы

P1p1

0.64

0.64

P4p1

0.096

0.096

0.192

0.36

P1p4

0.096

0.096

0.168

P3p1

0.064

0.064

0.128

P1p3

0.064

0.064

0.040

P4p4

0.0144

0.0144

P4p3

0.0096

0.0096

0.0256

P3p4

0.0096

0.0160

P3p3

0.0064

P4p2

0

P2p4

0

P3p2

0

P2p3

0

P2p1

0

P1p2

0

P2p2

0

По две буквы.

Характеристики кода рассчитываются по тем же формулам, что и для кода Шеннона–Фано.

Рассчитаем энтропию по формуле.

Рассчитаем минимальную среднюю длину кодовой комбинации по формуле.

Рассчитаем эффективность кода, согласно формуле. 

Энтропия источника. По одной букве:

По две буквы:

Средняя длина кодовой комбинации источника. По одной букве:

По две буквы:

Эффективность кода. По одной букве:

По две буквы:


  1.  ПРОПУСКНАЯ СПОСОБНОСТЬ КАНАЛА СВЯЗИ

Пропускная способность — метрическая характеристика, показывающая соотношение предельного количества проходящих единиц (информации, предметов, объёма) в единицу времени через канал, систему, узел. В информатике определение пропускной способности обычно применяется к каналу связи и определяется максимальным количеством переданной или полученной информации за единицу времени.

Задание: Определить пропускную способность канала связи, по которому передаются сигналы Si. Помехи в канале определяются матрицей условных вероятностей P(Si / Sj). За секунду может быть передано N = 10 сигналов.

Вариант №23.

 

Решение. Рассчитаем условную энтропию по формуле.

Рассчитаем пропускную способность канала связи по формуле.

Условная энтропия.

Пропускная способность канала связи.


заключение

В рамках контрольной работы были изучены различные алгоритмы решения задач на определение среднего количества информации, содержащейся в сообщении, определение пропускной способности канала связи и алгоритмы кодирования сообщений (метод Шеннона-Фано, алгоритм Хаффмана).

Было выполнено 5 заданий:

1. Определить среднее количество информации, содержащееся в сообщении, используемом три независимых символа S1, S2, S3. Известны вероятности появления символов p(S1)=p1, p(S2)=p2, p(S3)=p3. Оценить избыточность сообщения.

2. В условии предыдущей задачи учесть зависимость между символами, которая задана матрицей условных вероятностей P(Si / Sj).

3.  Провести кодирование по одной и блоками по две буквы, используя метод Шеннона – Фано. Сравнить эффективности кодов (величина энтропии). Данные взять из задачи 1.

4.  Алфавит передаваемых сообщений состоит из независимых букв Si. Вероятности появления каждой буквы в сообщении заданы. Определить и сравнить эффективность кодирования сообщений методом Хаффмана при побуквенном кодировании и при кодировании блоками по две буквы.

5.  Определить пропускную способность канала связи, по которому передаются сигналы Si. Помехи в канале определяются матрицей условных вероятностей P(Si / Sj). За секунду может быть передано N = 10 сигналов.

Простые вычисления и кодирования сообщений в заданиях были сделаны вручную, более сложные были сделаны с помощью среды разработки MATLAB R2014a. Формулы и решения задач были введены с помощью программы MathType.

список литературы

  1.  Зверева Е.Н. Сборник примеров и задач по основам теории информации и кодирования сообщений/ Е.Н. Зверева, Е.Г.Лебедько. – СПб: НИУ ИТМО, 2014. – 76 с.
  2.  Калинцев С.В. Методические указания к контрольной работе по курсу «Теория кодирования»/ С.В.Калинцев. –2012. – 20 с.


 

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

79518. Главные направления и цели деятельности школьной психологической службы 32.56 KB
  Психопрофилактика предполагает: Ответственность за соблюдение в образовательных учреждениях психологических условий необходимых для полноценного психического развития и формирования личности на каждом возрастном этапе: Своевременное выявление таких особенностей ребенка которые могут привести к определенным сложностям отклонениям в интеллектуальном и эмоциональном развитии в поведении и отношениях; Предупреждение возможных осложнений в связи с переходом на следующую возрастную ступень.Психодиагностика это изучение особенностей...
79519. Основные принципы деятельности педагога-психолога 29.62 KB
  Принцип индивидуального подхода к учащемуся основной принцип работы практического психолога в его основе лежат понимание и признание индивидуальности человека как ценности как уникального явления. Принцип целостности предполагает что деятельность психолога и психологической службы образовательного учреждения должна быть ориентирована на целое на систему. Это означает что внимнием психолога должно быть охвачено большинство учащихся.
79520. Этические принципы деятельности психолога 31.11 KB
  Укрепление авторитета психологической службы образования среди обучающихся воспитанников родителей и педагогической общественности. Принцип квалификационной пропаганды психологии.Информация полученная психологом в процессе проведения работы не подлежит сознательному или случайному разглашению а в ситуации необходимости передачи ее третьим лицам должна быть представлена в форме исключающей ее использование против интересов клиента.
79521. Психологическая служба как отрасль прикладной психологии. Роль психологической службы в образовании 31.88 KB
  Государственная ПСО – структура призванная в рамках общей концепции соблюдения прав ребенка на достойный уровень жизни и полноценное психическое развитие обеспечить психологическую поддержку воспитания и образования оказать квалифицированную помощь при наличии проблем и отклонений в развитии ребенка Развитие практической психологии в 1990 гг. в значительной степени обусловило гуманизацию системы образования что способствовало постановке и решению следующих задач: Переход от унифицированного образования к вариативному; Переход от...
79522. Концепция школьной психологической службы Л.М. Фридмана 31.7 KB
  Фридмана цели школьной психологической службы должны соответствовать главной цели школы на современном этапе воспитание каждого ученика образованной культурной высоконравственной творчески активной и социально зрелой личностью. Поэтому главной целью школьной психологической службы является научное психологическое обеспечение учебновоспитательного процесса в школе т. Утверждается что главная функция психологической службы образования профессиональная забота о психологическом здоровье детей.
79523. Объединение Русских земель Москвы (14-первая половина 16 веков) 21.07 KB
  Объединение Руси начавшийся в XIV XV веках процесс объединения раздробленных русских земель вокруг нескольких новых политических центров приведший в конечном итоге к образованию централизованного Русского государства и его последующему возобладанию над внешними политическими конкурентами за земли Руси. Объединение Северовосточной Руси завершилось в правление Ивана III присоединение Новгорода 1478 Твери 1485 ликвидация формальной автономии Пскова 1510 и Рязани 1521. Он принял титул государя всея Руси...
79524. Начало эпохи великих географических открытий и первые колониальные захваты. Новое время как особая фаза всемирно исторического процесса 22.1 KB
  Новое время или новая история период в истории человечества находящийся между Средневековьем и Новейшим временем. Критерием определения нового времени его новизны по сравнению с предшествующей эпохой был с точки зрения гуманистов расцвет в период Ренессанса светской науки и культуры то есть не социальноэкономический а духовнокультурный фактор. Однако этот период довольно противоречив по своему содержанию: Высокое Возрождение Реформация и гуманизм соседствовали с массовым всплеском иррационализма развитием демонологии...
79525. Реформация и ее экономические, политические и социокультурные причины. Религиозные войны в Европе 21.7 KB
  С одной стороны католический мир который объединял все народы Западной Европы под духовным руководством папы римского прекратил существование. С другой стороны национальные церкви способствовали росту национального сознания народов Европы. При этом существенно повысился культурный и образовательный уровень жителей Северной Европы которая до этого была как бы окраиной Христианского Мира необходимость изучения Библии приводила к росту как начальных учебных заведений в основном в форме церковноприходских школ так и высших что...
79526. Государство и общество стран Западной Европы в 17 веке 21.34 KB
  Их концептуальным выражением и итогом стали теории естественного права и общественного договора основанные на рационализме. Теория естественного права явилась классическим воплощением нового мировоззрения. Теория естественного права основана на признании всех людей равными от природы и наделенными природой же естественными страстями стремлениями разумом. Законы природы определяют предписания естественного права которому должно соответствовать положительное позитивное волеустановленное право.