Теория информации и надежная связь - Галлагер Р.
Скачать (прямая ссылка):
Вернемся теперь к теореме 9.3.1 и исследуем, как быстро скорость кода (т. е. (In M)/L) может сходиться к R (d*) при возрастании L. Для этой цели удобнее использовать центральную предельную теорему, а не неравенство Чебышева. Имеем
Рг {/ (u; v) > L [R (d*) + 6/2]} « Ф ^ j. (9.3.29)
Рт [D (и; v) > L (d* + 6/2)] « Ф ^j, (9.3.30)
где
ф(^*)" к*-(-?)*<-(-*)¦х>0¦
X
Следовательно, Pt(A) в (9.3.12) приближенно оценивается сверху выражением
Р,(Л);ехр(-^-) + ехр(-^). (9.3.31)
471
Подставляя это выражение в (9.3.11) и (9.3.10), получаем
< d* + 6/2 +
ехр —
+ ехр
8 а/
i^Wex р(_е“/2 +1)
8 Od /
шах d (k; у).
i
Выбирая*) 6^=2(CT/ + ad) ]/ (ln L)/L, находим, что dL сходится к d* с возрастанием L, как ]/(lnL)/L и (In M)/L сходится к R(d*) таким же образом.
Это означает, что для любой заданной точки на кривой R (d*) оценка скорости и искажения для кода источника длины L лежит на линии с наклоном 45°, проходящей через заданную точку, и стремится к ней, как ]/(In L)/L. Так как рассматриваемое d* можно изменять с L так, чтобы или di (dL > 0), или (In M)IL было фиксированным, то б может быть опущено или из границы для М или из границы для dL в теореме 9.3.1 при dL > 0. Легко видеть, что та же скорость сходимости имеет место и в теореме 9.3.2.
Используя более тонкие методы, Пилк (1967) установил существование кодов со скоростью R (d*), для которых искажение сходится к d* с возрастанием длины блока, как (In L)/L.
9.4. ВЫЧИСЛЕНИЕ R (d*)
Обратимся теперь к нахождению множества переходных вероятностей (т. е. тест-канала), на которых достигается R (d*). Обычный подход к минимизации функции О (Q; Р) при ограничении d ^.d* состоит в использовании множителя Лагранжа, скажем р, и минимизации
In
Р (i \ k) ю(/)
рd (k; j)
r0(p, P) = j+Pd = 2 QWpU\k) k, i
по всем выборам множества переходных вероятностей Р, где
со (/):
(9.4.1)
Другие ограничения
PU\k)>0, ZP{j\k) = i /
рассмотрим позднее. Варьируя р ^ 0, мы увидим, что можно найти R (d*) для всех значений d*. В этой задаче множитель р имеет геометрический смысл величины наклона кривой R (d*) в точке, порождаемой этим значением р.
*> Для того чтобы удостовериться, что ошибка аппроксимации с помощью центральной предельной теоремы стремится к нулю быстрее, чем б при этом выборе, см. Феллер (1966), т. 2, гл. XVI, § 6, теорема 1.
472
Для того чтобы показать это, рассмотрим Cf (Q; Р) и d для любого частного Р как точку на графике с ординатой С/ и абсциссой d. Прямая с наклоном —р, проходящая через эту точку, пересечет J-ось в точке С1 (Q; Р) + рd. Распределение Р, которое минимизирует R0 (р, Р), будет минимизировать ординату этой точки пересечения оси J, и все точки кривой R (d*) будут лежать на прямой или выше прямой с наклоном —р, проходящей через эту точку пересечения. Следовательно, эта прямая касается кривой R (d*). В дальнейшем будет показано, что для конечной меры искажения наклон R (d*) не может изменяться разрывно, Кроме, быТЬ МОЖет, ТОЧКИ dmax-
Для того чтобы в действительности провести минимизацию R0 (р,Р) по Р, целесообразно ввести множители Лагранжа для ограничений
2P(j\k)=i
г
при всех k. Удобно ввести эти множители в виде —Q (k) In р^,что
Ц(к)
означает, что нужно минимизировать выражение
F(р, Р, f) = ^Q(k)P(j\k)
k, j -pd{k\ j)
ln
P{i\k)
¦ In
fh
и затем выбирать f
Q(k)
(fo, •••, fK-i) так, чтобы
2P(i l*) = i
(9.4.2)
для всех k. Дифференцируя F, получаем
dp{]\k) ' где со (/)= 2,Q{k)P(j\k).
ln шт.
CO (/)
pd (k; /) — ln
fh
Q(k)
(9.4.3)
Следовательно, условия на P, которые приводят к стационарной точке для F, принимают вид (для всех k, j):
pd (k; j)— ln -Jy— = 0,
(o(i) Q(k)
P(j\k)=- ^(/) fk e~Pd<-k- />.
'1 Q (k)
Если умножить обе части (9.4.5) на Q (k), просуммировать по k и сократить на
® (/) = 2 Q (k)р (/1 k)>
k
(9.4.4)
(9.4.5)
то получим
1 = 2 fke~pd{к’п для всех /• к
(9.4.6)
473
