Теория информации и надежная связь - Галлагер Р.
Скачать (прямая ссылка):
0. Заметим далее, что минимум в (9.2.3) берется по множеству, удовлетворяющему некоторым ограничениям и расширяющемуся при увеличении d*. Следовательно, получающийся минимум R (d*) не возрастает с d*. Для того чтобы показать, что R (d*) выпукло положим, что для d* минимум в (9.2.3) достигается на Рх (/ jk), а для d*2 минимум достигается на Рг (/ \k). Тогда, так как d[ и d\ соответственно больше или равны искажениям, которые относятся к Рх и Р2, то имеем для любого 0, 0 < 0 < 1,
Ы\ + (1 -0) d*2 > 2 Q (k) [0Р, (У|Л)+ (1—0) Р2 (j | k))d (j- k). (9.2.4)
k, i
Это означает, что 0PX + (1 •— 0) P2 принадлежит множеству, удовлетворяющему заданным ограничениям, по которому Cf(Q, Р) минимизируется для нахождения R [0d* + (1 — 0) djl. Следовательно,
R[Qdl + (l — 0)d;]<J [Q; 0Рх+(1 —0)Р2]. (9.2.5)
460
Так как теорема 4.4.3 утверждает, что J(Q; Р) выпуклая ^ по Р, то (9.2.5) можно далее ограничить сверху неравенством
Я[0^ + (1-еК]<езг(О; p1) + (i-0)^(Q; р2) =
= 0/?Ю + (1-0)^Ю, (9.2.6)
которое представляет требуемый результат.
На рис. 9.2.1 изображен вид функции R (d*). Очевидно, что наименьшее возможное значение для среднего искажения равно нулю и достигается при отображении каждой буквы k алфавита источника в букву адресата /, для которой d {k\ j)=0. При d*<0 функция R (d*) не определена, так как по определению d (k\ j) ^ 0.
Далее определим d*nax как наименьшее d*, для которого R (d*) = 0 (рис. 9.2.1). Значение d*nax можно вычислить по формуле
dmax = min XQ(k)d (k; j). (9.2.7)
/ k
Для того чтобы показать это, заметим, что если Q; Р) = 0, то буква адресата должна быть статистически независима от буквы источника и, следовательно, среднее искажение при условии, что выбрана буква адресата /, равно
%Q(k)d (k\ j).
к
Следовательно, минимум d при условии C/(Q; Р) = 0 достигается всегда при выборе /, определяемом из (9.2.7). Если для каждого / имеется некоторое k, для которого d (k\ /) = ОО, ТО, очевидно, dmax =
Перейдем теперь к выводу того, что если выход источника с заданным R (d*) передается по каналу с пропускной способностью С натуральных единиц на символ источника, то среднее искажение на букву d должно удовлетворить неравенству С ^ R (d).
Теорема 9.2.1. Пусть R (d*) — скорость как функция искажения для заданных дискретного источника без памяти и меры искажения. Пусть ULVL — совместный ансамбль, UL — ансамбль последовательностей источника и '= (Ul> Ыь) длины L и VL — ансамбль последовательностей алфавита адресата v = (w1( ..., vL). Пусть
dt = -j- 2 d(u;; vt) (9.2.8)
i = i
является средним искажением на букву для этого совместного ансамбля. Тогда
j- I (и*-; V*-) > R (dL). (9.2.9)
Рис. 9.2.1. Вид типичной функции R(d*).
461
Доказательство. Имеем
-~ /(UL; VL)== ~(H(VL)~H(VL\ VL)), (9.2.10)
L
11 (V-) > H(U,), (9.2.11)
tf(UL|V^= S //(^^...^Х J- Я(?7г|У,). (9.2.12)
i=i i = i
В равенстве (9.2.11) использовано то, что источник без памяти, а в
(9.2.12) использованы соотношения (2.2.30) и (2.3.13). Подставляя
(9.2.11) и (9.2.12) в (9.2.10), получаем
4 /(Ub Vt)>± V I(Ui; V,). (9.2.13)
L 1 i = i
Полагая, что d (/) — среднее искажение l-я буквы, в соответствии с определением R (d*) в (9.2.3) находим, что I (Uй Vi) ^ R Id (/)]. Используя выпуклость w функции R (d*), теперь имеем
I- / (и*-; V*-) > У 4 * Ш] >
>R
2т
«=. L
R(dL).
Приведем интересное истолкование.этой теоремы. Пусть Р (/ | k) — переходные вероятности, на которых достигается R (d*) из (9.2.3) при заданном d*, и рассмотрим передачу L букв последовательности источника по дискретному каналу без памяти с этими переходными вероят-лостями. Тогда
1 (иь VL) =. R (d*)
и среднее искажение на букву между U7- и VL не превышает d*. Вместе с тем для любых других UiVL со средним искажением на букву, не большим d*, эта теорема утверждает, что
I (UL; V'-) > R (d*).
Следовательно, R (d*) может быть эквивалентно определена для любого L ^ 1 равенством
R(d*)== min -у- 1 (IJb VL), (9.2.14)
d*
где минимизация проводится по PL (v | и) при условии, что dL^d*.
Предположим теперь, что при заданном L выбирается множество, скажем М, последовательностей адресата vl( ..., v^, каждая из которых 462
имеет длину L, и множество последовательностей источника длины L отображается в это множество последовательностей адресата. Будем называть такое множество последовательностей и такое отображение (L, Л4)-кодом источника, а сами последовательности V!,...,v^— кодовыми словами. Каждое кодовое слово при таком кодировании можно представить последовательностью из I log2 j дбоичиых символов, и если эти двоичные символы передаются надежно по каналу с шумом, то искажение между последовательностью адресата (одним из кодовых слов) и последовательностью источника равно просто искажению, введенному при первоначальном кодировании.
