Теория информации и надежная связь - Галлагер Р.
Скачать (прямая ссылка):
——2(0 (l) e~pd{k’’=1 для всех k. (9.4.36)
Q(k) ,¦
Это является множеством К линейных уравнений с J неизвестными и имеется по крайней мере одно решение с со (/) ^ 0. А тогда, точно так же как в следствии 3 § 4.5, доказывается, что имеется решение, для которого только К чисел со (/)>0. Если прямая min R0 (р, Р)—
р
— рd* касается кривой R (d*) только в одной точке, то это решение должно дать эту точку. Вместе с тем, если min RQ (р, Р) — pd* является касательной к R (d*) на целом интервале, то для того чтобы найти Р, которое приводит к заданному d*, требуется дополнительное ограничение
2 Q (k)P (j\k) d (k; j) = d*.
k, j
Используя (9.4.5) и (9.4.9) с равенством при со (/) > 0, получаем
2®(i)2/&e-:p^feWM(/e; (9.4.37)
/ *
Из (9.4.37) и (9.4.36) получаем К + 1 линейных уравнений с J неизвестными и, как раньше, должно существовать решение, для которого только К + 1 из со (/) положительны. |
9.5. МОДИФИКАЦИЯ ОБРАЩЕНИЯ ТЕОРЕМЫ КОДИРОВАНИЯ ДЛЯ КАНАЛА С ШУМАМИ
Как было уже отмечено, функция искажения
d(k-,j) = {0, k = h (9.5.1)
(1 во всех других случаях,
при К = J является приемлемой мерой искажения для изучения ошибок при воспроизведении выхода источника. Действительно, средняя вероятность ошибки на букву источника <-Ре>, которая изучалась в гл. 4, является просто средним искажением на букву для указанной выше меры искажения. В этом параграфе вычисляется R (d*) для произвольного дискретного источника без памяти и этой меры искажения и, таким образом, отыскивается минимальная вероятность ошибки на букву источника, которая может быть достигнута для скоростей источника, больших пропускной способности. Будет показано, что нижняя граница <Ре>, приведенная в гл. 4, равна фактически минимуму вероятности ошибки для некоторого диапазона пропускных способностей каналов, меньших энтропии источника. Это вычисление будет иметь некоторый дополнительный смысл, так как будет показывать, как 480
результаты последней главы могут быть применены. Неравенства, задающие ограничения
?/Ле-Р* <*:/>< 1, k
упрощаются для этой меры искажения и имеют вид
Kl!fk)~fj е-р<1; (9.5.2)
*= 1 /
Из симметрии следует, что все эти неравенства могут быть удовлетворены с равенством, если положить все. fh равными одному и тому же значению, скажем f0¦ Тогда
/Л =:/о = п ч- (/с— 1) е-Р]-1. (9.5.3)
Используя это f в нижней границе (9.4.10), получаем
minJR0(р, Р)>Я(?/) —1п[1 + (/С-1)е-Р]. (9.5.4)
р
Тогда для всех р > 0 имеем
R (d*) > —pd* + H(U)~ln [1 + (К— 1) е-р]. (9.5.5)
Правая часть максимизируется по р, в результате давая точную границу при р, удовлетворяющем равенству
t (9.5.6)
1+(ЛС-1)е~Р V ’
р — In (К 1) + In ~ • (9.5.7)
Подставляя (9.5.7) в (9.5.5) и производя преобразования, выводим
R (d*) > Н (U) — Ж (d*) — d* ln (К — 1), (9.5.8)
где
Ж (d*) = — d* ln d* — (1 — d*) In (1 — d*). (9.5.9)
В соединении с теоремой 9.2.2 результат (9.5.8) эквивалентен для дискретных источников без памяти обращению теоремы кодирования для.канала с шумом, т. е. теореме 4.3.4. Для того чтобы достигнуть вероятность ошибки на символ ис.точиика, равную d*, канал должен иметь пропускную способность, по крайней мере, равную правой части (9.5.8), или, что эквивалентно, для канала такой пропускной способности, d* — нижняя граница вероятности ошибки на символ.
Теперь найдем условия, при выполнении которых (9.5.8) удовлетворяется и переходит в равенство. Из теоремы 9.4.1 следует, что (9.5.4) удовлетворяется с равенством, если для (9.5.7) существует решение с со (/) 0, которое для этой меры искажения принимает вид
со (k) + (1 — со (Уг)) е-р = Q (k)/fh, 0 < k < К — 1. (9.5.10)
Для fk = /о = И + (К — 1)е-р]-г
ш (к) ?(Ш1 j^Lzl2?^b?lp. (9.5.11)
1—е~р
16 Зак. 210 481
Все о (k) неотрицательны, если
Q(k) >-------^-----для всех к. (9.5.12)
' ер + (К-1)
Следовательно, (9.5.4) удовлетворяется с равенством для всех достаточно больших р. Так как для каждого р>0
min R0 (р, Р) —рd* р
имеет с кривой R (d*), по крайней мере, одну общую точку, и так как эта точка задается (9.5.6) для всех р, удовлетворяющих (9.5.12), то имеем
