Теория информации и надежная связь - Галлагер Р.
Скачать (прямая ссылка):
В этих выражениях Q («;) и Р (иг | иг) — вероятности источника и тест-канала соответственно. Взаимная информация равна
Рт (V I U)
I (и; v) = In 1 vi)» (9-3-5)
где
L
col(v)= S Ql (u) Pl (V I U) = П cb(w,). (9.3.6)
и / = 1
Другой ансамбль — это ансамбль кодов, в котором М кодовых слов выбраны независимо, с распределением вероятностей <s>L (v), последовательность источника выбрана с тем же распределением вероятностей Ql (и), как и выше, и для каждого кода в ансамбле и отображается в такое vm, обозначаемое v (и), которое минимизирует D (u; vm) на
1 < т < М.
Лемма 9.3.1. Пусть для заданных источника, меры искажения и тест-канала Pc[D>Ld\ — вероятность в указанном выше ансамбле кодов с М кодовыми словами длины L того, что D [u; v (и)] (т. е. искажение между и и кодовым словом, в которое оно отображается), превосходит заданное число Ld. Тогда
Рс [D>Ld] <Pt(A) -f ехр [— Afe-L«], (9.3.7)
где R — произвольное положительное число; А — множество u, v последовательностей, задаваемое соотношением
А= {u; v: или / (и; v)> LR или D (щ v)>Ld], (9.3.8)
и Р( (А) — вероятность А в ансамбле тест-канала.
467
Прежде чем доказывать лемму, используем ее для доказательства следующей теоремы кодирования источника.
Теорема 9.3.1. Пусть R (d*) — скорость как функция искажения для дискретного источника без памяти с конечной мерой искажения. Для любого d* ^ 0, любого б > 0 и любой достаточно большой длины блока L существует код источника с М ехр {L [7? (d*) + б]} кодовыми словами, для которого среднее искажение на букву удовлетворяет неравенству
dL^d* + б. (9.3.9)
Доказательство. Применим лемму к тест-каналу, для которого достигается R (d*) при заданном d*, выбирая d равным d* + 6/2 и R равным R (d*) + 6/2. Среднее искажение на букву dL по ансамблю кодов леммы удовлетворяет соотношению
< d* + 6/2 + Яс [D > L(d* +6/2)] max d (?;/). (9.3.10)
k. i
Это соотношение вытекает из того, что искажение на букву ограничивается сверху величиной d* + 6/2, когда D [u, v (и)] ^ L (d* + 6/2), и величиной таxd(k\ j) в других случаях. Для М = {____________ехр [LR(d*)-\-
k, j
+ L6]_J имеем
^ {exp [LR (d*) + L6]— 1} x X exp {— L [R (d*) + 6/2]} ^eL6/2— 1.
Таким образом, (9.3.7) принимает вид
PC[D>L (d* + 6/2)] < Pt (Л) + exp ( — ei6/2 + 1). (9.3.11)
В соответствии с определением А
Pt (Л) <С Рг {/ (u; v)>L[R (d*) + 6/2]} +
+ Pr \D (и; v) > L (d* + 6/2)], (9.3.12)
где вероятности справа берутся по ансамблю тест-канала. Так как каждая из величин / (u; v) и D (и; v) равна сумме L независимых одинаково распределенных случайных величин со средними R (d*) и d* соответственно, то по неравенству Чебышева
Л(Л)<— + —, (9.3.13)
1 ’ L62 7.62 V '
где ст? — дисперсия / (u; v) и о% ¦— дисперсия d (u; v) для источника, порождающего одну букву, и вероятностей тест-канала. Отсюда
Рс [D > L (d* + 6/2)] < М- + М. + ехр(— е«/2 + 1). (9.3.14)
LCr L Сг
468
Из этого неравенства видно, что последнее выражение в (9.3.10) стремится к 0 с возрастанием L для любого б > 0. Следовательно, для достаточно больших L
dL^d* + б.
(9.3.15)
Так как по крайней мере одно кодовое слово в ансамбле должно иметь искажение столь же малое, как среднее искажение, то теорема доказана, j
Заметим, что кодовые слова данного кода могут быть представлены I” L [R (d*) + б]/1п 2 j двоичными символами, или не более чем [R (d*) -+- S]/ln 2 -+- 1/L двоичными символами на символ источника. Следовательно, взяв L достаточно большим, можно подойти сколь угодно близко к среднему искажению d*, используя сколь угодно близкое к R (d*)/ln 2 число двоичных символов на символ источника.
Доказательство леммы. Вероятность Р C(D> Ld) можно представить в виде
Рс (D > Ld) = %Ql( u) Р с (D>Ld |u).
(9.3.16).
Для заданного и определим Аи как множество v, для которых пара и, v содержится в А:
Ли = {v: или /(и;v)'>LR или D(u;v)>LdJ. (9.3.17)
Отметим, что для заданного и имеем D [u; v (и)] > Ld только тогда, когда D (и; vm) > Ld при всех т, 1<; т М, и, следовательно, только тогда, когда vm ? Аи при всех т. Так как \т выбраны независимо то
