Условная энтропия. Объединение зависимых систем.

Кафедра ИУС

 

Лекции по предмету

"Теория информации"

 

 

 

Мурыгин А. В.

Красноярск 20 10

Информация. Язык. Общество

 

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

Теория информации развивалась как наука в конце 40-х г.г. В её основу положены труды Шеннона, Винера, Колмогорова, Котельникова. Это полуматематическая наука, т.е. прикладное приложение к математике.

 

 

Измерение информации

 

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

 

 

Структурный метод

 

Структурные методы имеют дело с информационными массивами. Массив информации представим в виде кубика.

			n – длина передаваемого числа; m – глубина числа; Поле – набор из элементов чисел m из гнезда выдвигаются нужное число,

 

 

а число определено.

	n

поле

 

 

Все ячейки называются числовой грядой (один слой). Совокупность слоев – это поле.

Количество чисел, которое может быть представлено с помощью одной числовой гряды:

В 1928г американец Хартли предложил использовать логическую меру:  - это мера информации по Хартли (аддитивная мера по Хартли) количество информации, измеренное такой мерой, измеряется в битах (это название даёт основание log₂). Если глубина числа m = 2 – это двоичная мера информации (0 или 1), если m = 1, то кол-во информации равно один бит. Это соответствует одному элементарному событию.

 

 

Статический метод

Обычно элементы сообщений не равновероятны, и это обстоятельство влияет на количество переданной информации. Пусть имеется алфавит из m элементов h₁, h₂, …,h_m – элементы алфавита. Вероятности появления символов равны p₁, p₂, …,p_m. Составим из этих элементов сообщения, содержащее n элементов. Среди них будут n₁ элементов h₁, n₂ элементов h₂, … n_m элементов h_m.

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

При достаточно большой длине числа n, можно считать, что n_i определяется как p_i*n. Кроме того можно считать, что все сообщения равновероятны, тогда вероятность отдельного сообщения:

 

 N – количество переданных сообщений;       

I = log₂N – количество информации            =

 

Кол-во информации, отнесённое к одному символу

- энтропия

Такая мера информации была введена Шенноном. Количество информации по Шеннону определяется как I. Измеряется [бит/символ]. Она характеризует количество переданной информации при неравновероятности появления символов и характеризует неопределённость состояния сообщения.

 

Энтропия и её свойства

 

Рассмотрим некоторую систему, которую обозначим за X, котороя может принимать конечное множество состояний x₁, x₂, …,x_n (пример: алфавит x₁,..,x_n - буквы). Вероятность появления символов p₁, p₂,..,p_n.

 

Свойства:

1) Энтропию системы X -  - всегда больше нуля. Это следует из того, что log₂ p_i – отр., p_i меньше единицы и – на -, даёт плюс.

2) Энтропия обращается в 0, когда одно из состояний достоверно, а другие невозможны, т.е. какая-то из вероятностей будет равна единице, логорифм даст ноль, следовательно, Н(x) = 0.

3) Обращается в максимальное, когда все состояния равновероятны.

4) Энтропия обладает свойством аддитивности, кода несколько систем объединяются в одну, их энтропии складываются.

 

Рассмотрим простейший случай. Система имеет два состояния и эти состояния равновероятны.

 

H(x) = - (0.5 log 0.5 + 0.5 log 0.5) = 1 бит/символ xi	x1	x2
p1	0.5	0.5

 

Определить энтропию системы X, которая имеет n равновероятных состояний

 

- log 1 + log n = log n xi	x1	x2 …	xn
pi		…

 

 

- это частный случай, когда все вероятности одинаковы.

 

Пример: Система X имеет восемь состояний. Определить энтропию. (состояния равновероятны)

n = 8                    

 

           

 

Пример:  Определить H, состояние которой описывается таблицей.

 

Система имеющая пять состояний

 

бит/символ xi	x1	x2	x3	x4	x5
p1	0.01	0.01	0.01	0.01	0.96

 

 

Иногда энтропию определяют через математическое ожидание

 

H(x) = M[-log₂ p(x)] – это позволяет упростить математические выкладки.

 

 

Пример: Алфавит состоит из букв a, b, c, d. Даны вероятности p_a = p_b = 0,25; р_с = 0,34; p_d = 0.16

 

H(x) = - (2*0.25 log 0.25 + 0.34 log 0.34 + 0.16 log 0.16) = 1.952 бит/символ

 

 

Энтропия сложной системы

 

Под объединением двух систем X и Y с возможными состояниями x₁,x₂,…,x_n, y_1, y_2,…,y_m, понимается сложная система (x, y), состояние которых x_i,y_i; представляют собой все возможные комбинации состояний x_i,y_i.

Число возможных состояний равно m х n.

Обозначим символом p_i,j, вероятность того, что система может находиться в состоянии p(x_i,y_i). Тогда вероятность p_ij можно представить в виде таблицы совместных вероятностей.

 

таблица совместных вероятностей xi & yi	x1	x2	…	xn
y1	p11	p21	…	pn1
y2	p12	p22		pn2
…	…	…	…	…
ym	p1m	p2m	…	pnm

 

;      ;    H(x, y) = M[- log p(x, y)].

Пусть системы X, Y независимы. Тогда по теореме умножения вероятностей имеем:

 

p(x, y) = p(x) * p(y)

 

Прологарифмируем левую и правую часть

 

log p(x, y) = log p(x) + log p(y)

 

H(x, y) = M[- log p(x) – log p(y)]

 

H(x, y) = H(x) + H(y), если независимые системы, то их энтропии складываются.

 

Полная условная энтропия

 

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

p_i = p(x_i) – вероятность наступления события x_i

;

 

p_i * p(y_j / x_i) = p_ij

 

Тогда

 

;         H(Y / x) = M[ - log P(y / x)]

В целом полная условная энтропия характеризует степень неопределённости состояния системы Y, оставшуюся после того, как состояние системы X полностью определилось.

 

Пример: Имеются две системы, объединённые в одну, вероятности состояния которых заданы таблицей совместных вероятностей. Определить полную условную энтропию.

 

	Определим вероятности каждого события. Для этого складываем pij по столбцам.

xi & yi	x1	x2	x3	rj
y1	0.1	0.2	0	0.3
y2	0	0.3	0	0.3
y3	0	0.2	0.2	0.4
pi	0.1	0.7	0.2

 

Построить таблицу условных вероятностей p(y / x).  в каждой строке

^yi& xj	x1	x2	x3
y1	1	0.2/0.7	0
y2	0	0.3/0.7	0
y3	0	0.2/0.7	1

 

 бит/символ

 

Составим таблицу условных вероятностей P(x / y).

xi& yi	x1	x2	x3
y1	0.1/0.3	0.2/0.3	0
y2	0	1	0
y3	0	0.2/0.4	0.2/0.4

 

H(x / y) = 0.3[h(0.1/0.3) + h(0.2/0.3)]+ 0.4[h(0.2/0.4 + h(0.2/0.4)] = 0.68 бит/символ

 

Н - характеризует потери сигналов при прохождении через канал связи.

Теорема сложения энтропий

 

Если две системы X и Y объединятся в одну, то энтропия объединений системы равна энтропии одной из систем плюс условная энтропия второй системы относительно первой.

 

H(x, y) = H(x) + H(y / x)

 

Доказательство этой теоремы:

 

Запишем H(x, y) через. математическое ожидание

 

H(x, y) = M[ - log p(x, y)]

 

По теореме умножения вероятностей

 

p(x, y) = p(x) * p(y / x)

 

log p(x, y) = log p(x) + log p(y / x)

 

M[x, y] = M[ - log p(x)] + M[ - log p(y / x)]

 

H(x, y) = H(x) + H(y / x)

 

Интерес представляют частные случаи:

· Когда системы независимы, условная энтропия H(y / x) = H(y) и получаем теорему сложения энтропий H(x, y) = H(x) + H(y).

 

H(x, y) £ H(x) + H(y)

 

· Когда состояние одной системы X полностью определяет состояние другой системы Y. В этом случае условная энтропия равна нулю.

 

H(y / x) = 0               H(y, x) = H(x)

 

Пример: Передаются два элемента a, b. Определить количество переданной информации в случае, когда:

1) Элементы взаимозависимы и не равновероятны

 

p(a) = ;    p(b) = ;    p(a / a) = p(b / a) =

                                           p(b / b) = 0  p(a / b) = 1

 

I = H – вероятность события а

I = H = - p(a)[ p(a / a) log p(a / a) + p(b / a) log p(b / a) ] – p(b)[ p(a / b) log p(a / b) + p(b / b) log p(b / b)] = 0.685 бит/символ.

 

2) не равновероятны и независимы:

 

p(a) = _;               p(b) =

I = - p(a) log p(a) – p(b) log p(b) = - log  - log  = 0.815 бит/символ

 

3) элементы независимы и равновероятны:

 

p(a) = p(b) = ;      I = log₂ = 1

 

 

Энтропия и информация

 

Пусть имеется система X с энтропией H(x). После получении информации о состоянии системы; система полностью определилась, т.е энтропия равна нулю, следовательно, информация, получаемая в результате выяснения состояния системы x равна уменьшению энтропии.

 

I_x = H(x) – 0 = H(x)

 

Количество информации приобретённое при полном выяснении состояния системы равна энтропии.

 

 - часть информации о системе

 

 - называют частной информацией о системе или информацией от отдельного сообщения.

Для системы с равновозможными состояниями

Полная информация

 

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

 

I_x = log 64 = 6 бит

 

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

 

P = ; - вероятность сообщения    = 4 бит

 

Пример 3: Определить частную информацию, содержащаяся в сообщении случайного лица о своём дне рожденье.

 

 - вероятность полученного сообщения;   бит – количество информации

 

 

Пример 4: Определить полную информацию от сообщения о дне рождения случайного лица.

 

x₁ – день рожденье             

x_{2 –} не день рожденье

 

 бит

 

Пример 5: По цели может быть произведено n выстрелов. Вероятность поражения цели при каждом выстреле p. После k-ого выстрела (1£ к á n) производятся разведка, сообщение поражена или не поражена цель. Определить к при условии, чтобы количество информации, доставляемая разведкой была максимальной.

x_k – система (цель после к-ого выстрела) имеет два состояния:

x_{1 –} цель поражена;

x₂ – промах

 

p₁ = 1 – (1 - p)^k p₂ = (1 - p)^k

 

Информация будет максимальна, когда p₁ = p_2, следовательно

1 – (1 - p)^k = (1 - p)^k, k =

p = 0.2;        к = 3

 

 

Взаимная информация

 

Имеется две системы: X и Y. Они взаимосвязаны. Необходимо определить, какое количество информации по системе X даст наблюдение за системой Y. Такую информацию определяют, как уменьшение энтропии системы X в результате получения сведений о системе Y.

 

I_y®x = H(x) – H(x / y)

I_y®x = I_x®y = I_x«y

 

1) Если системы X и Y независимы, то

H(x / y) = H(x) и I_y®x = 0 - информации не будет

 

       2) Система полностью зависимы

H(x / y) = H(y / x) = 0 I_y®x = H(x) = H(y)

 

Выражения для взаимной информации можно получить через взаимную энтропию

H(x / y) = H(x, y) – H(y)         I_y®x = H(x) + H(y) – H(x, y)

 

Формула для расчёта взаимной информации

H(x) = M[ - log p(x)],             H(y) = M[ - log p(y)]     H(x, y) = M[ - log p(x, y)]

 

I_y®x = M[ - log p(x) – log p(y) + log p(x, y)]

 

Сумма равна единице Этих сведений достаточно, чтобы определить взаим-  ную информацию, создавшуюся в системе

Пример: Найти полную взаимную информацию, содержащуюся в системах X и Y. Если задача на матрицы совместных вероятностей.

 

xi & yi	x1	x2	x3	rj
y1	0.1	0.2	0	0.3
y2	0	0.3	0	0.3
y3	0	0.2	0.2	0.4
pi	0.1	0.7	0.2

 

бит

 

Блочное кодирование

 

Пусть первичный алфавит содержит 2-е буквы: а и б. p(A) = 0.7; p(B) = 0.3

 

H = - 0.7*log 0.7 – 0.3 log 0.3 = 0.881 бит/символ

 

Составим новый алфавит из 2-х буквенных комбинаций

АА	0.49	1
АВ	0.21	0	1
ВА	0.21	0	0	1
ВВ	0.09	0	0	0

 

L_ср = 1 * 0.49 + 2 * 0.21 + 3 * 0.21 + 4 * 0.09 = 1.81 бит

 

На одну букву

бит < 1                             l_ср > H                   3%

Пример: Составим алфавит из трёх буквенных комбинаций.

 

Буква	Вероят.	1	2	3	4
ААА	0.343	1	1
ААВ	0.147	1	0
АВА	0.147	0	1	1
ВАА	0.147	0	1	0
АВВ	0.063	0	0	1	1
ВАВ	0.063	0	0	1	0
ВВА	0.063	0	0	0	1
ВВВ	0.027	0	0	0	0

 

l_ср = 2.686 бит

.895 бит - это больше 1,5% и H, следовательно, можно делить по четыре группы.

 

Избыточность от округления

Пример: Кодируются цифры от 0 до 10. Чтобы их представить в виде двоичных, надо

2³<10<2⁴

4 бита   

1 символ – 4 бита

Кодируем блоки по 2 цифры

00

01

…

99

Для передачи информации с помощью двоичной системы 2⁶<99<2⁷

                                              7 бит

На 1 символ: 7/ 2 = 3,5 бита

 

Кодируются блоки по 3 цифры

000

2^10= 1024, 10 бит информации, следовательно, на один символ: 10/3 = 3,3 бита

001

…

999

 

Подсчитаем энтропию

Н = log n = log 10 = 3,32 бит

 

Чтобы определить избыточность, вызванную округлением, воспользуемся:

где m1 – число символов первичного алфавита; m2 – число символов вторичного алфавита; L – длина кодовой комбинации.

,

 

Пример: Передается алфавит из 5 символов: 1, 2, 3, 4, 5, следовательно, m₁=5 с помощью двоичных символов 0,1, следовательно, m₂=2.

Для передачи сообщения потребуется:

 

D₀ – избыточность от округления

                               m - коэффициент;

                                                                                              К – большее целое число.

Пример:

Пример: Определить избыточность сообщений от округления при побуквенном и поблочном кодировании, если кодируются цифровые сообщения и передаются в двоичном коде. Кодирование осуществляется блоками по 4, 5, 6 цифр.

 

Первичный алфавит m₁=10

Вторичный алфавит m₂ = 2

Первичный алфавит из 2-х букв                 m₁=10000  m₂=2

Первичный алфавит из блоков по пять          m₁=100000

 

Кодируются символы по шесть букв                    m₁=10⁶

 , следовательно, этот алфавит наиболее близок к оптимальному.

 

 

Код Хафмана

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

Методика построения кодов следующая:

Пусть есть алфавит А, содержащий буквы а₁, а₂, …, а_n, вероятности появления которых р₁, р₂,…, р_n. Буквы алфавита располагаем в порядке убывания их вероятностей  . Берем две последние буквы   и объединяем их в одну букву b. Получаем новый алфавит А₁

а₁, а₂, …, а_n-2 b

p₁, р₂,…, р_n-2 p_n-1 + p_n

 

Алфавит А₁ называют сжатым, полученным из алфавита А путем однократного сжатия.

Буквы алфавита А₁ располагаем в порядке убывания их вероятностей. Затем проводим процедуру сжатия, получаем алфавит А₂. Продолжаем процедуру сжатия до тех пор, пока у нас не останется 2 буквы.

Буква а1 а2 а3 а4 а5 а6	А Вероятность 0,4 0 0,2 10 0,2 111 0,1 1101 0,05 11001 0,05 11000	Сжатые алфавиты
		А1 0,4 0 0,2 10 0,2 111 0,1 1101 0,1 1100	А2 0,4 0 0,2 10 0,2 111 0,2 110	А3 0,4 0 0,4  11 0,2 10	А4 0,6 (1) 0,4 (0)

 

Процедура кодирования

 

Две буквы последнего алфавита кодируем 1 и 0. Затем кодируется предыдущий алфавит. Процесс кодирования закончен. Чтобы определить эффективность, надо посчитать среднее число символов на алфавит.

Кодирование алфавита по методу Хафмана не является однозначно определенной процедурой. Можно получать разные коды Хафмана.

 

Чтобы посмотреть изменение кода Хафмана, рассмотрим пример другой кодировки:

 

Буква а1 а2 а3 а4 а5 а6	А Вероятность 0,4 11 0,2 01 0,2 00 0,1 100 0,05 101 0,05 1010	Сжатые алфавиты
		А1 0,4 11 0,2 01 0,2 00 0,1 101 0,1 100	А2 0,4 11 0,2 10 0,2 01 0,2 00	А3 0,4 0 0,4 11 0,2 10	А4 0,6 (1) 0,4 (0)

 

Если посчитать , то оно не изменилось ,т.е. каким образом кодировать роли не играет.

Процедура декодирования кодов Хафмана является однозначной.

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

Число букв исходного алфавита n должно быть представляемо  n = m + k *(m -1), k – целое число. Этого условия всегда можно достичь, если ввести в исходный алфавит фиктивные буквы, вероятность которых равна нулю.

Дан алфавит из 6 букв с вероятностями. Построить троичный код Хафмана 0, 1, 2.

 

Требуемое число букв:

n = 3 + k * (3 - 1),

k = 1 n = 5

k = 2 n = 7

не хватает одной буквы а₇ с вероятностью равной нулю

 

Буква а1 а2 а3 а4 а5 а6 а7	А Вероятность 0  0,4 2  0,2 10 0,2 11 0,1 120 0,05 121 0,05 122 0	С ж а т и е
		А1 0 0,4 2    0,2 10 0,2 11 0,1 12 0,1	А2 0,4 (0) 0,4 (1) 0,2 (2)

 

Подсчитаем энтропию

m – количество символов

Существует еще одна методика

(7)

1

1 0

Схема получения кода Хафмана с помощью кодового дерева

1 0

Дан алфавит. Располагаем буквы в порядке убывания вероятностей

	1 0

1

0,28

а₁    0,5

(4)

0,05

0,22

0,08

001  а₂    0,15

011  а₃    0,12 1

(2)

010  а₄    0,1   0                       

0,13

00011 а₅    0,04 1

(3)

00010 а₆    0,04 0

(1)

00001 а₇    0,03 1

00000 а₈    0,02 0

 

1. Находят 2 буквы с вероятностями (а₇ и а₈) и проводят от них линию к точке, в которой вероятность равна их сумме

2. Теперь меньшими вероятностями обладают буквы а₅ и а₆. Соединяют их линиями в одной точке с вероятностью 0.08

3. Соединяем 0,08 и 0,05, получает 0,13

4. Соединяем буквы а₃ и а₄

5. Соединяем 0,15 и 0,13

И так далее…

 

Кодируем ветки

Обозначим цифрой один верхнюю линию узла, нижнюю ноль.

Коды представляют собой последовательность 0 и 1, которые встречаются по пути от точки с вероятностью единица, до кодируемой буквы.

 

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

 

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

 

 

 

               Z               X                            Y                И

							ПИ

П2

П1

ИИ

 

 

             ЛС

 

ИИ – источник информации

П₁, П₂ – преобразователи

ЛС – линия связи

ИП – источник помех

ПИ – приёмник информации

Источник информации создаёт cигналы z, которые кодируются в преобразователе П1, превращаются в сигналы x и поступают в линию связи (ЛС). В результате действия помех, сигнал Y на приёмном конце, отличается от X. Помехи создаются воображаемым источником помех (ИП) и поступают в линии связи в виде мешающего сигнала . Преобразователь П2 декодирует сигналы, и передаёт в приёмник информации. Приёмник информации перерабатывает принятое сообщение. Для организации эффективной передачи информации решают три задачи:

1. Определение максимально возможной скорости передачи информации по каналу;

2. Разработка кодов, позволяющих увеличить скорость передачи информации;

3. Согласование канала с источником.

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

, где V_x- средняя скорость передачи символов, I_y®x – максимальное возможное значение среднего количества информации на один символ принятого сигнала.

, - средняя длительность передаваемых символов

Взаимная информация

           - характеризует потери информации.

 

При отсутствии помех H(x / y) = 0 и . А максимальные I_y®x = log₂m

Пропускная способность канала

       m – количество символов алфавита, который кодируется

 

Дискретный канал с помехами

 

Характеризуется канальной матрицей

…

Взаимная информация

…

…

- это максимальное значение определить сложно.

Средняя условная энтропия

Энтропия на выходе приёмника

Определим пропускную способность канала связи, по которому передаются двоичные сигналы со скоростью v_x, если вероятность искажения сигнала равна p.

Имеет источник информации , приёмник информации .

Разложение выполним в виде диаграммы

Правильный приём

Искажение

Канал такого типа называют симметричным бинарным, (т.к. два числа)

 

Определим среднюю условную энтропию

-, т.е потери не будут зависеть от характерис-тики источника

объединили

, получим, что

Учитывая, что

 

Поэтому

Пропускная способность канала

Рассмотрим два крайних условия:

1. Вероятность искажения (Р=0), следовательно, помех нет, следовательно, С = v_x и она имеет свое максимальное значение

2. Р=1/2. Значение С = 0 – это минимальное значение пропускной способности

 

Пример:  Определить пропускную способность канала связи, способного передавать 100 симв./сек. Каждый символ искажается с вероятностью 0,01.

 

 

 

Корректирующие коды

Это коды, которые позволяют обнаруживать и исправлять ошибки.

n – значность кода (из скольки символов состоит данная кодовая комбинация)

 

N₀ = 2ⁿ, n – число возможных кодовых комбинаций.

Идея возможности обнаружения ошибок заключается в том, что для передачи используются не все комбинации, а только их часть N.

И это значение N<N₀.

Используемые комбинации N называются разрешенные, а остальные N₀–N – это запрещенные комбинации.

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

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

 К исходной кодовой комбинации добавляют 1 или 0, таким образом, чтобы количество (сумма) единиц всегда была четной. Сбой любого одного символа обнаружит ошибку.