Ломакин Д.В., Туркин А.И. Прикладная теория информации и кодирования

r

H

HX

nn

n

И

=− =

−

1

0

max

()

.

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

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

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

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

последовательность из единиц и нулей соответствен-

но с вероятностями, равными р=0,3 и q=0,7.

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

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

ность источника

H

Xppqq

И

=

−

≈

() log log ,088бит .

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

точника

H

Xm

X

max

() log

=

= 1, поскольку m

X

=2. При

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

ми вероятностями (p=q= =0,5). Отсюда

r =− =1

088

1

012

,

.

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

го марковского источника, алфавит которого состоит

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

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

цепь Маркова. Заданы следующие значения условных

вероятностей

px x i i

i

k

i

k

kk

(|)

+

1

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

Решение. Безусловную вероятность того, что

(k+1)-м символом последовательности будет нуль, по

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

виде

ppp pp

k

+

=

+

−

1

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

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

k

(0)

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

нуль. В силу стационарности источника

ppp

k

+

=

1

000() () (). Подставив в равенство значе-

ния p(0|0) и р(0|1), получим

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

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

H

p

H

Xp

H

X

И kk

=

+

=

−

×

×+− +

+≈

++

() ( |) () ( |) ,

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

,log,) , ,

00110125

03 03 07 07 087501 01

09 09 051

11

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

r

H

HX

И

=− =− =11

051

1

049

max

()

,

где H

max

(X)=1.

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

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

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

которых

Q2

(n- )

≈

ν H

И

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

Q2

n

≈

H

И

.

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

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

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

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

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

жение состояний некоторой системы (источника со-

общений) с помощью состояний сложного сигнала,

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

элементарных сигналов. Мно-

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

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

у

. При т

у

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

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

1 и 0. Состояние сложного сигнала описывается по-

следовательностью из нулей и единиц, которая назы-

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

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

н

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

р а в н о м е р н ы м .

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

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

i

буква в этой после-

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

появляется п

i

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

i

X

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

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

i

(по-

символьное кодирование). Тогда длина соответст-

вующей последовательности из кодовых слов будет

равна

Lnl

ii

i

m

X

=

∑

.

1

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

LK

n

K

l

i

m

X

=

⎛

⎝

⎜

⎞

⎠

⎟

=

∑

.

1

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

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

i

буквы с вероятностью, равной единице, совпадает со

значением вероятности p

i

появления этой буквы. По-

этому с вероятностью, равной единице, выполняется

равенство

LKlp Kl

ii

i

m

X

≈=

=

∑

,

1

где

llp

ii

i

m

X

=

∑

1

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

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

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

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

L

K

l

=

маловеро-

ятны при неограниченном возрастании К.

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

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

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

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

l.

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

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

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

lL Kl ()≈

. Задача оптимального кодирования заклю-

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

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

няя длина минимальна.

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

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

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

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

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

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

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

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

чалом (приставкой) какого-либо другого

кодового

слова.

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

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

ски удобно изобразить в виде узлов дерева (рис. 2).

Дерево представляет собой множество точек (узлов),

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

ми дерева. Из каждого узла выходят m

y

ребер, каждое

из которых изображает соответствующий символ ал-

фавита кода. Слова, состоящие всего из одной буквы,

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

но m

y

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

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

го порядка в m

y

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

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

рождает m

y

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

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

его узлу как последовательность ребер (букв), кото-

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

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

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

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

3

2

1

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

x

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

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

рядков

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

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

равной l, то оно называется полным деревом порядка l

с алфавитом объема т

у

.

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

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

1

,

...

, l

i

,

...

, l

N

удовле-

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

m

y

i

N

l

i

=

−

∑

≤

1

1 , (7)

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

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

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

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

удовлетворяют указанному неравенству .

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

довых слов, удовлетворяющими (7), является пре-

фиксным. Так, например,

множество двоичных кодо-

вых слов 0,00,11 удовлетворяет (7), но не обладает

свойством префикса. Теорема утверждает только су-

ществование префиксного кода, но не указывает его

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

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

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

1

,

...

, l

i

,

...

, l

N

Удовле-

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

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

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

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

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

вать в порядке возрастания их значений. Тогда будем

иметь

ll l

N

12

≤

... . Построение будем вести на

полном дереве порядка

l

N

.

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

узлов порядков l

1

, l

2

, ..., l

N

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

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

выбранным узлом. Первый узел (кодовое слово) вы-

бирается произвольно из

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

1

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

y

l

−

1

-ю

часть

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

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

порядка l

2

уже

mm

y

l

y

l

−−

+

12

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

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

использована

1

−

=

−

∑

m

y

l

i

N

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

N

.

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

1

, ..., l

N

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

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

mm

y

l

i

N

y

l

N

−

=

−

∑

+≤

1

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

y

l

i

N

−

=

−

∑

1

строго меньше

единицы. Следовательно, существует часть узлов по-

рядка l

N

, из которых можно выбрать последний N-é

узел.

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

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

удовлетворяют неравенству Крафта. Доказательство

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

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

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

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

Крафта.

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

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

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

i

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

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

информации. Очевидно, код будет самым экономным,

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

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

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

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

x

X

i

∈

, равно -logp

i

, ин-

формационной емкости соответствующего кодового

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

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

том случае, если

его минимальная длина l

i

будет находиться в преде-

лах

−

≤≤

−

+

log

p

m

l

p

m

i

y

i

y

1,

где log m

y

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

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

слова.

Усредняя неравенство по всему множеству Х сооб-

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

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

HX

m

l

HX

m

yy

()

log

()

log

≤< +1

.

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

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

l. Однако при кодирова-

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

i

) средняя длина l при-

ближается к значению

HX

m

y

()

log

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

n, что следует из неравенства

HX

m

l

n

HX

mn

y

б

y

()

log

()

log

≤< +

1

,

где

l

б

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

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

l

n

б

— на одну букву

в блоке.

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

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

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

ГО КАНАЛА СВЯЗИ

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

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

дель. Канал называется д и с к р е т н ы м (непрерыв-

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

и п о л у н е п р е р ы в

н ы м , если одно из множеств

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

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

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

ностями

p

y

x

j

k

ii

k

(|,...,)

1

того, что k-ì принятым сим-

волом будет

j

k

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

k

=1,m

y

).

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

функцию

y

x

j

k

i

k

i

k

и ,...,

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

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

помехи и сигнала. Если

py x x py x

jm im

j

k

ii

k

j

k

i

k

ky kX

(|,...,) (|)

(,, ,),

1

11

=

==

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

памяти. Если вероятность

p

y

x

j

k

i

k

(|) не зависит от k

(от времени), то соответствующий канал называется

стационарным. Ограничимся рассмотрением только

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

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

R

IXY

n

=

→∞

lim

(,)

,

r

где

IXY(,)

r

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

переданным

r

x

X

∈

и принятым

r

yY

∈

. В случае от-

сутствия помех H(X/Y)=0, следовательно, R =H(X).

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

ной информации:

R=I(X,Y)=H(X) -H(X|Y)=H(Y) -H(Y|X)

.

Скорость передачи информации R полностью опре-

деляется

вероятностями

px py x i m

iji x

() (|) , и ()= 1 . Поэтому

изменять величину R мы можем только за счет изме-

нения вида распределения

p

x

i

(), поскольку p

y

x

ji

(|)

— характеристика неуправляемого канала. Опреде-

лим пропускную способность канала С как макси-

мальную по

p

x

i

() Скорость передачи информации:

CR

I

X

Y

px

i

px

i

=

max max ( , )

() ()

.

В случае отсутствия помех

C

H

Xm

px

i

x

=

max ( ) log

()

.

ВЫЧИСЛЕНИЕ ПРОПУСКНОЙ СПОСОБНО-

СТИ СИММЕТРИЧНЫХ КАНАЛОВ

Существует класс каналов, для которых пропускная

способность С легко вычисляется. Канал полностью

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

цей

py x py x

m

Y

m

X

m

Y

m

X

( | ), ..., ( | )

(| ),...,( | )

,

11 1

1

⎛

⎝

⎜

⎞

⎠

⎟

в

которой сумма всех элементов, образующих строку,

рвана единице.

Канал называется с и м м е т р и ч н ы м п о в х о д

у , если строки матрицы различаются только поряд-

ком расстановки некоторого множества чисел

pp

m

Y

1

,...,

Для симметричных по входу каналов частная ус-

ловная энтропия

HYx pyx yx p p

iji

j

m

Y

ji j

j

m

Y

j

(|) (|)log(|) log.=− =−

==

∑∑

11

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

жет быть вычислена по любой строке матрицы. По-

этому условная энтропия

HYX px HYx p p

ii

i

m

X

j

m

Y

j

(| ) ( ) (| ) log .==−

==

∑∑

11

Канал называется с и м м е т р и ч н ы м п о в ы х

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

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

qq

m

X

1

,..., .

Если распределение источника равномерное

(( ) ),px

m

i

X

=

1

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

p

y

j

() на выходе симметричного по

выходу канала также будет равномерным. При этом

энтропии Н(Х) и H(Y) достигают своего максимально-

го значения. В этом легко убедиться, если доказать,

что вероятность

p

y

j

() не зависит от у

j

. Представим

вероятность

p

y

j

() в виде

py px py x

jiji

i

m

X

() ()(|).=

=

∑

1

Поскольку и ,тоpx

m

py x q

i

X

ji i

() (|)==

1

py

m

q

j

X

i

m

X

() .=

=

∑

1

Сумма

q

i

m

X

=

∑

1

не зависит от номера столбца j и в об-

щем

случае не равна единице. Поэтому вероятность

p

y

j

()

также

не зависит от j и равна

py

m

j

Y

()=

1

. При этом

H

Xm

H

Ym

X

Y

( ) log , ( ) log .

=

Канал называется симметричным, если он симмет-

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

H(Y|X) не зависит от распределения источника сооб-

щений, поэтому пропускная способность

CHYHYX HYHYX

mpp

px

i

px

i

Yii

j

m

Y

=

−

=

−

=

=+

=

∑

max[ ( ) ( | )] max ( ) ( | )

log log .

() ()

1

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

ность симметричного канала, который описывается

матрицей

1

11

1

−

−−

−

⎛

⎝

⎜

⎞

⎠

⎟

p

m

p

m

p

m

p

e

ee

e

, , ...,

, ...,

,

. . . . . . . . . .

где m=m

X

=m

Y

. В этом случае

C 1

0,8

0,6

0,4

py x

pij

p

m

ij

ji

e

(|)

,,

,.

=

−

=

−

≠

⎧

⎨

⎪

⎩

⎪

1

0,2

0 0,2 0,4 0,6 0,8 1 P

e

Рис. 3. Зависимость пропускной

способности ДСК от вероятности

ошибки p

e

Вероятность 1-p

e

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

приема символа. Вероятность ошибки p

e

равна веро-

ятности приема y

j

c ji

≠

при условии, что было пере-

дано x

i

. Тогда

Cm p pp

p

m

eee

e

=+− −+

−

log ( ) log( ) log11

1

.

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

метрич-ный канал (ДСК) (m=2) , для которого пропу-

скная способность (Рис. 3)

Cpppp

eeee

=

+

−

+

11 1()log()log.

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

ная единице, получается при р

е

=0 и при р

е

=1. В этом

случае множества Х и Y находятся во взаимно одно-

значном соответствии, и по принятому у

j

(j=1, 2) все-

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

це, переданную букву. К сожалению, это возможно

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

значение вероятности р

е

(нуль или единица).

21

Д.В.Ломакин

ПИКЛАДНАЯ ТЕОРИЯ ИНФОРМАЦИИ И

КОДИРОВАНИЯ

конспект лекций

2ЧАСТЬ

Ломакин Д.В., Туркин А.И. Прикладная теория информации и кодирования

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