Теория информации и надежная связь - Галлагер Р.
Скачать (прямая ссылка):
N logD > L [Н (U) + б]. (3.1.15)
Тогда из (3.1.13) следует, что общее число кодовых слов DN больше, чем Мт и можно сопоставить кодовые слова всем uL, принадлежащим Т. Используя этот метод, получаем
7>e<e(Z,, б). (3.1.16)
58
Если теперь считать, что L достаточно велико и, одновременно увеличивая N, удовлетворить NIL ^ [Я (U) + 6]/logD, то можно увидеть из (3.1.8) и (3.1.16), что Ре стремится к 0 при любом б > 0. Покажем теперь, что, если NIL фиксировать равным любому числу, меньшему Я (U)llogD, то вероятность ошибки должна стремиться к 1 при L, стремящемся к оо. Выберем теперь N так, чтобы
N log D < I [Я (U) — 26]. (3.1.17)
Таким образом, число кодовых слов DN ие больше чем 2L^H^U'>~26^. Так как любая последовательность иь из 'Г имеет вероятность, не большую чем 2~LlH(u)—6J, то полная вероятность последовательностей, принадлежащих Г, которым можно сопоставить кодовые слова, не больше чем 2_z-[/f(c/)-6] . 2LtH(u)~263 = 2~L6. Можно было бы также сопоставить кодовые слова некоторым последовательностям источника, не принадлежащим множеству Т, в частности тем, которые имеют большую вероятность. Вместе с тем общая вероятность последовательностей, не принадлежащих Т, не больше е (L, 6). Следовательно, вероятность множества всех последовательностей, принадлежащих и не принадлежащих Т, которым могут быть сопоставлены кодовые слова, ограничена сверху в случае, если удовлетворяется (3.1.7), следующим образом:
l-Pe<s(L,6) + 2-L6. (3.1.18)
Таким образом, если L -> оо, a NIL < [Я (U)—25]/log D, то Ре должна стремиться к 1 при любом 6 > 0. Можно подытожить эти результаты следующей фундаментальной теоремой.
Теорема 3.1.1. (Теорема кодирования для источника.) Пусть дискретный источник без памяти имеет конечную энтропию Я (U). Рассмотрим кодирование последовательностей из L букв источника в последовательности из N кодовых букв, принадлежащих кодовому алфавиту объема D. Каждой кодовой последовательности может быть сопоставлена только одна последовательность источника. Пусть Р е — вероятность появления последовательности источника, которой не сопоставлена никакая кодовая последовательность. Тогда, если при каком-либо 6 > 0
NIL > [Я (U) + 6]/iog D, (3.1.19)
то Ре можно сделать произвольно малой, выбирая L достаточно большим. Обратно, если
NIL < [Я (U) — 6]/log D, (3.1.20)
то Р е становится сколь угодно близкой к 1, когда L становится достаточно большим.
Теореме 3.1.1 можно дать очень простое и полезное эвристическое толкование. Так как кодовые слова дают попросту другое представление вероятных последовательностей источника, то они должны иметь в точности такую же энтропию, как последовательности источника.
59
Кроме того, как было показано в гл. 2, log D представляет собой наибольшую энтропию на одну букву, которой может обладать последовательность букв алфавита объема D; такая энтропия возникает, когда буквы равновероятны и статистически независимы. Теорема 3.1.1 утверждает, таким образом, что можно закодировать буквы произвольного дискретного источника без памяти так, что энтропия кодовых букв будет, по существу, максимальной.
В интерпретации этой теоремы можно представлять себе L как общее число сообщений, которые выходят из источника во время его работы, и представлять себе N как общее число кодовых букв, которые мы пожелали использовать для представления источника. Затем любой метод може быть использован для кодирования и теорема утверждает, что Н (U)/\ogD является наименьшим числом кодовых букв на одну букву источника, которые можно использовать, чтобы все еще представлять источник с высокой вероятностью. То, что такое кодирование последовательностей фиксированной длины в последовательности фиксированной длины при очень больших длинах является довольно непрактичным, несущественно для рассматриваемого общего толкования.
3.2. НЕРАВНОМЕРНЫЕ КОДОВЫЕ СЛОВА
Предположим, что дискретный источник без памяти U имеет алфавит из К букв alt ак с вероятностями Р (аг), ..., Р (ак). Каждая буква источника должна быть представлена кодовым словом, состоящим из последовательности букв, принадлежащих заданному кодовому алфавиту. Обозначим через D число различных символов в кодовом алфавите, а через nh—число букв в кодовом слове, соответствующем ак. Позднее будут рассмотрены буквы источника, являющиеся последовательностями букв более простого источника,и, таким образом, мы получим существенное обобщение описанной выше ситуации.
В дальнейшем мы будем главным образом интересоваться величиной п — средним числом кодовых букв на одну букву источника:
n='EP{ak)nk. (3.2.1)
k= i
