Теория информации и надежная связь - Галлагер Р.
Скачать (прямая ссылка):
Предположим теперь, что S'0 — инвариантное множество последовательностей суперисточника и что его вероятность Q’ (S'0) больше 0. Соответствующее множество S0 <-» S'0 первоначального источника имеет вероятность Q (S0) = Q' (S'0) и удовлетворяет равенству TnS0 = = S0. Определим множества 1. ^ i ^ п — 1, равенствами
509
Si^PSo. (9.8.15)
Так как источник стационарный, то Q (Si) — Q (S0) для 1 < i 5^ п — 1. Пусть теперь множество А является объединением множеств S0, Slt ..., Sn_a. Тогда имеем
ТА ¦=гГй154)=Пй 1TSi=S1 U 52 U ••• U TS^. (9.8.16)
\г=о 1 i= о
Поскольку TSn-1=TTn-^S0 = S0, то это сводится к равенству ТА = = А. Так как источник эргодический и Q (А) > 0, то должно быть Q (А) = 1 и, следовательно, Q (S0) = Q' (S'0) ^ 1/«. Таким образом, показано, что каждое измеримое инвариантное множество для суперисточника имеет вероятность 0 или вероятность, не меньшую 1/п.
Далее предположим, что S0' — инвариантное множество последовательностей суперисточника и что В' — инвариантное подмножество S'о с 0 < Q’ (В') < Q' (S’ о). Пусть S'0 — В' — последовательности, содержащиеся в S'Q, но не содержащиеся в В', заметим, что Т (So — В') = TS'0 — ТВ' = S’о — В', так что S'n — В' — также инвариантное подмножество S'0. Из предыдущего результата следует, что 1 /п < Q' (В') сС Q' (S'о) — 1/п. Если теперь представить, что В' играет роль S' и повторить приведенные выше рассуждения, то увидим, что постепенно мы должны попасть в S'0, которое не имеет инвариантного подмножества В' с 0 < Q' (В') < Q' (S'0). Будем называть такое S'0 эргодической компонентой суперисточника. Источник, который порождает супербуквы в соответствии с условной вероятностной мерой Q' при условии, что задано S'0, является, очевидно, эрго-дическим источником, так как при условии, что задано S'0, каждое инвариантное подмножество S'0 имеет вероятность 0 или 1.
Пусть теперь S0<~>S'0, пусть St = Т‘ S0 и пусть S^S't. Каждое S’i должно также образовывать эргодическую компоненту суперисточника, т. е. если В' г — подмножество S' t и ТВ't = В' it то для соответствующего множества Bt первоначального источника имеем ТпВ% = Bt. Положив, что В0 = Т~1ВЬ получаем, что В0 — подмножество S0 и ТпВ0 = В0. Следовательно, В'0 — подмножество S'0 и ТВ'0 = В'0. Так как Q' (В'г) = Q' (В'0), то будет илиф' (В'г) = 0 или Q' (В'г) = = Q' (S'i). Наконец, рассмотрим пересечение Sj П Sj. Это пересечение является инвариантным множеством и является подмножеством как множества S'it так и множества Sj. Таким образом, или Q' (SI П Sj) = 0 или Q' (Si П Sj) = Q' (S'i). В последнем случае S'i и Sj—одни и те же множества (исключая, быть может, разность вероятности нуль). Легко видеть, что если Sj и Sj совпадают, то совпадают Sj.|_* и S/+*, где i + k и / + k взяты по модулю п. Отсюда легко следует, что число различных эргодических компонент, скажем п', является делителем п и что в качестве эргодических компонент могут быть взяты So, SI, ..., Sn'-i. В этом случае каждая эрго-дическая компонента имеет вероятность 1 In'. В случае, представляющем наибольший физический интерес, п’ — 1 и суперисточник с самого начала эргодический.
Следующая лемма подытоживает результаты.
510
Лемма 9. 8. 2. Рассмотрим суперисточник /г-го порядка, буквы которого — последовательности из п букв дискретного эргодического источника. Множество последовательностей суперисточника может быть разбито на п' эргодических компонент, каждая из которых имеет вероятность Мп , где п' является делителем п. Компоненты не пересекаются, за исключением, быть может, множеств вероятности нуль. Множества последовательностей 50, S1( ..., первоначального
источника, соответствующие этим эргодическим компонентам, можно связать соотношениями Т (5г) = 5i+1, —2 и Т Sn'-x=S 0-
В качестве примера рассмотрим двоичный источник, для которого выход образован парами одних и тех же символов. С вероятностью V2 каждый символ на четной позиции получается в результате независимого равновероятного выбора символов алфавита, а каждый символ с нечетным номером совпадает с предыдущим символом с четным номером. Аналогично с вероятностью 1/2 каждый символ с нечетным номером получается в результате независимого равновероятного выбора символов, а каждый символ с четным номером совпадает с предыдущим символом с нечетным номером. Это эргодический источник, однако супер источник второго порядка имеет две компоненты. На одной компоненте суперисточник не имеет памяти и порождает 00 с вероятностью 1/2и 11 с вероятностью Va .На второй компоненте все четыре пары символов равновероятны, однако последний символ любой пары совпадает с первым символом следующей пары. Очевидно, что в этом примере выход какой-либо компоненты (в символах первоначального источника) статистически эквивалентен выходу другой компоненты, сдвинутой во времени на один символ.
Как было показано, вообще суперисточник w-го порядка, соответствующий эргодическому источнику, может быть разбит на п' эргодических компонент, где п' является делителем п. В последующем изложении удобно рассматривать их как п эргодических компонент, где только п' среди них различны. Определим суперисточник i-й фазы
