Основы теории информации и кодирования: Учебное пособие [Евгений Феофанович Березкин] (pdf) читать постранично, страница - 20

заданном мно­
жестве сообщений {ик},к = \,М с энтропией H(U) и алфавитом, со­

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

_

п = ^пкр(ик) будет удовлетворять неравенствам

log2 D

log2 D

ДОКАЗАТЕЛЬСТВО. Докажем неравенство H(U) — п log2 D < 0 .
Пусть р(Н1),..., />(«л/) - вероятности сообщений источника, а и1;..., пм длины

кодовых
|

М

Представим

слов.

//(£/)— и log2 Z)

в

виде

м

^T?(wjlog2----------- 1оёг D • Поместим -пк под знак логаi=l
Р(Рк) к=1
м

D~nt

рифма, объединим слагаемые и получим V
log 2---------- Далее
*=1
р(ук)
воспользуемся
известным
свойством
натурального
логарифма
In а < а -1:
—

1 Ji,

.

м

rj-n*

м

U1Z i=l

А=1

Последнее неравенство следует из неравенства Крафта, что и доказы­

< п ■ Заметим, что равенство имеет место тогда и только

вает
10g2£>

169

тогда, когда piu^.) — D ”к . Это условие совпадает с ранее получен­

ным условием оптимального кодирования по Шеннону — Фано.

"

H(U)

,

Докажем неравенство П
полученное неравенство умножаем на /*(«*)
м
м
-logzPQU

^пкр(ик)

и суммируем по к

1],

W) .

------------ 1-1, что и
log2Z)

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

Рис. 7.4. Графическая интерпретация неравенств D

170

< p(uk)L;
р(а2 /a,) = p{a2 = aj /= ак}

L2;

р(а2 / аДг) = /?{ос3 =ad / cq = ак, a2 =ay} -»Z3;

p(at /aIa2...a,._1) = p{at = ат/щ - ak,oc2 =ay,...,a,._1 =as}
Совместная вероятность появления на выходе источника первых v
событий есть p(aja2...av) = р(ах)р(а2 Iа^.-.р^ Iap-.a^), а совме­

стное распределение (v - 1)-го и v-ro событий равно

/КА) = X-S^ 77(4) = - XH«i)10g2 А**]);
otje-dj

а, ос2 ->77(Л2/4) = -£ ^Xaia2)log2Xa2/ai);
“1е А “2е Л

«^4 а2еЛ2

ci] а2 ... а,. -> ff(Al/A1...Aj_1) =
а2е42

а/бД

= - S S • •Х^а1а2-“1)10ё2/’(а,/а1а2...а,._1).
oqeXj а2сЛ2

а,-еД.

Обозначим через H(At / Л4') условную энтропию z'-ro события при
условии, что v предшествующих событий уже произошло (рис. 8.4):

,)log2p(aI./ai_v...a,._i) =

77(4/Лу) =

= H(Ai/Ai_1...Ai_v).

Рис. 8.4. Иллюстрация условной энтропии Я(Д /?Г)
ОПРЕДЕЛЕНИЕ 8.1. Источник информации называют стационар­
ным, если условная вероятность появления события 0С(. при условии
задания v предшествующих событий не зависит от номера i для всех
целых V, т.е.

Хос, /a.-r -az-v) = p(aj / осу_]...ocy_v); i, j > v.
180

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

тий a1OC2...OC|....OCv или, говоря другими словами, статистические харак­

теристики процесса появления событий на выходе источника не зависят
от выбора начала отсчета времени или наблюдения (рис. 8.5).
Для
стационарных
источников
справедливо
равенство
Я(4 / Av) = Я(Д. / Av) для всех i, j>V.
v
•

v

ОС,

0Су

♦ ... »»,..** •—

j

i

p{ai=ak/at_1=am,...,ai_y=as} =
~ p{^j ~ ак !^j-i

— flmr"?0Cy_v — as}

Рис. 8.5. Иллюстрация свойства стационарности
ТЕОРЕМА 8.2. Для стационарного источника условные энтропии

событий Н(А^/ Av) при условии, что заданы все предшествующие
события, образуют монотонную невозрастающую последовательность.
ДОКАЗАТЕЛЬСТВО. При рассмотрении свойств энтропии доказа­
но, что
Я(Д /Av)< Н(А, / Д"’1) < Я(4 / Д'"2) 0 последовательность событий, порождаемых дис­
кретным стационарным источником, можно закодировать в последова­
тельность символов, выбираемых из заданного алфавита, таким образом,
чтобы среднее по ансамблю число символов на событие удовлетворяло
- Я(Л/Л~)
неравенству п