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

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

§4

В параграфе излагаются результаты возможности сжатия информации

при

кодировании.

теореме

кодировании источников

без

памяти приводится

нижняя граница

для

средней длины кодового слова

при

кодировании отдель-

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

ней границы средней длиной кодового слова.

Теорема

4.1.

Рассматривается источник

без

памяти

энтропией Ноо.

Возможно

так

закодировать буквы, порождённые

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

ного

алфавите

В, что

среднее число символов

на

букву

ср

удовлетворяет неравенству:

°0

^ £

logD

ср

logD

где D

|B|.

(3.4.1)

Вывод нижней границы. Согласно определению

ср

Zp(

kKk

'к ~~

ддина

к-го

кодового слова префиксного кода. Обозначим

= D"

Логариф-

мируя, получим: £

logD = -logq

. Подсчитаем разность:

H(A)-£

/ogD

= £

k=l

p(a

)tog

k).

(3.4.2)

Воспользуемся неравенством

Inx

-1,

справедливым

для x > 0.

H(A)-V^D^EPK)

k=l

loge =

.k=l

loge. (3.4.3)

Так

как для

целых чисел

...

справедливо неравенство Крафта

то по-

лучаем нижнюю границу

для £

ср

См. теорему

3.1.1.

ТЕОРЕМЫ

КОДИРОВАНИИ ИСТОЧНИКОВ СООБЩЕНИЙ

112

ГЛАВА

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

Лемма 4.1. Для существования префиксного кода со средней длиной

гп

= —— необходимо и достаточно, чтобы для каждой

ср

logD

буквы а

е А выполнялось условие:

I(a

) -fogp(a

)

IogD logD

' (3-4.4)

где С

G N .

Если это условие выполнено, то длина £

кодового слова,

соответствующего букве а

, равна:

-1<*к>

к==1 п

logD' (3.4.5)

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

слов

4?для

средней длины £

ср

которого выполняется:

/ =

°°

ср

logD'

Требуется доказать, что величины , k =

..,n

есть целые числа.

logD

Неравенство (3.4.3) обращается в равенство, когда неравенство

1пх

х -1

обращается в равенство. Это возможно при х = 1. В нашем случае должно вы-

полняться =1, к =

1,...,п,

что равносильно D~^

= р

. Логарифмируя

Р(

к)

это соотношение, получаем:

Z*®£k),

к = 1

,...,„. (3.4.6)

logD

Так как величины £

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

-fogp(ab)

ла Сь = ——— являются натуральными, что и доказывает

logD

необходимость.

Достаточность. Пусть для каждого к =

1,...,п

величины:

I(a

)^-/ogp(a

)

= c

logD logD

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

ный код, обладающий свойством

~ср

logD

113

Преобразуем выражение = С

p(a

) = D"

\ k =

l,...,n.

Суммируя по к, получаем:

к=1

Согласно неравенству Крафта

существует префиксный код с длинами слов

с,,...,с

, для средней длины которого выполняется:

k=1 k=l

Вывод

верхней границы.

Вообще говоря, величина

не

является нату-

logD

ральным числом. Лемма 3.4.1 указывает на возможность выбора £*ь букв ал-

фавита В для построения кодового слова, соответствующего букве а

, рав-

таь

чГ

ного

К«к)

logD

Поэтому рассмотрим множество п целых чисел £

к,

определяемых из соот-

ношения:

logD logD (3.4.7)

Числа £,,...,£„ удовлетворяют неравенству Крафта, так как D~'

= p(a

), а

£о-^=£р(а

)

= 1.

к=1 к=1

Числа также удовлетворяют неравенству Крафта

5>-*<1.

Следовательно, множество кодовых слов с длинами

£*\,...,£*

может быть

фактически построено. Средняя длина кодового слова в построенном коде

удовлетворяет неравенствам, полученным из неравенства (3.4.7) усреднением

по

алфавиту А. А

См.

теорему

3.1.1.

§ 4. ТЕОРЕМЫ О КОДИРОВАНИИ ИСТОЧНИКОВ

СООБЩЕНИЙ

114

ГЛАВА

III.

ОПТИМАЛЬНОЕ

КОДИРОВАНИЕ

Доказанная теорема 3.4.1 позволяет привести интерпретацию энтропии ис-

точника . В случае |в| - 2, согласно теореме, среднее число двоичных сим-

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

ком, не меньше энтропии источника и не превосходит эту энтропию более чем

на единицу.

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

рождённых источником, a m-грамм с соответствующим вероятностным расп-

ределением, среднее число символов кодового алфавита В, приходящихся на

одну кодируемую букву, будет не более средней длины кодового слова. Ра-

венство достигается в случае выполнения условий леммы

3.4.1.

Подойдём к

этому вопросу, введя соответствующие определения.

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

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

ковского источника

[A,P(S)]

С энтропией Н^. Пусть =(a

ilV

..,a^) последо-

вательность, полученная на рассматриваемом источнике. Обозначим а(с^)

длину соответствующего кодового слова.

Определение4.1.

Коэффициентом сжатия последова-

тельности длины I назовем величину

где р(с^) - вероятность последовательности

с,.При*

= 1,

(3.4.8)

Определение 4.2. Величина

ц = lim \x

коэффициентом сжатия кода.

= lim \х

, называется

(3.4.9)

Докажем фундаментальную теорему А.Я.Хинчина

, в которой выводится

нижняя грань возможного "сжатия" информации при кодировании, исполь-

зующем вероятностное распределение р(?) на алфавите источника [А,р(?)].

Значение теоремы состоит в том, что, согласно ей, для любого возможного

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

чем —™.

logD

См.

Библиографию

[68]

115

Для простоты доказательства будем полагать

|А|

|В|

= D.

Теорема 4.2.

Точная нижняя грань коэффициента сжатия \i по всем воз-

можным однозначно декодируемым кодам равна

logD

, гое

энтропия источника.

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

Доказательство теоремы разобьём на два этапа.

Покажем, что для произвольного кода

logD

Зададимся величиной г| > О

и рассмотрим произвольный код. Обозначим величину - 2ц = Н'. Назо-

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

особой, если

logD

Оценим сверху число особых последовательностей длины £, получен-

ных на источнике [A,p(s)]. не превосходит величины

т> <D+D

+ ...+D'

н'

JogU _

JogD ,

D D

/OI

(3.4.10)

D-1

где a >

- основание логарифмов.

Положим 0 < e < 1. Согласно второй теореме Шеннона

(2.2.2)

можно

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

|МДе)|,

где МДе) - класс наиболее вероятных последовательностей

(

, определяемый уровнем е. При этом:

*!EbW|.H..

£->оо £

Равенство

(3.4.11)

равносильно выполнению неравенства:

|/0g|M

(8)|-fflJ<4.

при ( > £

(р). Следовательно, для указанных

> £

(ц):

iM^a^^W^).

(3.4.11)

(3.4.11')

§ 4. ТЕОРЕМЫ О

КОДИРОВАНИИ

ИСТОЧНИКОВ

СООБЩЕНИЙ

116

ГЛАВА

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

Так как rj > 0 - фиксированная величина, то при достаточно большом

> (

{

будет выполняться:

D-1

Если I

£'

тах((

(т])

}

), то будут выполняться неравенства:

|M,(s)|>a^^>-^-a

4T,.

Б^Г (3.4.12)

Обозначим посредством X

суммарную вероятность всех особых последо-

вательностей. Тогда из неравенства (3.4.12) и второй теоремы Шеннона вы-

текает, что Х^<е при £>£', так как последовательности, входящие в класс

МДг^),

имеют наибольшие вероятности. Таким образом, для е>0 сущест-

вует такое £\ что при £ > £' выполняется

<е,

то есть

ПтХ

=0. (3.4.13)

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

довательности удовлетворяют неравенству:

о(с

)>-^-£.

logD

Суммарная вероятность всех таких последовательностей не меньше

- Х

(

. Отсюда получаем:

(Q)

°2°

(Q) *

1О

&°

Так как Х

(

0 при

оо,

то:

=lim

x^^-£ = ^^£.

^«э

logD logD

Так как ц > 0 - произвольная величина, то ц £ ——, то есть величина

logD

есть нижняя граница коэффициента сжатия.

lo%D

Покажем, что —^ - точная нижняя граница. Зададимся величинами

logD

Л>0,

8>0.

117

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

равенство:

logD

Величину £ обозначим сх(сЛ. Пусть

0<е<1.

logD

Согласно второй теореме Шеннона (2.2.2) можно выбрать наиболее

вероятные последовательности с номерами от единицы до |МД1-е)|. Число

их при достаточно больших £ удовлетворяет неравенству:

|M,(l-e)j<a'

+6)

==D

logJ>

«В^^^В^^. (3.4.14)

Наиболее вероятные последовательности, составляющие класс

МД1-6),

закодируем по какому-нибудь правилу кодовыми словами длины ]<*i(c^)[.

Такое кодирование возможно в силу строгого неравенства (3.4.14). Все ос-

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

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

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

какое-нибудь, но всегда одно и то же кодовое слово из числа неисполь-

зованных, длины

]orj(c^)

[. Такое кодовое слово найдётся, так как неравен-

ство (3.4.14) строгое. В построенном таким образом коде длины кодовых

слов равны либо

]cri(C{)

[, либо £+ ]oi(c^) [. Причём первая длина исполь-

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

ных. Оценим математическое ожидание кодового слова в построенном коде:

Ecr(c,)«€

Н^

+ 8

logD

J logD

+ xe,

logD logD

где

- фиксированная величина, которая удовлетворяет соотношению:

Ноо+5

logD

Еа(с

)

logD

+ 8

logD

б)

+ е +

+ хе

Выбором малых е,8 и достаточно большого

£>£

(в,х)

получаем оценку:

logD ' (3.4.15)

Еа(с

) < £

§ 4.

ТЕОРЕМЫ

О КОДИРОВАНИИ ИСТОЧНИКОВ СООБЩЕНИЙ

118

ГЛАВА

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

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

jkl(

^)[

+ falfc^t

средняя длина удовлетворяет оценке (3.4.15).

Положим, что источник произвёл последовательность c

, которую без ог-

раничения общности можно представить в виде к последовательностей дли-

ны i:

^)^^, L/

к^.

Если в к

-ю

последовательность входит символов меньше, чем £, то про-

извольным образом дополним её до длины £. Кодированная последователь-

ность длины a(c

) распадается при этом на к подпоследовательностей,

длины которых равны

<т(с^),.»>а(с^).

При этом:

Поэтому, с учётом

E<j(C

) L^

= kEa(4) < Ы =L •

logD logD

и.

<—55

Окончательно:

L->oc

logD

Подчеркнём, что значение доказанной теоремы заключается в том, что на

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

может быть закодирована последовательностью букв кодового алфавита В,

длина которой сколь угодно близка (сверху) к энтропии источника, делённой

на логарифм числа букв кодового алфавита.

ЗАДАЧИ

Символы источника без памяти

[A,p(s)]=

{a„...,a

};

р(а,)=Д;

i = l,...,n-l, р(а

)

р(а

) = ^

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

Определить минимальное среднее число символов на сообщение.

Символы источника без памяти [A,p(s)]

A = {a

..,a

} р^)^ £р*=1

кодируются двоичными последовательностями в алфавите В =

{0,l}.

Определить, можно ли построить двоичный префиксный код,

длины кодовых слов которого будут равны:

Ь)£,=1,

(

=£

=2,

с) £

]

—

2, £2 ~ 2)

£ 2

~ ^4 ~ ~

е)

= 1,

=^з=^

=3,

Каждому числу 1, 2, 4,17,98 поставим в однозначное соответствие в ка-

честве кодового слова его двоичное разложение.

Определить, будет ли такой код однозначно декодируемым.

Определить, можно ли построить двоичное кодовое дерево с

концевыми вершинами порядков 1,2,3,3,4.

Определить, можно ли построить троичное кодовое дерево с

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

a) 1,2,3,3,4,4,4;

1,2,3,3,3,4.

6. Покажите, что наибольшее возможное количество D-чных

последовательностей, длина которых не превосходит т, равно:

D-1

Существует ли двоичный префиксный код со 100 кодовыми сло-

вами, у которого длина i-го слова была бы равна i ?

Будет ли такой код оптимальным ?

120

ГЛАВА

III.

ОПТИМАЛЬНОЕ

К од И РОВ AH и Е

Символы источника без памяти

[A,p(s)] =

[{а

,а

};

р(а

)^0,4; р(а

) = 0,3; р(а

) = 0,2; p(a

) = 0,l]

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

1,01,001,0001;

1,10,100,1000.

1) Являются ли данные коды префиксными, однозначно декоди-

руемыми ?

2) Какова средняя длина кодового слова ?

9. Из нижеприведенных кодов выделить однозначно декодируе-

мые:

{0,01},

b) {0,10,11},

c) {0,01,11},

d) {0,01,10},

e) {ЮД1ДЮ},

f) {00Д0,01Д1},

д) {00Д0Д1Д00Д10}.

10.

Показать, что неравенство Крафта имеет место и для ис-

точников с бесконечным алфавитом и конечной энтропией.

11.

Показать, что максимальная длина кодового слова в опти-

мальном коде для алфавита

A(JA|

= m) не превосходит m -1.

Показать, что эта верхняя граница достижима.

12.

Показать индукцией по п(п = |А|), что сумма длин всех кодовых

слов оптимального кода не превосходит -(п + 2)(п-1).

Показать, что эта оценка достижимая.

13.

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

слов максимальной длины нечётно ?

b) Верно ли, что в оптимальном двоичном коде число кодовых

слов максимальной длины четно ?

c) Верно ли, что это число является степенью двойки ?