Теория информации и надежная связь - Галлагер Р.
Скачать (прямая ссылка):
Лемма 5.9.3. Пусть X будет наибольшим собственным значением неприводимой матрицы [а] и пусть vmax и vmin будут наибольшей и наименьшей компонентами положительного правого собственного вектора и], соответствующего к.
Тогда при любом s0
Eo.n(p, Qn, s0) =-----— lne(s0)[a]w 1].
N i-------1
(5.9.39)
[a] v] = к v].
(5.9.40)
^iL^<e(s0) [a]w 1]<
Vm/TT. 1 1
Vmax
vmax
vmin
(5.9.41)
Доказательство. Согласно (5.9.40) имеем
[a]w v\ — [a]w _ 1 [a] v] = X [a]w -1 v] = = ^2[a]w-2t»]=- ... =:lNV].
(5.9.42)
*> См., например, Гантмахер (1967).
199
Так как [а] имеет неотрицательные элементы, то компоненты вектора-строки е (s0) [аР являются неотрицательными и поэтому е (s0) [aFl]
I___I 1----1
можно оценить сверху, оценивая сверху компоненты 1] в рассматриваемом слу'чае величиной (Uvmin) и]. Отсюда
е (s0) [a]w 1] < —е (s0) [а]" v] =
1---1 Vmin L 1 ¦ 1
= —e(s0)i»K^^. (5.9.43)
Vmin 1---1 Vmin
Поступая аналогично, можно завершить доказательство неравенством е («о) [«]" П> — е (s0) [а]" v] > ^ Л" |
----1 Vmax 1-----1 Vmax
Подставляя (5.9.41) в (5.9.39) и используя обозначение X (р, Q) для того, чтобы отметить зависимость X от р и Q, получаем,
|?о.л-(р, Qjv, s0) + lnX(p, -Q)|< -J-ln^L , (5.9.44)
N Vmin
где правая часть (5.9.44) не зависит от s0.
Таким образом, доказана следующая теорема.
Теорема 5.9.3. Пусть задан канал с конечным числом состояний, в котором sn = g (уп, sn_i), и пусть Q является распределением вероятностей, таким, что, когда входы выбираются независимо с распределением вероятностей Q, любое состояние может быть достигнуто с ненулевой вероятностью из любого другого состояния за конечное число шагов, Тогда при любой R > 0 и любом положительном целом N существуют (N, /?)-коды, такие, что при любом сообщении пг, 1 ^ т ^ ре^к-!, любом s0 и всех р, 0 ^ р ^ 1,
ре, тп(5оХ4Л^^ехр{ — N[ —In х(р, Q) — pR]}, (5.9.45)
t'min
где X (р, Q) является наибольшим собственным значением матрицы [а], заданной (5,9.38) и (5.9.36), a vmax и vmin являются экстремальными компонентами положительного правого собственного вектора, соответствующего X (р, Q).
Граница в (5.9.45), конечно, может быть оптимизирована rio Q и р с целью получить более точную границу. К сожалению, в общем случае эта граница слабее, чем граница, представленная теоремой
5.9.2, так как здесь мы ограничились использованием ансамблей случайных кодов, в которых буквы кодовых слов выбираются независимо. Однако имеется важный класс каналов, для которого граница оптимизируется на независимо выбранных буквах, и в этом случае распределение Q, которое минимизирует a (sn-1, sn) в (5.9.36), не зависит от значений и sn. Чтобы увидеть это, фиксируем s„ и s = (slf ..., sN) и рассмотрим минимум выражения
no Qn (х). Используя такие же рассуждения, как в примере 4 § 4.6 с параллельными каналами, можно показать, что минимум достигается на произведении распределений
N
Qn(x)= П Q<»>(*b),
п= 1
где при каждом п на распределении Q<n) (хп) достигается минимум выражения
2fZQ(n) (хп)Р(уп, sn I хп, s„-1)1/<1 + P>\I + p .
«п J
Рис. 5.9.2. Двоичный канал с двумя состоя- Рис. 5.9.3. Канал, изображенный
ниями; состояние известно на приемном на рис. 5.9.1, у которого устране-
конце. на память.
Если то же самое Q минимизирует а = (sn _1( sn) при любых sn_ и sn, то Q(n) не зависит от п и не зависит такж е от s и s0. Следовательно
N
Qn (х) = П Q(xn)
п— 1
минимизирует указанное выше выражение при всех s и s0 и, таким образом, оно максимизирует Е0 (р, Qjv, s0) при всех s0. В этом случае ^ (р), заданное равенством (5.9.16), равно —In К (р, Q) при этом минимизирующем значении Q. Хотя отыскание X (р, Q) при этом минимизирующем значении является нетривиальной задачей, оно, по крайней мере, не зависит от длины блока.
Пример, изображенный на рис. 5.9.1, дает канал из указанного выше класса и для него почти очевидно, что входы нужно использовать независимо и с равными вероятностями в ансамбле кодов. Для этого канала Ет (R) изображена на рис. 5.9.2. Для сравнения на нем также изображена Ет (R) для канала без памяти, представленного на рис. 5.9.3. Этот канал эквивалентен каналу, представленному на рис. 5.9.1, с вероятностями q (sn Is,^), равными 1/2 при любых sn^1 и s„ или, говоря более наглядно, этот канал является каналом
