Реферат: Математическая система информации

Курс: «Теория информации и кодирования»

Тема: «МАТЕМАТИЧЕСКАЯ ТЕОРИЯ ИНФОРМАЦИИ»

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

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

Помехи

/>/>x1                                                                                           y1

x2                                                                                           y2

…<sub/>…

xn                                                      yn

Рис.1. Система передачи информации

 

Ансамбль сообщений — множество возможныхсообщений с их вероятностными характеристиками — {Х, р (х) }. При этом: Х={х1,х2,…, хm } — множество возможных сообщений источника;i = 1, 2,..., m, где m — объем алфавита; p (xi) — вероятностипоявления сообщений, причем p (xi) ³ 0 и поскольку вероятности сообщений представляютсобой полную группу событий, то их суммарная вероятность равна единице

/>.

Каждое сообщение несет в себе определенное количествоинформации. Определим количество информации, содержащееся в сообщении xi,выбранном из ансамбля сообщений источника {Х, р (х) }. Одним изпараметров, характеризующих данное сообщение, является вероятность егопоявления — p (xi), поэтому естественно предположить, чтоколичество информации I (xi) в сообщении xiявляется функцией p (xi). Вероятность появления двухнезависимых сообщений x1<sub/>и x2<sub/>равна произведению вероятностей p (x1, x2) = p (x1).p (x2), а содержащаяся в них информация должна обладатьсвойством аддитивности, т.е.:

I (x1, x2) = I (x1) +I (x2).(1)

Поэтому для оценки количества информации предложеналогарифмическая мера:

/>. (2)

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

logax = logbx/logba.

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

2 — [бит] (bynary digit — двоичная единица),используется при анализе ин-формационных процессов в ЭВМ и др. устройствах,функционирующих на основе двоичной системы счисления;

e — [нит] (natural digit — натуральная единица),используется в математических методах теории связи;

10 — [дит] (decimal digit — десятичная единица),используется при анализе процессов в приборах работающих с десятичной системойсчисления.

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

Среднее количество информации для всей совокупностисообщений можно получить путем усреднения по всем событиям:

/>. (3)

Количество информации, в сообщении, состоящем из n неравновероятных его элементов равно (эта мера предложена в 1948 г.К. Шенноном):

/>. (4)

Для случая независимых равновероятных событий количествоинфор-мации определяется (эта мера предложена в 1928 г.Р. Хартли):

/>. (5)

 

2. СВОЙСТВА КОЛИЧЕСТВА ИНФОРМАЦИИ

1. Количество информации в сообщении обратно-пропорциональновероятности появления данного сообщения.

2. Свойство аддитивности — суммарное количество информациидвух источников равно сумме информации источников.

3. Для события с одним исходом количество информации равнонулю.

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

Пример 1. Определить количество информации всообщении из 8 двоичных символов (n = 8, m = 2), если вероятностиравны: pi0 = pi1<sub/>= 1/2.

Количество информации равно:

I = n log m = 8 log2 2 = 8 бит.

 

Пример 2. Определить количество информации всообщении из 8 двоичных символов (n = 8, m = 2), если вероятностиравны:

pi0 = 3/4; pi1<sub/>=1/4.

Количество информации равно:

/>

 

3. ЭНТРОПИЯ ИНФОРМАЦИИ

 

Энтропия— содержательность, меранеопределенности информации.

Энтропия — математическое ожидание H (x) случайнойвеличины I (x) определенной на ансамбле {Х, р (х) }, т.е. онахарактеризует среднее значение количества информации, приходящееся на одинсимвол.

/>. (6)

Определим максимальное значение энтропии Hmax(x). Воспользуемся методом неопределенного множителя Лагранжа — l для отыскания условного экстремума функции[6]. Находим вспомогательную функцию:

/> (7)

Представим вспомогательную функцию F в виде:

/>. (8)

Найдем максимум этой функции

/>

т.к />.

Как видно из выражения, величина вероятности piне зависит от i, а это может быть в случае, если все pi<sub/>равны, т.е. p1 =p2 =… =pm =1/m.

При этом, выражение для энтропии равновероятных, независимыхэлементов равно:

/>. (9)

Рис.2. График энтропии для двух альтернативных событий

/>/>

Найдем энтропию системы двух альтернативных событий с вероятностямиp1 иp2. Энтропия равна

/>

При m= 2 для равновероятных событий pi  = 1/2 энтропияравна 1.  Изменение энтропии в зависимость от вероятности события  приведено нарис. 2. Как видно, максимум энтропии соответствует равновероятным событиям.

 

4. СВОЙСТВА ЭНТРОПИИ СООБЩЕНИЙ

1. Энтропия есть величина вещественная, ограниченная, неотрицательная, непрерывная на интервале 0 £ p £1.

2. Энтропия максимальна для равновероятных событий.

3. Энтропия для детерминированных событий равна нулю.

4. Энтропия системы двух альтернативных событий изменяетсяот 0 до 1.

Энтропия численно совпадает со средним количествоминформации но принципиально различны, так как:

H (x) — выражает среднюю неопределенность состоянияисточника и является его объективной характеристикой, она может быть вычисленааприорно, т.е. до получения сообщения при наличии статистики сообщений.

I (x) — определяется апостериорно, т.е. послеполучения сообщения. С по-лучением информации о состоянии системы энтропияснижается.

 

5. ИЗБЫТОЧНОСТЬ СООБЩЕНИЙ

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

/>, (10)

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

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

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

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

 

H (x) = log2m = log22 = 1 [дв. ед/симв.]

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

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

p (0) = 3/4, p (1) = 1/4.

 

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

/>

При этом избыточность равна

 

R = 1-0,815=0,18

 

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

Решение: Общее число пятибуквенных сообщений равно: N= mn<sup/>= 32

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

H = I = — log2 1/N = log2325 =5 log232 = 25 бит. /симв.

Литература

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

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

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

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

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

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