Теория информации и надежная связь - Галлагер Р.
Скачать (прямая ссылка):
так как любое у декодируется в точности в L сообщений и, следовательно, дает вклад в точности в L слагаемых Ап т. Используя это равенство, получим следующую лемму.
Лемма 1. Пусть задан ДСК с вероятностью ошибки е < 1/2 и пусть б — произвольное число, е < б < 1/2. Если
1п[/8 (-V-fl)-(l-e)/e] N
(5.8.28)
М N
— > /8 (N + 1) ехр {JV [In 2—Ж (б)]}, (5.8.29)
181
то
+ 6 In в-f-(1—6) In (1 —в)]}. (5.8.30)
Доказательство. Доказательство аналогично доказательству теоремы 5.8,3, с той лишь разницей, что следует положить
м
2 Ап =2NL
т= 1
при всех пфп'. |
Займемся теперь получением нижней границы для вероятности ошибки, лучшей, чем граница сферической упаковки для очень малого числа кодовых слов. Определим минимальное расстояние двоичного кода как расстояние между двумя ближайшими кодовыми словами.
Лемма 2. (Граница Плоткина.) Минимальное расстояние любого двоичного кода с М кодовыми словами и длиной блока N удовлетворяет неравенству
(5.8.31)
min 2(М— 1)
Доказательство. Расположим кодовые слова (N, М)-кода в таблицу с N столбцами и М строками двоичных символов; m-е кодовое слово будет т-й строкой таблицы. Рассмотрим теперь сумму всех расстояний в коде, т. е,
ММ N М М
2 2 d(xm;xm')= 2 2 2 d(xmtn-,xm>in). (5.8.32)
т— \ m' — l п~ 1 т= 1 т'= 1
Пусть Z (п)— число нулей в п-м столбце таблицы. Так как существует Z (п) различных значений т', для которых хт-1 п = 0, то
при хП:П = 1
м
2 d {хт п\ Хт',п) ~ Z (li). т’ — 1
Поскольку существуют М — Z (п) значений т, для которых хт п = 1, то
м
2 2 d(xmin;xm'.n) = lM-Z(n)\Z(n). (5.8.33)
т;хт)п=1 т' = 1
Точно так же существуют Z (п) значений т, для которых хт>п = 0, и М —Z(n) значений т', для которых хт\ п = 1 так что
м
2 2 d(xm<n-,xm,,n) = 2[M-Z(n)]Z(n). (5.8.34)
m= 1 m'~J
182
Правая часть (5.8.34) ограничена сверху числом М2/2, которое является максимальным значением выражения 2Z (М — Z), рассматриваемого как функция Z. Этот максимум достигается при Z = М/2. Поэтому
М. м NM2
2 2 d(xm;xm<)< ——. (5.8.35)
m= 1 m'= 1 2
Вместе с тем, так как d (xm; xm-) = 0, то можно опустить те слагаемые в указанной выше сумме, для которых т' = т ив результате останется М (М — 1) ненулевых слагаемых. Получим
м м
2 2 d(xm; х,п') ==
m = l т' = 1
М
= 2?2 d(xm;xm.)>M(M—l)dmin. (5.8.36)
т = 1 ш' 7*= m
Объединяя (5.8.35) и (5.8.36), получаем (5.8.31). |
Определим теперь Ре w (N, М) как минимальную вероятность ошибки для наихудшего кодового слова в коде при выполнении минимизации по всем кодам с данной длиной блока N и с данным числом кодовых слов М, т. е.
pe,w(N,M)= min [maxPeiJ.
по кодам т
Лемма 3. В ДСК с вероятностью ошибки е<1/2 при
М ^ N + 2 имеет место неравенство
Ре,w (N, М) >1- ехр [-NEex (0)1, (5.8.37)
{N + 4) (1 —е)
где
?в*(0) = -4- 1п[4в(1-в)]. (5.8.38)
Отметим, что показатель экспоненты Е ех (0) равен значению показателя экспоненты для процедуры с выбрасыванием при R = 0 [см.
(5.7.20)].
Доказательство. Так как dmin должно быть целым числом, то легко проверить, что из (5.8.31) вытекает неравенство dmin ^ N/2 при М ^ N + 2. Предположим, что в данном коде два кодовых слова хт и хт' находятся на расстоянии d = dmin друг от друга. Имеем
Ре,т + Ре,т'= 2 Р(УIхJ+ 2 Р(у|хт.). (5.8.38а)
yeYm >*УСт'
Можно получить НИЖНЮЮ границу ДЛЯ сумм Р е,т + Ре, т' > рас-ширяя Ym и Ym' так, чтобы все у декодировались либо в т, либо в т', и далее, строя нижнюю границу с помощью преобразования Ym и Ym’ в области, соответствующие декодированию по максимуму правдоподобия двух кодовых слов. При этом можно пренебречь тем,что было
183
принято на позициях, в которых хт и хт. совпадают, и таким образом рассмотреть только вероятность возникновения более чем d/2 ошибок в канале среди d символов, в которых отличаются хт и хт-. Получим
