Основные положения. Порядок выполнения лабораторной работы

Порядок выполнения лабораторной работы

1. Создать таблицу (50 рабочих строк) в Excel аналогичную рис.1.

		Таблица расчета энтропии источника
№ п/п	Символ	Код символа	Число вхождений символа в текст	Вероятность вхождения символа (рi)	Ii
…	…
	Я
		Всего символов в тексте (K)
			Полная вероятность(Р)	(должна получиться «1»)
				Энтропия источника (I ср)

Рис.1.

2. Заполнить столбец Символ следующими значениями:

Ø 33 буквы русского алфавита;

Ø 10 цифр (0 — 9);

Ø Знаки препинания – «.», «,», «:», «;», «-», «», «(».

3. Заполнить столбец Код символа используя функцию «КОДСИМВ(…)», находящуюся в категории «Текстовые».

4. Открыв каскадом текст по варианту и таблицу и используя в Word «Правка Þ Заменить» заполнить столбец Число вхождений символа в текст. (Предполагается, что других символов в тексте НЕТ.) Сосчитать общее число символов.

5. По формулам заполнить столбцы «р_i» и «I_i». Сосчитать полную вероятность и энтропию источника.

6. Создать таблицу, аналогичную рис.2 и заполнить ее по формулам.

	Неопределенность	Разрядность кода	Абсолютная избыточность	Относительная избыточность
Стандартная кодовая таблица ASCII
Мера Хартли

Рис.2.

7. Выписать применяемые формулы с расшифровкой использыемых символов.

Содержание отчёта

1. Название и цель работы.

2. Заполненная таблица №1 для 50-ти символов.

3. Заполненная таблица №2.

4. Использованные формулы с определением переменных.

5. Выводы по работе соответственно цели лабораторной работы. Сравнительный анализ таблицы на рис.2.

Приложение к лабораторной работе «Определение количества информации, содержащегося в сообщении»

1. Общие сведения об информации.

Понятие «информация» происходит от латинского слова informatio - разъяснение, осведомление, изложение и обозначает одно из основных свойств материи. В рамках науки — информация — первичное, неопределенное понятие. Оно предполагает наличие материального носителя информации, источника информации, передатчика и т.п. Конкретное толкование элементов, связанных с понятием информации, связано с методологией конкретной области науки.

Можно выделить некоторые свойства информации, определяющие смысл этого понятия:

Ø Информация переносит знания об окружающем мире, которых в рассматриваемой точке не было до получения информации;

Ø Информация не материальна — она проявляется в форме материальных носителей — дискретных знаков, сигналов или функций времени;

Ø Информация может быть заключена в знаках или в их взаимном расположении;

Ø Знаки и сигналы несут информацию только для получателя, который может их распознать.

Термин «информация» имеет много определений. В широком смысле —

Информация — отражение реального мира.

Существует определение термина в узком смысле, применимого к предметной области автоматизированной обработки информации.

Информация — любые сведения, являющиеся объектом хранения, передачи и преобразования.

В процессе передачи информации важно определить следующие понятия:

Сообщение — информация, представленная в определенной форме и предназначенная для передачи. Сообщение представляется последовательностью знаков и сигналов.

Сигнал — процесс, несущий информацию. Таким образом, сигнал служит для переноса информации.

Знак — реально различимые получателем материальные объекты: буквы, цифры, предметы. Знаки служат для хранения информации.

Данные — информация, представленная в формализованном виде и предназначенная для обработки техническими средствами.

Таким образом, любой информационный процесс, может быть представлен как процесс передачи информации от объекта, являющегося источником информации, к получателю. Для обеспечения передачи информации необходим канал связи, некоторая физическая среда, через которую информация, представленная в виде сигналов, передается получателю.

Множество всех знаков и сигналов, использующееся для формирования сообщения, называется алфавит.

Размер (глубина) алфавита A определяется количеством символов, составляющих алфавит. Если считать, что сообщение передается одним знаком алфавита размером A, всего может быть передано N=А сообщений.

Из знаков алфавита может быть составлено слово. Если размер слова фиксировано и составляет n знаков, то количество возможных слов N составленных символов из алфавита А, таким образом, что каждый символ алфавита может входить в слово 0,1,2,…,n, раз определяется

N = А^n.

(1)

Таким образом, с помощью слов можно представить информацию о любом из N сообщений.

Выражение (1) позволяет определить размер слова из алфавита А, с помощью которого можно представить N сообщений

n=élogA Nù.

(2)

Мы можем сопоставить тому или иному сообщению комбинацию знаков, тогда при приеме сообщения, зная правила сопоставления, можно распознать сообщение.

Информация всегда представляется в виде сообщения, которое передается некоторой физической средой. Носителем сообщения выступает сигнал, выражающийся в изменении энергии среды передачи информации — канала связи. Для того, чтобы передать информацию по каналу связи необходимо сопоставить исходному сообщению некоторое правило изменения сигнала. Такое правило сопоставления называют кодированием.

Кодирование — представление сообщений в форме, удобной для передачи информации по каналам связи.

Естественно, можно говорить о кодировании на различных этапах передачи информации. Так, например, можно говорить о кодере источника, кодере канала связи и т.д. Принятое сообщение подвергается декодированию.

Декодирование — операция восстановления принятого сообщения. В системе связи необходимо ввести устройства кодирования и декодирования. Очевидно, что правила кодирования и декодирования в системе должны быть согласованы.

Важный вопрос теории передачи и преобразования информации — установление меры, количества и качества информации.

2. Математические меры информации.

Информационные меры, как правило, рассматриваются в двух аспектах синтаксическом и семантическом.

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

Структурные меры оценивают строение массивов информации и их измерение простым подсчетом информационных элементов или комбинаторным методом. Структурный подход применяется для оценки возможностей информационных систем вне зависимости от условий их применения.

При статистическом подходе используется понятие энтропии как ме­ры неопределенности, учитывающей вероятность появления и информативность того или иного сообщения. Статистический подход учитывает конкретные условия применения информационных систем.

Семантический подход позволяет выделить полезность или ценность информационного сообщения (в настоящем пособии не рассматривается).

При синтаксическом анализе информация определяется как мера уменьшения неопределенности знаний о каком-либо предмете в познавательном процессе. Если H₁ — исходная (априорная) неопределенность до передачи сообщения, а H₂ — остаточная (апостериорная) неопределенность, характеризующая состояние знания после получения сообщения, то содержащаяся в этом сообщении информация определяется их разностью

I=H₁ – H₂. (3)

Известно достаточно большое количество различных мер, различающихся подходом к определению неопределенности в (3). Далее рассматриваются только две из них — структурная аддитивная мера Хартли и вероятностная мера, называемая энтропия, предложенная К.Шенноном.

3. Структурная мера информации. Аддитивная мера Хартли.

Аддитивная мера (мера Хартли) использует понятия глубины А и длины n числа.

Глубина числа — количество символов (элементов), принятых для представления информации. В каждый момент времени реализуется только один какой-либо символ.

Длина n числа — количество позиций, необходимых и достаточных для представления чисел заданной величины.

Эти понятия могут быть распространены и на вариант нечислового сообщения. В этом случае глубина числа тождественна размеру алфавита, а длина числа — разрядности слова при передаче символьного сообщения.

Если сообщение — число, понятие глубины числа будет трансформировано в понятие основания системы счисления. При заданных глубине и длине числа количество чисел, которое можно представить, N = Аⁿ. Очевидно, что N однозначно характеризует степень исходной неопределенности. Исходная неопределенность по Хартли определяется

H₁ = log_a N. (4)

Неопределенность после получения сообщения, остаточная неопределенность,

H₂ = log_a N*, (5)

где N* — число возможных значений принятого слова после получения сообщения.

Основание логарифма в (5) определяет только единицы измерения неопределенности. При a=2 это двоичная единица информации, называемая бит. При a = 10 десятичная (дит), при a =e натуральная (нат). Далее мы будем всегда пользоваться двоичной единицей.

N* равно единице, если после получения информации нет неопределенности, т.е. получатель гарантировано получил то сообщение, которое было передано. Если получателю приходится после приема информации выбирать сообщения из некоторого множества, а это происходит тогда, когда в канале связи за счет влияния помех возникают искажения переданного сигнала, то характеризует число возможных сообщений при выборе. Таким образом, если передается символ некоторого алфавита, N* определяет возможную неоднозначность приема символа за счет искажений в канале связи. В случае измерительного опыта, число N* — характеризует число возможных значений величины после измерения и определяет погрешность измерения.

Очевидно, что должно быть N* < N, а N* = 1 только в идеальном случае передачи сообщения без потери информации или, что то же самое, измерения некоторой физической величины без ошибок. Количество информации по Хартли оценивается как

I=H₁ – H₂ = log_a N - loga N* n = log_a N/ N*. (6)

Логарифмическая мера, позволяющая, вычислять количество информации, содержащейся в сообщении, переданном числом длиной n и глубиной А:

I(q) =log₂ N=n log₂ А, бит. (7)

Следовательно, 1 бит информации соответствует одному элементарному событию, которое может произойти или не произойти. Такая мера количества информации удобна тем, что она обеспечивает возможность оперировать мерой как числом. Из сравнения (7) и (2) следует, что численное значение неопределенности определяет число двоичных разрядов, необходимое для кодирования символа алфавита А.

Логарифмическая мера для неопределенности и информации выбрана не случайно. Она оказывается удобной при описании сложных опытов. Допустим, что задача состоит в одновременном приеме информации от двух источников, не зависящих друг от друга. При этом N₁ и n₁ — число возможных сообщений до и после приема информации от первого источника, а — N₂ и n₂ от второго. Пусть H₁₁ и H₁₂ — исходная неопределенность знания первого и второго сообщения, соответственно, первого и второго источника. Естественно потребовать, чтобы общая неопределенность знания о двух сообщениях определялась суммой неопределенностей каждого, т.е. мера должна обладать свойством аддитивности

H = H₁₁ + H₁₂.

Число возможных сочетаний двух независимых величин из множеств N₁N₂ N = N₁ N₂.

Тогда исходная неопределенность H =H₁₁ + H₁₂,, аналогично остаточная неопределенность H=H₂₁+H₂₂.

При наличии нескольких источников информации общее количество информации

I(q₁, q₂,...,q_n)= I(q₁)+ I(q₂)+...+I(q_k), (8)

где I(q_k) — количество информации от источника k.

Логарифмическая мера информации позволяет измерять количество информации и широко используется на практике. Однако всегда надо учитывать, что все сообщения в этой мере полагаются равновероятными и независимыми. Эти допущения приводит на практике к существенно завышенным оценкам.

Примечание. Для рассмотрения дальнейшего материала необходимо использовать понятие «вероятность события». Под вероятностью события (см., например, Лютикас В.С. Факультативный курс по математике. Теория вероятностей. М.: Просвещение, 1990.) принимается постоянная величина, около которой группируются значения частоты появление некоторого события, например, передачи одного из символов алфавита. Если частота появления любого символа алфавита при передаче длинной последовательности символов одинакова, то говорят о равновероятных событиях, символах, сообщениях и т.п. Независимыми сообщения полагают, если вероятности их передачи не зависят от того, какие сообщения были переданы ранее.

4. Статистическая мера информации.

В статистической теории информации вводится более общая мера количества информации, в соответствии с которой рассматривается не само событие, а информация о нем. Этот вопрос глубоко проработан К. Шенноном в работе «Избранные труды по теории информации». Если появляется сообщение о часто встречающемся событии, вероятность появления которого близка к единице, то такое сообщение для получателя малоинформативное. Столь же мало информативны сообщения о событиях, вероятность появления которых близка к нулю.

События можно рассматривать как возможные исходы некоторого опыта, причем все исходы этого опыта составляют ансамбль, или полную группу событий. К. Шеннон ввел понятие неопределенности ситуации, возникающей в процессе опыта, назвав ее энтропией. Энтропия ансамбля есть количественная мера его неопределенности и, следовательно, информативности, количественно выражаемая как средняя функция множества вероятностей каждого из возможных исходов опыта.

Поясним содержание статистической меры на следующем частном случае. Пусть выполняется посимвольная передаче текста, состоящего из символов алфавита А. Текст составлен из K символов алфавита. Опыт состоит в передаче очередного символа текста. Так как в один момент времени может быть передан любой символ алфавита, всего возможно А исходов опыта. Очевидно, что одни символы в тексте будут появляться часто, а другие — реже. Различные символы несут разную информацию. Обозначим через k_i количество появления символа в тексте, а количество вносимой этим символом информации как I_i. Будем полагать, что передаваемые символы независимы, т.е. передача i –того символа происходит с вероятностью, независящей от того, какой символ был передан ранее. Это означает, информация, вносимая символом постоянна для любых сочетаний символов. Тогда средняя информация, доставляемая одним опытом,

I_ср = (k₁I₁+ k ₂I₂+…+ k _AI_A)/K. (9)

Но количество информации в каждом исходе связано с его вероятностью р_i, и выражается в двоичных единицах (битах) как

I_i = log₂ (1/p_i) = -log₂ p_i.

Тогда

I_ср =[ k ₁ (-log₂ p₁)+...+ k _A (-log₂ p_A)]/K. (10)

Выражение (10) можно записать также в виде

I_ср =k₁/K (-log₂ p₁)+...+k_A/K (-log₂ p_A). (11)

Но отношения n/K представляют собой частоты повторения исходов, а, следовательно, могут быть заменены их вероятностями:

p_i =k_i/K,

Тогда средняя информация в битах

I_ср = p₁ (-log₂ p₁)+...+p_A (-log₂ p_A),

или

I_ср =∑ p_i (-log₂ p_i) = H (12)

Полученную величину H называют энтропией. Энтропия обладает следующими свойствами:

1. Энтропия всегда неотрицательна, так как значения вероятностей выражаются величинами, не превосходящими единицу, а их логарифмы — отрицательными числами или нулем, так что члены суммы (12) — неотрицательны.

2. Энтропия равна нулю в том крайнем случае, когда одно из рi, равно единице, а все остальные — нулю. Это тот случай, когда об опыте или величине все известно заранее и результат не дает новую информацию.

3. Энтропия имеет наибольшее значение, когда все вероятности равны между собой:

р₁ = р₂ =... = p_i =1/A.

При этом H=- log₂(1/A)=log₂ A=H_max.

4. Энтропия объекта BC, состояния которого образуются совместной реализацией состояний B и C, равна сумме энтропии исходных объектов B и C, т. е. Н(BC) = Н(B) + Н(C).

Если все события равновероятны и статистически независимы, то оценки количества информации, по Хартли и Шеннону, совпадают. Это свидетельствует о полном использовании информационной емкости системы. В случае неравных вероятностей количество информации, по Шеннону, меньше информационной емкости системы. Максимальное значение энтропии достигается при р=0,5, когда два состояния равновероятны. При вероятностях р=0 или р=1, что соответствует полной невозможности или полной достоверности события, энтропия равна нулю.

Наибольшее количество информации получается тогда, когда полностью снимается неопределенность, причем эта неопределенность была наибольшей — вероятности всех событий были одинаковы. Это соответствует максимально возможному количеству информации, оцениваемому мерой Хартли:

I_x = log₂ N = log₂ (1/p) = - log₂ p =H_max,

где N — число событий; р — вероятность их реализации в условиях равной вероятности событий, H_max — максимальное значение неопределенности, равное энтропии равновероятностных событий.

Абсолютная избыточность информации D_авс представляет собой разность между максимально возможным количеством информации и энтропией:

D_авс = I_x - Н, или D_авс = Н_max -Н. (13)

Пользуются также понятием относительной избыточности

D = (Н_max -Н)/H_max. (14)

Рассмотренные информационные меры в полной мере применимы для оценки количества информации при передаче и хранении информации в вычислительных системах и цифровых системах связи. Если информация передается с использованием некоторого алфавита A то передачу каждого символа можно рассматривать как опыт, имеющий A возможных исходов. В длинном сообщении, например, при передаче текста размером K символов, различные символы алфавита могут появляться различное число раз. Мы можем говорить о частоте появления символов в сообщении, которая с увеличением K стремится к вероятности появления конкретного символа в сообщении.

Информационные меры имеют важное значение при определении характеристик памяти ЭВМ, пропускной способности каналов связи и во многих других приложениях информатики.

Лабораторная работа №4 «Кодирование дискретных источников информации методом Шеннона-Фано»

Цель работы

Освоить метод построения кодов дискретного источника информации используя конструктивный метод, предложенный К.Шенноном и Н.Фано. На примере показать однозначность раскодирования имеющегося сообщения.

Дата добавления: 2014-10-15