Лекции - Прикладная теория информации. Краткий конспект лекций

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

нейшем будем иметь дело только со стационарными источ-

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

простой цепи Маркова (

=l). В этом случае вероятность

px x px px x px x

iii i

( ,..., ) ( ) ( | )... ( | )

11211

−

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

−=−−−−

−

log ( ... ) log ( ) log ( | ) ... log( | )px x px px x x x

iii i

n11211

Это равенство показывает, что индивидуальное количест-

во информации, которое несет слово, равно количеству ин-

формации, которое неcет первая буква, плюс количество

информации, которое несет вторая буква при условии, что

первая буква уже принята, и т. д.

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

информации, которое в среднем несет каждое слово:

HX X HX HX X HX X

nnn

( ,..., ) ( ) ( | ) ... ( | )

1121 1

=+ ++

−

Поскольку источник стационарный, то энтропия не зависит

от k и равна

HX X HX n HX X nHX

nkk

(,..., ) ()( )(| ) ()

11 1

1=+− ≤

−

Подставляя полученный результат в (6) и учитывая, что

всегда HX m

() log≤ , имеем

HX X HX X

kk kk

−













→∞

−−

lim

()

(| ) (| )

В случае марковской цепи

-ãî порядка H

вычисляется

аналогично и равна Н

=Н(Х

,..., X

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

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

УСЛОВИИ

, что известны v предшествующих.

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

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

HHX m

И X

≤≤() log .

Максимального значения, равного logm

, производитель-

ность источника достигает, когда отсутствует статистиче-

ская зависимость между буквами в слове и когда все буквы

алфавита вырабатываются с равными вероятностями. Оче-

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

ностью определяется размером алфавита т

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

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

метр

HXH

−

max

()

называемый и з б ы т о ч н о с т ь ю.

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

I, требуется п=I/H

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

ника равна H

. В случае, когда производительность источ-

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

max

(X)= =logm

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

мации I требуется минимальное количество букв, равное

=I/Н

max

(X).

Отсюда I=пН

=п

max

или

max

()

. Учитывая пос-

леднее равенство, выражение для. избыточности можно за-

писать в виде

=− =

−

max

()

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

букв в слове не загружена информацией.

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

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

ность из единиц и нулей соответственно с вероятностями,

равными р=0,3 и q=0,7.

Решение. Поскольку символы в последовательности ста-

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

HHX ppqq

==−− ≈

() log log ,0 88 бит .

Максимально возможная производительность источника

HX m

Xmax

() log==1, поскольку m

=2. При этом символы 1

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

(p=q= =0,5). Отсюда

r =− =1

088

012

Пример 2. Определить избыточность стационарного мар-

ковского источника, алфавит которого состоит из двух сим-

волов: 0 и 1. Вырабатываемая источником последо-

вательность представляет собой простую цепь Маркова. За-

даны следующие значения условных вероятностей

px x i i

(|)

( = 1,2 , = 1,2) :

Решение. Безусловную вероятность того, что (k+1)-м

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

ной вероятности можно представить в виде

ppp pp

kk k

=+−

00001001() () (|) [ ()](|).

В правую часть неравенства входит вероятность p

(0) того,

что k-ì символом последовательности будет нуль. В силу

стационарности источника ppp

kk+

000() () (). Подста-

вив в равенство значения p(0|0) и р(0|1), получим

р(0)=0,125 , р(1)=1— р(0)=0,875.

Производительность источника

HpHX pHX

И kk

=+=−×

×+− +

+≈

() ( |) () ( |) ,

( , log , , log , ) , ( , log ,

,log,) , ,

00110125

03 03 07 07 087501 01

09 09 051

а избыточность источника

=− =− =11

051

049

max

()

, ,

где H

max

(X)=1.

Когда отношение v/n стремится к нулю, при неограничен-

ном возрастании п марковский источник вырабатывает ти-

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

(n- )

≈

или более приближенно Q2

≈

4. КОДИРОВАНИЕ СООБЩЕНИЙ ПРИ ПЕРЕДАЧЕ

ПО КАНАЛУ БЕЗ ПОМЕХ

ВОЗМОЖНОСТЬ ОПТИМАЛЬНОГО (ЭФФЕКТИВ-

НОГО) КОДИРОВАНИЯ

П о д к о д и р о в а н и е м будем понимать отображение

состояний некоторой системы (источника сообщений) с по-

мощью состояний сложного сигнала, который представляет

собой последовательность из п элементарных сигналов.

Мно-

жество У состояний элементарного сигнала образует алфа-

вит кода размера т

. При т

=2 элементарный сигнал имеет

два состояния, которые обозначим через 1 и 0. Состояние

сложного сигнала описывается последовательностью из ну-

лей и единиц, которая называется к о д о в ы м с л о в о м.

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

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

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

Пусть источник сообщений вырабатывает последователь-

ность из k букв, причем x

буква в этой последовательности

появляется п

раз. Каждой букве xi m

(,)= 1 поставим в со-

ответствие кодовое слово с длиной, равной l

(посимвольное

кодирование). Тогда длина соответствующей последова-

тельности из кодовых слов будет равна

Lnl

∑

Это равенство можно представить в виде













∑

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

тельности относительная частота появления x

буквы с ве-

роятностью, равной единице, совпадает со значением веро-

ятности p

появления этой буквы. Поэтому с вероятностью,

равной единице, выполняется равенство

LKlp Kl

≈=

∑

где

llp

∑

— по определению средняя длина кодового

слова. Длина последовательности кодовых слов L является

случайной величиной, но значительные отклонения ее от

среднего значения

LKl= маловероятны при неограничен-

ном возрастании К.

Таким образом, источник сообщений с вероятностью,

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

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

ния К

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

ной L , то имеется возможность его сокращения за счет

уменьшения средней длины кодового слова

lL Kl ()≈

. За-

дача оптимального кодирования заключается в определении

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

при которых их средняя длина минимальна.

ПРЕФИКСНЫЕ КОДЫ

При неравномерном коде в длинной последовательности

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

переданной буквы.

Однако однозначное декодирование всегда имеет место в

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

са (приставки). Код обладает свойством префикса, если ни

одно кодовое слово не является началом (приставкой) како-

го-либо другого кодового слова.

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

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

изобразить в виде узлов дерева (рис. 2). Дерево представ-

ляет собой множество точек (узлов), соединенных отрезка-

ми, которые называются ребрами дерева. Из каждого узла

выходят m

ребер, каждое из которых изображает соответ-

ствующий символ алфавита кода. Слова, состоящие всего

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

число равно m

. Слова, состоящие из двух букв, изобража-

ются узлами второго порядка и т. д. Причем узлов (слов) К-

го порядка в m

раз больше, чем узлов (К-1)-го порядка, по-

скольку каждый узел предыдущего порядка порождает m

узлов следующего порядка. Конкретный вид кодового сло-

ва определяется по изображающему его узлу как последова-

тельность ребер (букв), которые соединяют основание де-

рева с указанным узлом. В случае префиксных кодов на пу-

ти, соединяющем основание дерева с изображающим уз-

лом, не может быть промежуточных изображающих узлов.

Рис. 2 Полное троичное (

=3) кодовое дерево третьего

порядка (l=3): 1, 2, 3 - узлоы первого, второго, третьего порядков

Поскольку с помощью дерева (рис. 2) можно изобразить

все кодовые слова с длиной, меньшей или равной l, то оно

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

НЕРАВЕНСТВО КРАФТА

Теорема 1. Если целые числа l

...

, l

...

, l

удовлетворя-

ют неравенству m

−

∑

≤

1 , (7)

то существует код, обладающий свойством префикса с

алфавитом объема ту, длины кодовых слов в котором рав-

ны этим числам. Обратно, длины кодовых слов любого ко-

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

занному неравенству .

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

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

например, множество двоичных кодовых слов 0,00,11 удов-

летворяет (7), но не обладает свойством префикса. Теорема

утверждает только существование префиксного кода, но не

указывает его конкретный вид. Кодовые слова 0,10,11 удов-

летворяют неравенству (7) и обладают свойством префикса.

Доказательство. Пусть числа l

...

, l

...

, l

довлет-

воряют неравенству (7).

Покажем, как можно построить префиксный код с этими

длинами кодовых слов, и тем самым докажем существова-

ние префиксного кода. Не нарушая общности доказательст-

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

их значений. Тогда будем иметь ll l

N12

≤≤ ≤ ... . Построе-

ние будем вести на полном дереве порядка l

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

порядков l

, l

, ..., l

, но так, чтобы очередной выбираемый

узел не был порожден каким-либо ранее выбранным узлом.

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

числа узлов порядка l

. Этот узел порождает m

−

-ю часть

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

использованы. После выбора следующего узла порядка l

уже mm

−−

часть узлов не может быть использована и

т.д. После выбора (N -1)-го узла может быть использована

−

∑

часть узлов порядка l

Поскольку для чисел l

, ..., l

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

Крафта, которое можно записать в виде mm

−

∑

+≤

,то величина m

−

∑

строго меньше единицы. Следователь-

но, существует часть узлов порядка l

, из которых можно

выбрать последний N-é узел.

Отметим еще одно свойство кодовых слов. Если код од-

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

ряют неравенству Крафта. Доказательство можно найти,

например, в работе [4].

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

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

часть кодов, удовлетворяющих неравенству Крафта.

ПРЕДЕЛЬНЫЕ ВОЗМОЖНОСТИ ОПТИМАЛЬНОГО

КОДИРОВАНИЯ

Определим границы для l

и l, пользуясь эвристическими

соображениями, основанными на количестве информации.

Очевидно, код будет самым экономным, если каждый сим-

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

ное количество информации.

Поскольку собственное количество информации, содер-

жащееся в сообщении

∈

, равно -logp

, информацион-

ной емкости соответствующего кодового слова будет дос-

таточно, чтобы перенести указанное количество информа-

ции, только в

том случае, если его минимальная длина l

бу-

дет находиться в пределах

−

≤≤

−

log

где log m

— максимальное количество информации, кото-

рое может перенести отдельный символ кодового слова.

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

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

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

()

log

()

log

≤< +

В данном случае довольно большой интервал изменения

возможных значений

. Однако при кодировании блоков

(слов из п букв x

) средняя длина

приближается к значе-

нию

()

log

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

следует из неравенства

()

log

()

log

≤< +

где l

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

ходящееся на один блок, а

— на одну букву в блоке.

Полученные неравенства справедливы для всех однознач-

но декодируемых кодов.

ПРОПУСКНАЯ СПОСОБНОСТЬ ДИСКРЕТНОГО

КАНАЛА СВЯЗИ

Для общего описания канала связи и построения теории

информации используется одна и та же модель. Канал назы-

вается д и с к р е т н ы м (непрерывным), если множества Х

и Y дискретны (непрерывны), и п о л у н е п р е р ы в н ы м

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

Ниже рассматриваются только дискретные каналы.

Канал полностью описывается условными вероятностями

py x x

(|,...,)

того, что k-ì принятым символом будет

-й символ множества Y (j

=1,m

Указанную вероятность можно рассматривать как функ-

цию

yx x

и ,...,

, вид которой отражает состояние кана-

ла, в частности, характер взаимодействия помехи и сигнала.

Если

py x x py x

jm im

ky kX

(|,...,) (|)

(,, ,),

то соответствующий канал называется каналом без памяти.

Если вероятность

py x

(|)

не зависит от k (от времени), то

соответствующий канал называется стационарным. Огра-

ничимся рассмотрением только стационарных каналов без

памяти. Определим скорость передачи информации как

предел:

IXY

→∞

lim

(,)

где

IXY(,)

- средняя взаимная информация между пере-

данным

xX∈ и принятым

yY∈ . В случае отсутствия по-