Теория информации и надежная связь - Галлагер Р.
Скачать (прямая ссылка):
Приведем теперь (5.8.19) к аналитически более простой, но несколько более слабой форме. Существует ряд методов, чтобы сделать это, которые приводят к одной и той же экспоненциальной границе для вероятности ошибки, но с разными коэффициентами. Хотя коэффициенты здесь получаются не очень хороши, но мы избегаем некоторых запутанных деталей при доказательстве теоремы 5.8.4. Для того чтобы получить точные численные значения, в особенности при малых N, следует исходить непосредственно из (5.8.19).
Теорема 5.8.3. (Граница сферической упаковки для ДСК.) Пусть задан двоичный симметричный канал с вероятностью ошибки е <С 1/2 и пусть б — произвольное число, е ^ б ^ 1/2 и Ж (5) = —61пб —
— (1 — б)1п (1 — б). Если число кодовых слов М удовлетворяет неравенству
ниями N и М, будем иметь
м
(5.8.19)
М >V8{N+\) ехр {М [In 2 — Ж (б)]}, (5.8.20)
то
PAN, Л*)>
-------.__ _ ехр {I
(l-e)V8(JV + l)
+ (1-6) In (1-е)]}.
ехр { N [Ж (б) + б In s +
(5.8.21)
179
Доказательство. Как видно из (5.8.14), любое увеличение в какой-
м
либо из сумм m До значений, больших, чем указанные в (5.8.17)
т—\
и (5.8.18), приводит к дальнейшему уменьшению нижней границы Ре.
м
Пусть п' — | и выберем АТm так, что An\m = 2N. Для всех
m=l
М
пфп' выберем Ап m так, что ^4 го = {п)М. Эти выборы, оче-
ГП= 1
видно, приводят к значениям сумм, большим, чем те, которые определяются из (5.8.17) и (5.8.18); подставляя эти выражения в (5.8.14), получаем
Pe(N, М)>
п' )~1г]е'1'(1-е)"~П'- (5-8-22)
Используя границу Стирлинга для факториала, можно оценить снизу (л') следующим образом (см. задачу 5.8(6)):
N ) >-7^гехрГл/Я?( —)]. (5.8.23)
п' ! V2N *4 V N
Если п'N12, то Ж (n'/N) ^ Ш (б). Так как 1/N > l/(N 1), то
(Л> уТО“р[Ж*<в)|- (5-8-24>
Так как 6< 1/2 и п'=\ |, то единственно возможное значе-
ние я', которое превышает Л/У2, равно (N + 1)/2. В этом случае, используем специальную границу (см. задачу 5.8(6)):
N )^z-—~L= -2N. (5.8.25)
(N +1)/2 1 У 2(N +1) v ’
Так как 2N ]^ехр{1ЯЖ (б)), то граница в (5.8.24) справедлива при всех возможных значениях п’. Далее, в силу того, что п' превышает б N не более чем на 1, будем иметь
е Nn' 8 / 8 \&N
1—е/ 1 —е
Подставляя это выражение и (5.8.24) в (5.8.22) п применяя границу для М в (5.8.20), получаем (5.8.21), что завершает доказательство теоремы. |
Если найти Esp (R) [в соответствии с (5.8.2)], то, используя те же рассуждения, что и в примере 1 § 5.6, получим, что при R <С С
Esp (R) - —б In 8—(1 -б) In (l-е )—Ж (6), (5.8.26)
Я = 1п2—Ж {б). (5.8.27)
Рассмотрим теперь некоторый произвольный (N, /?)-код, для которого (1//V)ln[8 (N + 1)] С R < С. Если выбрать б так, чтобы удовлетво-
180
рялось равенство
R ----- In 2—Ж (б) + — [8(Л^ + 1)]. ,
N
то М = [ ехрNR ] должно удовлетворять (5.8.20), и из (5.8.21) вытекает результат, который эквивалентен теореме 5.8.1:
Для R > С мы ниже выведем более сильную границу, чем граница в теореме 5.8.1.
Для того чтобы установить справедливость теоремы 5.8.2 для ДСК, нам понадобится несколько лемм, которые представляют самостоятельный интерес. В первой из них рассматривается концепция декодирования, называемая «декодирование списком». Предположим, что при заданном множестве М кодовых слов длины N декодер отображает любую принятую последовательность в список, скажем, L сообщений. Такое декодирование могло бы быть полезным, если бы планировалось использование обратной связи в системе передачи и при последующей передаче устранялась неопределенность в том, какое из L декодированных сообщений было в действительности передано. Если переданное сообщение не принадлежит списку из L декодируемых сообщений, то говорят, что произошла ошибка при декодировании списком. Пусть Ре (N, М, L) —минимальная вероятность ошибки при декодировании списком по всем кодам с М кодовыми словами, длиной блока N и списком из L декодируемых сообщений. Можно повторить вывод границы сферической упаковки для схемы декодирования списком, обозначая через Ym множество выходных последовательностей у, для которых т принадлежит декодируемому списку. Равенство (5.8.14) остается справедливым, если понимать под Ап> т число выходных последовательностей у, для которых т принадлежит декодируемому списку и которые находятся на расстоянии л от хт. В этих условиях ограничение (5.8.16) для АП:Лг принимает вид
