Теория информации и надежная связь - Галлагер Р.
Скачать (прямая ссылка):
N
2Q (k) f (k) = Е. Сумма 2 f (xn) Для большинства кодовых слов будет
П= 1
близка к N&. Однако небольшое число кодовых слов, для которых 2/ (х„) существенно меньше, чем N&, будут представителями ансамбля с меньшим значением Е0 (р, Q), а следовательно, с много большей ве-
346
роятностью ошибки. Вероятность ошибки, обусловленная этими немногими словами, определяет границу вероятности ошибки при г = О [в действительности эти слова не принадлежат ансамблю, однако они появляются в границе,поскольку граница для Qn (х) имеет вид (7.3.18)]. Смысл выбора г > О состоит в том, чтобы уменьшить влияние этих немногих плохих слов на границу.
Простейшим способом максимизации ?0(р> Q, г) по г и Q является нахождение стационарной точки относительно г и Q при ограничениях
2Q(*)-i и 2Q(?)[/№-#] = о.
k к
Используя К и у как множители Лагранжа, находим стационарную точку функции
+ Я 2 <? (ky+ у 2 Q (k) [f (к) -ёг (7.3.24)
k k
Взяв частные производные по всем Q (k), получаем условия
(1 + P)2 a?erlMA)“ CS]P(j\k)llil + p)+k + ylf(k) — g]>0 (7.3.25)
/
с равенством при Q (?) >0, где aj определяется формулой
а;- = 2 Q (к) er[f (А) —<^1 р (/ J /г)'^(1 + р) . (7.3.26)
к
Неравенство в (7.3.25) соответствует тому, что максимум Е0 (р, Q, г) может достигаться на границе, когда некоторые Q (k) = 0, точно так же как и в теореме 4.4.1. Взяв частные производные функции (7.3.24) по г, получаем условие
(1 + Р) 2 2 Q (А) [/ (к) - g] er «IР (Л А)1/(1 + р) =0. (7.3.27)
/ k
Умножая (7.3.25) на Q (k) и суммируя по k, находим, что
Ь = -(1 + р)2Х + Р.
/
Аналогично, умножив (7.3.25) на Q (k) [f (к)—ё\, просуммировав по k и сравнив с (7.3.27), находим, что у = 0. Таким сбразом, (7.3.25) преобразуется в
2 сс/ ег VW-%\p{j\k)U{l+p) >2сб!+р (7.3.28)
/ /
для всех & с равенством, если Q (&) > 0. Хотя это выше и не было доказано, однако можно показать, что соотношение (7.3.28) определяет множество необходимых и достаточных условий на г и на удовлетворяющий указанным ограничениям вектор Q, которые максимизируют Е0 (р, Q, г). Однако более важно то, что можно показать, что получающийся показатель экспоненты дает точное выражение для функции
347
надежности канала с ограничением при скоростях, лежащих между RCT и С, где RCT определена в § 5.8*\
Для величины ц из (7.3.19) трудно найти хорошую границу, однако она может быть точно оценена для больших N. Предположим, что Q удовлетворяет соотношению 2Q (k) / (k) = 8, и рассмотрим
2 f(xn)
п= 1
как сумму независимых случайных величин, выбранных в соответствии с вероятностной мерой Q. Тогда ц — вероятность того, что эта сумма расположена между средним значением и величиной, на б меньшей среднего значения. Из центральной предельной теоремы следует**’, что для фиксированного б
lim Y~N|х= -rJL— , (7.3.29)
N-+ оо У 2па/
о? =2 Q (А) [/(*)-ат. (7.3.30)
Из (7.3.29) можно увидеть, что для фиксированных г и б [егв/[х]Ч-Р
возрастает с iV, как ДДИ-р)/2, и, таким образом, этот коэффициент не
влияет на экспоненциальную зависимость границы от N.
Граница вероятности ошибки для процедуры с выбрасыванием § 5.7 может быть распространена на случай, когда имеются ограничения на входе, точно так же как и граница случайного кодирования. Рассмотрим (5.7.7), которое справедливо для любого ансамбля кодов, и верхние границы (7.3.18) для Qn (х) и Qw(x'). Раскрывая произведения, находим, что для всех М ^ 2 и N > 1 существует блоковый код длины N с М кодовыми словами, каждое кодовое слово которого хт удовлетворяет ограничению
2 f(xn,J<N$,
п— 1
а также удовлетворяет границе
Ре, — N [Ех(9, Q, г) — pR'l (7.3.31)
где
Ех (р, Q, г) = - р In {*2 "2' Q (k) Q (i) er +} U) ~ ^ 1X
I *=0 j=0
*> Чтобы доказать это, нужно начать с нижней границы вероятности — ошибки для кодов с фиксированной композицией, полученной Шенноном, Галлагером, Берлекэмпом (1967), см. неравенство (4.16). После оптимизации по композициям, удовлетворяющим ограничению, следует продолжить доказательство, как и в теореме 6 этой работы.
**> Для нерешетчатых распределений (7.3.29) следует из теоремы 1, гл. XVI, § 4, Феллер (1966), т. 2. Для решетчатых распределений равенство (7.3.29) справедливо только лишь, когда 8 кратно шагу; это следует из теоремы 3, гл. XV, §5, Феллер (решетчатая случайная величина f — это случайная величина, которая может быть сведена к целочисленной случайной величине 2 с помощью преобразования f—zh+a; шаг определяется как наибольшее h, для которого это сведение может быть проведено).