Духин А.А. Теория информации

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

§ 2.

ТЕОРЕМЫ

ШЕННОНА

ЛАЯ

ИСТОЧНИКОВ

БЕЗ

ПАМЯТИ

ВТОРАЯ

ТЕОРЕМА

ШЕННОНА.

Для

класса МДА) высоковероятностных

по-

следовательностей, реализованных

на

источ-

нике

без

памяти [A,p(S)], определяемого

за-

данным уровнем

а,

<а

1),

имеет место

G|M,(G)l

}

еН

(2-2.8)

где

Нда

-y^PjfogPj

энтропия источника.

Доказательство.

зависимости

от

величины

р(с^)

класс

С/

разделим

на

три

подкласса:

Q = Kj +

К2

+К3

следующим образом:

К,={с,:р(с

)*а-<<

«-

1>},

(2-2.9)

где

основание логарифмов,

т] > 0

постоянная, фигурирующая

формулировке первой теоремы

Шеннона (2.2.1).

с, :а^<

-^> <р(с,)<а^

(Н

)

}, (2.2.10)

с,:р(с,)<а^

-^}.

Согласно такому разбиению множества всех последовательностей

=С'Д

а К, иК

=С". Следовательно, при

-»оо

суммарная вероятность

последовательностей, вошедших

первый

третий классы, стремится

нулю:

(

Ит

I Р(<^) +

ZP(C^)

Значит,

класс

МДа)

войдут последовательности

из Kj и,

частично,

из К

Первую последовательность

из К

, не

вошедшую

МДа), обозначим

сДа).

Приведём ряд очевидных неравенств:

|МДа)|а^

(Ноо+Т1)

< Ер(с^)<а + р(сДа))<а +

а^

(Ноо

Т1)

М^(а)

Отсюда получаем:

log\M

(a)\

JOGG

a-^-^)

* .

'4-HEN

+Т|.

См.

следствие

из

первой

теоремы

Шеннона.

ГЛАВА

П.

ИСТОЧНИКИ

СООБЩЕНИЙ

Устремляя £

СЮ,

г| -> 0, получаем:

log\MAa)\

lim sup—

—

^йИ».

(2.2.11)

Г)->00

Имеет место неравенство:

iM^A^^^^A-P^,),

(2.2.12)

где PCKj) обозначает суммарную вероятность всех

последовательностей

из

класса

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

1о

\М

(а)\^1о

{а-¥(К

))

00 Ь

Устремляя £

со,

т]

-> 0, получаем:

/t'

(2213)

Из неравенств (2.2.11)

(2.2.13) получаем доказательство теоремы 2.2.2.

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

цию распределения вероятностей

на

множестве реализаций

источника без

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

е С

расположим

по

убыванию

их величины

занумеруем натуральными числами

от 1 до к/. В

класс

войдут

все

последовательности

аномально повышенными вероятностями.

Так

как К

= , то

класс

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

примерно одинаковые вероятности (р(с

£)~а~"

°°), удовлетворяющими

закону больших чисел. Класс МДа) составлен

из

всех последовательностей

и,

частично,

из

последовательностей

Подавляющее число последова-

тельностей, составляющих класс

имеет аномально малые вероятности.

ТЕОРЕМЫ

ШЕННОНА

ДЛЯ

ИСТОЧНИКОВ

БЕЗ

ПАМЯТИ

P(c

)

'л

Рис.

2.1.

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

[А,р($)]

Информационная устойчивость, которой обладают последовательности

cJeC',,

означает,

что

собственная информация

для

любой последовательнос-

ти

из

этого класса есть величина постоянная.

Это же

свойство можно трак-

товать

как

свойство равнораспределённости,

то

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

тельностей

из

класса

С\

приближенно равны а~

°°*. Отсюда получаем

|С',|

Из второй теоремы Шеннона (2.2.8) также следует,

что

|МДа)|

= а

Но0

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

класс

Kj,

пренебрежимо мало

по

сравнению

с |К

| или

|МДа)|.

то

же

время имеет место:

Щ=1ш

P\=lim

= Вт

.<№<>•**•>.

Так

как <

logn, причём равенство возможно только

при

равномерном

распределении

на А, то

искомый предел равен нулю. Число последователь-

ностей, удовлетворяющих (2.2.4), исчезающе мало

по

сравнению

общим

числом последовательностей.

Пример

2.1.

Рассмотрим источник

без

памяти

[A,p(s)j

следующего вида:

{0Д},

р(0)

р(1)Л.

Положим основание логарифмов

а = 2.

Для

удобства

восприятия масштаб

по

оси

ординат

участок

на

оси

абсцисс,

соответствующий

классам

^ и К

искусственно

увеличены.

ГЛАВА

II. Источники

СООБЩЕНИЙ

Тогда н = -

Источник порождает двоичные последовательности:

=(б

...,вг),

е>=0,1;

р(с^) = ^.

Для т|>0 для любой последовательности с^еС^ выполняется:

2-«

+т

»<р(с^)<2^

(Н

л)

то есть С, = С,, С? = 0.

Пример 2.2. Рассмотрим источник без памяти [A,p(s)j следующего вида:

= {o,l},

p(0)

= q,

р(1)

р,

p + q

= l, р£0, q^O.

Пусть в последовательности е С

имеется т

нулей и т

единиц; т

+ т, = £

пусть 5>0. Тогда, согласно (2.2.4), в класс

С\ войдут те последовательности, для которых

Imi

<8,

<8.

Приведённые неравенства означают, что С\ состоит из последовательнос-

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

ти математического ожидания.

Зависимость числа последовательностей в классах С'^ и CJ от величины

р = р(1) изображена на рис. 2.2:

Рис.

2.2

§3

Результаты, полученные в предыдущем параграфе, распространяются на

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

Определение

3.1.

Дискретный стационарный источник

[A,p(s)] называется марковским

источником порядка т, если для любого

£(£

ш) и любой последовательности

с( = (а^ ,...,а;^) выполняется:

i^i v^ajj )= р(а^ /а^

,...,а^_

т+1

(2.3.1)

Из определения следует, что последовательности {с^} являются реализа-

циями конечной стационарной цепи Маркова с глубиной зависимости т. Ни-

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

Определение

3.2.

Величина

(Ю

_ y

ll1M

.,a

)tog p(a

/а^^а^)

{cr}

называется шаговой энтропией мар-

ковского источника порядкак.

(2.3.2)

Определение

3.3.

Величина

=-J-Ур(а|,,...,а|

)^ p(a

ilV

..,a

)

называется энтропией источника на\

один знак.

(2.3.3)

Рассмотрим соотношение:

р(

ч >~>Ч )

р(

и )p(

h )p(

) P(

ik-i '->

ч )•

Здесь и ниже символ означает, что суммирование проводится по всем последователь-

{с

}

ностям 6 •

МАРКОВСКИЕ ИСТОЧНИКИ

ГЛАВА

11. И ст

очники

СООБЩЕНИЙ

Логарифмируя

его,

усредняя

по

множеству

{С

умножая

на -

—,

полу-

чаем связь шаговой энтропии

энтропии

"на

знак":

= ~~ Е

,-,а

1к

)

togp^,,)-

i У

рСа^

,...,a

)fogp(a,

/а^

) -

-™

)/agp(a

ik t

,...,

а|1

£H

(|)

}

i=l

Покажем,

что

последовательность

(k)

k = l, 2,.,.

является невозрастаю-

щей,

то

есть для любого

к € N

Н*

к+1)

^ Н

(к)

Действительно:

(к+,)

=-Vp(a

llf

.^a

lk+1

)fogp(a

lk+1

/а,

,...,а

)

(

i! H(a

ik+1

,...a

н(а

1к

/а

1м

„.л^

) = Н<

Последовательность

также является невозрастающей:

к+1

<к

1)Хн<

>-кХн<'>

- Н

к+1

= Ы И =

-J_V(

('>

(К+1)

Ъ:

к 1

к(к

1) k(k

l)~

Определение 3.4.

Величина

lim Н

(к)

= Н

= > 0 -

назы-

к-¥со к-¥<в

вается энтропией марковского источника.

(2.3.4)

Первый предел существует

силу теоремы Вейерштрасса, второй

- как

сред-

нее арифметическое членов последовательности

{н

(к>

имеющей конечный

предел.

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

пространяться

на

произвольную глубину

т.

Рассмотрим некоторые частные

случаи.

- 0.

Зависимость между отдельными знаками отсутствует. Марковский

ис-

точник является источником

без

памяти.

(к)

= Н, = , где Я

= - £

log

i=l

= 1.

Появление очередного знака

последовательности зависит

от

предыду-

щего знака.

(к)

\ при к>2.

§ 3. МАРКОВСКИЕ

ИСТОЧНИКИ

lim

(к)

(2)

=- У p(a

iiai2

)togp(a

/aj.

{С

}

Энтропия на знак для этого случая представляется выражением:

=-[н

(1)

+(к-1)Н

(2)

]. lim =

Пусть зависимость между знаками в последовательностях

{с^

}

распростра-

няется на глубину т. Тогда Н

(к)

= Н*

\ при к>т.

(2.3.5)

lim Н

(к)

= Н<"" = Н

да

к ->•«>

,{т)_

- I р(ч, ' ~'

*т

Kp(

im-l '-'

Ч )

{Сщ}

Hk=-

т-1

]Гн

+(к--т

+ 1)Н

(т)

. lim Нь = Н

(т)

= Н

Рассмотрим источник сообщений

[A,p(s)J,

порождающий символы алфави-

та А согласно простой, стационарной и эргодической цепи Маркова с конеч-

ным числом состояний. Обозначим так же, как и в § 2, посредством - {с^}

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

этим источником.

Теорема 3.1 (Первая теорема Шеннона для марковских источников порядка

m = 1). Для любых е >

О,

> 0 существует £

такое, что

при £>£

все реализации длины £ источника [A,p(s)j

могут быть разбиты на два класса:

-1-

с ^.

Для любой последовательности с'

е С\ имеет место:

II,

<Т

Ь (2.3.6)

Jog

где H

= -

Тр,р

fog

=-Ур(ц)

log р

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

точника сообщений.

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

С" меньше е.

Доказательство.

1°.

Зададимся произвольными е>0, т|>0. Множество всевозможных после-

довательностей С^,. порождённых рассматриваемым источником, разделим

ГЛАВА

II. Источники

СООБЩЕНИЙ

на два класса. Отнесём к первому классу С\ те и только те последователь-

ности, для которых выполнено неравенство:

u - ^PiPtjj <*8, У =

1,...,п,

(2.3.7)

где - абсолютная частота встречаемости биграммы (а

ар. Ко второму

классу С" отнесём все последовательности, для которых неравенство

(2.3.7) не выполнено, по крайней мере, для одной пары (ij).

Условие (2.3.7) равносильно выполнению системы неравенств:

^PiPij

™

^<п1ц<Ф*Ру

^8.

l,...,n.

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

тот rn,j появления биграмм (a^j):

ij=^PiPij+^

ij>

(|в

|<1,

i,j = l

..,n).

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

е равна:

Р(«г)-Р|111Рц

(М)

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

fog-77r = -togpi

-2)WpiP

+^8e

)fogp

Р(с<)

(Ц)

Далее, оцениваем, сверху модуль разности:

hog

Р(с'/)

<- log +

t Pi,

(2.3.8)

bYjog-.

При i

и достаточно малом 5 из неравенства (2.3.8) следует первое

утверждение теоремы:

<Т), где П

= -]£PiPij log ру.

P(cJ)

-H

2°.

Ко второму классу С" отнесём все последовательности, для которых нера-

венство (2.3.7) не выполнено, по крайней мере, для одной пары (ij).

Для доказательства второго утверждения теоремы следует оценить сверху

сумму

Ip(k,-*p,pJ>«).

(2.3.9)

(i,j)

§ 3. МАРКОВСКИЕ ИСТОЧНИКИ

Зафиксируем пару (ij). В силу эргодичности рассматриваемой цепи

Мар-

кова для произвольного е' > 0 при достаточно большом £ будет выпол-

няться закон больших чисел:

'{к

ГП::

Ш:

—

(2.3.10)

для абсолютных частот встречаемости символов и биграмм.

Из неравенств (2.3.10) получаем:

—

~Pi

Ш:

<^>1-2Б'.

Учитывая включение случайных событий

П1:

Pij

2 Г V

Pijmi

Ч~

]Г

РцЩ

^С^Шу-РцШ,^!^,

получаем оценку:

р||

т|

- ф

| < |т

-р

цт1

j >

- 2е'.

Случайное событие

j|mi-^p

|<^j

эквивалентно событию

||miPij-'PiPu|<|'P«}-

что для последне

iPij -

*Р|Рц|

< |^Pijj С

||т,р

*р,р„|

|*J

для случайных событий

A = ||m

-^p

|<|^| и B = ||m

-p

|<|^J

Очевидно, что для последнего события имеет место включение

Поэтому для случайных событий

справедлива оценка:

||«П|Р

^PiPij|

< |т

-р

Ш||

< |*J >

- 2б'.

Преобразуем введённые случайные события:

В = jniiPij - ^£ < т

< m

iPij

+ .

}•

A = <jm

--^p

<m,p

+^l

ГЛАВА

11.

Источники

СООБЩЕНИЙ

8 5

.P»j

+ 2

1 >

^Р«РУ

га

«Ри

iPij

-t

-^p

iPiJ

-m

iPij

+ -I

Откуда получаем:

{-8^ < my -^р^у <

8^}= {jmy

py| <

8^}.

p(|my

^PiPy

< 8^)>

2e'.

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

образом:

р{|ту-ф|ру|^8^}^

2е\

Следовательно,

для

суммы (2.3.9) получаем:

iPJImy

-^PiPijl^5^}< 2s'n

<е,

(ч)

если 8

выбрать меньшим,

чем —~.

2п

Далее,

из

очевидного соотношения получаем:

£р<с2)

* 1Р(К -

^PiPijI

•

(23.11)

cJeCJ

(ij)

чем

завершается доказательство теоремы

2.3.1.

Распространим доказательство первой теоремы Шеннона

на

случай мар-

ковских источников порядка

т.

сделанных предположениях относительно

цепи реализации источника порядка

удовлетворяют закону больших чисел.

Для любых 8

> 0,

в >

0 и

достаточно большой длине

последовательности

Г1!у-р(М

1>8|<е,

(2.3.12)

где

абсолютная частота встречаемости буквы

последовательности

С^.

Jl V'

]m)

(2.3.13)

где

bwi

абсолютная частота встречаемости

m-граммы

(а^

..,aj

Jiv-Jm =lv^n,B последовательности

c^.

Вероятность реализации последовательности

может быть представлена

следующим образом:

См. Библиографию [1].