Теория информации и надежная связь - Галлагер Р.
Скачать (прямая ссылка):
0 ^ i п — 1 как источник, который порождает последовательности из S'i в соответствии с первоначальной вероятностной мерой на последовательностях супербукв при условии наступления 5'г. Тогда для и' < п суперисточники i-й , (i -|- п')-й, (i -j- 2п')-й фаз и т. д. тождественны. Первоначальный суперисточник моделируется как совокупность п эргодических суперисточников, каждый из которых используется во всей бесконечной последовательности с вероятностью 1/п.
Используем теперь эту модель в конструкции кодов эргодического источника. Для заданного п пусть Rn (d*)—скорость как функция искажения n-го порядка и для заданного d* с Rn (d*) <i оо пусть Рп К [ ип) обозначает множество переходных вероятностей, на которых достигается Rn (d*). В терминах суперисточника n-го порядка ип является единичной буквой и\, и аналогично можно рассматривать vn как отдельную букву v\ в супер алфавите последовательностей п букв адресата. Полагая, что V — ансамбль отдельных супербукв и V' — ансамбль отдельных супербукв адресата, определяемый Рп,
511
имеем
Rn(d*)=-^-im v).
п
(9.8.17)
Аналогично
d*^>-±-D(u; vn) = -^-d'(u'; v[),
(9.8.18)
n
n
где d' определяется равенством D (u; vn) = d' (u'; v\) и неравенство возникает из-за возможности Rn (d*) = 0.
Пусть теперь I (U'\ V' \ i) — средняя взаимная информация между супербуквой суперисточника i-й фазы, 0 i ^ п — 1, и буквой супералфавита адресата при использовании переходных вероятностей Рп. Так как средняя взаимная информация в канале—выпуклая^ функция входных вероятностей, то
Аналогично среднее значение d' является линейной функцией вероятностной меры на и', так что
где d'i — среднее значение d! (u'; v\) для суперисточника /-й фазы.
Заметим теперь, что I (UV' |/) является верхней границей для скорости как функции искажения первого порядка для суперисточника /-й фазы, вычисленной при среднем искажении d'i. Так как суперисточник i-й фазы является эргодическим, то теорема 9.8.2 применима и для любого 8>0 при любом достаточно большом L имеется множество Mi ^ ехр [LI (UV' | /) + L8] кодовых слов длины L (супербукв), для которых среднее искажение на супербукву для этого источника не больше d't + б. Для заданного б > 0 пусть L достаточно велико, так что для каждой из п фаз такой код может быть выбран, и рассмотрим это множество из п кодов.
Удобно представлять себе кодовые слова в этих кодах не как последовательности L супербукв, а как последовательности Ln букв первоначального алфавита адресата. Будем рассматривать такой i-й код, выбранный выше для суперисточника i-й фазы, как i-й малый код. Используем теперь эти п малых кодов для построения нового множества п больших кодов с длиной блока Ln2 + и, как показано на рис. 9.8.1. Построенный i-й большой код, 0 ^ i п — 1, кодирует выход суперисточника /-й фазы. Как показано на рис. 9.8.1, для каждого I,
0 ^ ^ и — 1, множество букв на позициях от I [nL + 1] + 1 до llnL + 1] + Ln является произвольным кодовым словом из (i + /)-го малого кода, где i + I берется по модулю п. Буквы на позициях Ln + 1,2 [Ln + 1], ..., п [Ln + 1] являются фиксированными буквами алфавита адресата. Таким образом, общее число кодовых слов
1 п~1
(9.8.19)
i = 0
(9.8.20)
512
л—I
б i-м большом коде равно П Mt, где Мг — число кодовых слов в i-м ма-
1 = 0
лом коде. Напомним теперь, что из леммы 9.8.2 следует, что если S* — множество последовательностей букв первоначального алфавита источника, порожденное суперисточником i-й фазы, то TSi = 5г+1. Отсюда следует, что для суперисточника i-й фазы вероятностная мера на буквах позиций от I (Ln + 1) + 1 до I (Ln + 1) + Ln такая же, как для суперисточника (i + I)-й фазы на позициях от 1 до Ln. Следовательно, среднее искажение на букву между суперисточником i-й фазы и i-м большим кодом на позициях I (Ln 1) + 1 до / (Ln + 1) + Ln составляет 1 In часть среднего искажения на супербукву между суперисточником (i + Q-й фазы и (i + /)-м малым кодом (где i + I взята по моду-
Фи.ксиро&аннь/е дукбь/______________Л____________
I v2 V3 | V5 Vg\v7\ V8 Vg v,0 | vff Vfz V,3 | v№ [ V!S Vfg V„ | Vfg v19vzg | v2/ |
Кодовое слова Ксдсвое csroffo Kodoffee c/?aSa
l - го малого xo&a. (i+f)-eo малого кода. ({+2)-гс мамого кода,
Рис. 9.8.1. Конструирование большого кода из малого кода; п = 3, L—-2.
лю п). Выберем малые коды так, чтобы среднее искажение на букву было ограничено сверху выражением (\!п) [d'i+t + 6]. Замечая, что искажение между каждой из п фиксированных позиций в коде и источником ограничено сверху sup d (u; v0), находим, что среднее искажение на букву между i-м суперисточником и i-м большим кодом ограничено сверху выражением
