Научная литература
booksshare.net -> Добавить материал -> Физика -> Галлагер Р. -> "Теория информации и надежная связь" -> 168

Теория информации и надежная связь - Галлагер Р.

Галлагер Р. Теория информации и надежная связь — М.: Советское радио, 1974. — 738 c.
Скачать (прямая ссылка): teoriyainformacii1974.pdf
Предыдущая << 1 .. 162 163 164 165 166 167 < 168 > 169 170 171 172 173 174 .. 355 >> Следующая


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, для которого это сведение может быть проведено).
Предыдущая << 1 .. 162 163 164 165 166 167 < 168 > 169 170 171 172 173 174 .. 355 >> Следующая

Реклама

c1c0fc952cf0704ad12d6af2ad3bf47e03017fed

Есть, чем поделиться? Отправьте
материал
нам
Авторские права © 2009 BooksShare.
Все права защищены.
Rambler's Top100

c1c0fc952cf0704ad12d6af2ad3bf47e03017fed