681_Trofimov_V.K._Teoremy_kodirovanija_neravnoznachnymi_

3.3.Оценка стоимости кодирования известного источника неравнозначными символами

Теорема 3.3.1. Для кодирования o , p : X N Y * , где

log p wi l o , p wi t ** log 0 .

Умножая на p wi , суммируя по всем словам источника и последовательно

преобразуя, получим

Из последнего неравенства с учетом (1.7) и (1.8) для бернуллиевских и марков-

ских источников получаем утверждение теоремы:

Теорема доказана.

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

стремится к 0 с ростом длины кодируемого блока N.

4.Универсальное кодирование бернуллиевских источников буквами кодового алфавита с неравными длительностями

Приведенные выше методы кодирования строились на знании информа-

ции об источнике. А именно, эффективность данных методов достигалась за

счет того, что вероятности появления сообщений источника были известны.

В большинстве реальных ситуаций информация об источнике не дана, но

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

белого изображения. Очевидно, что, например, для любой страницы текста,

разбитой на точки, существует зависимость между цветом точек ''по-

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

Рассмотрим ситуацию, когда закон распределения вероятностей для ис-

точника информации заранее не известен. В этом случае необходим некоторый

метод универсального кодирования, т.е. кодирования, не зависящего от кон-

кретного источника и подходящего для всех источников определенного класса.

Универсальное кодирование впервые рассматривалось в работах

[2, 14, 23, 24, 50]. В [23] дано определение универсального кодирования как ко-

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

42

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

полняется

Определение 4.1. Универсальное кодирование произвольного источника сообщений – это кодирование, не зависящее от закона распределения вероятно-

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

ности (1.15).

Определение 4.2. Избыточность универсального кодирования – это наибольшая разность между стоимостью наилучшего кодирования на букву сообщения источника и отношением энтропии источника к пропускной спо-

собности канала:

Yinf sup r N, , 0, tY .

Вчастности, если Ω содержит единственный источник Θ, то мы имеем дело с известным источником.

4.1.Схема кодирования множества бернуллиевских источников буквами кодового алфавита с неравными длительностями

Рассмотрим 0 – множество всех бернуллиевских источников с алфави-

Это верно для любого закона распределения вероятностей. Энтропия H

бернуллиевского источника Θ [28] определяется равенством (1.5).

43

Пусть 0 – произвольное множество бернуллиевских источников. Из основной теоремы К. Шеннона [28] следует, что избыточность универсального

R N, , t1 , 0 , стремятся к нулю.

Избыточность кодирования известного источника при равных длительно-

стях кодовых символов достигает своего минимума при кодировании методом Д. Хаффмана [1, 4]. Однако этот метод не позволяет априори оценить, какой избыточности можно достигнуть при его применении.

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

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

алфавита с равными длительностями оценку вида

где 0 . Таким образом, установлено, что код Шеннона при кодировании блоков близок к оптимальному.

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

[2] и [23]. В частности, в [23] установлено, что величина R N, 0 , t1 с ростом N

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

сального кодирования множества бернуллиевских источников символами алфа-

вита с равными длительностями получено Р. Е. Кричевским [3]. А именно, им доказано, что

44

Из неравенств (4.2), (4.3) и (4.4) вытекает, что множитель log N являет-

ся «платой» за незнание источника. Так как log N растет медленнее, чем N ,

где 0 сколь угодно мало, то эту «плату» можно считать приемлемой.

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

вита имеет свою специфику. В частности, до настоящего времени не существу-

ет алгоритма построения оптимального кода при tY t1 , поэтому получение оценок избыточности кодирования известного бернуллиевского источника символами неравнозначного алфавита и избыточности универсального кодиро-

вания множества бернуллиевских источников символами неравнозначного ал-

фавита приобретает особое значение. При получении хороших оценок для

R N, , tY и R N, 0 , tY можно говорить если не об оптимальных кодах, то по

крайней мере о близких к оптимальным.

В работах И. Чисара [25] и И. Катоны [46] для известного источника ин-

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

венствам

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

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

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

ности R N, 0 , tY кодирования блоков длины N, порожденных неизвестным

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

Максимальное значение функции (4.9) как функции (k-1) аргумента p (xi ) до-

Логарифмируя и преобразуя последнее неравенство, получим соотношение

С учетом ограничений в (4.12) на величину (z) неравенство принимает вид:

Из последнего неравенства следует утверждение леммы.

Лемма доказана.

Из леммы 4.1.1. вытекает следующая лемма.

Лемма 4.1.2. (оценка информационной дивергенции распределения

источника и КТ-распределения). Для бернуллиевского источника с алфави-

Доказательство.

По определению информационной дивергенции (1.9),