Теория информации и надежная связь - Галлагер Р.
Скачать (прямая ссылка):
Точно так же, суммируя (9.4.5) по / и используя ограничение 2 P(j | k)=
/
= 1, получаем
1=—2 ® (/) e-pd для всех &. (9.4.7)
Q (*) /
Равенства (9.4.6) дают У линейных уравнений относительно переменных fk, а (9.4.7) дают К линейных уравнений относительно со (/). Если J = К, то обычно эти уравнения можно решить и затем найти Р (/1 k) из (9.4.5). Так как J (Q; Р) выпукло ^ по Р, то F (р, Р, f) также выпукло ^ и решение дает минимум.
Трудность указанного выше подхода заключается в том, что получающиеся Р (j\k) не обязательно будут неотрицательными. В следующей теореме этот подход излагается строго с учетом ограничения P(i\k) ^ 0. В ней даются необходимые и достаточные условия, налагаемые на множество переходных вероятностей Р, которые минимизируют R0 (р, Р) и определяют удобную нижнюю границу для R0 (р, Р) и, следовательно, для R (d*).
Теорема 9.4.1. Для заданного источника с энтропией Я (U) и заданной меры искажения пусть
1п "У Ъпр(:\ л + pd (/г; 2jQ (0^010
Ro(p, P)=^iQ(k)P(i\k)
к; I
Здесь и всюду в дальнейшем сумма берется только по тем k, j, для которых Р (/1 k) > 0. Тогда для любого р > 0
min R0 (р, Р) = Я (U) +таx%Q (k) ln fh, (9.4.8)
p t k
где максимум берется по всем f = (/0, ..., /к—i) с неотрицательными компонентами, удовлетворяющими ограничениям
2/fte-pd№/>< 1, 0</<У—1. (9.4.9)
k
Необходимые и достаточные условия, накладываемые на f, при которых достигается минимум в (9.4.8), сводятся к тому, что существует множество неотрицательных чисел со (0), ..., со (J — 1), удовлетворяющих (9.4.7), и что (9.4.9) удовлетворяется с равенством для каждого / с со (/) > 0. Выраженный через f ий вектор Р, задаваемый (9.4.5), минимизирует R0 (р, Р).
Обсуждение. Одно из следствий из (9.4.8) заключается в том, что для любого множества fk ^ 0, которое удовлетворяет (9.4.9),
min R0 (р, Р) > Я (U) +2Q (k) In fk. (9.4.10)
р k
Так как уже было показано, что
min R0 (р, Р)— pd* < R (d*), р
то это означает, что для любого р ^ 0 и любого f, удовлетворяющего (9.4.9) для этого р,
R(d*)^H(U)+ 2Q(A)ln/ft —pd*. (9.4.11)
k
474
Это соотношение задает нижнюю границу для R (d*) и фактически дает R (d*), если р и f выбраны оптимально.
Попытка фактического нахождения min Я0 (р, Р) приводит нас
к ситуации, весьма похожей на ту, которая была при отыскании пропускной способности. Можно попытаться решить (9.4.9) относительно f, сначала угадывая множество /, для которых должно иметь место равенство; затем, используя полученное f для решения (9.4.7) относительно со (/) и после этого, находя Р (/1 k) с помощью (9.4.5). Суммируя
(9.4.5) по / и используя (9.4.7), видим, что Р (j \k) действительно являются переходными вероятностями. Умножая (9.4.5) на Q (к), суммируя по k и используя (9.4.9), находим, что со (/) действительно являются выходными вероятностями EQ(&)P (/)&). Хотя (9.4.8) выражает
min R0 (р, Р) только через f, нужно еще решить (9.4.7), чтобы убедиться, что со (/) ^0 и что (9.4.9) удовлетворяется с равенством для каждого / сю (/) > 0. В следующем параграфе эта процедура будет применена к важному примеру. Другой подход к нахождению min R0 (р, Р) в случае, если источник и мера искажения достаточно симметричны, состоит в угадывании решения и проверке, что это решение удовлетворяет условиям теоремы. И в еще одном последнем подходе используется то, что так как Б Q (k) In fk выпукло по f, то R0 (р, Р) выпукло
'w по Р и множества ограничений выпуклы; при этом относительно легко вычислить минимум или максимум численными методами с помощью вычислительной машины.
Следует отметить, что в силу строгой выпуклости 2Q (k) In fh по
k
f значение f, на котором достигается максимум в (9.4.8), является единственным. Вместе с тем Р и о не обязательно являются единственными.
Для того чтобы дать простую интерпретацию максимизирующего значения f в теореме, заметим, что для Р и f, удовлетворяющих (9.4.5), вероятность входа при заданном выходе (иногда называемая обратной переходной вероятностью) равна
Тогда соотношение (9.4.9) с равенством представляет собой условие, что эти выражения действительно являются условными вероятностями, а (9.4.7) представляет собой условие, что эти обратные вероятности согласуются с входными вероятностями.
Доказательство теоремы. Сначала покажем, что для всех Р и f, удовлетворяющих заданным ограничениям,
р
k
k
Pb(k\i)=fhz-pd(k'n-
Яо(р, P)>H(U)+2Q(k)lnfh. k
