Теория информации и надежная связь - Галлагер Р.
Скачать (прямая ссылка):
Рг [ошибка | т, хт, у]
(5.6.9)
PN (У I хтУ
Подставляя (5.6.9) в (5.6.5), будем иметь
Ре. т < (М - 1)р 2 [ 2 Qn (хт) Pn (у | xj1 ~ sp] X
У ХТП
X [2<Мх)Яд,(у|х)‘1р. (5.6.10)
X
Отметим, что если PN (у | хт) =--0, то соответствующее слагаемое может быть опущено в сумме (5.6.5). Таким образом, Pn (у | xm)I-sp можно положить равным нулю в (5.6.10), если PN (у | хт)=0. Наконец, подставляя*’ s = 1/(1 + р) в (5.6.10) и замечая, что хт является глухим переменным суммирования, получаем (5.6.1) при 0<р^1. Справедливость (5.6.1) в случае р = 0 следует из того, что правая часть (5.6.1) равна 1 при р = 0 .|
Эта теорема обладает удивительной общностью и силой. Она применима как к каналам без памяти, так и к каналам с памятью и (как это будет показано в гл. 7) она может быть легко обобщена на недискретные каналы. Большая часть оставшегося в этой главе материала представляет собой следствия и интерпретации этой теоремы. Заметим,
*> Хотя это и не нужно для доказательства, этот выбор минимизирует (5.6.10) по s (см. задачу 5.6).
153
что отдельные технические детали доказательства являются очень простыми и не связаны с какими-либо предыдущими результатами. Однако доказательство этой теоремы в значительной степени связано с результатом, относящимся к двум кодовым словам. Единственным новым фактом, использованным в доказательстве, является лемма. Аддитивная граница (5.6.3) довольно точна для независимых событий, если получающаяся в результате граница мала по сравнению с 1, но является, очевидно, очень плохой, когда получающаяся в результате граница велика по сравнению с 1. Лемма дает способ уточнения аддитивной границы в последних случаях за счет первых случаев. Лемма никогда не дает границу более точную, чем наименьшая из границ (5.6.3) и (5.6.4), но, как это было использовано в теореме, она позволяет получить удобную для исследования границу для PBj т.
Используем теперь теорему 5.6.1 для случая дискретного канала без памяти, в котором
Пусть Q (k), k = 0, 1, ..., К — 1, является некоторым произвольным распределением вероятностей на входном алфавите канала и пусть каждая буква кодовых слов выбирается независимо с этим распределением вероятностей, так что
При переходе от одного выражения к другому здесь были использованы такие же соображения, как и при переходе от (5.5.6) к (5.5.10).
Представим теперь эту границу таким образом, чтобы явно показать экспоненциальную зависимость границы от N при фиксированной скорости R. Напомним, что R по определению равна (In M)/N. Таким образом, М = oMR и при фиксированной скорости М экспоненциально зависит от N. К сожалению, при различных значениях N и при фиксированной R не обязательно получаются целочисленные значения eNR, и это обстоятельство будет обойдено с помощью следующего определения. При любом положительном целом значении N 'и любом положительном числе R (N, Р)-блоковый код является кодом с j eNR | кодовыми словами длины. N, где [ ел'^П обозначает наименьшее целое число, большее или равное eNR.
Pn iy\x) — TIP (yn | xn).
П
N
<Mx)= П Q(xn),
Pe,m<(M~ 1)P.
= (M~i)p n 2 fSQ(^)^(i/nl^)1/(1+p)l1+p =
„ _ i L дг_ J
n=\ Un L
= {M—i)p| 2 2 Q.{k)P(j\kyi^ + «) . (5.6.11)
I / = o L* =o
J54
Рассматривая описанный выше ансамбль кодов как ансамбль (М, /?)-блоковых кодов с М — 1 < eNR ^ М, получаем
Q (k) P(j | &)i/0 -Нр)| 1 + pjw. (5.6.12)
Полученные результаты можно суммировать следующей теоремой, в которой также произведено дальнейшее преобразование (5.6.12).
Теорема 5.6.2. Пусть дискретный канал без памяти имеет переходные вероятности P{j\k). При любом положительном целом значении N и положительном числе R рассмотрим ансамбль (N, /?)-блоковых кодов, в котором буквы всех кодовых слов выбираются независимо
с распределением вероятности Q (k). Тогда для любого сообщения т,
1 ^ пг ^ г eNR П. и любого р, O^p^l, средняя по ансамблю вероятность ошибочного декодирования при использовании декодирования по максимуму правдоподобия удовлетворяет неравенству
Ре, т<ехр { — N [Е0 (р, Q)—рЯ]}, (5.6.13)
где
Е0(Р, Q) = — In
/' = о
qwp а \куш+Р)
к =0
1 + Р
(5.6.14)
В силу того, что (5.6.13) справедливо для любого сообщения в коде, средняя вероятность ошибки по сообщениям при произвольном наборе вероятностей сообщений Рг (т) удовлетворяет неравенству _ м _
Ре= 2 Pr(m)Pe,m < ехр{ — N[E0(p, Q) —рЯ]}. (5.6.15)
