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

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

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

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

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

Помехи

x₁ y₁

x₂ y₂

x_n y_n

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

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

.

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

I (x₁, x₂) = I (x₁)+I (x₂). (1)

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

. (2)

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

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

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), если вероятности равны: p_i0 = p_i1 = ½.

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

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

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

p_i0 = ¾; p_i1 = ¼.

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

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

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

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

. (6)

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

(7)

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

. (8)

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

т. к.

.

Как видно из выражения, величина вероятности p_i не зависит от i, а это может быть в случае, если все p_i равны, т. е. p₁ =p₂ = …=p_m =1/m.

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

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

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

. (9)

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

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) = log₂m = log₂2 = 1[дв.ед/симв.]

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

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

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

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

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

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

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

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

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

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

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

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

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

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