<< Предыдущая

стр. 4
(из 50 стр.)

ОГЛАВЛЕНИЕ

Следующая >>

задана в битах, то средняя длина п также выражается в битах, что
прямо указывает на использование двоичного кода.
Теорема кодирования источников указывает на то, что средняя
длина кодового слова не может быть меньше энтропии. Однако, как
будет показано в разделах 5.2 и 5.5, при блоковом кодировании ис-
точников, средняя длина кодового слова может приближаться к эн-
тропии как угодно близко. Это обстоятельство еще раз подчерки-
вает важность понятия энтропии. Энтропия - есть мера минималь-
ных средних затрат. Примером практической реализации неравен-
ства (3.1) является код Хаффмана, рассматриваемый в следующем
разделе.
3.1. Теорема кодирования источников I

Замечание. Доказательство теоремы, 3.1.1 сводится к использо-
ванию неравенства Крафта и не несет в себе каких-либо консщрук-
гпивиых соображений для построения оптимальных, с точки зре-
ния затрат, кодов. Доказательство довольно объемно, но дает хо-
рошее представление о методах теории информации. Тем не менее,
оно может быть пропущено без ущерба для понимания последую-
щих ра,чделов.
Доказательство.
Ш а г 1. Неравенство Крафта.
Для существования однозначно декодируемого D-ичного кода,
содержащего К кодовых слов с длинами П1,П2,.-.,щ, необходимо
и достаточно, чтобы выполнялось неравенство Крафта

к
(3.2)
it=i


Для доказательства этого утверждения воспользуемся кодовой
конструкцией, изображенной на рис. 3.2.
Уровень Число
возможных
О узлов




оконечный узел
(кодовое слово)


Рис. 3.2. Кодовое дерево для D = 2 и п = 4.

Мы видим 3 характерных свойства этой конструкции:

1. Существует D1 узлов г-го порядка (г-го уровня);

2. Каждый узел г-го порядка порождает точно Dn"% п-го уровня;

3. Кодовая конструкция соответствует префиксному коду, т.е. ни-
какое кодовое слово не является началом другого кодового сло-
ва, так как кодовые слова однозначно определяются конечными
узлами.
Глава 3. Кодирование для дискретных источников без памяти

Для простоты упорядочим длины кодовых слов
=
п п n п
1 ^ 2 ^ ''' k (3.3)
-
Теперь начнем отсчет. Кодовое слово с\ длины п\ запрещает в точ-
ности Dn˜ni возможных конечных узлов на последнем п-ом уровне.
Так как кодовые слова префиксного кода не сливаются, в совокуп-
ности получим
К
??>»-»* (3.4)
fc=i
запрещенных узлов на п-ом уровне. Общее число возможных узлов
n
на п-ом уровне равно D , следовательно
К
n nk n
(3.5)
Y^D - <D .
fc=i
n
Разделив обе части неравенства на D , получим неравенство Крафта.

Ш а г 2. Утверждение Мак-Миллана.
Каждый однозначно декодируемый код удовлетворяет неравен-
ству Крафта.
При выводе неравенства Крафта были использованы особенности
префиксных кодов. Но это условие не является необходимым. Как
будет показано далее, необходимым условием является однозначная
декодируемость кода. Возведем сумму в неравенстве Крафта в сте-
пень L
iL
к к к к



Обозначив через Ai число комбинаций, содержащих L кодовых
слов с суммарной длиной г, запишем (3.6) в компактной форме

к
у*
=

где L n m a x максимальная длина сообщения, содержащего L кодо-
вых слов.
Если код является однозначно декодируемый, то все последова-
тельности из L кодовых слов суммарной длины г различны. Так как
имеется всего D1 возможных последовательностей, то

At < Dl (3.8)
3.1. Теорема кодирования источников I 27J

и, таким образом,



5] (3.9)
fc=l J

Извлекая L-ичный корень, получим оценку сверху для суммы в
неравенстве Крафта

К
? > - » * < (?n,max)1/2 (ЗЛО)


для всех натуральных L.
Обсудим значение числа L. Это число независимых кодовых слов,
которые выбираются из {1,2, ...,К} и используются для построе-
ния всех возможных последовательностей длины, не превышающей
L n m a x . Поэтому, при L — оо, мы приходим к неравенству Крафта
>

к
Y,D˜Hk < П М ^ т а х ) 1 ^ = 1- (З.П)
fc=l ˜^°°

Приведенные выше рассуждения справедливы для каждого од-
нозначно декодируемого кода. Поэтому, каждый однозначно декоди-
руемый код удовлетворяет неравенству Крафта.

Ш а г 3.
Запишем левую часть неравенства (3.1) в виде

(3.12)
H(x)-n\ogD<0.

Используя вероятность событий рь и соответствующие длины ко-
довых слов Пк , имеем

к к
= Vpfclog Vpfc7ifclogi3= (3.13)
H(x)-nlogD
fc=l ^ fc=l
nk

Pk


Как и при доказательстве утверждения (2.1), оценим сверху ло-
, 28 Глава 3. Кодирование для дискретных источников без памяти

гарифмическую функцию при помощи (2.19) и получим


YVlog <loge [y^Pk 1I=
f-f V*-f L Pk
Pk \I
(3.14)
nk
= logel ^D' -^\
^ fc=l k=l



к
Здесь было использовано неравенство Крафта и условие ? pjt = 1.
fc=i
Таким образом, левая часть неравенства (3.1) теоремы о кодирова-
нии источников доказана.
Шаг 4.
Правая часть неравенства (3.1)

(ЗЛ5)
logD
При доказательстве используем неравенство Крафта, условие су-
ществования кода с соответствующими длинами кодовых слов п& и
условие 2_,(.=i Pk = 1-
Неравенство Крафта можно записать в виде
к к
D nk
<X>- (3-16)
Y, ˜
fc=i fc=i

Пока имеет силу неравенство Крафта, мы свободны в выборе
длин кодовых слов n/t G Л/*. Выберем для каждого слагаемого та-
кое наименьшее п^, при котором

?Г"* < рк. (3.17)

Неравенство Крафта при таком выборе будет выполняться, сле-
довательно, используя конструкцию рис. 3.2, мы можем построить
такой префиксный код. Так как п/, наименьшее целое, при котором
имеет место (3.17), то для nk — 1 справедливо

рк < D-{nk˜l). (3.18)

Остальная часть доказательства лишь формальна.
3.2. Коды Хаффмана 29)


Используя свойства логарифмической функции, получаем

PfclogPfc < Pit log D˜(nk˜^ = pk(—Пк + l)logi). (3.19)

Суммируя по всем К, имеем
к
(3.20)

-H(X)

Разделив обе части неравенства на \ogD и переставляя члены с
домножением на —1 (что меняет знак неравенства), получаем иско-
мое доказательство. •


3.2. Коды Хаффмана
Коды Хаффмана1 принадлежат к семейству кодов с переменной дли-
ной кодовых слов. Самый известный код неременной длины - азбука
Морзе2 (табл. 3.1). Основная идея азбуки Морзе - передавать часто
встречающиеся буквы кодовыми словами короткой длины и, наобо-
рот, редко встречающиеся буквы длинными кодовыми словами для
того, чтобы минимизировать средние затраты. Такой способ кодиро-
вания называют так же кодированием с минимальной избыточно-
стью или энтропийным кодированием.
Так, например, в азбуке Морзе часто встречающаяся буква «Е»
кодируется одним знаком « » а редкая «X» четырьмя знаками
•,

В 1952 г. Хаффман показал, что предложенное им кодирование
с переменной длиной кодовых слов является оптимальным префикс-
ным кодом для дискретных источников без памяти. То есть, средняя
длина слова кода Хаффмана минимальна и он так же является кодом
без запятой. Термин «код без запятой» означает, что при установ-
ленной синхронизации.возможна непрерывная передача потока сооб-
щений с однозначным декодированием без специального разделения
кодовых слов.
В префиксном коде никакое кодовое слово не является префиксом
другого слова.

Давид Хаффман (1925-1999) - американский ученый.
Самуэль Морзэ (1791-1872) американский художник и изобретатель.
Глава 3. Кодирование для дискретных источников без памяти

Таблица 3.1. Буквы, символы азбуки Морзе и их относи-
тельная частота в немецком литературном
тексте.


Буква
Буква Относитель- Символ Относитель-
Символ
ная частота азбуки ная частота
азбуки
Морзе
Морзе

•• ••
N 0,0992
0,0651
А

<< Предыдущая

стр. 4
(из 50 стр.)

ОГЛАВЛЕНИЕ

Следующая >>