Духин А.А. Теория информации

Подождите немного. Документ загружается.

ГЛАВА ТРЕТЬЯ

ОПТИМАЛЬНОЕ

КОДИРОВАНИЕ

§1

Рассмотрим схему передачи информации от источника сообщений к

адресату в той ее части, в которой информация, порожденная источником,

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

Источник

Кодер

Источник

источника

JkJ2'

Рис. 1.1

Для того чтобы эффективнее, экономичнее использовать канал связи, сле-

дует так преобразовать порождённую информацию, чтобы на её передачу по

каналу затрачивалось минимально возможное время. Такое преобразование

информации называют кодированием источников сообщений. В настоящее

время задача кодирования получила исчерпывающее решение для источников

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

Наряду с алфавитом А = (a

..,a

), |А| = п источника [A,p(s)] будем рас-

сматривать алфавит B = (b

..,b

|B|

= D кодера для источника. Кодирова-

нием будем называть отображение cpraj -> щ =(Ь^

..,bj

где a

кодовое слово. При этом естественно предполагать, что если а^а^ то

Sj^aj.

Совокупность всех кодовых слов {a

..,a

} называют кодом. Код

называется равномерным или блоковым, если длины всех кодовых слов

одинаковы, и неравномерным - в противном случае. Код называется

однозначно декодируемым или разделимым, если существует метод одноз-

начного разделения на отдельные кодовые слова а^ ,—>

^ последовательности

букв алфавита В, полученной на входе декодера. Рассмотрим некоторое

кодовое слово а

=Ь^ ,.->Ь^. Начальная часть слова Ь^,..,,Ь^; i =

l,...,l

называется префиксом слова а

. Говорят, что код {a

..,a

} является

префиксным, если никакое кодовое слово не совпадает с началом другого

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

Преимущество префиксных кодов заключается в том, что для них декоди-

рование может осуществляться без задержек в ходе поступления букв

алфавита В в декодер.

ОСНОВНЫЕ

ПОНЯТИЯ И ОПРЕДЕЛЕНИЯ

§ 1. ОСНОВНЫЕ ПОНЯТИЯ И ОПРЕДЕЛЕНИЯ

Для определения однозначной декодируемости неравномерного кода сущест-

вует простой способ. Рассмотрим всевозможные пары кодовых слов, в кото-

рых одно слово является префиксом другого. Если таких пар нет, то в силу

вышеизложенного код является префиксным, а следовательно, однозначно де-

кодируемым. Для каждой такой пары найдём "повисший" суффикс, который

остается после удаления префиксного слова из начальной части более длинно-

го слова. Выпишем все повисшие суффиксы. Далее проделаем то же самое

для каждой пары слов, состоящей из повисшего суффикса и кодового слова, в

которой одно слово является префиксом другого. Выпишем все новые повис-

шие суффиксы, которые при этом получатся, и т.д. Будем продолжать этот

процесс до тех пор, пока не появятся новые суффиксы. Код является одноз-

начно декодируемым тогда и только тогда, когда никакой суффикс не совпа-

дает ни с одним кодовым словом.

Для построения префиксных кодов и описания их свойств используем удоб-

ное графическое представление таких кодов, применяя хорошо известные гра-

фы без петель и контуров, то есть D-чные графы-деревья. Для всякой проме-

жуточной

вершины дерева выходящим из неё ребром приписывает буквы ал-

фавита В от 0 до D

-1.

Определение

1.1. D-чный граф-дерево с метками-буквами алфави-

та В, приписанными его рёбрами, называется

кодовым деревом.

Каждой вершине соответствует единственный путь, ведущий в нее от корня

дерева. Вершине сопоставляется слово, составленное из меток, приписанных

ребрам, лежащим на пути. Если D-чное слово *£

является началом D-чного

слова а

, то вершина аГ]

лежит на пути, ведущем от корня в вершину а

Отсюда следует, что концевые вершины образуют префиксный код и,

наоборот, всякому префиксному коду соответствует некоторая совокупность

концевых вершин.

Корень дерева называют вершиной нулевого порядка. Ребра, выходящие из

него,

заканчиваются вершинами первого порядка. Их может быть не более D

штук. Ребра, выходящие из них, заканчиваются вершинами второго порядка.

Вершин второго порядка может быть не более D

штук и т. д.

Вершины

кодовые

слова

будем

обозначать

одним

символом.

ГЛАВА

III.

ОПТИМАЛЬНОЕ

КОДИРОВАНИЕ

Определение

1.2. Кодовое дерево называется полным, если из

каждой его промежуточной вершины выходит в

точности D рёбер. Совокупность всех концевых

вершин полного кодового дерева называется

полным множеством концевых вершин.

Нетрудно видеть, что минимальное число концевых вершин полного кодово-

го дерева, имеющего п уровней, равно n(D-l) + l.

Характеристикой сжатия сообщений при побуквенном кодировании служит

среднее число кодовых букв из алфавита В, приходящихся на одну букву

сообщения, порождённого источником.

Определение

1.3. Средней длиной кодового слова называется

величина:

ср

5^p(aj)^j,

где £

- длина кодового

i=i

слова а

(3.1.1)

Для равномерного, блокового кода понятие средней длины становится три-

виальным, так как не зависит от вероятностного распределения p(s) и совпа-

дает с длиной блока. Иное дело получается, когда рассматривается неравно-

мерный код, для которого величина £

ср

меняется в зависимости от выбора

длины кодовых слов. Очевидно, что если более вероятным буквам, порождён-

ным источником, ставить в соответствие короткие кодовые слова, то при этом

будем получать уменьшение средней длины.

Определение

1.4. Однозначно декодируемый код {a

...,a

} назы-

вается оптимальным, если он обладает

минимально возможной средней длиной в

множестве всех кодов, построенных для

данного источника.

Другими словами оптимальное кодирование приводит к максимальному уп-

лотнению, сжатию информации. В настоящей главе рассмотрены способы по-

строения однозначно декодируемых, оптимальных кодов, изучены вопросы о

возможном сжатии информации при кодировании.

§ 1.

ОСНОВНЫЕ

ПОНЯТИЯ

И ОПРЕДЕЛЕНИЯ

Лемма 1.1. Число концевых вершин полного кодового дерева равно

D + m(D-l), где meN.

Доказательство. Полное дерево, имеющее один уровень, содержит D кон-

цевых вершин. Если одну из концевых вершин превратить в промежуточную

вершину, то образуется D новых концевых и одна концевая вершина теряет-

ся.

В результате получаем приращение D-1 вершин. Так как любое полное

дерево может быть построено с помощью таких последовательных преобразо-

ваний концевых вершин в промежуточные вершины и так как каждое такое

преобразование концевой вершины увеличивает число концевых вершин на

D-1,

то окончательное число вершин должно иметь вид

+ m(D-l). А

Рассмотрим кодовое дерево, максимальный порядок концевых вершин кото-

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

шина b (n-l)-ro порядка, из которой выходит единственное ребро, ведущее

в а. Других рёбер из неё не выходит. Операцию удаления этого ребра и прев-

ращения промежуточной вершины b (n-l)-ro порядка в концевую вершину

будем называть операцией усечения. Средняя кодовая длина после операции

усечения становится меньше.

Наконец, приведём необходимые и достаточные условия того, что набор чи-

сел

.„

е N задает множество длин кодовых слов некоторого префиксного

кода.

Теорема 1.1 (Неравенство Л. Крафта). Пусть ^,<

,.»^

" набор нату-

ральных чисел. Для того чтобы существовал префиксный

код с длинами кодовых слов

...,£

необходимо и доста-

точно, чтобы выполнилось неравенство

(3.1-2)

i=l

Необходимость. Пусть существует префиксный код {a

..,a

} с длинами

кодовых слов

{

,...,£

. В качестве кодовых слов

..,a

можем рассматри-

вать концевые вершины дерева. Покажем, что для чисел £

,...

выполняет-

ся неравенство (3.1.2). Из каждой промежуточной вершины дерева исходит не

более D рёбер. Отсюда следует, что может быть не более D* вершин порядка

t Пусть t> тах(££

). Такое число вершин получается тогда, когда D рё-

ГЛАВА

III.

ОПТИМАЛЬНОЕ

КОДИРОВАНИЕ

бер выходят из каждой промежуточной вершины порядка, меньшего, чем t С

другой стороны, наличие концевой вершины порядка

исключает D

возможных вершин порядка t. Так как общее число исключенных вершин не

должно превосходить общего числа концевых вершин порядка t, то это

соответствует неравенству

к=1

Деля обе части неравенства на В \ получаем (3.1.2), что и доказывает необ-

ходимость условий теоремы.

Достаточность. Пусть выполнено неравенство (3.1.2). Нужно показать, что

кодовое дерево с концевыми вершинами порядков £

1У

...,£

может быть факти-

чески построено.

Предположим, набор £

...,£

упорядочен по возрастанию, то есть

<£

k+l

k = l,...,n-l.

Доказательство проведём индукцией по максимальному порядку концевой

вершины.

Предположим, что построено кодовое дерево, содержащее все заданные кон-

цевые вершины порядка, меньшего т. Пусть имеется w

чисел £

, равных m

в наборе £

,...,(

. Нужно построить дерево, содержащее w

концевых вер-

шин порядка т. Можем ли мы найти необходимое число свободных концевых

вершин ? Перепишем неравенство (3.1.2), выделив слагаемые, отвечающие

числам £

, равным т.

XD-

D-

5>-^<1,

(3-1-2)'

k=l k=j+w

здесь j - число концевых вершин порядка, меньшего, чем т.

Выделим в неравенстве (3.1.20 величину w

-]TD

-^ - JTD

(

)

k=l k=j+w

Следовательно, число концевых вершин порядка m ограничено сверху вели-

чиной, стоящей в правой части неравенства (3.1.3). С другой стороны, число

доступных вершин порядка m равно D

за вычетом числа вершин, исключён-

ных из-за наличия концевых узлов меньшего порядка, то есть:

k=l

§ 1.

ОСНОВНЫЕ

ПОНЯТИЯ

И ОПРЕДЕЛЕНИЯ

Отсюда следует, что число доступных возможных вершин порядка га не ме-

нее заданного числа концевых вершин того же порядка, а потому они все мо-

гут быть включены в дерево. Поскольку это справедливо для всех целых ш, то

отсюда следует, что дерево с требуемыми концевыми вершинами всегда может

быть

построено шаг за шагом, если только для порядков вершин выполнено

неравенство (3.1.2). А

Заметим, что теорема не утверждает, что любой код с длинами кодовых

слов,

удовлетворяющими (3.1.2), является префиксным. Например, множество

двоичных кодовых слов 0,01,11 удовлетворяет неравенству (3.1.2), но не об-

ладает свойством префикса.

заключение отметим, что равенство

£D-'"=I

14)

к=1

является необходимым и достаточным условием того, чтобы заданное множест-

во концевых вершин было полным.

ГЛАВА

III. ОПТИМАЛЬНОЕ КОДИРОВАНИЕ

В этом параграфе сформулированы необходимые определения и понятия

для построения кодов, осуществляющих сжатие информации. В дальнейшем, в

главе III основной исходной посылкой при построении таких кодов является

неизменность вероятностных распределений на алфавите источника без

памяти.

§2

Рассмотрим методы построения двоичных префиксных кодов, которые

в ря-

де случаев приводят

кодам

минимально возможной средней длиной

ср

Достижение нижней границы всегда происходит

в тех

случаях, когда вероят-

ностное распределение

p(s) на

алфавите

источника [A,p(s)] задаётся

на-

бором отрицательных степеней двойки. Для произвольных распределений

p(s)

существуют методы кодирования,

помощью которых можно строить

префиксные коды

минимальной средней длиной. Этому вопросу будет

по-

священ следующий параграф. Достоинством предлагаемых методов является

простота

их

реализации.

Первый метод

(Метод

Р.

Фано). Алгоритм сводится

последовательному

выполнению следующих шагов:

Буквы алфавита

упорядочиваем

по

убыванию вероятностей:

р(а

)>р(а

)^...^р(а„).

Множество упорядоченных букв разбивается

на два

подмножества А

(0)

,А

(5)

с помощью некоторого порогового целого числа

£ k

(1)

-1 так,

чтобы

величина

к<*>

(l)

=2>i)-

5>i>

(3.2.1)

i-i

О)

достигала наименьшего возможного значения. Буквам

из

подмножества

приписываем

буквам подмножества А*

* приписываем

Если подгруппы состоят более чем из двух букв,

то

разбиваем мно-

жество букв каждой

из

подгрупп

на

две подгруппы

(00)

,А

(0,)

(10)

,А

(П

соответственно,

помощью пороговых целых чисел

l£k

(I,)

£k

(l)

-1,

(1)

(,2)

-1

так, чтобы величины

Uii)

<и>

К<

1=1

£ p(*i)- Zp(ai)|

=k(

)

i=k(

(3.2.2)

(3.2.3)

достигали наименьших возможных значений. Буквам

из

подгрупп

(00)

,А

(10)

с нулевыми последними индексами приписываем

буквам

из

подгрупп

д<01)д(Ц)

приписываем 1.

ПРОСТЕЙШИЕ МЕТОДЫ ПОСТРОЕНИЯ ПРЕФИКСНЫХ КОДОВ

ГЛАВА

III.

100

ОПТИМАЛЬНОЕ

КОДИРОВАНИЕ

Если подгруппа A*

'** iJ =

ОД

состоит более чем из одной буквы, то пе-

реходим к шагу 4. Если все подгруппы состоят из одной буквы, то перехо-

дим к шагу 5.

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

каждую из них на две подгруппы, исходя из соотношения, аналогичного

(3.2.1).

Буквам подгрупп с нулевыми последними индексами приписываем

нуль,

буквам подгрупп с единичными последними индексами приписываем

единицу.

Если все образовавшиеся подгруппы состоят из одной буквы, то перехо-

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

то повторяем шаг 4.

Если образовавшиеся подгруппы состоят из одной буквы, то последователь-

но,

начиная с первой метки, выписываем нули и единицы, относящиеся к

каждой букве алфавита А.

В итоге получается двоичный префиксный код для заданного источника

[A,p(s)].

Рассмотрим следующий пример:

р(ч)

0.36

0.18

«3 0.18

0.12

5 0.09

0.07

(

) О

А(

) О

№\ 1

(m)fl

А<

Ш0

Ь А<

1Ш

) 1

Средняя длина для построенного кода £

ср

= 2,44. Соответствующее кодовое

дерево имеет вид:

а«

о\