Теория информации и надежная связь - Галлагер Р.
Скачать (прямая ссылка):
Более того для любого однозначно декодируемого множества кодовых слов
2 D~nh = 2 Ai D~‘,
(3.2.5)
k=l J i=i
(3.2.6)
к
2 D-nkdLnnaxy/L.
A=1
(3.2.7)
3.3. ТЕОРЕМА КОДИРОВАНИЯ ДЛЯ ИСТОЧНИКА
(3.3.1)
п
H(U)
(3.3.2)
log D
66
Доказательство. Покажем вначале справедливость (3.3.2), установив, что
H(U) — nlogD<0. (3.3.3)
Пусть Р (dj), ..., Р (ак)— вероятности букв источника и пусть nlt .... пк — длины кодовых слов. Имеем
H(U)-n\ogD - 2 P(aft) log ——- - 2 Р (ak) nh log D. (3.3.4)
k=l P(ah) *=i
Помещая —nk под знак логарифма и объединяя слагаемые, будем иметь
Н (U) — п log D = 2 Р К) log • (3.3.5)
ft=i P(ah)
Используя неравенство log г < (z — 1) log е при г > О, получаем
2 П~пь~%Р(ак) k= 1 /;= 1
И (U) — п log D (log е)
<0. (3.3.6)
Последнее неравенство в (3.3.6) следует из неравенства Крафта
(3.2.3), которое справедливо для любого однозначно декодируемого кода. Это доказывает (3.3.2). Заметим, что равенство в (3.3.2) имеет место тогда и только тогда, когда
P(ak)=D~nh, (3.3.7)
Это условие совпадает с ранее полученным условием (3.2.2) для каждой кодовой буквы и приводит к максимуму энтропии.
Покажем далее, как выбрать код, удовлетворяющий (3.3.1). Если бы длины кодовых слов не обязательно были целыми числами, то можно было бы просто подобрать tih, чтобы удовлетворить условию (3.3.7). Однако можно приближенно удовлетворить (3.3.7), выбирая целые числа nh так, чтобы удовлетворялись неравенства
Ц~П]1 ^ Р(ah) < Z)_nft+1, 1 (3.3.8)
Суммирование (3.3.8) по k превращает левое неравенство в неравенство Крафта (3.2.3), и существует префиксный код с этими, длинами. Логарифмируя правое неравенство в (3.3:8), получаем
logР (ak) < (— nk + 1) logD, %<~logPn(aft)+ 1. (3.3.9)
log D
Умножая (3.3.9) на P (ah) и суммируя по всем k, получаем (3.3.1), что завершает доказательство теоремы. |
Можно получить более сильные результаты, если кодовые слова приписывать не отдельным буквам источника, а прямо последовательностям L букв источника.
Теорема 3.3.2. Для заданных дискретного источника без памяти U с энтропией Н (U) и кодового алфавита из D символов возможно так приписать кодовые слова последовательностям L букв источника, что 3* 67
будет выполняться свойство префикса и средняя длина кодовых сло^ч на одну букву источника п будет удовлетворять условию
+ —. (3.3.10)
log D log D L
Более того, левое неравенство справедливо для любого однозначно декодируемого множества кодовых слов.
Доказательство. Рассмотрим произведение ансамблей для последовательностей L букв источника. Энтропия произведения ансамблей равна LH (U), а средняя длина кодовых слов равна nL, где п означает среднюю длину на одну букву источника. Теорема 3.3.1 утверждает, что минимально достижимое значение tiL (при сопоставлении кодового слова неравномерного кода каждой последовательности L букв источника) удовлетворяет неравенствам
logD log D
Разделив эти выражения на L, получим результат теоремы. |
Теорема 3.3.2 очень похожа на теорему 3.1.1. Если выбрать L достаточно большим и затем применить закон больших чисел к длинной последовательности, состоящей, в свою очередь, из последовательностей L букв источника, то можно заметить, что из теоремы 3.3.2 следует первая часть теоремы 3.1.1. Однако теорема 3.3.2 немного сильнее, чем теорема 3.1.1, так как она предлагает относительно простой метод кодирования, а также альтернативу случайным ошибкам, а именно случайные длинные задержки.
3.4. ПРОЦЕДУРА ВЫБОРА ОПТИМАЛЬНОГО НЕРАВНОМЕРНОГО КОДА
В этом параграфе будет дана предложенная Д. А. Хаффманом (1952) конструктивная процедура отыскания оптимального множества кодовых слов для кодирования данного множества сообщений. Под оптимальностью будет подразумеваться то, что никакое другое однозначно декодируемое множество кодовых слов не имеет меньшую среднюю длину кодового слова, чем заданное множество. Множество длин, задаваемое (3.3.8), обычно не минимизирует п, даже если на нем достигается граница в теореме 3.3.1. Вначале будут рассмотрены двоичные коды и затем будет дано обобщение на произвольный кодовый алфавит.
Пусть буквы источника а1у ..., ак имеют вероятности Р («j), ..., ..., Р (ак); предположим для простоты обозначений, что буквы упорядочены так, что Р (а^^Р (а2)^ ...^ Р (ак). Пусть хь ..., — мно-
