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

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

Галлагер Р. Теория информации и надежная связь — М.: Советское радио, 1974. — 738 c.
Скачать (прямая ссылка): teoriyainformacii1974.pdf
Предыдущая << 1 .. 27 28 29 30 31 32 < 33 > 34 35 36 37 38 39 .. 355 >> Следующая


Каждая буква ut представляет собой статистически независимую выборку для одного и того же источника и, следовательно, (3.1.2) утверждает, что I (иь) является суммой L независимых одинаково распределенных случайных величин. Так как среднее значение каждой из случайных величин I (ыг) является энтропией источника Н (U), то из закона больших чисел следует, что, если L велико, то I (ul)!L будет с большой вероятностью близко к Н (U):

I (вЛ

-^-«?#(?/). (3.1.3)

Символ «? в равенстве (3.1.3) используется как для того, чтобы показать приближенность равенства, так и для того, чтобы подчеркнуть, что мы не хотим указать точный смысл этого приближения. В начале

56
рассмотрим следствия равенства (3.1.3), а затем возвратимся, чтобы дать необходимые математические уточнения. Из (3.1.3) имеем

— log2 Рг (и/.) да ? LH (U), (3.1.4)

Рг (и/.) да ? 2~LH (иК (3.1.5)

Здесь и до конца этой главы все энтропии будут выражаться в битах, т. е. будут определены логарифмами с основанием 2. Из равенства

(3.1.5) вероятность любой типичной достаточно длинной последовательности источника длины L в некотором смысле приближенно равна 2—lh{U) и> следовательно, число таких типичных последовательностей Мт должно быть приближенно равно

Мт да ? 2LH (UK (3.1.6)

Если требуется сопоставить двоичные кодовые слова всем этим типичным последовательностям, то следует отметить, что имеется 2N различных двоичных последовательностей и, следовательно, требуется, чтобы N было приближенно равно LH (U) для того, чтобы представить все типичные последовательности источника.

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

Как было показано, / (uL) является суммой L независимых одинаково распределенных случайных величин, каждая из которых имеет конечное математическое ожидание И (U). Закон больших чисел*) утверждает при этом, что для любого б > 0 существует такое г (L, б) > > 0, что

Рг

1 (ul)

H(U) > б

; е (l, б)

(3.1.7)

lim е (L, б) = 0.

(3.1.8)

Это означает, что вероятность того, что выборочное среднее / (ul)IL отличается от Н (U) более чем на произвольную фиксированную вели-

** См. задачу 2.4 или какой-либо элементарный учебник по теории вероятностей. Для счетного бесконечного алфавита следует предположить, что H(U) конечна. Предположение конечности дисперсии в задаче 2.4 не является необходимым (см. Феллер (1950), т. 1, гл. 10, § 2).

57
чину б, стремится к нулю при увеличении L. Для некоторых заданных б и L пусть Т — множество последовательностей uL, для которых

Я(?/)(<6; uLer. (3.1.9)

Это множество ранее мы называли множеством типичных последовательностей; из (3.1.7) получаем

Pr (Т) > 1— e(L, б). (3.1.10)

Преобразуя (3.1.9), получаем для uL е Т,

L[H (U)~6\^I(ul)^L[H(U) + 8\, (3.1.11)

2-l[h (U) б] pr (Ui) 2-l [h (u>+a]_ (3.1.12)

Можно ограничить число Mj- последовательностей в Т, заметив, что

1 Pr (71) ^ Мт min Рг (ui).

uLer

Отсюда, используя (3.1.12) в качестве нижней границы Pr (uL) для uL, принадлежащих Т, получаем

Мг<2^я<у>+в1. (3.1.13)

Точно так же, используя (3.1.10), получаем

1 — е (L, 6) ^ Рг (Т) ^ Мт max Pr (uL)

uLer

и, используя (3.1.12) в качестве верхней границы Pr (uL) для nL, принадлежащих Т, находим

Мт > [1 — е (L, б)] 27- Iя (3.1.14)

Неравенства (3.1.12)—(3.1.14) дают точные утверждения, соответствующие (3.1.5) и (3.1.6).

Предположим далее, что требуется закодировать последовательности источника uL в последовательности длины N, представляющие собой кодовые слова с алфавитом из D букв. Будем отображать только одну последовательность источника сообщений в каждую кодовую последовательность, при этом часто будут возникать последовательности из множества последовательностей сообщения, которым не будет сопоставлено никакое кодовое слово. Определим вероятность ошибки Ре как вероятность множества, которому не сопоставлены кодовые слова. Выберем вначале N так, чтобы удовлетворить неравенству
Предыдущая << 1 .. 27 28 29 30 31 32 < 33 > 34 35 36 37 38 39 .. 355 >> Следующая

Реклама

c1c0fc952cf0704ad12d6af2ad3bf47e03017fed

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

c1c0fc952cf0704ad12d6af2ad3bf47e03017fed