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

М Вернер Основы кодирования

4.2. Совместная и условная энтропия

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

Рис. 4.2. Два связанных дискретных источника.

Совместная энтропия двух источников определяется как матема­тическое ожидание информации всех пар событий.

Совместная энтропия двух дискретных источников без памяти X и Y

Замечание. Здесь подразумевается, что рассматриваются все, па­ры совместных событий, то есть

Усредняя условные информации всех пар событий, получим услов­ную энтропию.

Таблица 4.1. Оценка совместной вероятности пар символов и вероятность отдельных символов и

Условная энтропия двух дискретных источников без памяти X и У

Пример: Связанные источники.

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

Пусть мы имеем выборку 100000 нар совместных событий дискретных источников X и У и алфавит каждого источника со­держит четыре события. Пусть пара встретилась 10000 раз. Тогда оценка вероятности пары равна 10000/10000 = 0,1.

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

1. Энтропии источников, X и Y ;

2. Совместную энтропию источников;

3. Обе условные энтропии;

Для контроля мы также вычислим:

4. Условные вероятности ;

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

Замечание. Для простоты проведем расчеты с точностью до 4 знаков после, запятой.

3. Без длинных вычислений из (4.16) получаем

Таблица 4.2. Условная вероятность

4. В таблице 4.2 приведены условные вероятности, подсчитанные ис­ходя из таблицы 4.1. Заметим, что при этом мы получили так назы­ваемую стохастическую матрицу. Сумма условных вероятностей для каждой строки равна 1.

4.3. Выводы

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

Таблица 4.3. Дискретные источники без памяти X и Y с сим­волами и

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

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

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

Глава 5. Стационарные дискретные источники с памятью

5.1. Энтропия

Сигналы аналоговых источников информации ограничены по поло­се, поэтому коррелированы во времени. Примером может служить аналоговый речевой сигнал в телефонной линии. После оцифров­ки, аналоговый источник превращается в дискретный и. например, после квантования сигнала на 256 уровней, мы получаем последовательнось 8-ми битовых двоичных целых чисел от 0 до 255. Как видно из рис. 5.1, значение двух соседних чисел близки друг к дру­гу, т.к. телефонный сигнал передается в узкой полосе частот. Из-за временной связи соседних отсчетов, то есть памяти отсчета, его неопределенность (информация) снижается по сравнению с анало­говым источником без памяти, поэтому основной задачей методов сжатия, особенно при передаче видеосигналов, является снижение избыточности.

Рис. 5.1. Непрерывный сигнал.

Возникает вопрос о том, каким образом определить энтропию дискретного источника с памятью. Начнем с постановки задачи.

Определение 5.1.2. Дискретный источник является стационар­ным, если совместные вероятности последовательностей событий не зависят от выбора начальной точки отсчета времени.

Замечание. Независимость наблюдений от, точки отсчета озна­чает, что мы можем начинать выборку с любого момента време­ни, то есть статистика не зависит от времени начала наблюде­ний.

Подход 1. Совместная энтропия.

Совместная энтропия двух источников х 1 и x 2 с одинаковыми алфавитами и одинаковыми распределениями вероятностей событий определяется как

Распространим это определение на L последовательных источников X i и найдем энтропию источника X L как

где вектор и суммирование производится по всем

Подход 2. Условная энтропия.

Хотя в левых частях равенств (5.3) и (5.4) мы уже использовали оди­наковое обозначение энтропии отдельного события, этот факт пред­стоит доказать. Проведем это доказательство за 4 тага.

1. не возрастает с ростом длины блока L ;

3. Н L (Х) не возрастает с ростом длины блока L ;

4. Энтропия стационарного дискретного источника

1. Из определения энтропии, как меры неопределенности источ­ника, непосредственно следует, что возрастание числа ограничений не может повлечь за собой рост неопределенности, а следовательно и энтропии.

2. Из «правила цепочки» для совместной энтропии следует

Так как энтропия всегда неотрицательна и имеет место неравен­ство

откуда следует нижняя оценка 2.

3. Из (5.5) прежде всего следует разложение

Используя уже известное соотношение (5.5). получаем неравенство

После подстановки получаем утверждение 3.

4. Утверждения 1.. 2. и ограничение устанавливают существование предела. Используя далее «правило цепочки», полу­чаем

Согласно утверждению 1., условная энтропия в правой части ра­венства не возрастает, поэтому справедлива оценка

Устремляя j к бесконечности, получим

5.2. Теорема кодирования источников 2

Теперь мы можем дополнить теорию информации еще одной теоре­мой. Оказывается, что объединяя события источника в блоки длины L и кодируя эти блоки, средняя длина кодового слова на событие может достигнуть энтропию источника при как угодно близко. При этом намять источника полностью учитывается.

Теорема 5.2.1. Теорема кодирования стационарного дискретного ис­точника с энтропией

Для блока длины L существует D-ичный префиксный код, в кото­ром средняя длина кодового слова на одно событие п удовлетворяет неравенству

Теорема (5.14) не нуждается в специальном доказательстве. Если мы рассматриваем блоки длины L как новые независимые события с энтропией, равной и применяем теорему кодирования источников 1, то мы имеем

5.3. Конечные цепи Маркова

В этом и последующих параграфах будет рассматриваться специ­альная форма дискретных источников с памятью марковские ис­точники. Их описание сходно с марковскими цепями, которые на­шли разнообразное применение в других областях науки и техники. Так, на основе марковских цепей строятся модели распознавания ре­чи, модели передачи по телефонным коммутируемым каналам. Це­пи Маркова* используются при исследовании моделей сетей связи (каналы Гильберта-Элиота) и в теории управления транспортными потоками. Значение цепей Маркова основывается не только на их полном математическом описании, но также на том факте, что с их помощью можно составить математическую модель многих процес­сов, наиболее близкую к практике.

* Л. А. Марков (1856-1922) выдающийся русский математик. Прим. перев.

5.3.1. Дискретные во времени цепи Маркова

В этом разделе шаг за шагом вводится понятие конечных дискрет­ных во времени марковских цепей. Мы наглядно поясним это поня­тие на простейшем примере «случайных блужданий».

Пример: Случайные блуждания студента:

Р («случайные блуждения» приведут к состоянию S 1 в момент времени п — 7).

Рис. 5.2. Случайные блуждания студента.

Исходным пунктом для описания марковской цени является мно­жество состояний

Для того, чтобы полностью определить цепь Маркова, нам оста­ется задать метод подсчета вероятностей для любого момента времени п. Из определения вероятности имеем

Особое значение имеет распределение вероятностей в начале на­блюдения, т.е. начальные условия

Смена состояний описывается переходными, вероятностями

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

1. Одно из состояний в момент времени п всегда достигается при любом S i в момент п 1

При преобразовании (5.30) в (5.26), мы предполагаем

Последнее равенство характеризует марковский процесс.

Определение 5.3.1. Марковским процессом называется процесс, в котором прошлое не оказывает влияния на будущее, если настоящее известно.

Применение цепей Маркова сильно упрощается, когда они гомо­генны, стационарны и регулярны. Рассмотрим эти три понятия.

Определение 5.3.2. Цепь Маркова гомогенна, если переходные ве­роятности между состояниями не зависят от выбора временной точ­ки отсчета.

Таким образом, переходные вероятности зависят только от раз­ности времен отсчетов /.

Это равенство может быть представлено в виде суммы покомпонент­ных произведений векторов-строк на векторы-столбцы. Записав пе­реходные вероятности в виде матрицы, получим уравнение (5.33) в матричной форме

Этот процесс может быть начат с первого шага с помощью мат­рицы переходных вероятностей

Заметим, что матрица П стохастическая матрица с суммой веро­ятностей строк равной 1.

Теорема 5.3.1. Гомогенная цепь Маркова полностью характеризу­ется матрицей переходных вероятностей и исходным распределе­нием состояний.

Источник

Энтропия объединения

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

Рассмотрим объединение, состоящее из двух ансамблей X и Y, например из двух дискретных измеряемых величин, связанных между собой вероятностными зависимостями. Объединение ансамблей характеризуется матрицей P(X, Y) вероятностей P(x_i, y_i) всех возможных комбинаций состояний ансамбля X и состояний ансамбля Y:

. (2.16)

Cуммируя столбцы и строки матрицы (2.16), получим информацию об ансамблях X и Y исходных источников:

(2.17)

где и .

Вероятности P(x_i, y_j) совместной реализации взаимозависимых состояний x_i и y_i можно выразить через условные вероятности P(x_i /y_j) или P(y_j /x_i) в соответствии с тем, какие состояния принять за причину, а какие – за следствие.

(2.18)

где P(x_i /y_j) – вероятность реализации состояний x_i ансамбля X при условии, что реализовалось состояние y_j ансамбля Y; P(y_j / x_i) – вероятность реализации состояний y_j ансамбля Y при условии, что реализовалось состояние x_i ансамбля X.

Тогда выражение для энтропии объединения в соответствии с (2.14) принимает вид:

(2.19)

(2.20)

При усреднении по всем состояниям ансамбля X получаем среднюю неопределенность, приходящуюся на одно состояние ансамбля Y при известных состояниях ансамбля X:

(2.21)

Величину H(Y/X) называют полной условной или просто условной энтропией ансамбля Y по отношению к ансамблю X.

Подставляя (2.21) в (2.19), получаем

(2.22)

Выражая через другую условную вероятность в соответствии с (1.18), найдем

(2.23)

(2.24)

и (2.25)

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

В случае статистической независимости ансамблей X и Y имеют

и ,

(2.26)

Свойства энтропии

2.4.1. Энтропия всегда неотрицательна, так как значения вероятностей выражаются дробными величинами, а их логарифмы – отрицательными величинами (2.14).

2.4.2. Энтропия равна нулю в том крайнем случае, когда одно событие равно единице, а все остальные – нулю. Это положение соответствует случаю, когда состояние источника полностью определено.

2.4.3. Энтропия имеет наибольшее значение при условии, когда все вероятности равны между собой (2.15).

2.4.4. Энтропия источника Х с двумя состояниями х₁ и х₂ изменяется от нуля до единицы, достигая максимума при равенстве их вероятностей

График зависимости Н(Х) в функции Р:

приведен на рис. 2.1.

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

Рис. 2.1. Зависимость Н(Х) в функции Р

2.4.5. Энтропия объединения нескольких статистически независимых источников информации равна сумме энтропий исходных источников

2.4.6. Энтропия объединения двух статистически связанных ансамблей X и Y равна

2.4.7. Энтропия объединения любого числа зависимых ансамблей определяется из выражения

(2.29)

2.4.8. Энтропия не зависит от значений, принимаемых случайными величинами, а зависит только от вероятностей их появления (2.14).

2.4.9. Если события x_i и y_j статистически независимы при любых i и j, то

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

Действительно, условные вероятности P(x_i/y_j) и P(y_j, x_i) в этом случае принимают значения, равные нулю или единице. Поэтому все слагаемые, входящие в выражения (2.20) и (2.25), для частных условных энтропий равны нулю. Тогда в соответствии с (2.21) и (2.24) условные энтропии равны нулю.

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

Уяснению соотношений между рассмотренными энтропиями дискретных источников информации (ансамблей) соответствует их графическое отображение (рис. 2.2).

Источник

Контрольная работа: Энтропия сигналов

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

На тему: Энтропия сигналов

1. ЭНТРОПИЯ ОБЪЕДИНЕНИЯ

X Y X Y

Рис. 1. Безусловная энтропия

Рис. 2. Условная энтропия

Рис. 3 Совместная энтропия

Рис. 4. Взаимная энтропия

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

Рассмотрим схему рис. 5:

Рис. 5. Передача сообщений

Энтропия источника представляет собой неопределенность появления на выходе источника сообщений символа первичного алфавита и определяется соотношением:

()

Энтропия приемника представляет собой неопределенность появления на входе приемника сообщений символа после его появления на выходе источника и определяется соотношением:

(2)

При отсутствии потерь: H(X) = H(Y). При наличии помех они уничто-жают часть информации. При этом потери информации можно определить через частные и общую условную энтропию.

Вычисление общей условной энтропии удобно производить с помощью канальных матриц ( матрицей переходных состояний).

Потери информации в канале можно оценивать со стороны источника или приемника сообщений.

Y

.

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

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

. (3)

Для не равновероятных сигналов на выходе источника общая условная энтропия вычисляется по формуле:

(4)

Частная условная энтропия определяет потери информации, приходящиеся на долю какого – либо конкретного сигнала (например, потери для сигнала x₁ )

. (5)

При отсутствии помех вероятность получения правильного сигнала станет безусловной, а условная энтропия будет равна нулю.

Канальная матрица имеет вид, приведенный в табл. 2.

Y

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

. (6)

Для не равновероятных сигналов на входе приемника общая условная энтропия вычисляется по формуле:

( 17)

. (8)

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

Пример 2. Определить энтропию источника сообщений, если вероят-ности появлений символов на входе приемника, равны: P(b₁ )=0,1; P(b₂ )=0,3; P(b3)=0,4, P(b₄ )=0,2 а канальная матрица имеет вид:

P(a/b) =.

Сумма вероятности при одноименных условиях равна

Решение: Определим энтропию источника

.

= 0,1 × 0,01+0,3 × 0,98+0,4 × 0,01+0, × 2 × 0,01=0,301;

0,1 × 0+0,3 × 0+0,4 × 0,98+0,2 × 0,02=0,396;

0,1 × 0+0,3 × 0+0,4 × 0,01+0,2 × 0,97=0,198;

0,105+0,301+0,396+0,198=1.

При этом энтропия источника равна:

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

.

Решение: Для равновероятных символов в сообщении энтропия источника сообщений равна:

бит/симв.

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

=

,

Решение: Энтропия приемника равна:

.

Вероятности появления символов на входе приемника

;

;

.

.

2. ЭНТРОПИЯ ИСТОЧНИКА НЕПРЕРЫВНЫХ СООБЩЕНИЙ

Рис. 6. График функции плотности вероятности

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

(9)

Переходим к пределу:

.

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

, (20)

Различные классы физических явлений и процессов подчиняются различным законам распределения. Непрерывные сигналы полностью характеризуются законами распределения (интегральным или дифференциальным). На любые реальные сигналы накладываются определенные ограничения, например: по средней мощности (нагрев аппаратуры); по мгновенной или пиковой мощности (перегрузки).

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

; .

Решив уравнения, получим симметричный нормальный закон распределения

. (11)

Если среднюю мощность не ограничивать

то получим равномерный закон распределения.

Определим максимальное значение для энтропии:

Дифференциальная энтропия для нормального распределения равна:

(12)

Полная энтропия для нормального распределения равна:

. (13)

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

Дифференциальная энтропия для равномерного распределения равна:

(14)

Полная энтропия сигнала с равномерным распределением равна:

, (15)

Определим дифференциальную энтропию для экспоненциального распределения. Это распределение широко используется для определения интенсивности отказов в радиоэлектронной аппаратуре

Полная энтропия для экспоненциального распределения равна:

. (16)

1. Коганов А. В. Векторные меры сложности, энтропии, информации. “Математика. Компьютер. Образование”. Вып. 7, ч. 2, “Прогресс-Традиция”, М., 2000, с. 540 — 546

2. Яглом А. М., Яглом И. М. Вероятность и информация. М., 1957.

3. Шеннон К. Работы по теории информации и кибернетике. — М.: Изд. иностр. лит., 1963. — 830 с.

4. Волькенштейн М. В. Энтропия и информация. — М.: Наука, 1986. — 192 с.

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

6. Вероятностные методы в вычислительной технике. /Под ред. А.Н. Лебедева, Е.А.Чернявского. –М.: Высш. шк., 1986.

7. Седов Е.А. Взаимосвязь информации, энергии и физической энтропии в процессах управления и самоорганизации. Информация и управ­ление. М., Наука, 1986.

Источник