Научная литература
booksshare.net -> Добавить материал -> Физика -> Галлагер Р. -> "Теория информации и надежная связь" -> 44

Теория информации и надежная связь - Галлагер Р.

Галлагер Р. Теория информации и надежная связь — М.: Советское радио, 1974. — 738 c.
Скачать (прямая ссылка): teoriyainformacii1974.pdf
Предыдущая << 1 .. 38 39 40 41 42 43 < 44 > 45 46 47 48 49 50 .. 355 >> Следующая


\у\ = 2 [у]+-у. (3.5.26)

Пользуясь рис. 3.5.1, можно также заметить, что для у ^ 0

у log е

[log у]+<

Из (3.5.26) и (3.5.27) следует, что

. 2 log е

log

Qm (UL)

Р(Ч)

Qm (UL)

РЫ

Qm (ul)

-log

P(UL)

Для выражения, стоящего в правой части в (3.5.28), имеем

Qm (ul)

Р(Ч)

UL

ры

1,

(3.5.27)

(3.5.28)

(3.5.29)

- log = т Нт (U) + (L -m) Н (Um+1 \ Um• • • Ux)~LHl (U).

р (ul)

Подставляя выражения (3.5.28)—(3.5.30) в (3.5.24), получим

(3.5.30)

Рг

у-log Qm К)-----i-l0gP(UL)



<

*> См. (5.4.5) для вывода неравенства Чебышева.

79
Заметим, наконец, что из теоремы 3.5.1 следует, что выражение, стоящее в квадратных скобках в правой части (3.5.31), при L> m стремится к нулю при возрастании пг равномерно по L> пг. Таким образом, для любого фиксированного е правая часть°неравенства будет меньше, чем 8 для достаточно больших пг. |

Доказательство теоремы. Для заданных е> 0, б> О выберем т достаточно большим так, чтобы правая часть (3.5.31) была меньше, чем б для всех L > т, и

| Н (Um+1 \ит... их)~Нх (и) I < е. (3.5.32)

Выберем затем достаточно большое L0>- т так, чтобы для всех L ^ L0

Рг

-logQm(uI) + H(U,n+1\Um...U1)

> е

<6. (3.5.33)

Это возможно сделать на основании леммы 1. Из неравенств (3.5.31)— (3.5.33) для L0 имеем

Рг Г log P(UL)+ #«,(?/) >3ej<2S. (3.5.34)

Для того чтобы увидеть это, следует заметить, что, если не имеют места ни событие в левой части (3.5.31), ни событие в левой части (3.5.33), то тогда не может произойти событие в (3.5.34). Следовательно, вероятность события в (3.5.34) не больше, чем сумма вероятностей событий в (3.5.31) и (3.5.33). В силу произвольности е> 0 и 6> О это эквивалентно (3.5.16), что завершает доказательство теоремы. | Теорема 3.1.1 с заменой Н (U) на Нх (U) доказывается теперь, как и раньше при Н (U), если использовать теорему 3.5.3 вместо (3.1.7).

3.6. МАРКОВСКИЕ источники

Некоторые идеи последнего параграфа могут быть выявлены с особой ясностью, если рассмотреть частный класс источников, называемых марковскими источниками. Эти источники задаются множеством состояний, обозначаемых целыми числами 1, ..., J и алфавитом букв источника, обозначаемым, как обычно, ах, ..., ац. В каждую единицу времени источник производит букву и переходит в новое состояние. Последовательность букв источника обозначается через и = (их, и2, ...), а последовательность состояний — через s = (slt s2, ...).

Пусть Qji обозначает условную вероятность перехода в состояние

i при условии, что задано предыдущее состояние j:

Qn =--= Pr (st = i | sw = /). (3.6.1)

Предположим, что вероятность перехода в состояние зависит только от предыдущего состояния

80
Pr (s, I s,_lt s,_2, ...) = Pr (s, | s^i). (3.6.2)

Случайная последовательность состояний, для которой выполнены

(3.6.1) и (3.6.2), называется конечной однородной цепью Маркова.

Пусть Pj (ah) обозначает вероятность того, что производится буква ak, когда источник находится в состоянии /, и предположим, что эта вероятность зависит только от текущего состояния

рЛак) = Рг [“< = ak I = Л, (3.6.3)

Pr {lit | S;) = Pr (lli | S;, Ы,_!, S,_(3.6.4)

Предположим, наконец, что состояние источника однозначно определяется предыдущим состоянием и предыдущей буквой.

Рис. 3.6.1 иллюстрирует работу марковского источника. Узлы соответствуют состояниям, а направленные ребра соответствуют буквам

а2-//г

Рис. 3.6.1. Марковский источник; на ребрах указаны выход ah и вероятность

Pj(ah).

источника и переходам между состояниями. Каждое ребро, направленное от данного узла, должно соответствовать различным буквам для того, чтобы новое состояние однозначно определялось по предыдущему состоянию и букве.

Состояние марковского источника можно представить себе как тот объект, который определяет влияние истории источника на следующую букву. Так, например, стационарный источник, для которого каждая выходная буква статистически зависит лишь от I предыдущих выходных букв, является марковским источником, состояниями которого являются всевозможные последовательности из I букв. Из этого примера становится ясным, что большинство хороших стационарных источников может быть по крайней мере аппроксимировано марковскими источниками.

Поучительно рассмотреть моделирование английского текста с помощью марковского источника. Шеннон (1948) привел примеры последовательностей, порождаемых такими моделями; в первой из них буквы зависят от одной или двух предыдущих букв, а во второй — слова зависят от предыдущего слова с соответствующим выбором вероятностей.
Предыдущая << 1 .. 38 39 40 41 42 43 < 44 > 45 46 47 48 49 50 .. 355 >> Следующая

Реклама

c1c0fc952cf0704ad12d6af2ad3bf47e03017fed

Есть, чем поделиться? Отправьте
материал
нам
Авторские права © 2009 BooksShare.
Все права защищены.
Rambler's Top100

c1c0fc952cf0704ad12d6af2ad3bf47e03017fed