Pl sql триггер на чтение. Триггеры ORACLE FORMS для начинающих. О событиях и триггерах

ВЗАИМНАЯ ИНФОРМАЦИЯ.

ЦЕЛЬ ЛЕКЦИИ: На основе понятия условной энтропии дать определение взаимной информации, рассмотреть свойства и представить вывод формулы для вычисления среднего количества взаимной информации.

Измеряй все, доступное измерению, и делай недоступное измерению доступным. Галилео Галилей

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

или H(x,y) = H(x) + H x (y)

Условная энтропия удовлетворяет следующим условиям.:

0 ≤ H x ( y ) ≤ H ( y ),

H x ( y ) = 0 , когда по реализации ансамбля X можно точно установить реализацию ансамбля Y ;

H x ( y ) = H ( y ), когда ансамбли Х и У независимы и знание реализации X не прибавляет информации об Y ;

H ( y ) > H x ( y ) – общий случай, когда знание реализацииX снижает первоначальную неопределенность Y .

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

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

Введем обозначение взаимной информации I ( x , y ). В соответствии со свойством 5 энтропии, можем записать соотношение

I ( x,y )= H ( x ) – H ( x,y ),

которое будет определять меру взаимной информации для любых пар ( x , y ) ансамблей Х и У.

В выражении Н(х) – априорная энтропия, Н( x , y ) – остаточная энтропия после получения сведений об ансамбле Х . Тогда I ( x , y ) будет характеризовать полную информацию, содержащуюся в ансамбле У об ансамбле Х .

Проиллюстрируем графически энтропию системы и информацию

Рис. 1 Графическое отображение взаимной информации.

Верхние раздельные овалы - при отсутствии связи между ансамблями переменных Х и У ;

Нижние совмещенные овалы - при наличии статистической связи между ансамблями Х и У .

Рассмотрим ансамбли Х и У , характеризующие систему. Энтропию ансамбля Х изобразим овалом с площадью Н(Х) : чем больше энтропия, тем больше площадь. Энтропия ансамбля У - второй овал с площадью Н(У ). Если ансамбли статистически независимы, т.е. связь между ними отсутствует, овалы не пересекаются. Полная энтропия системы равна сумме энтропий, т. е. сумме площадей.

Если же между ансамблями возникает статистическая связь (корреляция), то овалы на схеме пересекаются. Возникшая взаимная информация I(Х,У) и есть количественная мера этого пересечения. Энтропия уменьшается на величину этой информации:

Н(Х,У) = Н(Х) + Н(У) - I(Х, Y )

Чем больше взаимная информация, тем теснее связь, тем меньше энтропия Н(Х,У).

Из свойства 5 энтропии следует

H(X,Y) = H(X) + H X (Y)

H(X,Y) = H(Y) + H Y (X )

H(X) + H X (Y) = H(Y) + H Y (X)

H(X) –H X (Y) = H(Y) – H Y (X)

Сравнив и , отметим, что выражение характеризует взаимное равенство информации об ансамбле Х , если известен ансамбль У , и обратно, знание об ансамбле У , если известен ансамбль Х .

I ( X , Y ) – называется средней взаимной информацией, содержащейся в ансамблях Х и У .

Свойства взаимной информации .

I ( X,Y ) = I ( Y,X ). Взаимная информация симметрична.

I ( X , Y ) ≥ 0 . Взаимная информация всегда положительна.

3. I ( X , Y ) = 0 тогда и только тогда, когда ансамбли Х и У независимы.

I ( X , Y ) = H ( X ) – H X ( Y ) = H ( Y ) – H Y ( X ) = H ( X ) + H ( Y ) – H ( X , Y ), т. е. в случае наступления совместного события H ( X ) + H ( Y ) = H ( X , Y ) взаимная информация отсутствует.

I(X,Y) ≤ min{H(X),H(Y)}. Взаимная информация не может быть больше информации о каждом ансамбле в отдельности.

I(X,Y) ≤ min {log‌‌ ‌‌|X|, log|Y|}. Логарифмическая мера каждого из ансамблей в отдельности больше или равна взаимной информации.

7. Взаимная информация I ( X , Y ) имеет максимум (является выпуклой функцией распределения вероятностей).

В общем случае свойство 4 определяет взаимную информацию через энтропию объединенной системы H ( X , Y ) и энтропию отдельных ее частей H ( X ) и H ( Y ) рис.1.

I(X,Y) = 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(X,Y) =M[ - logP(X) – logP(Y) + log(X,Y)].

Преобразовав, получим

Выражение преобразуем с использованием свойства математического

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

У= [у=φ(х)]

представляет собой набор множества значений случайных величин. Для вычисления математического ожидания величины у необязательно знать распределение вероятностей p y ( y ) для у . Если распределение p x ( x ) по ансамблю Х известно, то

Тогда, если p ( x i ) m элементов ансамбля Х , а p ( y j ) вероятность реализации любого из n элементов ансамбля У , то выражение количества взаимной информации будет иметь вид

Данная формула позволяет определить полное количество взаимной информации об ансамбле Х по принятому на выходе канала ансамблю У . Количество взаимной информации измеряется в битах.

Марковская модель источника.

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

Случайный процесс х 1, x 2, … со значениями x i , алфавита Х, ( i = 1, 2, …) задан, если для любых n указан способ вычисления совместных распределений вероятностей p ( x 1 ,… x n ). Проще всего задать случайный процесс, предположив, что его значения в различные моменты времени независимы и одинаково распределены.

где p ( x i ) – вероятность появленияx i в момент i . Для описания такого процесса достаточно указать вероятности p ( x ) для всех x (всего I Х I – 1 вероятностей). Для описания более сложных моделей процессов следует опираться на свойство стационарности, позволяющее упростить математические выкладки. Процесс называется стационарным, если для любых n и t имеет место равенство

p(x 1 , …, x n ) = p( x 1+ t x n+ t ),

причем x i = x 1+ t , i = 1, … n . Случайный процесс стационарен, если вероятность любой последовательности не изменится при ее сдвиге во времени. Числовые характеристики, в частности математическое ожидание, стационарных процессов не зависят от времени. Рассматривая стационарные процессы, мы можем вычислять независящие от времени информационные характеристики случайных процессов. Пример стационарного процесса – процесс, значения которого независимы и одинаково распределены.

К. Шеннон так определяет дискретный источник сообщений: “ Можно считать, что дискретный источник создает сообщение символ за символом. Он будет выбирать последовательные символы с некоторыми вероятностями, зависящими, вообще говоря, как от предыдущих выборов, так и от конкретного рассматриваемого символа. Физическая система или математическая модель системы, которая создает такую последовательность символов, определяемую некоторой заданной совокупностью вероятностей, называется вероятностным процессом. Поэтому можно считать, что дискретный источник представляется некоторым вероятностным процессом. Обратно, любой вероятностный процесс, который создает дискретную последовательность символов, выбираемых из некоторого конечного множества, может рассматриваться как дискретный источник”.

Статистическая структура такого процесса и статистические свойства источника вполне определяются одномерными p ( i ), двумерными p ( i , j ) вероятностями появления элементов сообщений на выходе источника. Как указывалось, если между последовательными элементами сообщения отсутствует статистическая связь, то статистическая структура сообщения полностью определяется совокупностью одномерных вероятностей. Появление того или иного элемента сообщения на выходе источника можно рассматривать как определенное событие, характеризующееся своей вероятностью появления. Для совокупности событий вместе с их априорными вероятностями появления существует понятие ансамбля .

Примерами дискретного источника могут служить:

Печатные тексты на различных языках.

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

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

Подобные источники создают представляют собой вероятностные процессы, известные как дискретные Марковские процессы. В общем случае результат может быть описан следующим образом. Существует конечное число возможных “состояний” системы : S 1 , S 2 ,. . . , S n . Кроме того, имеется совокупность переходных вероятностей pi (j ), т. е. вероятностей того, что система, находящаяся в cостоянии S i , перейдет затем в состояние S j . Чтобы использовать этот Марковский процесс в качестве источника сообщений, нужно только предположить, что при каждом переходе из одного состояния в другое создается одна буква. Состояния будут соответствовать “остатку влияния” предшествовавших букв. В графическом примере “состоянием” является узловая точка схемы, а переходные вероятности и создаваемые при этом буквы указаны около соответствующих линий.

Такой источник из четырех букв A , B , C , В , имеющих, соответственно, переходные вероятности 0,1; 0,4; 0,3; 0,2, возвращаясь в узловую точку после

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

На дискретный источник можно распространить такие характеристики случайного сигнала, как эргодичность и стационарность. Полагая источник эргодическим, можно “… отождествлять средние значения вдоль некоторой последовательности со средним значением по ансамблю возможных последовательностей (причем вероятность расхождения равна нулю)”. Например, относительная частота буквы А в частной бесконечной последовательности будет с вероятностью единица равняться ее относительной частоте по ансамблю последовательностей.

Простейшей моделью источника, порождающего зависимые сообщения, является Марковский источник. Случайный процесс называют цепью Маркова связности s , если для любых n и для любых x = ( x 1 , …, x n ) алфавита X справедливы соотношения

p(x) = p(x 1 , …, x s )p(x s+ 1 / x 1 , … , x s )p(x s+2 /x 2 , …,x s+1 )…p(x n /x n-s ,…,x n-1 ).

Марковским процессом связности s называется такой процесс, для которого при n > s p ( x n ,…, x n -1 ) = p ( x n / x n - s ,…, x n -1 ), т. е. условная вероятность текущего значения при известных s предшествующих не зависит от всех других предшествующих значений.

Описание Марковского процесса задается начальным распределением вероятностей на последовательностях из первых s значений и условными вероятностями p ( x n / x n - s ,…, x n -1 ) для всевозможных последовательностей. Если указанные условные вероятности не изменяются при сдвиге последовательностей во времени, Марковская цепь называется однородной . Однородная Марковская цепь связности s = 1 называется простой цепью Маркова. Для ее описания достаточно указать распределение вероятностей p ( x 1 ) величины х, принадлежащей множеству Х и условные вероятности

π ij = P(x t = j / x t-1 = i), i,j = 0,1,…,M-1 ,

называемые переходными вероятностями цепи Маркова.

Переходные вероятности удобно записывать в виде квадратной матрицы размерности М х М

называемой матрицей переходных вероятностей. Эта матрица – стохастическая (неотрицательная, сумма элементов каждой строки равна 1).

Если p t - стохастический вектор, компоненты которого – вероятности состояний цепи Маркова в момент времени t , т.е. p t =[ p t (0),…, p t (M -1)], где p t (i ) есть вероятность состояния i в момент времени t (I = 0,1,…, M -1 ), то из формулы полной вероятности следует

или в матричной форме

p t +1 = p t Π . [ 10 ]

Для произвольного числа шагов n получим

,

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

p = p Π . [ 2 ]

Предположим, р 1 = р . Тогда, воспользовавшись выражением , получим р 2 = р и, наконец, p t = p при всех t . Таким образом, Марковская цепь стационарна, если в качестве начального распределения выбрано решение уравнения [ 2 ].

Стохастический вектор р , удовлетворяющий уравнению [ 2 ], называется стационарным распределением для цепи Маркова, задаваемой матрицей переходных вероятностей Π. Финальным распределением вероятностей называют вектор

[ 3 ]

Величина p ∞ не зависит от начального распределения и от времени, т. е. является стационарным распределением. Цепи, определяемые выражением [ 3 ], называют эргодическими. Если все элементы матрицы Π положительны и не равны нулю, соответствующая Марковская цепь эргодична. Чтобы сформулировать необходимое и достаточное условие эргодичности, введем несколько определений.

Состояние цепи i достижимо из состояния j , если для некоторого n вероятность перехода из состояния j в состояние i за n шагов положительна. Множество состояний называется замкнутым , если никакое состояние вне С не может быть достигнуто из состояния, входящего в С .

Цепь называетсянеприводимой , если в ней нет никаких замкнутых множеств кроме множества всех состояний. Цепь Маркова неприводима тогда и только тогда, когда состояния достижимы друг из друга. Состояние i называется периодическим, если существует такое t > 1 , что вероятность перехода из i в i за n шагов равна нулю при всех n не кратных t . Цепь, не содержащая периодических состояний, называется непериодической. Непериодическая неприводимая цепь Маркова эргодична.

ЛИТЕРАТУРА .

1. Шеннон К. Работы по теории информации и кибернетике. М.: изд. “ИЛ”, 1963 г., стр. 249 – 259 .

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

Наименование параметра	Значение
Тема статьи:	Взаимная информация
Рубрика (тематическая категория)	Образование

Определим теперь информацию, содержащуюся в одном ансамбле относительно другого, к примеру, в принятом сигнале относительно переданного сообщения. Для этого рассмотрим сообщение двух дискретных ансамблей A и B , вообще говоря, зависимых. Его можно интерпретировать как пару ансамблей сообщений, либо как ансамбли сообщения и сигнала, с помощью которого сообщение передаётся, либо как ансамбли сигналов на входе и выходе канала связи и т. д. Пусть P(a k ,b l )совместная вероятность реализаций a k и b l . Cовместной энтропией ансамблей A и B будем называть:

(2.6)

Введём также понятие условной энтропии:

(2.7)

где P(a k / b l )- условная вероятность a k , если имеет место b l , здесь математические..

Из теоремы умножения вероятностей следует, что .

Для условной энтропии справедливо двойное неравенство:

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

1. Равенство имеет место в том случае, когда, зная реализацию , можно точно установить реализацию . Другими словами, содержит полную информацию об .

2. Другой крайний случай, когда имеет место, в случае если события и независимые. В этом случае знание реализации не уменьшает неопределённости , ᴛ.ᴇ. не содержит ни какой информации об А.

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

Подставляя в эту формулу значения H(A) и H(A/B) выразим взаимную информацию через распределœение вероятностей:

В случае если воспользоваться теоремой умножения , то можно записать в симметричной форме т.к. :

(2.12)

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

Сформулируем основные свойства взаимной информации:

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

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

3.

4. , причём равенство имеет место, когда по реализации можно точно установить реализацию .

5. Полагая и учитывая, что получим:

(2.14)

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

Пусть - ансамбль дискретных сообщений, а - ансамбль дискретных сигналов, в которые преобразуются сообщения . Тогда в том и только в том случае, когда преобразование обратимо. При необратимом преобразовании и разность можно назвать потерей информации при преобразовании . Её называют ненадёжностью. Τᴀᴋᴎᴍ ᴏϬᴩᴀᴈᴏᴍ, информация не теряется только при обратимых преобразованиях.

В случае если - среднее время передачи одного сообщения, то разделив на формулы H(A/B) и I(A,B) и обозначая:

, , (2.15)

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

Рассмотрим пример: если - ансамбль сигналов на входе дискретного канала, а - ансамбль сигналов на его выходе, то скорость передачи информации по каналу.

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

“производительность канала”, то есть полная собственная информация о принятом сигнале за единицу времени.

Величина представляет собой скорость “утечки” информации при прохождении через канал, а - скорость передачи посторонней информации, не имеющий отношения к и создаваемой присутствующими в канале помехами. Соотношение между и зависит от свойств канала. Так, к примеру, при передаче телœефонного сигнала по каналу с узкой полосой пропускания, недостаточной для удовлетворительного воспроизведения сигнала, и с низким уровнем помех теряется часть полезной информации, но почти не получается бесполезной. В этом случае . В случае если же расширяется полоса, сигнал воспроизводится точно, но в паузах ясно прослушиваются “наводки” от сосœеднего телœефонного канала, то, почти не теряя полезной информации, можно получить много дополнительной, как правило, бесполезной информации и .

Эффективное кодирование дискретных сообщений

Применим полученные результаты к проблеме кодирования дискретных сообщений. Пусть - источник последовательности элементарных сообщений (знаков) с объёмом алфавита и производительностью . Для передачи по дискретному каналу нужно преобразовать сообщения в последовательность кодовых сигналов так, чтобы эту кодовую последовательность можно было затем однозначно декодировать. Для этого крайне важно, чтобы скорость передачи информации от источника к кодеру равнялась производительности источника , =. Но с другой стороны из предыдущего: . Следовательно, необходимым условием для кодирования является или, обозначая через длительность кодового символа, через длительность элементарного сообщения, , или

, (2.17)

где - число кодовых символов, a - число сообщений, передаваемых в секунду.

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

Но это отношение представляет среднее число кодовых символов, приходящихся на одно элементарное сообщение. Τᴀᴋᴎᴍ ᴏϬᴩᴀᴈᴏᴍ, для возможности кодирования и однозначного декодирования сообщения крайне важно, чтобы среднее число двоичных символов на сообщение было не меньше энтропии . Является ли это условие достаточным?

Одна из базовых теорем теории информации утверждает, что оно “почти достаточно”. Точнее, содержание теоремы кодирования для источника состоит по сути в том, что передавая двоичные символы со скоростью симв/с можно закодировать сообщения так, чтобы передавать их со скоростью:

(сообщений в секунду),

где - сколь угодно малая величина.

Эта теорема почти тривиальна, в случае если источник передаёт сообщения независимо и равновероятно. В этом случае и, в случае если ещё к тому же -целая степень двух , то .

Таким образом можно закодировать сообщения любого источника с объёмом алфавита , затрачивая двоичных символов на элементарное сообщение. В случае если, однако, сообщения передаются не равновероятно, и (или) не независимо, то и возможно более экономное кодирование с затратой символов на сообщение. Относительная экономия символов при этом окажется равной . Τᴀᴋᴎᴍ ᴏϬᴩᴀᴈᴏᴍ, избыточность определяет достижимую степень ”сжатия сообщения”.

Рассмотрим несколько примеров.

Так, в случае если элементарными сообщениями являются русские буквы и они передаются равновероятно и независимо, то . Каждую букву можно закодировать последовательностью из пяти двоичных символов, поскольку существует 32 такие последовательности.

Разумеется, таким же равномерным кодом можно закодировать и буквы в связном русском тексте, и именно так часто поступают на практике. Но можно обойтись значительно меньшим числом символов на букву. Для русского литературного текста и, следовательно, возможен способ эффективного кодирования (или кодирования со сжатием сообщения), при котором в среднем на букву русского текста будет затрачено немногим более 1,5 двоичных символа, то есть на 70% меньше, чем при примитивном коде.

Существует довольно много способов сжатия сообщений или сокращения избыточности текста. Так, к примеру:”Эта фр.
Размещено на реф.рф
напис. сокращ. и тем не м. мож. надеят., что Вы пойм. её прав.” В предыдущей фразе удалось уменьшить число букв, а следовательно и символов, в случае если её кодировать равномерным кодом почти на 40%.

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

Дальнейшее сжатие сообщений возможно путём применения неравномерного кода, в случае если более короткие последовательности используются для более частых букв (слов) и более длинные – для более редких. Заметим, что эта идея неравномерного кодирования впервые нашла применение в телœеграфном коде Морзе, в котором наиболее короткие комбинации использованы для часто встречающихся букв (е, и, т, с, а).

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

Разработано много методов эффективного кодирования для различных источников. Задача эффективного кодирования наиболее актуальна не для передачи текста͵ а для других источников со значительно большей избыточностью. К ним относятся, к примеру, телœевизионные передачи (промышленное телœевидение), некоторые телœеметрические системы, в которых возможно сжатие в десятки раз, фототелœеграфия.

Тема 2.4. Информация в непрерывных сигналах

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

Разобьём область значений на небольшие интервалы протяжённостью . Вероятность того, что лежит в интервале , +, то есть , приблизительно равна , причём приближение тем точнее, чем меньше интервал . Степень неожиданности такого события равна . В случае если значения в пределах конечного интервала заменить значениями в начале интервала, то непрерывный ансамбль заменится дискретным, а его энтропия определится как:

Будем теперь увеличивать точность определœения значения , уменьшая интервал . В пределœе, при должна получиться энтропия непрерывной случайной величины:

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

Обратим внимание на первый член в данной формуле. Он является конечным и определяется плотностью распределœения вероятности . Его называют дифференциальной энтропией и обозначают :

(2.20)

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

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

Здесь - определённая ранее дифференциальная энтропия , а - условная дифференциальная энтропия. Легко убедиться, что основные свойства взаимной информации остаются справедливыми и в данном случае.

В качестве примера найдём дифференциальную энтропию случайной величины с нормальным распределœением вероятности:

, (2.23)

где математическое ожидание, а - дисперсия .

Подставив (2.23) в (2.20), найдём:

Первый интеграл по общему свойству плотности вероятности равен 1, а второй – по определœению дисперсии равен . Окончательно

Τᴀᴋᴎᴍ ᴏϬᴩᴀᴈᴏᴍ, диффиринциал энтропия гауссовский случайной величины не зависит от её математического ожидания и монотонно возрастает с увеличением дисперсии.

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

Тема 2.5. Пропускная способность канала связи

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

Максимальное количество переданной информации, взятое по всœевозможным источникам входного сигнала, характеризует сам канал и принято называть пропускной способностью канала в расчёте на один символ:

бит/ симв.

(где максимизация производится по всœем многомерным распределœениям вероятностей Р(А))

Можно также определить пропускную способность С канала в расчёте на единицу времени.

Вычислим пропускную способность симметричного канала без памяти

(2.26)

Величина в данном случае легко вычисляется, поскольку условная (переходная) вероятность принимает только два значения: , в случае если и (1-Р), в случае если .

Первое из этих значений возникает с вероятностью Р, а второе – с вероятностью (1-Р). К тому же, поскольку рассматривается канал без памяти, результаты приёма отдельных символов независимы друг от друга.

По этой причине

(2.27)

Следовательно Н(В/А) не зависит от распределœения вероятности в ансамбле А, а определяется только переходными вероятностями канала. Это свойство сохраняется для всœех моделœей с аддитивным шумом.

Подставив (2.27) в (2.26) получим:

Поскольку в правой части только член Н(В) зависит от распределœения вероятности Р(А), то максимизировать крайне важно именно его.

Максимальное значение Н(В) равно log m и реализуется оно тогда, когда всœе принятые символы равновероятны и независимы друг от друга. Легко убедиться, что это условие удовлетворяется, в случае если входные символы равновероятны и независимы, поскольку в данном случае

При этом и

Отсюда пропускная способность в расчёте на единицу времени

Для двоичного симметричного канала (m=2) пропускная способность в двоичных единицах в единицу времени

Зависимость от Р согласно формуле (2.31)

При Р=1/2 пропускная способность двоичного канала С=0, поскольку при такой вероятности ошибки последовательность выходных двоичных символов можно получить совсœем не передавая сигналы по каналу, а выбирая их наугад (к примеру, по результатам бросания монеты), то есть при Р=1/2 последовательности на выходе и входе канала независимы. Случай С=0 принято называть обрывом канала. То, что пропускная способность при P=1 в двоичном канале такая же, как при Р=0 (канал без шумов), объясняется тем, что при Р=1 достаточно всœе выходные символы инвертировать (то есть заменить 0 на 1 и 1 на 0), чтобы правильно восстановить входной сигнал.

Пропускная способность непрерывного канала вычисляется аналогично. Пусть, к примеру, канал имеет ограниченную полосу пропускания шириной F. Тогда сигналы U(t) и Z(t) соответственно на входе и выходе канала по теореме. Котельникова определяются своими отсчётами, взятыми через интервал 1/(2F), и в связи с этим информация, проходящая по каналу за неĸᴏᴛᴏᴩᴏᴇ время Т, равна, сумме количества информации, переданной за каждый такой отсчёт. Пропускная способность канала на один такой отсчёт:

Здесь U и Z – случайные величины – сечения процессов U(t) и Z(t) на входе и выходе канала соответственно и максимум берётся по всœем допустимым входным сигналам, то есть по всœем распределœениям U.

Пропускная способность С определяется как сумма значений , взятая по всœем отсчётам за секунду. При этом разумеется дифференциальные энтропии в (2.35) должны вычисляться с учётом вероятностных связей между отсчётами.

Вычислим пропускную способность непрерывного канала без памяти с аддитивным белым гауссовским шумом, имеющим полосу пропускания шириной F, в случае если средняя мощность сигнала . Мощность (дисперсию) шума в полосœе F обозначим . Отсчёты выходного и входного сигналов, а также шума N связаны равенством:

Так как N имеет нормальное распределœение с нулевым математическим ожиданием, то и условная плотность вероятности при фиксированном U будет так же нормальной – с математическим ожиданием U и дисперсией .

Пропускная способность на один отсчёт определятся по формуле (2.32):

Согласно (2.24) условная дифференциальная энтропия h(Z/U) нормального распределœения не зависит от математического ожидания и равна . По этой причине для нахождения следует найти такую плотность распределœения , при которой максимизируется h(Z). Из (2.33) учитывая, что U и N независимые случайные величины имеем для дисперсий

Τᴀᴋᴎᴍ ᴏϬᴩᴀᴈᴏᴍ, дисперсиия фиксирована, так как и заданы. Как известно, при фиксированной дисперсии максимальная дифференциальная энтропия обеспечивается нормальным распределœением. Из (2.33) видно, что при нормальном одномерном распределœении U распределœение Z будет так же нормальным и, следовательно, обеспечивается максимум дифференциальной энтропии (2.24).

(2.34)

Переходя к пропускной способности С в расчёте на секунду, заметим, что информация, переданная за несколько отсчётов, максимальна в том случае, когда отсчёты сигналов независимы. Этого можно достичь, в случае если сигнал U(t) выбрать так, чтобы его спектральная плотность была равномерной в полосœе F. Отсчёты разделённые интервалами, кратными 1/(2F), взаимно некоррелированы, а для гауссовских величин некоррелированность означает независимость. По этой причине пропускную способность С (за секунду) можно найти, сложив пропускные способности (2.35) для 2F независимых отсчётов:

(2.36)

Она реализуется, в случае если U(t) – гауссовский процесс с равномерной спектральной плотностью в полосœе частот F (квазибелый шум).

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

Соотношение (2.36) принято называть формулой Шеннона. Эта формула имеет важное значение в теории информации, так как определяет зависимость пропускной способности рассматриваемого непрерывного канала от таких его технических характеристик, как ширина полосы пропускания и отношение сигнал шум. Формула Шеннона указывает на возможность обмена полосы пропускания на мощность сигнала и наоборот. При этом поскольку С зависит от F линœейно, а от – по логарифмическому закону, компенсировать возможное сокращение полосы пропускания увеличением мощности сигнала, как правило, не выгодно. Более эффективным является обратный обмен мощности сигнала на полосу пропускания.

Максимальный объём информации, которую можно в среднем передать по непрерывному каналу за время ,

Для гауссовского канала

(2.37)

Заметим, что при Выражение (2.37) совпадает с характеристикой названной ёмкостью (объёмом) канала.

Тема 2.6. Теорема К. Шеннона

Пропускная способность канала характеризует потенциальные возможности передачи информации. Οʜᴎ раскрываются в фундаментальной, теореме теории информации, известной как оснавная теорема кодирования К. Шеннона. Применительно к дискретному источнику она формулируется так: если производительность источника сообщений Н(А) меньше пропускной способности канала С:

(A)

то существует способ кодирования (преобразования сообщения в сигнал на входе) и декодирования (преобразования сигнала в сообщение на выходе канала), при при котором вероятность ошибочного декодирования и ненадёжность бывают сколь угодно малы. В случае если же (A)>C, то таких способов не существует.

Рассмотрим содержание теоремы Шеннона.

Как отмечалось, для восстановления по пришедшему сигналу переданного сообщения крайне важно, чтобы сигнал содержал о нём информацию, равную энтропии сообщения. Следовательно, для правильной передачи сообщения крайне важно, чтобы скорость передачи информации была не меньше производительности источника. Так как по определœению скорость передачи информации не превышает пропускной способности, то неравенство (A)

Но является ли это условие достаточным?

Конечно, при C>H’(A) можно передавать такие сигналы, что достигнет значения H’(A). Но - ϶ᴛᴏ скорость передачи информации о сигнале В, а не о сообщении А. По этой причине вопрос сводится к тому, можно ли установить такое соответствие (код) между сообщением А и сигналом В чтобы вся информация, полученная на выходе канала о сигнале В, была в то же время информацией о сообщении А? (Чтобы преобразования между А и В были обратимыми)

Положительный ответ на данный вопрос очевиден в тривиальном случае, когда в канале нет помех и сигнал В принимается безошибочно. При этом , и если между А и В установлено взаимно однозначное соответствие, то по принятому сигналу можно однозначно восстановить сообщение. В общем же случае в канале имеются помехи и сигнал В принимается с ошибками, так что . Отсюда следует, что даже если достигнет (A), то всё равно (В)> (А), так как . Это значит, что производительность источника сигнала В должна быть выше производительности источника сообщения А и, следовательно, В содержит, кроме информации об А дополнительную собственную информацию. Часть информации о сигнале В в канале теряется. Вопрос сводится к следующему: можно ли осуществить кодирование так, чтобы терялась только дополнительная (избыточная) часть собственной информации В, а информация об А сохранялась?

Теорема Шеннона даёт на данный вопрос почти положительный ответ, с той лишь поправкой, что скорость ʼʼутечки информацииʼʼ (или ненадёжность) не равна в точности нулю, но должна быть сделана сколь угодно малой. соответственно сколь угодно малой должна быть сделана вероятность ошибочного декодирования. При этом, чем меньше допустимая вероятность ошибочного декодирования, тем сложнее должен быть код.

В случае если бы двоичный канал был без помех и допускал передачу двоичных символов со скоростью символ/с, то пропускная способность в расчёте на секунду была бы

В этом случае данная теорема свелась бы к теореме о кодировании источника.

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

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

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

Тема 2.7. Информация в непрерывных сообщениях. Эпсилон-энтропия

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

Тем не менее, непрерывные сообщения (к примеру, телœевизионные, телœефонные) успешно передаются по каналам связи и записываются. Это объясняется тем, что на практике никогда не требуется абсолютно точного воспроизведения переданного и записанного сообщения. А для передачи даже с самой высокой, но ограниченной точностью требуется конечное количество информации аналогично тому, как и при передаче дискретных сообщений. Это количество информации тем больше, чем выше точность, с которой требуется передать (воспроизвести) непрерывное сообщение. Пусть допустимая неточность измеряется некоторым малым параметром . То минимальное количество информации, ĸᴏᴛᴏᴩᴏᴇ требуется передать по каналу связи для воспроизведения непрерывного сообщения с неточностью не более допустимой, академик А.Н.. Колмогоров предложил называть -энтропией (эпсилон-энтропией)

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

Взаимная информация - понятие и виды. Классификация и особенности категории "Взаимная информация" 2017, 2018.