Сорока Н.И., Кривинченко Г.А. Теория передачи информации

Подождите немного. Документ загружается.

Величина H(S

) случайно меняется в зависимости от состояния источника,

поэтому только среднее значение H(S

) может характеризовать энтропию ис-

точника:

åå

kbkb

k k kb

kbkbkkk

SSPSSP

SSPSSPSPSHSPXH

),/(log),(

)/(log)/()()()()(

где значок b/k у суммы означает, что производится суммирование по всем пере-

ходам из состояния S

в S

Таким образом, энтропия Н(Х) есть среднее значение (математическое

ожидание) энтропий всех характерных состояний источника.

В случае, когда символы источника независимы, имеется лишь одно состо-

яние S

, вероятность которого P(S

) = 1. При появлении символа x

источник

вновь возвращается в состояние S

(рис. 3.1), и при этом P(S

) = P(x

), следо-

вательно,

),(log)()()(

1 i

xPxPSHXH

-==

что совпадает с (2.14).

Если коррелятивные связи имеются между двумя соседними символами, то

P(S

) = P(x

) и P(S

) = P(x

Из (3.3) тогда получим

() () (/)log(/)

k bk bk

H X Px Px x Px x

=-=

åå

дв.ед.

(,)log(/).

символ

kb bk

Pxx Pxx

åå

(3.4)

Источник, генерирующий n разных символов – x

...

, в этом случае

может иметь n характерных состояний. Пример такого источника для случая

3 приведён на рис. 3.2.

В случае когда коррелятивные связи имеются между тремя символами, ха-

рактерные состояния определяются передачей двух символов, и их удобно ну-

меровать двумя индексами. Так, если генерируются x

, то источник переходит

в состояние S

и тогда:

P(S

) = P(x

) и P(S

) = P(x

) .

Из (3.4) получаем

111

() (,) (/,)log(/,)

nnn

hj i hj i hj

hji

H X Px x Px x x Px x x

===

ååå

111

дв.ед.

(,,)log(/,).

символ

nnn

hji i hj

hji

Pxxx Px xx

===

ååå

(3.5)

(3.3)

Чисел характерных состояний для этого случая столько, сколько имеется

различных пар (x

). Таких пар, очевидно, n

Аналогичные соотношения получаются и в случае, когда коррелятивные

связи распространяются на большее число символов.

3.2. Свойство энтропии эргодических источников

Теорема 1. Для любых

можно найти такое M

, при котором

эргодические последовательности с длиной

распадаются на два класса:

1) типичные, вероятности которых удовлетворяют следующему неравен-

ству:

)(

log

)( d<-

XH (3.6)

где Н(Х) – энтропия эргодического источника;

2) нетипичные, сумма вероятностей которых меньше e.

Доказательство. Последовательность C длины M образуется в результате

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

Рассмотрим переход из состояния S

в состояние S

во множестве последо-

вательностей С. Число M всегда может быть выбрано настолько большим, что

сумма вероятностей всех нетипичных последовательностей меньше e. Учиты-

вая, что для типичной последовательности частота событий может быть как

угодно близка к их вероятности, можно утверждать, что в каждой типичной по-

следовательности источник пребывает в состоянии S

приблизительно M

)

раз, а число переходов из состояния S

в состояние S

приблизительно равно

) P(S

), а точнее

M(P(S

) P(S

) ± h), (3.7)

где h с увеличением M может быть сделано как угодно малым.

Вероятность того, что в рассматриваемой последовательности имеет место

М переходов из состояния S

в S

, равна по теореме умножения вероятностей

.)/(

))/()((

kbk

SSPSPM

SSP (3.8)

Вероятность появления конкретной последовательности С определяется

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

.)/()(

))/()((

ÕÕ

kbk

SSPSPM

k kb

SSPCP

(3.9)

Логарифмируя последнее равенство, получаем:

)/log()/(log)/()(

)(

log

k kb

bkbk

k kb

SSSSPSSPSP

åååå

h±-= .(3.10)

Если учесть, что первая сумма в правой части совпадает с (3.3), а вторая

вследствие произвольной малости h всегда может быть меньше d, то получим

неопределённость (3.6).

P(x

)

P(x

)

P(x

)

P(x

)

P(x

)

P(x

)

P(x

)

P(x

)

P(x

)

P(x

)

P(x

)

P(x

)

Рис. 2.1. Диаграмма перехода, когда источник имеет

одно характерное состояние

Рис. 2.2. Диаграмма перехода, когда источник имеет

три характерных состояния

Следствие 1. Типичные последовательности приблизительно равноверо-

ятны. Для доказательства из (3.6) найдём Р(С):

.2)(2

)()( d--d+-

HMHM

При

Поэтому при достаточно большом М можно положить

P(C) » 2

-MH(X)

(3.11)

Из (2.11) видно, что все последовательности С равновероятны и число их

= 2

MH(X)

. (3.12)

В случае, если все n символов источника независимы и равновероятны, то

= 2

Mlogn

= n

. (3.13)

Легко видеть, что (3.13) определяет число всех возможных последователь-

ностей длины М, содержащих n различных символов.

Следствие 2. Чтобы экспериментально определить энтропию эргодиче-

ского источника, у которого вероятностные связи распространяются на очень

большое число символов, нам необходимо располагать последовательностью

ещё большей длины (

); при этом вычисленная энтропия будет как угодно

близка к своему пределу log1/P(C) = H(X).

3.3. Избыточность источника сообщений

Как известно, энтропия характеризует среднее количество информации,

несомое одним символом источника. Она максимальна, когда символы выраба-

тываются источником с равной вероятностью. Если же некоторые символы по-

являются чаще других, энтропия уменьшается, а при появлении дополнитель-

ных вероятностных связей между символами становится ещё меньше. Чем

меньше энтропия источника отличается от максимальной, тем рациональнее он

работает, тем большее количество информации несут его символы.

Для сравнения источников по их информативности введём параметр, назы-

ваемый избыточностью, равный

)(

)()(

max

XHXH

= (3.14)

Источник, избыточность которого R = 0, называется оптимальным. Если

1, то Н(Х) = 0, и, следовательно, информация, вырабатываемая источником,

равна нулю. В общем случае

Чем меньше избыточность R, тем раци-

ональнее работает источник.

Следует, однако, иметь в виду, что не всегда нужно стремиться к тому,

чтобы R = 0. Некоторая избыточность бывает полезной для обеспечения надеж-

ности передачи сообщений. Простейшим видом введения избыточности для

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

3.4. Поток информации источника сообщений

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

ляются через некоторые интервалы времени; в этом смысле мы можем говорить

о длительности отдельных символов, и, следовательно, может быть поставлен

вопрос о количестве информации, вырабатываемой источником в единицу вре-

мени.

Длительность выдачи знаков источником в каждом состоянии в общем

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

одного знака:

,)()(

k i

xPSP (3.15)

где P(S

) – вероятность того, что источник сообщений находится в состоянии

; P(x

) – вероятность появления символа x

в состоянии S

; t

– длительность

выдачи знака x

источником в состоянии S

Энтропия источника, приходящаяся на единицу времени, может быть

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

( ) дв.ед.

().

HX =

(3.16)

Если длительность выдачи знака не зависит от состояния источника, для

всех знаков одинакова и равна

то

Выражение для )(XH принимает

вид:

дв.ед.)(

)(

XH (3.17)

В этом случае поток информации максимальный, если энтропия источника

на символ максимальна. Для увеличения потока информации необходимо по

возможности уменьшить среднюю длительность символов

. С этой целью,

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

ния которых больше, была меньше, чем для символов, вероятность появления

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

информации на выходе источника необходимо не только обеспечить по воз-

можности большую энтропию на символ, но и правильно выбрать длительность

разных символов.

КОНТРОЛЬНЫЕ ВОПРОСЫ

1. Дайте определение эргодическому источнику.

2. Запишите выражение для энтропии эргодического источника, когда кор-

релятивные связи имеются между двумя и тремя символами.

3. Приведите диаграмму переходов, когда источник имеет четыре харак-

терных состояния.

4. Перечислите свойства энтропии эргодических источников.

5. Что характеризует избыточность источника сообщений?

6. Что понимается под потоком информации источника сообщений?

4. ИСТОЧНИКИ НЕПРЕРЫВНЫХ СООБЩЕНИЙ

4.1. Дифференциальная энтропия

Источники информации, множество возможных состояний которых со-

ставляют континуум, называют непрерывными.

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

зования устройств дискретизации и квантования. Вместе с тем существует не-

мало и таких систем, в которых информация передаётся и преобразуется непо-

средственно в форме непрерывных сигналов. Примерами могут служить систе-

мы телеизмерений с частотным разделением сигналов.

Основные информационные характеристики источников непрерывных со-

общений следующие: энтропия, условная энтропия, эпсилон

–

энтропия, эпси-

лон

–

производительность, избыточность, объём информации.

Формулу для энтропии источника непрерывных сообщений получают пу-

тем предельного перехода из формулы (2.14) для энтропии дискретного источ-

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

личины Х, характеризующейся плотностью распределения вероятностей W(X),

на конечное число m малых интервалов шириной Dx (рис. 4.1).

При реализации любого значения х, принадлежащего интервалу [x

, x

+Dx],

будем считать, что реализовалось значение x

дискретной случайной величины

Х. Поскольку Dx мало, то вероятность )( xxxxP

реализации значения

х из интервала [x

, x

+Dx] равна

.)()()( xxWdxxWxxxxP

D»=D+<<

D+

Тогда энтропия дискретной случайной величины

может быть записана

в виде

1 11

( ) () log () () log () () log

m mm

i ii

HX Wx x Wx x Wx x Wx Wx x x

= ==

=- D D=- D - D D=

å åå

( ) log ( ) log ,

Wx x Wx x

=- D -D

(4.1)

так как

xxW

.1)(

По мере уменьшения )( xxxxPx

все больше приближается к ве-

роятности P(x

), равной нулю, а свойства дискретной величины

– к свой-

ствам непрерывной случайной величины Х.

В результате предельного перехода при

получено

®D®D

D--=-= .loglim)(log)()(lim)(

xdxxWxWXHXH

(4.2)

Первый член выражения (4.2) зависит только от закона распределения не-

прерывной случайной величины Х и имеет такую же структуру, как энтропия

дискретного источника. Второй член

®D

loglim

стремится к бесконечности,

это полностью соответствует интуитивному представлению о том, что неопре-

деленность выбора из бесконечно большого числа возможных состояний (зна-

чений) бесконечно велика.

Рис. 3.1. Зависимость плотности распределения вероятностей

случайной величины

123

W(x)

Чтобы избавить теорию от бесконечности, имеется единственная возмож-

ность – ввести относительную меру неопределенности исследуемой непрерыв-

ной случайной величины Х по отношению к заданной Х

. В качестве заданной

величины Х

возьмем непрерывную случайную величину, равномерно распре-

деленную на интервале с шириной

. Тогда её плотность вероятности

е1)(

, а энтропия

( ) log lim log log

ε lim log

εε

HXdxxx

D® D®

=- -D=-D

Положив для простоты записи e = 1, составим разность

,)()log()()()(

-=-= dxXWXWXHXHXH

(4.3)

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

личины Х с законом распределения W(X) больше

[

]

0)( >

или меньше

[

]

0)( <

неопределенности случайной величины, распределенной равномер-

но на интервале e = 1. Поэтому величину

= dxXWXWXH )(log)()( (4.4)

называют относительной дифференциальной энтропией или просто диф-

ференциальной энтропией непрерывного источника информации (непрерывно-

го распределения случайной величины Х). В отличие от энтропии источников

дискретных сообщений

)(XH

может принимать положительные, отрицатель-

ные и нулевые значения. Величиной

)(XH

можно характеризовать информа-

ционные свойства источников непрерывных сообщений.

Аналогично, используя операции квантования и предельного перехода,

найдем выражение для условной энтропии непрерывного источника сообще-

ний.

(,)

( ) ( , )log lim log

()

W xy

HXYWxy dxdyx

¥¥

D®

-¥ -¥

=- -D

òò

. (4.5)

Обозначим первый член через )( YXH

(,)

( ) ( , )log

()

W xy

H X Y W x y dxdy

¥¥

-¥ -¥

òò

. (4.6)

Эта величина конечна и называется относительной дифференциальной

условной энтропией, или просто дифференциальной условной энтропией не-

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

рывной случайной величины Х при условии, что известны результаты реализа-

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

величины Y, и по сравнению со средней неопределенностью выбора случайной

величины Х

, изменяющейся в диапазоне, равном единице, и имеющей равно-

мерное распределение вероятностей.

4.2. Свойства дифференциальной энтропии

1. Величина )(

XH изменяется при изменении масштаба измерения Х.

Изменим масштаб случайной величины Х в k раз, оставив неизменным

масштаб равномерно распределенной в единичном интервале случайной вели-

чины Х

, принятой за эталон. Если x

= kx, то

)(

)( =

. Тогда

() ()

( ) ( )log ( ) log

Wx Wx

H X W x W x dx kdx

¥¥

-¥ -¥

æö

=- =- =

òò

ç÷

èø

()log () log () ( ) log .

W x W xdx k W xdx H X k

¥¥

-¥ -¥

=- + =+

òò

(4.7)

Если одновременно изменить масштаб Х

, соотносительная неопределен-

ность также изменится, так как значение эталона будет уже иным.

Из относительности дифференциальной энтропии следует, что энтропия

может принимать положительные, отрицательные и нулевые значения.

2. Дифференциальная энтропия не зависит от конкретных значений слу-

чайной величины Х и, в частности, от изменения всех её значений на постоян-

ное. Действительно, масштаб Х при этом не меняется и справедливо равенство

( ) ()log() )

H X Wx Wx d(x

-¥

+q=- +q +q +q=

()log () ( )

Wx Wxdx H X .

-¥

=-=

(4.8)

3. Если единственным ограничением для случайной величины Х является

область её возможных значений [a, b], то максимальной дифференциальной эн-

тропией обладает равномерное распределение вероятностей в этой области, т.е.

при W(X) = (b - a)

-1

( ) log( )

= b-a

. (4.9)

4. Если ограничения на область значений непрерывной случайной величи-

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

дифференциальной энтропией, равной

maxx

() log2

πe

HХ

, (4.10)

обладает нормальное (Гауссовское) распределение величин Х:

()

2π

WXe

-s

. (4.11)

5. Соотношения для дифференциальной энтропии объединения статисти-

чески зависимых непрерывных источников аналогичны соответствующим

формулам для дискретных источников:

(,) () () () ()

HXY HX HYX HY H XY

D D D DD

=+ =+

, (4.12)

где

òò

¥-

dxdyyxWyxWYXH ),()log,(),(

6. Если статистические связи между X и Y отсутствуют, то

)()(),( YHXHYXH

DDD

. (4.13)

4.3. Эпсилон - энтропия источника сообщений

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

и разрешающая способность различных информационно-измерительных систем

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

но не требуется. Наличие помех и искажений сигналов в реальных каналах де-

лает точное воспроизведение сообщений невозможным. Поэтому введём поня-

тие эпсилон–энтропии. Эпсилон–энтропия – это то среднее количество инфор-

мации в одном независимом отсчете непрерывного случайного процесса Х(t),

которое необходимо для воспроизведения этого сигнала с заданной средне-

квадратичной погрешностью e

Рассмотрим подробнее сущность этого понятия. Предположим, что пере-

давался сигнал Х(t), а был принят сигнал Y(t). Пусть в канале действует адди-

тивная помеха E(t), тогда Y(t) = X(t) + E(t) . Расстояние между сигналами X(t) и

Y(t) определяется величиной