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

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

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


--------------------h о, (3.5.12)

logD logD

и левое неравенство для п никогда не нарушается для однозначно декодируемого кода.

Доказательство. Доказательство (3.5.11) аналогично доказательству соответствующего условия в теореме 3.3.2, за исключением того, что энтропия последовательности L букв источника равна LHb (U), а не LH (U). При переходе к пределу в (3.5.11) при L —>- оо Нь ((]) стремится к Н^ (U) и ML стремится к 0, что доказывает (3.5.12) .|

При рассмотрении дискретных источников без памяти наш интерес к п был обусловлен законом больших чисел, который показывает, что число кодовых букв на букву источника в длинной последовательности кодовых слов стремится к п. Следующий пример показывает, что это предельное поведение не обязательно имеет место для произвольных дискретных стационарных источников. Предположим, что источник с алфавитом (аи а2, а3) имеет два типа поведения, каждый из которых происходит с вероятностью х/2. При первом типе источник производит бесконечную последовательность повторений а±. При втором типе источник производит бесконечную последовательность статистически независимых равновероятных выборок букв а2 и а?„ Если закодировать последовательности L букв источника двоичным кодом, то легко увидеть, что п минимизируется отображением последовательности букв ах в один-единственный двоичный символ и отображением каждой из 2L последовательностей букв а.2 и а3 в кодовые слова длины L + 1. Так как тип поведения источника никогда не меняется, то либо все кодовые слова последовательности будут иметь длину 1 либо все будут иметь длину L + 1. Для таких источников ни п, ни энтропия не являются величинами, которые играют значительную роль.

Источники, которые не могут иметь различные устойчивые типы поведения, называются эргодическими источниками. Для того чтобы определить эргодичность более точно, предположим, что u=..., и_ь и0, «1, ... ¦— бесконечная последовательность букв источника п пусть Т1 и обозначает последовательность, сдвинутую по Бремени па / позиций. Т. е. если обозначить Т1 и через и', то имеем

1п + 1’

¦ 00< П

Аналогично, если S — множество бесконечных последовательностей букв источника, то TlS обозначает то же самое множество, сдвинутое на I позиций, т. е. если u' = Т1 и, то и' принадлежит множеству TlS тогда и только тогда, когда и принадлежит S. Множество последовательностей называется инвариантным, если TS = S. Легко можно заметить, что множество всех последовательностей дискретного источ-
ника инвариантно, а также то, что для любого и множество ..., Т~хи,

и, Тм, Т2и, ... инвариантно. Дискретный стационарный источник называется эргодическим, если любое измеримое инвариантное множество последовательностей имеет либо вероятность 1 либо вероятность 0. Можно заметить, что в предыдущем примере множества последовательностей в каждом из описанных типов поведений были инвариантными множествами и вероятности каждого из них были равны V2. Следовательно, этот источник не был эргодическим.

Хотя приведенное выше определение является весьма изящным, с ним иногда довольно трудно работать, и оно не дает интуитивного понимания эргодичности. Следующее определение эквивалентно данному ранее. Пусть fn (и) является функцией бесконечной последовательности источника и, которая зависит только от конечной последовательности и1} ..., и„ букв источника. Дискретный стационарный источник является эргодическим тогда и только тогда, когда для всех п ^ 1 и всех fn (и), для которых | fn (и) ] < оо, имеет место соотношение

для всех последовательностей источника и, за исключением множества вероятности 0. Класс функций в этом определении может быть расширен до всех измеримых функций / (и), для которых |/ (и) | < оо, или может быть сужен до частного класса функций /Ц)' (и), где и,'г — фиксированная последовательность и\, ..., и’п букв и

Доказательство эквивалентности этих определений эргодичности содержится у Хинчина (1956); Вольфовиц (1961), лемма 10.3.1, рассмотрел другое определение и доказал его эквивалентность приведенным здесь.

Определение (3.5.13) особенно важно, так как оно касается свойства эргодических источников, которое нам понадобится в дальнейшем. Соотношение (3.5.13) означает, что закон больших чисел применим к эргодическим источникам. Иначе это можно выразить как среднее по времени, т. е. усреднение по времени по какой-нибудь выборке выхода источника (исключение составляет множество нулевой вероятности), равно среднему по ансамблю fn (и). Так как /„' (и) просто равно вероятности последовательности u/t, то (3.5.14) утверждает, что относительная частота появления и'п в очень длинной последовательности источника будет приближенно равна вероятности мп.

К сожалению, свойства эргодичности не хватает для того, чтобы число кодовых букв на букву источника в неравномерном коде стремилось к п. Если кодировать сразу L букв источника и если через п (и1г ..., uL) обозначить длину кодового слова, то среднее по времени число
Предыдущая << 1 .. 36 37 38 39 40 41 < 42 > 43 44 45 46 47 48 .. 355 >> Следующая

Реклама

c1c0fc952cf0704ad12d6af2ad3bf47e03017fed

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

c1c0fc952cf0704ad12d6af2ad3bf47e03017fed