Теория информации и надежная связь - Галлагер Р.
Скачать (прямая ссылка):
Ix (Ul; Vl) = In /Л . (9.8.8)
“l (vl)
Заметим, что /х (uL; vL) не является взаимной информацией между uL и \L при использовании источника на входе тест-канала без памяти
507
с переходными вероятностями, задаваемыми Р (j\k), так как ($ь (vL) не является вероятностью vz выхода тест-канала.
Пусть d и R произвольны ; определим
Л = {и, vz.: или 1г (u/.; vl)>LR или Z)(u; vL)>Ld\. (9.8.9)
Пусть Pt (А) — вероятность А в ансамбле тест-канала. Заметим, что этот ансамбль содержит бесконечные последовательности на выходе источника, но содержит последовательности адресата vL только конечной длины. Пусть Р с (D > Ld) — вероятность в ансамбле кодов и ансамбле выходов источника того, что искажение (между и и кодо-еым слоеом, в которое оно отображается) превысит Ld. Тогда из доказательства леммы 9.3.1 следует, что
Pc(D>Ld)^Pt(A) + ехр(— Me-1*). (9.8.10)
Читателю сейчас следует просмотреть это доказательство. Существенная разница состоит в том, что a>L (vL) было в лемме как выходной вероятностной мерой для тест-канала, так и вероятностной мерой, с которой выбирались кодовые слова. Если заметить, что только последнее свойство было использовано в доказательстве, то становится очевидным, что здесь применимо неравенство (9.8.10).
Теперь пусть R — R± (d*) + 6/2 и d — d* + 6/2. Как и в теореме 9.3.1, среднее искажение на букву dL по ансамблю кодов удовлетворяет неравенству
rfZ<d* + 6/2 + Pc[D>L(d*+6/2)] supd(u; р0). (9.8.11)
U , V о
Так как d (u; v0) по предположению ограниченно, то теорема будет доказана, если будет показано, что Pc[D>L{d*-\- 6/2)] сходится к 0 при L-v оо. Как в теореме 9.3.1 последнее слагаемое в (9.8.10) стремится к 0 с возрастанием L. Первое слагаемое оценивается сверху выражениями
Pt (А) < Рг {/х (иг, vt) > L [Rx (d*) + 6/2]} +
Pr {D (u; vL)>L[d* + 8/2]}, (9.8.12)
Pr{/i(uz; Vz) > L [/?! (a*) + 6/2]} =
= Pr
(9.8.13)
Вместе с тем, так как совместный процесс и, v является эргодическим, то из (3.5.13) вытекает, что с вероятностью 1
z
L со (уг) со(иг)
Следовательно, вероятность в (9.8.13) стремится к 0 с возрастанием L. Такие же рассуждения применимы к последнему слагаемому в (9.8.12), что завершает доказательство. |
508
Один из наиболее интересных аспектов предыдущей теоремы состоит в том, что как Rx (d*), так и ансамбль кодов, использованный в доказательстве, зависит только от меры искажения и вероятностей отдельной буквы источника. Это указывает весьма ясно, что если хороший код источника конструируется только на основе знания вероятностей отдельной буквы источника, то можно с уверенностью сказать, что любая память в источнике только уменьшит среднее искажение по отношению к тому, которое ожидается в случае источника без памяти. К сожалению, это утверждение нельзя сделать точным и не очень трудно указать примеры кодов, для которых среднее искажение источника с памятью превышает среднее искажение для источника без памяти с теми же самыми вероятностями отдельных букв.
Было показано, что для дискретного эргодического источника можно найти коды источника со скоростями, произвольно близкими к R± (d*) и со средними искажениями на букву, сколь угодно близкими к d*. Перейдем теперь к изложению более сильного результата, когда Rx (d*) может быть заменена на R (d*). Путь доказательства заключается в том, что сначала выбирается п достаточно большим, так чтобы Rn (d*) было близко к R (d*). Затем рассматриваются последовательности из п букв источника как единые буквы «суперисточника», который порождает одну букву каждые п единиц времени. Затем применим предыдущую теорему к этому суперисточнику и после соответствующей нормировки по п получим требуемый результат. Имеется небольшая трудность в этой процедуре: суперисточник не обязательно будет эргодическим. Чтобы обойти ее, сначала покажем, что суперисточник может быть разбит не более чем на п «эргодических компонент» и затем применим предыдущую теорему в каждой компоненте отдельно.
Предположим теперь, что дискретный эргодический источник имеет алфавит объема К и рассмотрим суперисточник п-го порядка с алфавитом объема Кп, где каждая буква суперисточника является последовательностью п букв первоначального источника. Каждой последовательности и == (..., ы_ь «о, ult ...) первоначального источника соответствует последовательность и' = и'0, и\, ...) супер-
источника, где и\ = (ии иг, ..., «„), и\ = («„+ь ..., игп) и т. д. Обозначим это соответствие между последовательностями первоначального источника и суперисточника в виде ими'. Так как сдвиг на п единиц времени в первоначальном источнике соответствует сдвигу на одну единицу времени для суперисточника, то имеем Tln Т1 и' для и<->и'. Аналогично, любое множество S последовательностей первоначального источника соответствует множеству S' суперисточника и Tln S <-> Т1 S'. Напомним, что, как указано в § 3.5, инвариантное множество S является множеством, для которого TS = S, и что источник эргодический тогда и только тогда, когда любое измеримое инвариантное множество имеет вероятность 1 или 0.
