Теория информации и надежная связь - Галлагер Р.
Скачать (прямая ссылка):
^¦J2L+_Pe:m'у / d \ е<' (1 —e)rfw. (5.8.39)
2 i>d/2 \ i J
При четных d это выражение ограничено снизу следующим образом:
z(d/2)+1 (1 — eycT/2)—1 .
+ :
(d + 2,’c—e)(d/2) Ч1"2 d-»)1"2 >
^, д+2> (,—S) vsaехр {т *"148 (1~e)1
где было использовано неравенство (5.8.23). Это выражение представляет собой убывающую функцию d при четных d, и так как d^ N/2, то
----VEl----ехр ( — In [4е (1 —е)]| . (5.8.40)
2 (Л' + 4) (1 — е) *4 4 J
При нечетном d рассуждения почти совпадают; используется (5.8.25)
при получении нижней границы для {(d + 1)/2). В результате получим неравенство
-------?----------------ехр (— In [4е (1 —е)]
2 У (1_е)(Л' + 2) К \ 4 1 .
правая часть которого ограничена снизу выражением (5.8.40); это заканчивает доказательство. |
Для того чтобы дать интерпретацию доказанной лемме, заметим, что скорость кода с М = N + 2 кодовыми словами стремится к нулю при N, стремящемся к оо. В силу того, что показатель экспоненты в лемме совпадает с показателем экспоненты случайного кодирования для процедуры с выбрасыванием при нулевой скорости*’, то, как было сказано, Еех (0) является надежностью канала в пределе при R, стремящемся к 0. Однако нужно быть всегда осторожным с этим утверждением. Лемма 3 не применима при М С N + 2 и в действительности, как можно показать**1, при фиксированном М в ДСК
,|ш -In„.JL-e (0),
N-+™ N М— 1 *
Одним из интересных аспектов леммы является то, что она выявляет значение минимального расстояния кода (для кода с малой скоростью) в определении его вероятности ошибки. Важность этого расстояния была также указана при рассмотрении границы случайного коди-
*> См. задачу 5.32 для установления связи между Pe,w{NM) и Pe(NM). **> Шеннон, Галлагер и Берлекэмп (1967, II).
184
рования для процедуры с выбрасыванием, где мы выбрасывали кодовые слова, которые были слишком близки друг к другу. При больших скоростях, близких к пропускной способности, минимальные расстояния становятся относительно маловажными и нетрудно заметить, что в ансамбле случайных кодов большинство кодов имеют очень малые минимальные расстояния. Можно провести чистку ансамбля, значительно увеличив минимальное расстояние кодов, однако при больших скоростях это не может существенно снизить среднюю по ансамблю вероятность ошибки, так как это среднее близко к исходной границе сферической упаковки.
Лемма 4. Для произвольных положительных целых чисел А^,
jV2, М и L
, (AVf- Nv М) > Ре {N!, М, L) PetW (N„ L+ 1). (5.8.41)
Интуитивная идея, лежащая в основе этой леммы, состоит в том, что в коде с длиной блока Nx + N2 ошибочное декодирование произойдет, если для первых N1 принятых символов имеются L сообщений, более вероятных, чем переданное сообщение, и если для последних N2 принятых символов одно из этих L сообщений опять является более вероятным, чем переданное сообщение. Вероятности, стоящие в правой части (5.8.41), связаны с вероятностями этих событий. Хотя здесь рассматривается только ДСК, ниже следующее доказательство применимо к произвольному дискретному каналу без памяти.
Доказательство. Пусть задан код с М кодовыми словами длины Nx + N2, пусть хга является т-м кодовым словом и пусть префиксом хт_ г будут первые Nx символов хт, а суффиксом хт< 2 будут последние N2 символов. Точно так же принятую последовательность у разобьем на префикс ух и суффикс у2, состоящие из Nx и N2 букв соответственно. Пусть Yт при любом т, 1 ^ m ^ М, является множеством выходных последовательностей у, декодируемых в сообщение т, и пусть Ycm является дополнением Ym. Тогда
[ и
pe-—h 2 Р (у | хт)- (5.8.42)
/и га— 1 vfYc у т
При любом префиксе у, пусть Утл (ух) будет множеством суффиксов
у2, для которых (у2, у2) ? Ут. В канале без памяти Р (уь у2 | х;п) =
== Р (у2 | xm l) Р (у21 Хпг,2), и (5.8.42) можно переписать в виде
J и
Ре = — 2 2P(yilxm,l) 2 Р(Уг1хт,2). (5.8.43)
м т= ly, y2ev^ 2(yi)
Для любого заданного ух можно рассматривать множество суффиксов (xm 2}, 1 ^ М, и множество областей {Ymt2 (yi)}. 1 ^ т ^ М,
как код и его области декодирования. Вероятности ошибок для слов в этом коде при условии, что задано ylt равны
Рв.т( Ух) = 2 Я(уа|хт.2). (5.8.44)
y^i2(y1)
185
Пусть т1 (у,) обозначаетт, для которого Pei„, (yi) является наименьшей, т2 (ух) обозначает т, для которого Ре]т (yi) является наименьшей из оставшихся вероятностей, и т. д. Требуется показать, что для всех т, кроме, быть может, тг (у^, ..., ть (уд),
