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

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

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


85
Следующая теорема подытоживает полученные результаты.

Теорема 3.6.1. Энтропия на букву марковского источника задается равенством (3.6.21), где 9о,сс)(г) задается (3.6.18), а Н (U\s = i) задается (3.6.9). Если цепь Маркова имеет не больше одного неразложимого множества состояний, то q^, и)(0 не зависит от распределения вероятностей дляй^, и если это неразложимое множество является эрго-дическим, то q^u x)(i) = q (i), где q (i) задается (3.6.5) и (3.6.6).

Исследование неравномерных кодов для источника, проведенное для дискретных стационарных источников, непосредственно применимо к марковским источникам, однако для марковского источника возможны некоторые упрощения. В (3.5.11) среднее число кодовых букв на букву источника для кодирования сразу L букв источника удовлетворяет условию п ^ Нь (U)Hog D. Для того чтобы приблизить п к Нх (C/)/log D, возможно, потребуется взять L довольно большим. Для стационарных эргодических марковских источников будет показано, что, используя информацию о состоянии и кодируя сразу L букв источника, можно получить п, удовлетворяющее неравенствам

\ /осо,ач

------<И<—----------------• (3.6.21а)

log D log D L

Чтобы получить этот результат, используются различные коды для различных начальных состояний. Длина кодового слова, соответствующая последовательности и = щ, ..., иь и sx = /, может быть выбрана, как и в (3.3.6), удовлетворяющей неравенствам

D - П j <О) ^ рг („ | Si =г /) < D -11 j<11 >+1. (3.6.22)

Так же как и в теореме 3.3.1, эти длины удовлетворяют неравенству

Крафта для каждого начального состояния, и средняя длина кодового

слова iijL для данного начального состояния j удовлетворяет неравенствам [Н (t/j ... UL I s-l = /)/logD]<rt;L<[tf {U1...UL\ sx = /)/log D] -f 1.

Усредняя по состояниям, деля на L и используя (3.6.17), полученное неравенство можно свести к (3.6.21 а).

ИТОГИ и выводы

Эта глава преследовала три цели: первая — выяснить смысл энтропии; вторая — получить некоторый навык работы с последовательностями событий и третья — узнать, как закодировать источники, используя минимальное среднее число кодовых букв на букву источника. Мы установили, что энтропию И (U) дискретного источника без памяти можно истолковать в терминах последовательностей L букв источника для больших L. Грубо говоря, Н (U) равна умноженному на 1/L логарифму числа «типичных» последовательностей источника, или минус умноженному на 1/L логарифму вероятности типичной последовательности источника. Энтропия Н (U) равна также минимальному числу кодовых букв на букву источника п, которое требуется для представления выхода источника. Для кода с фиксированной длиной такое п может быть достигнуто только ценой ненулевой (но убывающей вместе с L) вероят-86
ности получения последовательности источника с неоднозначно приписанным кодовым словом. Для неравномерного кода достижение такого п связано с проблемами ожидания в случае, если символы источника поступают на кодирующее устройство с фиксированной скоростью и кодовые символы должны выходить из кодирующего устройства с фиксированной скоростью.

В гл. 9 будет рассмотрена намного более общая задача кодирования для источника, в которой источник не нужно будет воспроизводить точно, а лишь с некоторым заданным критерием верности.

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

Следует помнить, что для большинства реальных источников центральные проблемы не являются теоретико-информационными проблемами представления источника, а состоят в более субъективных проблемах определения, что имеется ценного на выходе источника.

ИСТОРИЧЕСКИЕ ЗАМЕЧАНИЯ И ССЫЛКИ

Другое рассмотрение затронутых здесь вопросов (в особенности, содержащихся в первых четырех параграфах) можно найти у Эбрамсо-на (1963), Фано (1961), Эша (1965) и Шеннона (1948). Теорема кодирования для источника (теорема 3.1.1) была получена Шенноном (1948), который развил большинство концепций этой главы. Шеннон также установил теорему для случая, когда буквы источника имеют неравные длительности и когда источник является марковским. Как указано в тексте, процедура построения оптимального кода, изложенная в §2.4, принадлежит Хаффману (1952). Кодирование для источника, обладающее свойством синхронизации, было изучено Голомбом, Гордоном и Велчем (1958), Кендаллом и Ридом (1962), Истманом (1965), Шоль-цем (1966) и другими.
Предыдущая << 1 .. 41 42 43 44 45 46 < 47 > 48 49 50 51 52 53 .. 355 >> Следующая

Реклама

c1c0fc952cf0704ad12d6af2ad3bf47e03017fed

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

c1c0fc952cf0704ad12d6af2ad3bf47e03017fed