ТЕОРИЯ ИНФОРМАЦИИ И КОДИРОВАНИЯ. Воронежский институт мвд россии кафедра высшей математики
 Скачать 1.43 Mb.
|
|
y x y=x-1 y=ln x 1 -1 Лемма 1. (Гиббс) Для любых p и q, таких что X p = 1, X q = 1 имеет место неравенство X p · lbp ≥ X p · lbq. Доказательство. Из рисунка легко увидеть, что логарифмическая функция обладает простым свойством lb p ≤ p − 1. Тогда, для выражения X p · lb q p ≤ X p · q p − 1 = X p · q − p p = X (q − p) = X q − X p = 1 − 1 = 0, получим P p · lb q p ≤ 0, или X p · lb q p = X p · ( lbq − lbp) ≤ 0. Отсюда следует утверждение леммы. Определение 1 эквивалентно следующей теореме. Теорема 1. Энтропия произвольной случайной величины x = (x 1 , x 2 , ..., x n ) меньше соответствующей равномерной, распределенной на том же интервале: H(x) ≤ lb n. Доказательство. Обозначим распределение произвольной случайной величины через p = (p 1 , p 2 , ..., p n ) а распределение равномерной случайной величины, через q = (q 1 , q 2 , ..., q n ) = 1 n , 1 n , ..., 1 n Тогда, по определению энтропии H(x) = − X p · lb p ≤ − X p · lb q = − X p · lb 1 n = X p · lb n = lb n · X p = lb n · 1 = lb n. 14 Глава 1. Энтропия и информация Пример 1.5. Среди всех законов распределения непрерывной случайной величины x с одинаковой дисперсией D найти закон с максимальной энтропией. Решение. По определению энтропии H = − Z f (x) lbf (x)dx → max . Нам необходимо найти экстремаль функционала H(f) с дополнительными ограничениями: 1) условием нормировки Z f (x)dx = 1, 2) ограничением на дисперсию Z (x − x) 2 f (x)dx = D. Записывая задачу Лагранжа в виде F (f, λ, µ) = f lbf + λ · f + µ · (x − x) 2 f найдем экстремум функции: ∂F ∂f = 0, lbf + 1 + λ + µ · (x − x) 2 = 0, откуда f = e 1−λ e −µ·(x−x) 2 Из условия нормировки найдем Z f (x)dx = e λ−1 Z e µ·(x−x) 2 dx = e λ−1 r π µ = 1 или e 1−λ = r µ π , тогда f = r µ π e −µ·(x−x) 2 Ограничение на дисперсию Z (x − x) 2 f (x)dx = D дает r µ π Z (x − x) 2 e −µ·(x−x) 2 dx = 1 2µ = D 1.2. Энтропия непрерывных источников сообщений 15 или µ = 1 2D , тогда f = r 1 2πD e − (x−x)2 2D N 1. Среди всех законов распределения непрерывной случайной величины x, определенных на интервале a ≤ x ≤ b, найти закон распределения с максимальной энтропией. f = 1 b−a 2. Среди всех законов распределения непрерывной случайной величины x, определенных на полуоси 0 ≤ x < ∞, при заданном математическом ожидании M[x], найти закон распределения с максимальной энтропией. 1 m e − x m 3. Среди всех законов распределения непрерывной случайной величины x, при заданном втором начальном моменте µ 2 , найти закон распределения с максимальной энтропией. 4. Среди всех законов распределения дискретной случайной величины x, найти закон распределения с максимальной энтропией. p = 1 n Пусть теперь случайные величины x = (x 1 , x 2 , ..., x n ) и y = (y 1 , y 2 , ..., y n ) имеют совместную функцию распределения p(x, y). Тогда совместная энтропия системы случайных величин x и y будет записываться как H(x, y) = − X x X y p(x, y) · lbp(x, y). Аналогичное выражение для совместной плотности вероятностей непрерывных случайных величин имеет вид H(x, y) = − Z Z f (x, y) · lbf(x, y)dxdy. Теорема 2. Для системы случайных величин x и y имеем H(x, y) ≤ H(x) + H(y). Здесь, равенство имеет место, если x и y - независимы. Доказательство. Используя редуцированные законы распределения p(x) = X y p(x, y), p(y) = X x p(x, y) получим выражения H(x) = − X x p(x) · lb p(x) = − X y X x p(x, y) · lb p(x), 16 Глава 1. Энтропия и информация H(y) = − X y p(y) · lb p(y) = − X x X y p(x, y) · lb p(y). Тогда H(x) + H(y) = − X y X x p(x, y) · ( lb p(x) + lb p(x)) = − X y X x p(x, y) · lb (p(x)p(y)) = − X y X x p(x, y) · lb q(xy). Здесь мы ввели обозначение q(xy) = p(x)p(y). Теперь, используя лемму Гиббса, получим H(x, y) = − X x X y p(x, y) · lb p(x, y) ≤ − X x X y p(x, y) · lb q(x, y) = H(x)+H(y). Очевидным способом можно доказать обобщение этой теоремы H(x 1 , x 1 , ..., x n ) ≤ H(x 1 ) + H(x 2 ) + ... + H(x n ), где равенство имеет место, если (x 1 , x 1 , ..., x n ) - независимы. 1.3 Условная энтропия Для системы двух случайных величин с совместной вероятностью p(x, y) можно ввести условную вероятность p(x|y). В частности: p(x|y i ) - закон распределения случайной величины x при условии, что y принимает конкретное значение y i (аналогично для p(y |x i ). Таким образом, мы можем определить условную энтропию y данную при x = x i : H(y |x = x i ) = H(y |x i ) = − X k p(y k |x i ) · lbp(y k |x i ), И среднюю условную энтропию y относительно x: H(y |x) = X i p(x i )H(y |x i ) = − X i p(x i ) X k p(y k |x i ) · lbp(y k |x i ). Поскольку из теории вероятностей известно, что p(y, x) = p(x)p(y |x), мы получим H(y |x) = X i p(x i )H(y |x i ) = − X i X k p(x i , y k ) · lbp(y k |x i ). 1.3. Условная энтропия 17 Аналогично, можно определить энтропию H(x, y, z) = − X i X k X n p(x i , y k , z n ) · lbp(x i , y k , z n ) и среднюю условную энтропию системы из трех случайных величин H(yz |x) = − X i X k X n p(x i , y k , z n ) · lbp(x i , y k |x n ). Очень часто бывает полезной следующая Теорема 3. H(x, y) = H(x) + H(y |x) = H(y) + H(x|y) Доказательство. По определению H(x, y) = − X x X y p(x, y) · lbp(x, y) = − X x X y p(x, y) · lbp(x)p(y|x) = − X x X y p(x, y) · lbp(x) − X x X y p(x, y) · lbp(y|x) = − X x p(x) · lbp(x) − X x p(x) X y p(y |x) · lbp(y|x) = H(x) + H(y|x). Теорема 4. H(y |x) ≤ H(y) Доказательство. По определению H(x, y) = H(x) + H(y |x), H(y |x) = H(x, y) − H(x). Но согласно теореме 2 H(x, y) ≤ H(x) + H(y) или H(x, y) − H(x) ≤ H(y), тогда H(y |x) = H(x, y) − H(x) ≤ H(y). Условная энтропия случайной величины x относительно случайной величины y дается выражениями H(x/y) = − X p(x/y) lbp(x/y), H(x/y) = − Z f (x/y) lbf (x/y)dx. Математическое ожидание условной энтропии M [H(x/y)] называется средней условной энтропией: H y (x) = M y [H(x/y)] = X p(y)H(x/y) = − X X p(y)p(x/y) lbp(x/y), 18 Глава 1. Энтропия и информация H y (x) = − Z Z f (y)f (x/y) lbf (x/y)dxdy. Количество информации о случайной величине x, которое может быть получено в результате наблюдения значений y, измеряется разностью энтропии H(x) и ее средней условной энтропии относительно y: I y (x) = H(x) − H y (x). Если после получения сообщения о дискретной случайной величине y значение x полностью определено, то H y (x) = 0 и I y (x) = H(x). Если x и y независимы, то H(x) = H y (x) и I y (x) = 0. Отметим свойство симметрии условной информации I y (x) = I x (y). Пример 1.6. Производится стрельба по двум мишеням: по первой мишени сделано 2 выстрела, по второй три. Вероятности попадания при одном выстреле соответственно равны 1/2 и 1/4. Исход стрельбы по какой мишени является более определенным. Решение. Составляем законы распределения для случайных величин x и y - числа попаданий по мишени: x 0 1 2 p 1/4 1/2 1/4 y 0 1 2 3 p 27/64 27/64 9/64 1/64 Мерой неопределенности исхода стрельб является энтропия числа попаданий: H = − X p i lbp i H 1 = − 1 4 · lb 1 4 + 2 4 · lb 2 4 + 1 4 · lb 1 4 = − 1 4 (1 · lb1 + 2 · lb2 + 1 · lb1) + lb4 = − 1 4 (0 + 2 + 0) + 2 = 1.5; H 2 = − 27 64 · lb 27 64 + 27 64 · lb 27 64 + 9 64 · lb 9 64 + 1 64 · lb 1 64 = lb64 − 1 64 (27 · lb27 + 27 · lb27 + 9 · lb9 + 1 · lb1) ∼ = 6 − 1 64 (27 · 4.75 + 27 · 4.75 + 9 · 3.17 + 1 · 0) = 4.45. Поскольку H 1 < H 2 - то исход стрельбы по первой мишени обладает большей определенностью. N 1.3. Условная энтропия 19 Задача 1.2. В двух урнах по n шаров, причем в первой урне k 1 красных, b 1 белых и c 1 черных, а во второй соответственно – k 2 , b 2 и c 2 . Из каждой урны вынимается по одному шару. Определить, для какой урны исход опыта является более определенным. № k 1 b 1 c 1 k 2 b 2 c 2 № k 1 b 1 c 1 k 2 b 2 c 2 1 10 5 5 7 7 6 16 1 15 4 15 5 0 2 12 4 4 6 6 8 17 2 14 4 14 6 0 3 14 2 2 8 8 4 18 3 13 4 13 5 2 4 1 16 1 10 5 5 19 4 12 4 12 4 4 5 18 0 2 5 12 3 20 5 11 4 11 3 6 6 4 8 8 1 10 9 21 6 10 4 10 2 8 7 5 4 11 2 8 10 22 7 9 4 9 1 10 8 6 3 11 3 7 10 23 8 8 4 8 2 10 9 7 2 11 4 6 10 24 9 7 4 7 3 10 10 5 10 5 6 7 7 25 10 6 4 6 14 0 11 8 1 11 5 2 13 26 11 5 4 5 13 2 12 9 2 9 7 3 10 27 12 4 4 4 12 4 13 10 3 7 8 4 8 27 13 3 4 3 11 6 14 11 4 5 8 5 7 29 14 2 4 2 10 8 15 5 5 10 7 6 7 30 15 1 4 1 9 10 Дополнительные упражнения 1. В правильный n-угольник путем соединения середин его соседних сторон вписан другой правильный n-угольник. Точка, поставленная внутри данного многоугольника может оказаться внутри или вне вписанного многоугольника. Определить. а) энтропию опыта; б) значение n, при котором энтропия максимальна. (P n = cos 2 π/n) 2. Вероятность появления события при одном испытании равна p. Испытания повторяются до первого появления события. Найти энтропию числа испытаний. а) p = 1/2; б) в общем случае. H = − (p lbp+q lbq) p 3. Определить энтропию случайной величины, подчиненной биноминальному закону распределения: а) p = 1/2, n = 2; б) в общем случае. 4. Определить энтропию непрерывной случайной величины подчиненной равномерному закону распределения на (a, b). ( lb(b − a)) 5. Определить энтропию непрерывной случайной величины подчиненной нормальному закону распределения. 20 Глава 1. Энтропия и информация 1.4 Задачи информационного поиска Энтропия H – удобная мера неопределённости законов распределения вероятностей, особенно в тех случаях, когда распределения являются асимметричными, многовершинными и когда использование таких числовых характеристик, как среднее значение, дисперсия и моменты высших порядков, теряет всякую наглядность. Приведем выражения для энтропии некоторых дискретных законов распределения вероятностей: Биномиальный P n (k) = C k n p k q n−k H(x) = −n[p ln p + q ln q] − n−1 X k=1 C k n p k q n−k ln C k n Пуассона P n (k) = λ k k! e −λ H(x) = λ ln e λ + ∞ X k=1 λ k k! e −λ ln(k!) Равномерный P n (k) = 1 n H(x) = lbn Полиа P n (k) = P 0 λ 1+αλ k × 1(1+α)...[1+(k−1)α] k! H(x) = −λ ln λ + 1 + αλ α ln(1 + αλ) − ∞ X k=1 P 0 λ 1 + αλ k 1(1 + α)...[1 + (k − 1)α] k! × ln 1(1 + α)...[1 + (k − 1)α] k! Особенно эффективным является использование метода расчета энтропии при решении задач многошагового информационного поиска. Результаты каждого шага поиска образуют полную группу событий, т.е. случайную величину x. Необходимо выбрать такую стратегию поиска, что бы каждый шаг давал максимальное количество информации об исследуемом объекте. Поскольку среди всех законов распределения максимальной энтропией (информацией) обладает равномерный закон, то поиск необходимо производить таким образом, чтобы случайная величина x была распределена равномерно. Пример 1.7. Имеется 3 монеты одного достоинства; 1 из них фальшивая. Какое наименьшее число взвешиваний на рычажных весах без гирь, позволит обнаружить фальшивую монету и выяснить, легче она или тяжелее чем остальные? Решение. Каждая из 3 монет может оказаться фальшивой и быть при этом тяжелее или легче остальных. Таким образом имеется N = 2 · 3 = 6 возможных исходов. Поэтому выбор отдельно взятой монеты дает информацию, равную I = − lbp = − lb 1 N = − lb 1 6 = lb6 ≈ 2.585 bit. 1.4. Задачи информационного поиска 21 Каждое взвешивание имеет 3 исхода: перевешивает левая чаша, правая чаша и равновесие. Поэтому произвольное единичное взвешивание дает информацию I 0 = − lb 1 3 = lb3 ≈ 1.6 bit. Следовательно, минимальное число взвешиваний не может быть меньше, чем n = I I 0 = lb6 lb3 = 2.585 1.6 ≈ 1.631 ≈ 2, т.е. оно не меньше двух. Схема решения этой задачи следующая. Положим на обе чашки по 1 монетке. 1. Если весы остались в равновесии, то фальшивая монета осталась одна на столе и нам необходимо еще одно взвешивание чтобы определить легче она или тяжелее настоящей. 2. Если весы не в равновесии, то мы меняем монету с любой чашки на настоящую. (a) Если весы в равновесии – то фальшивая на столе. (b) Если весы не в равновесии – то фальшивая осталась на весах. 1 1 1 1 0 0 0 0 0 0 0 0 0 0 1 N Пример 1.8. Имеется 4 монеты одного достоинства; 1 из них фальшивая. Какое наименьшее число взвешиваний на рычажных весах без гирь, позволит обнаружить фальшивую монету и выяснить, легче она или тяжелее чем остальные? Решение. Каждая из 4 монет может оказаться фальшивой и быть при этом тяжелее или легче остальных. Таким образом имеется N = 2 · 4 = 8 возможных исходов. Поэтому выбор отдельно взятой монеты дает информацию, равную I = − lbp = − lb 1 N = − lb 1 8 = lb8 ' 3 bit. Каждое взвешивание имеет 3 исхода: перевешивает левая чаша, правая чаша и равновесие. Поэтому произвольное единичное взвешивание дает информацию I 0 = − lb 1 3 = lb3 ' 1.6 bit. 22 Глава 1. Энтропия и информация Следовательно, минимальное число взвешиваний не может быть меньше, чем n = I I 0 = lb8 lb3 = 3 1.6 ≈ 1.893 ' 2, т.е. оно не меньше двух (с точки зрения теории информации). К сожалению, пока не известен алгоритм решения этой задачи с помощью 2-ух взвешиваний. N Пример 1.9. (Для продвинутых пользователей.) Теперь докажем, что решение предыдущей задачи с помощью 2-ух взвешиваний невозможно. Для этого вычислим реальное количество информации, получаемое нами при первом взвешивании. Оно зависит от стратегии взвешивания. Мы можем положить на обе чашки весов по 2 монеты и по 1 монете. Напомним, что I 0 = lb3 ' 1.585 bt это максимальная информация о системе, которую мы можем получить с помощью одного взвешивания. Рассмотрим 1 стратегию. Пусть x - положение чашки весов при взвешивании x = ( −1; 0; 1). Поскольку при первом взвешивании на обе чашки положено по 2 монеты, то весы не смогут остаться в равновесиии и мы имеем три возможные исхода с вероятностями: 1) x = −1 - перевесила левая чашка, p(-1)=1/2; 2) x = 0 - чашки остались в равновесии, p(0)=0; 3) x = 1 - перевесила правая чашка, p(1)=1/2. Построим таблицу распределения случайной величины x x −1 0 1 p 1/2 0 1/2 и найдем ее энтропию H = − 1 2 lb 1 2 + 0 · lb0 + 1 2 lb 1 2 = lb2 = 1 bt. Т.е. мы получили 1 bt. информации, а энтропия системы была 3 bt. Т.е. с помощью взвешивания мы уменьшили неопределенность системы до 2 bt. и у нас осталось еще одно взвешивание, которое в идеале может дать только lb3 ' 1.585 bt. Очевидно что оставшегося взвешивания нам недостаточно для решения задачи. Рассмотрим другую стратегию. Положим на обе чашки по 1 монете. Тогда результат взвешивания дает три возможных исхода с вероятностями: 1) x = −1 - перевесила левая чашка, p(-1)=1/4; 2) x = 0 - чашки остались в равновесии, p(0)=1/2; 3) x = 1 - перевесила правая чашка, p(1)=1/4. Построим таблицу распределения случайной величины x x −1 0 1 p 1/4 1/2 1/4 1.4. Задачи информационного поиска 23 и найдем ее энтропию H = − 1 4 lb 1 4 + 1 2 lb 1 2 + 1 4 lb 1 4 = 1.5 bt. Т.е. нам осталось получить еще 1.5 bt. информации о системе с помощью одного оставшегося взвешивания. В принципе, это возможно, поскольку при удаче одно взвешивание может нам дать lb3 ' 1.585 bt. информации. Если в результате первого взвешивания одна из чашек перевесила, то мы точно знаем, что на столе лежат настоящие монеты. Меняя одну любую монету на весах с настоящей мы получим таблицу распределения для второго взвешивания x −1 0 1 p 1/4 1/2 1/4 с энтропией H = 1.5 bt. Т.е. задача решена. Однако, если в результате первого взвешивания чашки весов остались в равновесии, то фальшивая монета осталась на столе. Но для того, чтобы определить ее необходимо n = I I 0 = lb4 lb3 ≈ 1.262 > 1, т.е. больше одного взвешивания 1 N Пример 1.10. Имеется 5 монет одного достоинства; 1 из них фальшивая. Какое наименьшее число взвешиваний на рычажных весах без гирь, позволит обнаружить фальшивую монету и выяснить, легче она или тяжелее чем остальные? Решение. Каждая из 5 монет может оказаться фальшивой и быть при этом тяжелее или легче остальных. Таким образом имеется N = 2 · 5 = 10 возможных исходов. Поэтому выбор отдельно взятой монеты дает информацию, равную I = − lbp = − lb 1 N = − lb 1 10 = lb10 ≈ 3.322 bit. Каждое взвешивание имеет 3 исхода: перевешивает левая чаша, правая чаша и равновесие. Поэтому произвольное единичное взвешивание дает информацию I 0 = − lb 1 3 = lb3 ≈ 1.6 bit. Следовательно, минимальное число взвешиваний не может быть меньше, чем n = I I 0 = lb10 lb3 = 3.322 1.6 ≈ 2.096 < 3, т.е. оно не меньше трех. Схема решения этой задачи следующая. Положим на обе чашки по 1 монетке. 1 Мы сможем найти фальшивую монету, но не сможем определить легче она или тяжелее настоящих. 24 Глава 1. Энтропия и информация 1. Если весы остались в равновесии, то фальшивая монета осталась среди 3 подозрительных на столе и нам достаточно еще 2 взвешиваний чтобы ее идентифицировать (см. задачу о 3 монетах). 2. Если весы не в равновесии, то мы меняем монету с любой чашки на настоящую со стола. (a) Если весы в равновесии – то фальшивая на столе. (b) Если весы не в равновесии – то фальшивая осталась на весах. 1 1 1 0 0 0 0 0 0 0 0 1 0 0 0 1 0 0 0 N Пример 1.11. Имеется 6 монет одного достоинства; 1 из них фальшивая. Какое наименьшее число взвешиваний на рычажных весах без гирь, позволит обнаружить фальшивую монету и выяснить, легче она или тяжелее чем остальные? Решение. Минимальное число взвешиваний не может быть меньше, чем n = I I 0 = lb12 lb3 = log 3 12 ≈ 2.262 < 3, т.е. оно не меньше трех. Схема решения этой задачи следующая. Определим количество монет которое необходимо положить на весы при первом взвешивании, т.е. рассчитаем стратегию взвешивания используя методы теории информации. Чтобы число взвешиваний было наименьшим, каждое взвешивание должно давать наибольшее количество информации, т.е. исход взвешивания должен обладать наибольшей энтропией. Введем случайную величину x положение чашки весов при взвешивании x = ( −1; 0; 1). Пусть при первом взвешивании на обе чашки положено по i монет. При этом возможны три исхода: 1. x = −1 - перевесила левая чашка; 2. x = 0 - чашки остались в равновесии; 3. x = 1 - перевесила правая чашка; 1.4. Задачи информационного поиска 25 Построим таблицу распределения случайной величины x x −1 0 1 i = 1 p 1/6 4/6 1/6 i = 2 p 2/6 2/6 2/6 i = 3 p 3/6 0 3/6 Чтобы взвешивание дало наибольшую информацию, распределение вероятностей исходов должно обладать наибольшей энтропией, чему соответствует равенство всех вероятностей исходов (равномерный закон распределения x). В нашем случае максимальной энтропией обладает распределение при i = 2. При первом взвешивании на каждую чашку весов следует положить по 2 монеты. Далее рассмотрим отдельно случаи: 1. Если весы остались в равновесии, то на весах мы имеем 4 настоящих, а фальшивая монета осталась среди 2 подозрительных на столе и нам достаточно еще 2 взвешиваний чтобы ее идентифицировать, (см. задачу о 3 монетах). 2. Если весы не в равновесии, то мы берем 2 монеты с одной из чашек и взвешиваем их. (a) Если весы в равновесии – то фальшивая на столе и мы знаем ее вес. Одним взвешиванием мы ее идентифицирум. (b) Если весы не в равновесии – то фальшивая осталась на весах и по предыдущему взвешиванию мы знаем ее вес (больше или меньше настоящей). Одним взвешиванием мы ее идентифицирум. N Пример 1.12. Имеется 12 монет одного достоинства; 11 из них имеют одинаковый вес, а одна – фальшивая. Какое наименьшее число взвешиваний на рычажных весах без гирь, позволит обнаружить фальшивую монету и выяснить, легче она или тяжелее чем остальные? Решение. Каждая из 12 монет может оказаться фальшивой и быть при этом тяжелее или легче остальных. Таким образом имеется N = 2 · 12 = 24 возможных исхода. Поэтому выбор отдельно взятой монеты дает информацию, равную I = − lbp = − lb 1 N = − lb 1 24 = lb24 ≈ 4.6 bit. Каждое взвешивание имеет 3 исхода: перевешивает левая чаша, правая чаша и равновесие. Поэтому произвольное единичное взвешивание дает информацию I 0 = − lb 1 3 = lb3 ≈ 1.6 bit. 26 Глава 1. Энтропия и информация Следовательно, минимальное число взвешиваний не может быть меньше, чем n = I I 0 = lb24 lb3 = 4.6 1.6 ≈ 2.875 ≈ 3, т.е. оно не меньше трех. Напомним решение этой задачи классическим методом дискретной математики. Для этого предлагается стратегия последовательного парного разбиения с lb12 ≈ 3.57 ∼ = 4 взвешиваниями: 1. положить на обе чашки по 6 монет; 2. положить на обе чашки по 3 монеты; 3. положить на обе чашки по 1 монете; 4. определить вес монеты (легче или тяжелее настоящей). Теперь рассчитаем стратегию взвешивания используя методы теории информации. Чтобы число взвешиваний было наименьшим, каждое взвешивание должно давать наибольшее количество информации, т.е. исход взвешивания должен обладать наибольшей энтропией. Введем случайную величину x положение чашки весов при взвешивании x = (−1; 0; 1). Пусть при первом взвешивании на обе чашки положено по i монет. При этом возможны три исхода: 1. x = −1 - перевесила левая чашка; 2. x = 0 - чашки остались в равновесии; 3. x = 1 - перевесила правая чашка; Построим таблицу распределения случайной величины x x i −1 0 1 p i i 12 12−2i 12 i 12 Чтобы взвешивание дало наибольшую информацию, распределение вероятностей исходов должно обладать наибольшей энтропией, чему соответствует равенство всех вероятностей исходов (равномерный закон распределения x). Отсюда 12 − 2i 12 = i 12 , или i = 4. Взвешивание 1: при первом взвешивании на каждую чашку весов следует положить по 4 монеты. 1.4. Задачи информационного поиска 27 Далее рассмотрим отдельно случаи: 2.1. когда при первом взвешивании чашки весов остались в равновесии; 2.2. когда одна из чашек перевесила другую. В случае 2.1. имеем 8 настоящих и 4 подозрительных монет. Для второго взвешивания мы можем положить на правую чашку i подозрительных монет, а на левую k подозрительных и i − k настоящих. Все возможные значения, соответствующие вероятности исходов и энтропию случайной величины x сведем в таблицу № i k p 1 p 2 p 3 H ik [x] 1 1 1 0.25 0.5 0.25 0.452 2 1 0 0.125 0.75 0.125 0.320 3 2 2 0.5 0 0.5 0.301 4 2 1 0.375 0.25 0.375 0.470 5 2 0 0.25 0.5 0.25 0.452 6 3 1 0.5 0 0.5 0.301 7 3 0 0.375 0.25 0.375 0.470 8 4 0 0.5 0 0.5 0.301 Наибольшую энтропию дают опыты 4 и 7. Выберем для примера взвешивание 7, т.е. на первую чашку ложем 3 подозрительные монеты, а на другую 3 настоящие. Здесь возможны 2 случая: 2.1.1. если весы окажутся в равновесии, то фальшивая монета останется одна и необходимо дополнительное 3 взвешивание для определения ее веса; 2.1.2. если чаша перевесила, то вес фальшивой монеты определен, из 1 чаши выбирается 2 монеты и на 3 взвешивании она обнаруживается. В случае 2.2., когда одна из чашек перевесила другую (для определенности - левая), монеты распределяются следующим образом: 1. 4 левых (группа L); 2. 4 правых (группа R); 3. 4 настоящих (группа O). При втором взвешивании мы можем положить: 1. на левую чашку весов - i 1 левых и i 2 правых; 2. на правую чашку весов - j 1 левых, j 2 правых и остальные настоящие. Сравнивая все возможные 25 вариантов выберем из них случай с максимальной энтропией. Например, для второго взвешивания подойдет: i 1 = 1, i 2 = 2, j 1 = 0, j 2 = 2. Здесь тоже возможны 3 случая: 28 Глава 1. Энтропия и информация а) весы в равновесии; б) перевешивает левая чашка; в) перевешивает правая чашка. В случае а) - равновесия мы точно знаем вес фальшивки (тяжелая фальшивка), а сама фальшивка находится в трех оставшихся монетах группы L. Третьего взвешивания в составе 1:1 из монет группы L нам достаточно, чтобы ее обнаружить. В случае б): Третье взвешивание есть разбиение j 2 = 2 в составе 1:1 на обе чашки весов: 1. Если весы в равновесии, то i 1 = 1 - тяжелая фальшивка из группы L; 2. Если перевесила левая чашка, то из j 2 = 2 правая – легкая фальшивка R; 3. Если перевесила правая чашка, то из j 2 = 2 левая – легкая фальшивка R. В случае в): легкая фальшивка из группы R находится в i 2 = 2. Третье взвешивание есть разбиение i 2 = 2 в составе 1:1 на обе чашки весов и определение фальшивки по верхней чашке. N Дополнительные упражнения 1. Имеется N монет одного достоинства, из которых одна фальшивая, несколько легче остальных. Сколькими взвешиваниями на рычажных весах без гирь можно обнаружить фальшивую монету? При каком наибольшем N достаточно пяти взвешиваний? (3 k−1 < 2N < 3 k−1 ) 2. Неисправная система находится в одном из 5 различных состояний, которым соответствуют различные виды неисправностей. Для обнаружения вида неисправности может быть проведено несколько из 7 возможных проверок, приводящих при различных состояниях системы к тому, что контрольный индикатор загорается или не загорается. В приведенной таблице это обозначается соответственно единицей или нулем. № проверки № состояния 1 2 3 4 5 1 0 0 0 0 1 2 0 0 0 1 1 3 0 1 1 0 0 4 1 0 1 0 0 5 1 0 1 0 1 6 1 1 1 0 0 7 1 1 1 1 0 Составить последовательность из минимального числа проверок, позволяющих определить вид неисправности системы. 1.5. Взаимная информация 29 1.5 Взаимная информация Количество информации, которое может быть получено в результате наблюдения полной группы несовместных событий, измеряется ее энтропией I(x |y) = H(x) − H(x|y), I(y |x) = H(y) − H(y|x), I(x |y) = H(x) + H(y) − H(x, y) = I(y|x). Рассмотрим следующий эксперимент. Пример 1.13. Во время эксперимента в течение 8 дней проводилось измерение случайной величины x - отклонение курса доллора от значения в 33 рубля/доллар. Данные измерения показаны в таблице. № измерения 1 2 3 4 5 6 7 8 значение x 0 0 0 1 0 0 0 1 Одновременно проводилось измерение случайной величины y - отклонение дневной температуры на улице от 0 ◦ С: № измерения 1 2 3 4 5 6 7 8 значение y 0 0 0 0 0 1 1 1 Определить количество информации относительно y которое мы получим измеряя x. Решение. Другими словами нам необходимо определить взаимную информацию: I(x |y) = H(x) + H(y) − H(x, y). Запишем данные измерения в одну таблицу значение x 0 0 0 1 0 0 0 1 значение y 0 0 0 0 0 1 1 1 и подсчитаем количество совпадений значений x и y: x y 0 1 0 4 2 1 1 1 P P P P P Если теперь разделить все данные в таблице на 8, то мы получим таблицу совместного распределения случайных величин x и y: x y 0 1 0 1/2 1/4 1 1/8 1/8 P P P P P 30 Глава 1. Энтропия и информация Взяв суммы по строкам и столбцам найдем редуцированные законы распределений случайных величин x и y: x y 0 1 p x 0 1/2 1/4 3/4 1 1/8 1/8 1/4 p y 5/8 3/8 1 P P P P P Вычисляем энтропию H(x) = − X p x · lbp x = − 3 4 lb 3 4 + 1 4 lb 1 4 = 0.811 H(y) = − X p y · lbp y = − 5 8 lb 5 8 + 3 8 lb 3 8 = 0.954 H(x, y) = − X p xy · lbp xy = − 1 2 lb 1 2 + 1 8 lb 1 8 + 1 4 lb 1 4 + 1 8 lb 1 8 = 1.75 и взаимную информацию. I(x |y) = H(x) + H(y) − H(x, y) = 0.811 + 0.954 − 1.75 = 0.015(bit). N Заметим, что теория вероятностей также дает влияние случайной величины x на случайную величинц y с помощью коэффициента корреляции r = hxyi − hxi hyi σ x σ y Учитывая, что hxi = x 2 = 1/4, hyi = y 2 = 3/8, D x = x 2 − hxi 2 = 3/16, D y = y 2 − hyi 2 = 15/64, получим r = hxyi − hxi hyi √ D x √ D y = 1/8 − 1/4 · 3/8 p3/16 p15/54 = 0.149. Другими словами, мы получили ненулевое значение влияния курса доллора на погоду. Очевидно, что к таким расчетам необходимо относится с осторожностью (с чувством юмора). Для независимых случайных величин hxyi = hxi hyi, поэтому коэффициент корреляции r = hxyi − hxi hyi σ x σ y = hxi hyi − hxi hyi σ x σ y = 0. 1.5. Взаимная информация 31 Если же случайные величины x и y линейно зависимы: y = ax + b, то для них hyi = hax + bi = haxi + hbi = a hxi + b, y 2 = (ax + b) 2 = a 2 x 2 + 2ab hxi + b 2 , D y = y 2 − hyi 2 = a 2 x 2 + 2ab hxi + b 2 − (a hxi + b) 2 = a 2 x 2 − x 2 2 = a 2 D x , hxyi = hx(ax + b)i = ax 2 + bx = a x 2 + b hxi и коэффициент корреляции r = hxyi − hxi hyi √ D x √ D y = a hx 2 i + b hxi − a hxi 2 − b hxi √ D x √ a 2 D x = a( hx 2 i − hxi 2 ) pa 2 D 2 x = aD x aD x = 1. Пример 1.14. (Ash [12]) Имеются две монеты. Одна из монет правильная, а у другой – два герба. Монета выбирается случайным образом, дважды подбрасывается, а результат записывается. Спрашивается, как много информации относительно идентичности монет мы можем получить, подсчитывая количество выпавших орлов? Очевидно, что количество орлов должно нам что-то сообщить о природе монеты. Решение. Обозначим через x – случайную величину, определяющую выбранную монету (x = 0 - правильная, x = 1 - фальшивая). Вероятность выбора правильной или фальшивой монеты одинакова: p(x = 0) = p(x = 1) = 1/2. Обозначим через y количество выпавших гербов при двух подбрасываниях выбранной монеты. Поскольку y зависит от того какую монету мы взяли (правильную или фальшивую), мы получим два условных закона распределения x = 0 : y 0 1 2 p 1/4 1/2 1/4 x = 1 : y 0 1 2 p 0 0 1 0 1/2 1/2 1 0 1 2 1/4 1/2 1/4 1 Совместный закон распределения получим по формуле полной вероятности p(x, y) = p(x)p(y |x) или p(x, y) = 1 2 · 1 4 1 2 · 1 2 1 2 · 1 4 1 2 · 0 1 2 · 0 1 2 · 1 = 1 8 1 4 1 8 0 0 1 2 32 Глава 1. Энтропия и информация Складывая вероятности по строкам и столбцам, получим редуцированные (маргинальные) законы распределения p( x) и p(y): x y 0 1 2 p(x) 0 1/8 1/4 1/8 1/2 1 0 0 1/2 1/2 p(y) 1/8 1/4 5/8 P = 1 Средняя взаимная информация вычисляется по формуле I(x |y) = H(x) + H(y) − H(x, y), где H(x) = − X x p(x) lb p(x) = − 1 2 · lb 1 2 − 1 2 · lb 1 2 = 1 2 · 1 + 1 2 · 1 = 1 bit, H(y) = − X y p(y) lb p(y) = − 1 8 · lb 1 8 − 1 4 · lb 1 4 − 5 8 · lb 5 8 = 3 8 + 2 4 + 0.678 8 = 1.3 bit, H(x, y) = − X x X y p(x, y) lb p(x, y) = − 1 8 · lb 1 8 − 1 4 · lb 1 4 − 1 8 · lb 1 8 − 0 · lb0 − 0 · lb0 − 1 2 · lb 1 2 = 3 8 + 2 4 + 3 8 + 0 + 0 + 1 2 = 14 8 = 1.75 bit. Тогда I(x |y) = H(x) + H(y) − H(x, y) = 1 + 1.3 − 1.75 = 0.55 bit. N Задача 1.3. Найти средне количество информации, доставляемое случайной величиной x относительно y. 1. Дважды бросается игральная кость. Случайные величины x - появление 6, y - появление четной цифры. 2. Дважды бросается игральная кость. Случайные величины x - появление 5, y - появление четной цифры. 3. Дважды бросается игральная кость. Случайные величины x - появление 4, y - появление четной цифры. 4. Дважды бросается игральная кость. Случайные величины x - появление 5, y - появление четной цифры. 5. Дважды бросается игральная кость. Случайные величины x - появление 6, y - появление четной цифры. 1.5. Взаимная информация 33 6. Дважды бросается игральная кость. Случайные величины x - появление 1, y - появление нечетной цифры. 7. Дважды бросается игральная кость. Случайные величины x - появление 6, y - появление нечетной цифры. 8. Дважды бросается игральная кость. Случайные величины x - появление 5, y - появление нечетной цифры. 9. Дважды бросается игральная кость. Случайные величины x - появление 4, y - появление нечетной цифры. 10. Дважды бросается игральная кость. Случайные величины x - появление 5, y - появление нечетной цифры. 11. Дважды бросается игральная кость. Случайные величины x - появление 6, y - появление нечетной цифры. 12. Дважды бросается игральная кость. Случайные величины x - появление 1, y - появление нечетной цифры. 13. Один раз подбрасывается игральная кость. Случайные величины x - появление четной цифры, y - появление цифры кратной трем. 14. Иван и Петр наудачу извлекают по одному шару из урны, содержащей 6 белых и 4 черных шара. Иван извлекает шар первым. Случайные величины: x - количество белых шаров у Ивана, y - количество белых шаров у Петра 15. Решить предыдущую задачу при условии, что шары извлекаются с возвращением. 16. Из коробки, в которой 4 красных, 2 синих и 3 зеленых карандаша, наудачу извлекли 3 карандаша. Пусть x – число красных, а y – число синих карандашей среди извлеченных. 17. 10 студентов написали контрольную работу по математике, причем 4 из них получили оценку «отлично», 3 – «хорошо», а остальные «удовлетворительно». Для разбора в группе случайным образом отобрано 4 работы. Пусть x – число отличных, а y – число хороших работ среди отобранных. 18. 2 стрелка независимо друг от друга сделали по 2 выстрела по одной и той же мишени. Вероятность попадания для первого стрелка 0,8, а для второго – 0,6. Пусть x – число попаданий первого стрелка, а y –число попаданий второго. 19. В условиях предыдущей задачи пусть y – общее число попаданий в мишень. 20. Случайная величина x принимает значения (0; 1; 2) с вероятностями (0.3; 0.7; 0.1), а независящая от нее случайная величина y - значения (−1; 0; 1) с вероятностями (0.3; 0.5; 0.2). 34 Глава 1. Энтропия и информация 21. По цели производится два независимых выстрела. Вероятность попадания в цель при первом выстреле равна p 1 , при втором p 2 . Случайные величины: x - число попаданий при первом выстреле, y - число попаданий при втором выстреле. 22. Из урны, содержащей 6 белых и 4 черных шара наудачу извлекают 2 шара без возвращения. Случайные величины: x - число извлеченных белых шаров, y - число черных шаров в выборке. 23. Число x выбирается случайным образом из множества целых чисел (1, 2, 3). Затем из того же множества выбирается наудачу число y, большее первого или равное ему. 24. Бросается два раз игральная кость. Случайные величины x - появление шестерки, y - появление единицы. 25. Два раза бросается монета. Случайные величины x - появление орла, y - появление решки. 26. Три раза бросается монета. Случайные величины x - появление орла, y - появление решки. 27. Бросается один раз игральная кость. Если на грани выпадает цифра 1, 2, 3 или 4, то монета бросается 1 раз. В противоположном случае – монета бросается 2 раза. Случайные величины: x - появление цифры 1,2,3 или 4, y – количество выпавших орлов на монете. 1.5. Взаимная информация 35 Пример 1.15. Источник сообщений вырабатывает ансамбль независимых символов x с частотами n. Вычислить энтропию источника. x 1 2 3 4 n 25 40 0 35 Решение. Поскольку источник сообщений выработал всего N = X n = 25 + 40 + 0 + 35 = 100 символов, то вероятность появления определенного символа равна p i = n i P n = n i N , и мы получаем таблицу распределения случайной величины х вырабатываемой источником x 1 2 3 4 p 1/4 2/5 0 7/20 По определению, энтропия – это среднее количество информации содержащееся в случайной величине H = M(I) = X lb 1 p · p = − X p · lbp. Для нашей задачи, получим H = − X p · lbp = − 1 4 · lb 1 4 + 2 5 · lb 2 5 + 0 · lb(0) + 7 20 · lb 7 20 = 1.5589 bit. N Задача 1.4. Вычислить энтропию источника сообщений, который вырабатывает ансамбль независимых символов x с частотами n. № n № n 1 23 2 1 15 3 2 1 1 16 4 1 2 0 2 0 0 4 2 2 20 1 20 3 0 1 5 17 2 1 1 13 2 2 5 22 3 1 1 2 3 11 1 23 2 18 23 2 1 15 1 1 9 3 4 6 1 0 3 20 1 2 20 19 2 23 1 12 3 9 1 1 5 2 1 1 3 15 1 21 2 20 1 1 1 2 3 11 11 23 6 2 21 1 14 3 1 1 2 21 1 1 6 3 13 2 23 2 7 2 0 1 13 3 2 3 21 22 2 2 1 14 2 2 5 22 8 2 1 2 3 14 1 23 2 23 3 20 1 20 3 4 3 1 9 1 0 6 3 20 2 21 2 24 3 20 12 20 3 4 3 1 10 2 20 2 20 3 6 0 1 25 3 20 12 20 3 4 3 3 11 2 0 1 13 3 2 5 22 26 23 2 1 15 3 2 1 1 12 6 3 20 2 23 2 2 0 27 2 20 1 20 3 0 1 5 13 20 2 22 2 3 6 0 2 28 6 1 0 3 20 1 2 20 14 2 2 1 15 3 1 5 25 29 2 0 1 13 3 2 3 21 15 23 2 1 16 1 7 3 1 30 2 1 2 3 14 1 23 2 36 Глава 1. Энтропия и информация 1.6 Кодирование информации методом Шеннона При передаче информации во многих случаях выгодно первоначальное сообщение источника представить при помощи другого алфавита путем кодирования. Характеристиками кода являются значность и его основание. Значность кода n – число символов в кодовом слове (кодовой комбинации), а основание L – число различных символов кода. Наиболее распространенны двоичные (бинарные) коды с основанием L = 2. Равномерным является такой код, у которого значность кода для всех кодовых слов одинакова (например, код Бодо). При кодировании сообщений, передаваемых по каналам связи без помех, необходимо выполнить два условия: 1. кодовые слова должны быть различимы и однозначно связаны с соответствующими сообщениями; 2. применяемый способ кодирования должен обеспечить максимальную экономичность (краткость) кода, при которой на передачу данного сообщения затрачивается минимальное время. Код, удовлетворяющий второму из этих условий, называется оптимальным. Если x = {x i }, i = 1, 2, ..., N - ансамбль взаимно независимых сообщений с априорными вероятностями p(x i ), a y = {y k }, k = 1, 2, ..., L - ансамбль символов кода и L < N, то число кодовых слов по n символов в каждом слове M = L n . При L n ≥ N, где n – наименьшее целое число, для которого выполняется это неравенство, ансамбль сообщений x = {x i } можно однозначно закодировать при помощи N различных кодов слов по n символов в слове. Пример 1.16. Закодировать по методу Шеннона-Фено сообщение из N = 24 символов: математика_-_царица_наук Решение. Выпишем в таблицу частоты n i и вероятности p i = n i N появления каждой буквы сообщения: x М А Т Е И К Ц Р Н У _ - n 2 6 2 1 2 2 2 1 1 1 3 1 p 0.08 0.25 0.08 0.04 0.08 0.08 0.08 0.04 0.04 0.04 0.15 0.04 Найдем энтропию сообщения H(x) = X p i lbp i = 0.08 · lb0.08 + 0.25 · lb0.25 + 0.08 · lb0.08 + 0.04 · lb0.04 + + 0.08 · lb0.08 + 0.08 · lb0.08 + 0.08 · lb0.08 + 0.04 · lb0.04 + 0.04 · lb0.04 + + 0.04 · lb0.04 + 0.15 · lb0.15 + 0.04 · lb0.04 ∼ = 3.3. Расположим символы в порядке убывания вероятностей: 1.6. Кодирование информации методом Шеннона 37 x А _ Ц К И М Т Е Р Н У - n 0.25 0.15 0.08 0.08 0.08 0.08 0.08 0.04 0.04 0.04 0.04 0.04 Разобьем таблицу на две группы таким образом, чтобы сумма вероятностей появления символов в каждой группе была приблизительно одинаковой. Пометим все буквы попавшие в первую группу символом 0, а все буквы попавшие во вторую группу символом 1. 0.64 0.36 А _ Ц К И М Т Е Р Н У - 0.25 0.15 0.08 0.08 0.08 0.08 0.08 0.04 0.04 0.04 0.04 0.04 0 1 Аналогично, разбиваем первую группу на две равные по вероятностям части и присваиваем первой группе символ 0, а второй группе – символ 1 и.т.д. А _ Ц К И М Т Е Р Н У - 0.25 0.15 0.08 0.08 0.08 0.08 0.08 0.04 0.04 0.04 0.04 0.04 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 Объединяя символы для каждой буквы получим кодовую таблицу А 000 И 011 Р 1100 _ 001 М 100 Н 1101 Ц 0100 Т 1010 У 1110 К 0111 Е 1011 - 1111 Экономность кода – количество информации, приходящееся на один кодовый символ, вычисляется как отношение энтропии алфавита к математическому ожиданию длины кодового обозначения букв сообщения. В нашем случае буквам сообщения соответствуют коды длиной 3 символа для букв (А, _, И, М) и 4 символа - для остальных 8-ми букв. Распределение вероятностей появления кода данной длины дано в таблице x 3 4 n 4 8 p 1/3 2/3 Таким образом, математическое ожидание длины закодированной буквы есть M[n] = X x i p i = 3 · 1 3 + 4 · 2 3 = 11 3 ∼ = 3.67. Для экономности кода получим S = H(x) M(n) = 3.3 3.67 = 0.899. N 38 Глава 1. Энтропия и информация Оптимальным называется код, в котором средняя длина кодового слова равна энтропии, т.е. S = 1. Задача 1.5. Закодировать по методу Шеннона-Фено сообщение фамилия_имя_отчество и найти экономность кода. 1.7 Избыточность сообщения Для характеристики величины, на которую удлиняются сообщения на данном языке по сравнению с минимальной длинной, необходимой для передачи той же информации, вводят специальный параметр R – избыточность: R k = 1 − H k H 0 = 1 − H k lbN где N – число различных букв используемого алфавита; H k - энтропия, приходящаяся на одну букву смыслового текста при учете всех k-буквенных сочетаний; H 0 = lbN – максимальная энтропия, приходящаяся на букву, когда буквы независимы и равновероятны. Пример 1.17. По каналу связи передается сообщение «многоногое». Найти: а) избыточность R 1 источника сообщений при статистической независимости букв; б) избыточность R 2 c учетом зависимости между буквами. Решение. Для передаваемого сообщения, таблица распределения вероятностей появления символов имеет вид x м н о г е n( x) 1 2 4 2 1 P = 10 p( x)=n/Σ 0.1 0.2 0.4 0.2 0.1 а) Поскольку мы имеем всего N = 5 различных символов, то H 0 = lbN = lb5 = 2.322 bit, H 1 = − 4 X i=1 p i lbp i = −(0, 1 · lb0, 1 + 0, 2 · lb0, 2 + 0, 4 · lb0, 4 + 0, 2 · lb0, 2 + 0, 1 · lb0, 1) = 2.122 bit. и по определению избыточности, имеем R 1 = 1 − H 1 H 0 = 1 − H 1 lbN = 1 − 2.122 2.322 = 0.086. б) При учете статистической зависимости между буквами мы заполняем таблицу частот появления двухбуквенных сочетаний 1.7. Избыточность сообщения 39 x \ y м н о г е n( x) м 0 1 0 0 0 1 н 0 0 2 0 0 2 о 0 1 0 2 1 4 г 0 0 2 0 0 2 е 1 0 0 0 0 1 n( y) 1 2 4 2 1 P = 10 Теперь, таблица распределения вероятностей имеет вид p( x) = n/Σ: x \ y м н о г е p( x) м 0 1/10 0 0 0 1/10 н 0 0 2/10 0 0 2/10 о 0 1/10 0 2/10 1/10 4/10 г 0 0 2/10 0 0 2/10 е 1/10 0 0 0 0 1/10 p( y) 1/10 2/10 4/10 2/10 1/10 P = 1 Избыточность R 2 c учетом зависимости между буквами вычисляется по формуле R 2 = 1 − H 2 H 0 = 1 − H 2 lbN , где H 2 – энтропия на букву при учете двухбуквенных сочетаний. Энтропия двухбуквенного текста H(x, y) = − 5 X i=1 5 X j=1 p(x j , y i ) lbp(x j , y i ) = −4 · 0.1 · lb0.1 − 3 · 0.2 · lb0.2 = 2.39 bit Следовательно H 2 = H(x, y) 2 = 1.195 bit, R 2 = 1 − H 2 lbN = 1 − 1.195 2.322 ≈ 0.485 bit. N Пример 1.18. Алфавит состоит из 8 букв (x 1 , x 2 , x 3 , x 4 , x 5 , x 6 , x 7 , x 8 ), вероятности появления которых равны: 8 16 , 4 16 , 2 16 , 1 16 , 1 16 , 1 16 , 1 16 , 0 . Найти избыточность R 1 источника сообщений при статистической независимости букв. Решение. По определению избыточности имеем R 1 = 1 − H 1 H 0 = 1 − H 1 lbN Поскольку мы имеем всего N=8 различных символов, то H 0 = lbN = lb8 = 3 bit, 40 Глава 1. Энтропия и информация H 1 = − 4 X i=1 p i lbp i = = − 8 16 · lb 8 16 + 4 16 · lb 4 16 + 2 16 · lb 2 16 + 4 · 1 16 · lb 1 16 + 0 · lb0 = 8 16 · 1 + 4 16 · 2 + 2 16 · 3 + 4 · 1 16 · 4 + 0 = 8 + 8 + 6 + 16 16 = 2.375 bit и R 1 = 1 − 2.375 3 = 0.208. N Задача 1.6. Найти: а) избыточность R 1 источника сообщений при статистической независимости букв; б) избыточность R 2 c учетом зависимости между буквами. для сообщения № сообщение № сообщение № сообщение 1 атомизатор 11 даунтаун 21 клочочек 2 менеджмент 12 плодовод 22 волнолом 3 кавказка 13 шаровары 23 воздуховоз 4 барбарис 14 эстафета 24 подлодка 5 берберин 15 прототип 25 размазня 6 варварка 16 прививка 26 гонгконг 7 колокол 17 прабабка 27 колокольня 8 женьшень 18 пленение 28 математик 9 чихуахуа 19 метатанк 29 постылость 10 наносность 20 ленинизм 30 водопровод Глава 2 Каналы связи 2.1 Пропускная способность каналов связи Пусть имеется дискретный стационарный канал связи без памяти (без последействия) с заданными характеристиками, причем все символы x i закодированного сообщения и соответствующие им элементарные сигналы y i имеют одинаковую длительность τ, где F = 1/τ - частота посылки символов. Канал без памяти полностью описывается априорными вероятностями P (x), характеризующими структуру закодированных сообщений, и условными вероятностями P (x/y), определяющимися характеристиками канала. Основные понятия: 1. информация, доставляемая символом x i по каналу связи определяется формулой I(x i ) = − lbp(x i ); 2. условная собственная информация I(x i /y k ) переданного символа x i при известном принятом y k I(x i /y k ) = − lbp(x i /y k ); 3. взаимная информация I(x i ; y k ) двух символов относительно друг друга (количество информации в доставленном y k относительно отправленного x i ) I(x i ; y k ) = lb p(x i /y k ) p(x i ) = lb p(x i , y k ) p(x i )p(y k ) ; 4. собственная информация I(x i y k ) совместного события x i y k I(x i y k ) = − lbp(x i y k ); 5. среднее количество информации I(x; y k ) доставляемое принятым символом y k относительно множества всех передаваемых символов x = {x i } I(x; y k ) = X i I(x i ; y k )p(x i /y k ) = X i p(x i /y k ) lb p(x i /y k ) p(x i ) ; 41 42 Глава 2. Каналы связи 6. среднее количество взаимной информации I(x i y) по множеству символов y = {y i } при фиксированном x i I(x i ; y) = X k I(x i ; y k )p(y k /x i ) = X k p(y k /x i ) lb p(y k /x i ) p(y k ) ; 7. полное среднее количество взаимной информации I(x; y) в множестве символов y относительно множества символов x I(x; y) = X k I(x; y k )p(y k ) = X i,k p(x i , y k ) lb p(x i /y k ) p(x i ) При решении большинства задач, связанных с построением систем связи наибольший интерес представляет величина I(x; y). Если символ x i статистически связан не только с символом y j , но и с третьим символом z k , то при известных вероятностях p(x i , y j , z k ) условная взаимная информация равна I(x i ; y j /z k ) = lb p(x i /y j z k ) p(x i /z k ) = lb p(x i ; y j /z k ) p(x i /z k )p(y j /z k ) , где I(x i ; y j /z k ) - количество информации, доставляемое y j относительно x i , когда предварительно известен символ z k По аналогии со средней взаимной информацией, средняя собственная информация определяется формулой I(x) = X i p(x i )I(x i ) = − X i p(x i ) lbp(x i ) = H(x). Здесь H(x) - энтропия случайного сигнала x, определяет количественную меру неопределенности о сообщении до его приема. Для энтропии справедливы следующие выражения: H(y/x) = − X ik p(x i , y k ) lbp(y k /x i ) = − X i p(x i ) X k p(y k /x i ) lbp(y k /x i ) = I(y/x), H(x/y) = − X ik p(x i , y k ) lbp(x i /y k ) = − X k p(y k ) X i p(x i /y k ) lbp(x i /y k ) = I(x/y), H(xy) = − X ik p(x i , y k ) lbp(x i , y k ), H(xy) = H(x) + H(y/x) = H(y) + H(x/y), где H(y/x) - условная энтропия множества событий y при данном множестве событий x; H(xy) - энтропия множества совместных событий xy. Когда множества x и y независимы, то H(y/x) = H(y), H(x/y) = H(x). 2.1. Пропускная способность каналов связи 43 При этом H(xy) = H(x) + H(y). Средняя взаимная информация связана с энтропией соотношениями I(x; y) = H(x) − H(x/y) = H(y) − H(y/x) = H(x) + H(y) − H(xy), I(x; y) ≤ H(x), I(x; y) ≤ H(y). Скорость передачи V k – среднее количество информации, получаемое за единицу времени: V k = F I(x; y) = F [H(x) − H(x/y)] = F [H(y) − H(y/x)] При отсутствии помех множества событий x и y статистически полностью взаимно зависимы, т. е. H(x/y) = H(y/x) = 0, следовательно, V k max = F H(x) = F H(y). Пропускная способность канала связи – максимальная скорость передачи информации, которая может быть достигнута выбором оптимального распределения вероятностей передачи P (x) символов сообщения: C = max p(x) F I(x; y) = max p(x) F [H(x) − H(x/y)] = max p(x) F [H(y) − H(y/x)] При отсутствии помех H(x/y) = H(y/x) = 0: C = C m = max p(x) F I(x; y) = max p(x) F H(x) = max p(x) F H(y). encoding data channel error source decoding |