Теория информации и надежная связь - Галлагер Р.
Скачать (прямая ссылка):
(loge) (2 2 Р(ы- °) Г
[ V и V
2 р(и-v)
(M — l)P(u\v) 1—Ре
1
+
Р (и | V)
1
- (log е)
М — 1 V и V V 11-/= V
+ (1 -Ре)ЪРУ)~ 2 Р(Ч, V)
(4.3.8)
(4.3.9)
L» V, U = V
= (loge)[Pe-Pe + (l-Pe)-(l-Pe)] = 0. (4.3.10) I
Теорема 4.3.2. Пусть ULVL обозначает совместный ансамбль последовательностей и = (иъ ..., uL) и v = (и1; Vl), в котором выборочные пространства для ьц и Vi состоят из одних и тех же М элементов аъ ..., ам- Пусть <Ре> определено в (4.3.2). Тогда
1
(Pe>log(M-l) + ^«Pe»> —^(UL|VL). (4.3.11)
Доказательство. Используя цепное правило для совместного ансамбля UL = UJJ2... UL [см. равенство (2.2.30)], имеем
Н (UL I VL) = Н {V11 Vl) + H(U2 I U, VL) + ...
... + H(UL\VLU1...UL-i)^ (4.3.12)
(4.3.13)
/=1
Неравенство (4.3.13) следует из общего неравенства Н (X\Z\~>-^ Н (X\ZY) [см. неравенство (2.3.13)].
96
Применяя теорему 4.3.1 к каждому слагаемому в (4.3.13), получаем
Н(U*-|V*K 2 1ре. 1^ё(М-\)+Ж(Ре,1)]} (4.3.14)
/-= i
-j-H (UL| VL) ^ <Ре> log (М— 1)+ -j- 2 (4-3.15)
1=1
Чтобы завершить доказательство теоремы, следует показать, что
Ж(Ре,1)<Ж((Ре». (4.3.16)
/= 1
Это может быть установлено с помощью неравенства log2< (log е) х Х(г—1). Однако мы не будем вдаваться в детали доказательства, так как (4.3.16) является также простым следствием свойства выпуклости энтропии, которое будет рассмотрено в следующем параграфе. |
Мы уже ограничили вероятность ошибки, связанной с источником, с помощью неопределенности Н(\iL\VL). Теперь рассмотрим канал в сочетании с источником.
По определению будем считать, что последовательность источника и = («j, ..., uL) связана с адресатом при N-кратном использовании канала, если совместный ансамбль ULXWYWVL [соответствующий выходу источника и, входу канала х = (хх, ..., Xn), выходу канала У ~ {уъ •••> Уы) и декодированному выходу (сообщению на выходе) v = (иь ..., vl)] обладает тем свойством, что у не зависит от и при условии, что задано х, a v не зависит отиих при условии, что задано у.
Для дискретных ансамблей это условие означает, что Р (у | х, и) = = Р (у | х) и Р (v | у, х, и) = Р (v | у). В общем случае, как показывает рис. 4.3.1, оно означает, что выход канала статистически зависит от последовательности источника лишь через последовательность на входе канала, а декодированный выход v зависит от и и х лишь через выход канала у. Другими словами, эти условия являются математическим выражением того, что нет вспомогательного «скрытого» канала, передающего декодеру информацию о и.
Если источник обладает памятью, то это определение не столь невинно, как оно представляется. Если последовательные блоки из L символов источника передаются адресату, то может быть построен декодер, который использует блок полученных букв при декодировании следующего. Вышеприведенное условие исключает такие декодеры, но, как будет показано позже, эта проблема перестает существовать при переходе к пределу при L оо.
Теорема 4.3.3. (Теорема переработки информации.) Пусть последовательность источника и = (их, ..., ul) связана с адресатом каналом, используемым N раз. Тогда
/(UL; VL)</(XW; VN), (4.3.17)
где I (UL; VL) является средней взаимной информацией между последовательностью источника и = («!,..., «х.) и декодированной вы-4 Зак. 2 j о 97
ходной последовательностью v = (vlt ..., v{), a I (XN; YN) является средней взаимной информацией при Л^-кратном использовании канала.
Доказательство. Первое условие приведенного выше определения совместно с теоремой 2.3.3 дает: I (UL; Yw | Xw) = 0. Из (2.3.19) теперь получим
/(UL; Y^)</(X^; \N). (4.3.18)
Второе условие определения дает I (UL; \L | Yw) = 0 и, используя вновь (2.3.19), имеем
/ (UL; У^)</(1^; \N). (4.3.19)
Объединяя (4.3.18) и (4.3.19), получаем (4.3.17). |
Из доказанных двух теорем следует, что
<Ре> log (М- 1 ) + Ж«Ре'>) \L) - HL (U)~
—VL)> HL{U)- ~I{XN\ yN), (4.3.20)
где Hl(U)--=(IIL)H(\Jl).
Если канал является ДКБП, то будем иметь / (Х^; \N) < NC, отсюда получаем
<Pey\og{M~~\) + M {{Ре»> HL{V)~ у-с. (4.3.21)
