Теория информации и надежная связь - Галлагер Р.
Скачать (прямая ссылка):
5.8. (а) Применение формулы Стирлинга дает
(Г
что равносильно N /
N
2л j (N— j)
N
N-j
N-i
ехр[8д, —Bj — ew_/],
,~N&e (UN)
N
2 nj(N-j)
exp [e
e;—
Так как eN < г. и e,N_j> 0, то, замечая, что ехр [Ед, —г. — < 1,
получаем искомую верхнюю границу. Для нижней границы eN > 0 и
1 1
ехр [8дг — ej—ед/-— /1 > ехр
12/ 12 (N—j)_
607
1 1 1
Заметим теперь, что —-------—------------- >—— с исключением случаев
12/ 12 (N— /') 9
/ = 1, N — j= 1; /= 1, N — j — 2 и /=2, N—/ = 1. Таким образом, за этими исключениями имеем
ехр [6yv -г}-eN_ ,] > ехр [ ) >
/т- ¦
>/-snbr/T-V
V / ; г 2nj(N-j) V 8 У 8/(JV-/)
Нижняя граница должна быть оценена численно для указанных выше исключительных случаев и можно увидеть, что неравенство имеет место при/ = 1 и N — /= 1.
jV
(б) Минимизируя !/ —------------ по /', 0</<jV, находим, что минимум
8 j(N — i) ______________
N , / 1
1 / " 1 / 1
достигается при j=N/2, что дает I/ ---------- -------> I/ ——. Аналогично
___________ V 8 l(N—j) \ 2N
N
максимизируется по целым /, 1< j < N—1, и достигает
2 nj(N-j)
V/ N _ / 1
------------< I / -----< 1 .
2nj(N—j) ^ ^ 2п
/"У
Заметим, что 1/ ------- является границей, в которую не входят ни N, ни /.
у 2я Далее отметим, что
2N~1 ^ —( 2N \ > -i- (1/2) |/ __L_ __ 1 / 1 22N~ 1
N j 2 \ N j " 2
]/ AN AN ‘
(в). Нижняя граница является очевидной, а верхняя граница следует непосредственно из указания; получаем
N \ ( N \ I N—п \ ( N \ (N—п
<
/ N \ ( N \ / N—(j + tn—1) \ / JV \ ( N—/
\/+« / \/+/я —1 J V } + т— 1 1 \/ + т—1
По индукции будем иметь
(/+.М")(-т*Г-
Из пунктов (а) и (в) следует, что
f N
\ Sj(N-j) ехр {yV-^(//jV) + /lne+ (N~i) In (1 —е)}
<2 CI)'"у
N
X
п=/ ¦ ¦ 2л/ (Л/— /)
608
(г) Первый результат получается легко. Для границы Чернова имеем Рг [ш > /] e“s/ [se^-f (1—e)]‘v при всех s > 0.
Правая часть достигает минимума по s > 0 при
(1-6) UN
s = ln
После преобразования получаем Pr [w > j] < ехр jN
в(1 — j/N)
М — )+ — 1пе + —------------ In (1 — е)
\ N ) N N У .
Сравнивая с (в), получаем, что граница Чернова дает правильную экспоненциальную зависимость от N.
5.9. (а) Рг (у j xm) = srf(Xm’ У) (1 — ?)N~d(x™’ у>.
Это выражение убывает с ростом d (хт, у) так, что выбор т для минимизации d (хт, у) равносилен выбору пг для максимизации Рг (у | хт).
(б) Когда сообщение т поступает на кодер и какое-нибудь частное значение хт передается по каналу, то d (хт, у) является числом ошибок, которые происходят в канале. Следовательно, Pr [d (хт, у) = г] просто равна вероятности г ошибок для N символов. Поэтому
Pr [d {хт, у)=,'] = ^ ) е‘(1 -в)"-'.
Точно так же при каждом т' ф т кодовое слово хт, статистически не зависит как от хт, таки от переходов в канале и поэтому хт, не зависит от у при условии, что т поступает на кодер. Так как каждая компонента хт, является 0 или 1 с рав-ными вероятностями, независимо от у, то отсюда следует, что каждая компонента хт’ отличается от соответствующей компоненты у с вероятностью Va, так что
СИ
Pr [d (хш/, у) = г] —вероятность г отличий в N символах—равна
(в) Ошибка происходит только тогда, когда d (хт,, у) < d (хт, у) при т’ Ф т. Ограничивая сверху вероятность объединения этих событий суммой вероятностей, получим
Рг [ошибка | d(xm, у). /] 2 Pr[d(xm,, y)<t|d(xm, у) = »'] -
т ’ т
Однако, как уже было показано, на ансамбле кодов d (хт,, у) не зависит от d (хт, у) и поэтому
Pr [d (хт,, у) < i I d (хт, у) = /] = V ( ) 2~N-
п—0 \ П )
Так как имеются М — I возможных значений для т’ Ф т и так как вероятность не превосходит 1, то
Рг [ошибка ] d (хт,, у) = i] ~