Измерение количества информации

Размещено на http://www.allbest.ru/

Содержание

Введение

1. Меры информации, количество информации

2. Определение количества информации по Шеннону

3. Энтропия

4. Избыточность сообщений, примеры и решения

Заключение

Список использованных материалов



Введение

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

В пункте 1 под названием "Меры информации, количество информации", я хочу описать существующие меры информации, как измеряется количество информации, с помощью каких формул.

В данном пункте 2 я хочу рассмотреть каким образом определяют количество информации и по каким формулам, введенными замечательным ученым Клодом Шенноном.

В пункте 3 данной работы под названием "Энтропия". В данном пункте я хочу рассмотреть понятие энтропии, ее свойства, и способы нахождения.

В последнем, 4 пункте, под названием "Избыточность сообщений, примеры и решения" я хочу рассмотреть, что такое избыточность, а так же привести примеры решения задач на эту тему.



1. Меры информации, количество информации

Комбинаторное определение количества информации дано американским инженером Р. Хартли. Это определение предполагает модель с детерминированной связью (помехи отсутствуют) между дискретными состояниями двух систем без их вероятностного описания.

До получения сведений о состоянии системы имеется априорная неопределенность её состояния. Сведения позволяют снять эту неопределённость, то есть определить состояние системы. Поэтому количество информации можно определить как меру снятой неопределённости, которая растёт с ростом числа состояний системы.

Количественная мера информации устанавливается следующими аксиомами. количество информация энтропия шеннон

Аксиома 1. Количество информации, необходимое для снятия неопределённости состояния системы, представляет собой монотонно возрастающую функцию числа состояний системы.

В качестве количественной меры информации можно выбрать непосредственно число состояний системы m_x, которое является единственной характеристикой множества X.

Однако такое определение неудобно с точки зрения его практического применения. Поэтому в теории информации вводится несколько иная количественная мера информации, которая является функцией m_x. Вид указанной функции позволяет установить аксиома 2.

Аксиома 2. Неопределённость состояния сложной системы, состоящей из двух подсистем, равна сумме неопределённостей подсистем.

Если для снятия неопределённости первой подсистемы необходимо количество информации, равное I(т ₁), а для второй подсистемы количество информации, равное I(m₂), то для снятия неопределённости сложной системы необходимо количество информации, равное:

I(m₁m₂) = I(m₁) + I(m₂),

где т ₁ - число состояний первой подсистемы; т ₂ - число состояний второй подсистемы; т ₁ т ₂ - число состояний сложной системы.

Единственным решением полученного функционального уравнения является логарифмическая функция:

I(т)=К log_a m,

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

Произвольный коэффициент К выбирается равным единице, а основание логарифма а определяет единицу измерения количества информации. В зависимости от значения а единицы измерения называются двоичными (а=2), троичными (а=3) и в общем случае а-ичными. В дальнейшем под символом log будем понимать двоичный логарифм (log m = log₂ m), под символом lg - десятичный логарифм (lg m = log₁₀ m), а под символом ln - натуральный логарифм (ln m = log_e m). Двоичная единица иногда обозначается bit (от английского binary digit - двоичная цифра).

Каждое передаваемое слово из n букв, записанное в алфавите, содержащем т букв, можно рассматривать как отдельное "укрупнённое" состояние источника сообщений. Всего таких состояний (слов) будет m?n. Тогда количество информации, которое несёт слово из n букв, равно I = log_a mn=n log_a m. Отсюда следует, что одна буква несёт log_a m а-ичных единиц информации. Если единица измерения информации a=т, то количество информации в слове (I=n) измеряется количеством содержащихся в нём букв, а единица измерения информации определяется размером алфавита т. Таким образом, одна a-ичная единица содержит log_a m a-ичных единиц информации.

2. Определение количества информации по Шеннону

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

Величина количества информации была введена в 1948 году Клодом Шенноном на примере текстового сообщения. Количество информации в сообщении, содержащем n символов I_n, по Шеннону равно:

(1)

где M - число букв в алфавите, p_i - частота встречаемости i-ой буквы в языке, на котором написано сообщение, знак "- " перед всей правой частью формулы поставлен для того, чтобы I_i была положительной, несмотря на то, что log₂ p_i < 0 (p_i<1). Двоичные логарифмы выбраны для удобства. При однократном бросании монеты М=2 ("орёл" или "решка"), n = 1 и pi =¹/₂. При этом получаем минимальное количеств информации (I=1), которое называется "бит" От англ. binary digit - двоичная цифра.. Иногда в (1) используются натуральные логарифмы. Тогда единица информации называется "нат" От англ. natural digit - натуральная цифра. и связана с битом соотношением: 1 бит = 1,44 ната.

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

В этом примере текст можно рассматривать как результат выбора определённого варианта расстановки букв.

В общем случае, когда делается выбор одного варианта из n возможных (реализующихся с априорной вероятностью p_i i=1, 2, ..., n), количество информации выражается формулой:

(2)

Если все варианты равновероятны, то есть p_i =¹/_n, то, I = log₂ n.

В частном случае сообщения из n букв из бинарного алфавита (М=2) число вариантов равно: k = 2ⁿ, количество информации I = n, что совпадает с формулой (1).

На этом примере удобно пояснить, что означает слово "равноправные" в определении "информация есть запомненный выбор одного варианта из нескольких возможных и равноправных". Представим, что в тексте имеются символы, которые в алфавите вообще не содержатся (не "буквы"). Априорная вероятность такового считается очень малой (pn+1 " ¹/_n) и в сумме (2) не учитывается, поскольку он выпадает из рассматриваемого множества.

Отметим, что формула (2) отражает количество информации, но не ценность её.

Поясним это на примере. Количество информации в сообщении, определяемое формулой Шеннона, не зависит от того или иного сочетания букв: можно сделать сообщение бессмысленным, переставив буквы. В этом случае ценность информации исчезнет, а количество информации останется прежним. Из этого примера следует, что подменять определение информации (с учётом всех её качеств) определением количества информации нельзя.

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

Обсудим в связи с количеством информации ещё два понятия: "Информационная тара" и "Информационная ёмкость". Первый связан с мощностью множества, из которого выбираются варианты. Второй используется для физических систем, способных хранить информацию. По смыслу они близки друг другу.

Поясним смысл их на примере текста. Если любое сочетание букв в тексте является ценным, то количество ценной информации совпадает с полным количеством, но не может превышать его. Это значит, что любая передача сигналов и-или запоминающее устройство может содержать какое-то количество ценной (или осмысленной) информации [не больше, чем (3.2)], но может содержать и меньшее или не содержать вовсе. В этой связи количество информации в (3.2) можно назвать информационной тарой. Это понятие играет существенную роль при рецепции информации и-или при обработке её (в частности при перекодировке).

Пример. Имеется текст на русском языке, содержащий n_r букв кириллицы (алфавит содержит 32 буквы). Перевод его на английский содержит n_a букв латинского алфавита (26 букв). Русский текст - результат выбора определённого варианта из n_r возможных (число вариантов порядка ). Английский перевод - выбор определённого расположения латинских букв, который предопределён русским текстом (рецепция информации). Число вариантов в английском текста порядка . Количество ценной информации одинаково (если смысл не искажен), а количество информации различно.

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

Допустим, некоторое устройство вырабатывает (генерирует) число как независимую последовательность из единиц и нулей, которые появляются соответственно с вероятностями, равными p и q=1-р. В этом случае при неограниченном возрастании длины последовательности n с вероятностью, равной единице, появляются последовательности, количество единиц в которых незначительно отличается от среднего значения, равного пр. Такие последовательности называются типичными. Они различаются между собой только размещением единиц, а не их количеством. Поскольку количество типичных последовательностей Q меньше общего количества последовательностей, то имеется возможность уменьшить количество информации, необходимое для определения числа.

Последовательность назовём типичной для заданного источника, если количество единиц п ₁ в ней удовлетворяет неравенству:

или |п ₁ - np| < n? (3)

и нетипичной в противном случае, то есть когда:

|п ₁ - np| ? n? (4)

Вероятность появления нетипичной последовательности равна вероятности, с которой п ₁ удовлетворяет неравенству (3.4). Для оценки этой вероятности воспользуемся неравенством Чебышева, которое для произвольной случайной величины ? имеющей конечную дисперсию, при каждом b>0 записывается в виде:

,

где ? и - соответственно математическое ожидание и дисперсия случайной величины ?. Полагая ? = n₁, ? = n₁ = np, b = ?n, , [q = (1-p)]получим аналогичное неравенство для случайного числа единиц n₁:

.

Следовательно, вероятность появления нетипичной последовательности:

,

а вероятность появления типичной последовательности:

.

Вероятность Р_HT>0, а вероятность Р_T>1 при любом сколь угодно малом значении ? и неограниченном возрастании длины последовательности п. Интервал [?n?, n?], которому принадлежит количество единиц в типичной последовательности, неограниченно увеличивается (n?>?) хотя относительная величина интервала всегда меньше значения ?. Докажем, что одновременно с неограниченным увеличением длины последовательности n можно уменьшать значение ?=?(n) с такой скоростью, при которой относительная величина интервала будет стремиться к нулю, а вероятность появления типичной последовательности - к единице. При этом абсолютная величина интервала по-прежнему неограниченно возрастает. Вероятность Р_T стремится к единице, если величина ?²(n)·n неограниченно увеличивается с ростом n. Пусть ?²(n) n=n^2?, где ?>0 некоторый параметр, определяющий скорость роста величины ?²(n) n. Отсюда:

?(n) = n^{?0,5+ ?} (0<?<0,5).

Величина ?(n) стремится к нулю с ростом n при ?<0,5. При этом абсолютная величина интервала n·?(n) не может быть постоянной или стремиться к нулю одновременно с неограниченным увеличением величины ?²(n)·n, стремлением ?(n) к нулю.

Определим количество типичных последовательностей Q. Вероятность появления произвольной последовательности B_k равна:

В результате тождественных преобразований получим:

.

Прологарифмировав последнее равенство, получим:



где величина H(x) = - plog_mp-qlog_mq является характеристикой источника сообщений и называется энтропией.

3. Энтропия

Величина, характеризующая количество неопределенности в теории информации обозначается символом H и имеет название энтропия, точнее информационная энтропия.

Энтропия (H) - мера неопределенности, выраженная в битах. Так же энтропию можно рассматривать как меру равномерности распределения случайной величины.

Величина:

H(x) = - plog_mp - qlog_mq

является характеристикой источника сообщений и называется энтропией.

Покажем, что в случае типичных последовательностей остаточным членом O(n) по сравнению с величиной H(X) можно пренебречь.

Поскольку для типичных последовательностей справедливо неравенство |n₁-np|<n?, то:

Следовательно,

Таким образом, при достаточно большом n справедливо приближённое равенство:

Отсюда вероятность появления отдельной типичной последовательности:

P(B_k) ? m^-nH(X).

Поскольку правая часть равенства не зависит от номера типичной последовательности k, то все типичные последовательности примерно равновероятны. Вероятность появления типичной последовательности:

где суммирование ведётся по Q последовательностей. Отсюда,

Q = m^nH(X),

причём единица измерения энтропии Н(X) совпадает с основанием степени m. Поскольку количество информации, нужное для определения числа (состояния регистра), равно log Q, энтропия:

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

Аналогично определяется количество типичных последовательностей, вырабатываемых источником с алфавитом размера m_X, только в этом случае энтропия:

Энтропия:

поскольку p_i удовлетворяет неравенству 0 p_i 1. Энтропия H(Х)=0, когда система находится в одном из состояний с вероятностью, равной единице, и во всех остальных - с вероятностью, равной нулю. При этом имеется в виду, что:

При равномерном распределении:

(p_i = 1/m_X)

H(X) = log m_x.

Докажем, что это максимальное значение энтропии. Используя равенство , можно выполнить следующие тождественные преобразования:

.

для оценки выражения воспользуемся неравенством ln z z-1, положив:

.

Заменяя на , получим:

где H(X) = log mX.

Пусть множество Х состоит из двух элементов, которые обозначим через единицу и ноль, причём единица позволяется с вероятностью, равной p, а ноль - с вероятностью, равной q=1-р. Тогда,

H(X) = - p log p - (1-p) log(1-p).

Указанная зависимость изображена на рис. 1. Максимум достигается при p=q=0,5.

Рис. 1. Энтропия системы с двумя состояниями: p - вероятность одного из состояний

4. Избыточность сообщений, примеры и решения

Одной из информационных характеристик источника дискретных сообщений является избыточность, которая определяет, какая доля максимально-возможной энтропии не используется источником:

, (10)

где - коэффициент сжатия.

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

Пример 1. Вычислить энтропию источника, выдающего два символа 0 и 1 с вероятностями p(0) = p(1) = 1/m и определить его избыточность.

Решение: Энтропия для случая независимых, равновероятных элементов равна:

H(x) = log₂m = log₂2 = 1 [дв.ед/симв.]

При этом H(x) = H_max(x) и избыточность равна R = 0.

Пример 2. Вычислить энтропию источника независимых сообщений, выдающего два символа 0 и 1 с вероятностями p(0) = 3/4, p(1) = 1/4.

Решение: Энтропия для случая независимых, не равновероятных элементов равна:

При этом избыточность равна R = 1-0,815=0,18.

Пример 3. Определить количество информации и энтропию сообщения из пяти букв, если число букв в алфавите равно 32 и все сообщения равновероятные.

Решение: Общее число пятибуквенных сообщений равно: N = mⁿ = 32.

Энтропия для равновероятных сообщений равна:

H = I = -log₂ 1/N = log₂32⁵ = 5 log₂32 = 25 бит./симв.



Заключение

В данной работе я постаралась раскрыть все вопросы данной темы. Свой реферат я разбила на 4 пункта. В своей работе я использовала новые для себя понятия и определения, несколько новых формул, рассмотрела примеры и решения некоторых задач по данной теме, а так же использовала 6 новых для себя источников информации. Кроме книг, дополнительно были использованы интернет источники.

Данный реферат состоит из 13 страниц, полностью пронумерован и записан в соответствии с содержанием реферата.



Список использованных материалов

1. Гринченко А.Г. Теория информации и кодирование: Учебн. пособие. - Харьков: ХПУ, 2000.

2. Цымбал В.П. Теория информации и кодирование. - М.: Высш. шк., 1986.

3. Кловский Д.Д. Теория передачи сигналов. - М.: Связь, 1984.

4. Кудряшов Б.Д. Теория информации. Учебник для вузов Изд-во ПИТЕР, 2008. - 320 с.

5. Цымбал В.П. Теория информации и кодирование. - М.: Высш. шк., 1986.

6. Асанов М.О., Баранский В.А., Расин В.В. Дискретная математика: графы матроиды, алгоритмы. - Ижевск: НИЦ "РХД", 2001, 288 стр.

Размещено на Allbest.ru