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

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

Д. Ломакин Л. Туркин

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

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

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

МИНИСТЕРСТВО ВЫСШЕГО И СРЕДНЕГО СПЕЦИАЛЬНОГО |

ОБРАЗОВАНИЯ РСФСР

ГОРЬКОВСКИЙ ОРДЕНА ТРУДОВОГО КРАСНОГО ЗНАМЕНИ

ПОЛИТЕХНИЧЕСКИЙ ИНСТИТУТ

Д. В. Ломакин А. И. Туркин

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

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

ГОРЬКИЙ 1988

ДК 007

Прикладная теория информации и кодирования: Конспект лекции/Д. В.

Ломакин, А. И. Туркнн; Горькое, политехн. ин-т. Горький, 1988. 52 с.

Изложены теоретические основы прикладной теории информации и

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

Рассматривается роль теории информации и теории кодирования в задачах

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

Предназначено для студентов специальности 22.02 «Автоматизированные

системы обработки информации и управления». Табл. 2. Ил. 3. Библиогр.: 9

назв.

Рецензенты:

кафедра радиотехники Горьковского государственного университета изд. Н. И.

Лобачевского; канд. техн. наук Л. И. Ларин

ОГЛАВЛЕНИЕ

Предисловие

1. Модели, используемые в статистической теории информации

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

3. Дискретные источники сообщений и их описание

4. Кодирование сообщений при передаче по каналу без помех

5. Кодирование информации при передаче по каналу с помехами

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

7. Итеративный алгоритм декодирования произвольных линейных

кодов .Библиографический список

ПРЕДИСЛОВИЕ

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

третьего курса специальности 22.02 «Автоматизированные системы обработки

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

специальности 23.01 «Радиотехника» при изучении курса радиотехнических

систем передачи информации.

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

информации и научить их применять информационные методы решения

прикладных задач.

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

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

этом по возможности простой математический аппарат.

К сожалению, ограниченный объем работы не позволил изложить

интересные и важные вопросы передачи непрерывных сообщений и

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

Гл. 1, 2, 3', 4 написаны Д. В. Ломакиным, а гл. 5, 6, 7— А. И. Туркиным.

1. МОДЕЛИ, ИСПОЛЬЗУЕМЫЕ В СТАТИСТИЧЕСКОЙ ТЕОРИИ

ИНФОРМАЦИИ

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

части реального мира. Область применения результатов теории ограничена

областью примеЕЕе-ния принятой модели. Мы рассмотрим модель, которая

лежит в основе статистической теории информации [1, 2]. Существуют и

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

информации. Однако в настоящей работе они рассматриваться не будут, за

исключением прагматической (ценностной) теории информации, которая

может быть построена в рамках статистической теории информации.

Понятие информация тождественно понятию сведения п ассоциирует с

наличием по крайней мере двух взаимодействующих систем А и В, одна из

которых В является наблюдаемой системой (приемником), а вторая А—

источником информации. Вис указанной схемы понятие информация теряет

смысл.

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

могут зависеть от параметров. Состояния системы — это значения физической

величины или параметра, которые ее описывают. Если эти значения

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

называется системой с непрерывным множеством состояний.

Сообщение — это то, что можно сообщить, а сообщить можно только

состояние системы. Следовательно, сообщение — это состояние системы.

Система случайным образом с некоторой вероятностью может оказаться в

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

соответствует передаваемой букве). Следовательно, множество состояний

системы можно рассматривать как множество случайных событий.

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

одной из них влияет на вероятность состояния другой.

Множества состояний Х и У соответственно систем А и В

В зависимости от

того, в каком отношении они рассматриваются, можно интерпретировать как

множества состояний, сообщений и событий.

Два множества Х и У с заданным на них двумерным рас

пределением Р{Хi, ;Yi,) (xi Є X

i, yi

) представляют собой модель двух

взаимодействующих систем. Эта модель лежит в основе построения

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

Сигнал— это материальный переносчик информации в пространстве и во

времени.

Сигналы могут быть динамическими и статическими. Динамические

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

(электромагнитная волна). Статические сигналы (запоминающие устройства)

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

кинофильм и т. д.). Точнее, сигналом является не сам материальный

переносчик информации, а его состояние. Поэтому целесообразно

конкретизировать определение сигнала. Сигнал — это значение физической

величины, которое отображает состояние источника сообщений. Поскольку

множество сообщений можно рассматривать как множество случайных

событий, то отображающее значение физической величины также будет

случайным.

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

сигнала. В общем случае состояние системы' (передаваемое сообщение)

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

изменяться во времени, .зависеть от времени. Случайная величина, зависящая

от времени (некоторого параметра), называется слу-ч а ^ ной фуи к ц и е и.

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

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

ИНФОРМАЦИИ

КОМБИНАТОРНОЕ ОПРЕДЕЛЕНИЕ КОЛИЧЕСТВА

ИНФОРМАЦИИ

Комбинаторное определение количества информации дано американским

инженером Р. Хартли. Это определение предполагает модель с

детерминированной связью (помехи отсутствуют) между дискретными

состояниями

ДВУХ систем без их вероятностного описания.

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

неопределенность ее состояния. Сведения позволяют снять эту

неопределенность, то есть определить состояние системы. Поэтому

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

неопределенности, которая растет с ростом числа состояний системы.

Количественная мера информации устанавливается следующими

аксиомами.

Аксиома 1. Количество информации, необходимое для снятия

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

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

В качестве количественной меры информации можно выбрать

непосредственно число состояний системы mx , которое является

единственной характеристикой множества X.

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

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

количественная мера информации, которая является функцией mx. Вид

указанной функции позволяет установить аксиома 2.

Аксиома 2. Неопределенность состояния сложной системы, состоящей из

двух подсистем, равна сумме неопределенностей подсистем.

Если для снятия неопределенности первой подсистемы необходимо

количество информации, равное /(т;), а для второй подсистемы количество

информации, равное I(т1), то

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

информации, равное где m1— число состояний первой подсистемы: m2—

число состояний второй подсистемы; т1 т2—число состояний сложной

системы. Единственным решением полученного функционального уравнения

является логарифмическая функция I (т)= Кlogam , которая определяет

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

Произвольный коэффициент К выбирается равным единице, а основание

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

зависимости от значения а единицы измерения называются двоичными (а=2),

троичными (a=3) и в общем случае a-ичными. В дальнейшем под

СИМВОЛОМ

1оg будем понимать двоичный логарифм. Двоичная единица иногда

обозначается bit; (от английского binari digit— двоичный знак). Каждое

передаваемое слово из п букв, записанное в алфавите. Cодержащем т букв,

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

сообщений. Всего таких состояний (слов) будет m

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

I=logam

=nlogam. Отсюда следует, что одна буква несет loga т а-ичных

единиц информации. Бели единица измерения информации а=т, то

количество информации в слове (1=п) измеряется количеством содержащихся

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

алфавита т. Таким образом, одна a-ичная единица содержит loga т й-ичных

единиц информации.

ОПРЕДЕЛЕНИЕ КОЛИЧЕСТВА ИНФОРМАЦИИ ПО

К. ШЕННОНУ

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

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

требуется п двоичных единиц информации (по одной двоичной единице или

по одному двоичному вопросу на выяснение содержания каждого разряда).

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

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

этом числе ничего, кроме того, что оно записано в регистр, не знаем.

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

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

частности, о способе его записи (генерации).

Допустим, некоторое устройство вырабатывает (генерирует) число как

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

соответственно с вероятностями, равными р и q=1—р. В этом случае при

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

равной единице, появляются последовательности, количество единиц в

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

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

только размещением единиц, а не их количеством. Поскольку количество

()

),2()1(21 mImImmI

типичных последовательностей Q, меньше общего количества

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

информации, необходимое для определения числа.

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

количество единиц п1 в ней удовлетворяет неравенству

или

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

Вероятность появления нетипичной последовательности равна

вероятности, с которой п\ удовлетворяет неравенству (2). Для оценки этой

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

произвольной случайной величины ^, имеющей конечную дисперсию, при

каждом Ь>0 записывается в виде

Где ξ и σ

и —соответственно математическое ожидание и

дисперсия случайной величины ξ. Полагая ξ = n1,ξ

=n1=np , b=εn,

= σ

=npq(q=(1-p)) получим аналогичное неравенство для случайного числа

единиц п1:

Следовательно, вероятность появления нетипичной последовательности

nnpnP

}1{

≤≥−

−

(1)

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

nnpn <−1

HTT

11 −−= >

nnpn ≤−1

Вероятность PHT стремится к нулю, а вероятность Рт стремится к единице при

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

последовательности л. Интервал [-nε, nε], которому принадлежит количество

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

(nε→∞), хотя относительная величина интервала

,}{

ξσ

εξξ

≤≥−

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

увеличением длины последовательности п можно уменьшать значение ε=nε c

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

миться к нулю, а вероятность появления типичной последовательности—к

единице. При этом абсолютная величина интервала по-прежнему

nn −1

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

величина ε

(n)n неограниченно увеличивается с ростом п. Пусть ε(n)n=n

2δ

где

δ>0—некоторый параметр, определяющий скорость роста величины ε(n)n.

Отсюда

(n)=n

-0,5+

(0<6<0,5).

Величина ε (n) стремится к нулю с ростом п при δ<0,5. При этом абсолютная

величина интервала ε

п(п) не может быть постоянной или стремиться к нулю

одновременно с неограниченным увеличением величины ε

(n)n, стремлением

(n)n к нулю.

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

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

)(

−

)(

)1(

)1()1(

*)(

qpqp

npn

nqnpnqnnnqnpnnp

−

−−+−+

В результате тождественных преобразований

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

)],()([

]

[)1()(

loglogloglogloglog

XOXHn

npn

qppn

npnnqpnpP

mmmmm

−−=

−

−−−=−++=

где величина

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

Покажем, что в случае типичных последовательностей остаточным членом

0(п} по сравнению с величиной Н{Х} можно пpенебречь.

nnpn <−1

nXO

loglog

5,0

)()(

+−

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

неравенство

0)(

lim

=nO

Следовательно,

)0)(0( ≠

≠

qqppXH

loglog

)( −−=

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

приближенное равенство

)()(

log

XnHP

−≈

Отcюда вероятность появления отдельной типичной последовательности

Поскольку правая часть равенства не зависит от номера типичной

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

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

где суммирование ведется по всему множеству типичных

последовательностей. Отсюда,

Q=m

nH(X)

причем единица измерения энтропии Н(X) совпадает с основанием степени m.

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

регистра), равно

logQ; С- энтропия Н(Х)= logQ/n равна количеству информации,

которое необходимо для определения состояния одного разряда.

Аналогично определяется количество типичных последо-

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

только в этом случае энтропия

СВОЙСТВА ЭНТРОПИИ

Энтропия

поскольку р, удовлетворяет неравенству. Энтропия Н(Х)-=0, когда система

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

остальных—с вероятностью, равной нулю. При этом имеется в виду, что

xnH

)(

−

≈

При равномерном распределении( p

i=1/

) энтропия

H(X)-log m

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

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

()

loglog

log

loglog

∑∑

⎟

⎠

⎞

⎜

⎝

⎛

−

=−=−

Для оценки выражения

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

∑

≈−

XnH

1)(

)(

()

() ()

PXH

log

∑

−=

()

0log

≥−=

∑

piPXH

0log

lim

→

∑

log

ln z<=z-1, положив z=1/p

Заменяя на

получим

Отсюда H(X)<=log

Рис. 1. Энтропия системы с

двумя состояниями: р —

вероятность одного

из состояний

Пусть множество Х состоит из двух элементов, которые обозначим через 1 и 0

Причем 1 появляется с вероятностью, равной р, а ноль — с вероятностью,

равной q=1-p Тогда

H(X)=-p logp-{1-p)log(1-p}.

Указанная зависимость изображена на рис. 1. Максимум достигается при

p=q=0,5.

ЦЕННОСТЬ ИНФОРМАЦИИ

Все определения ценности информации связаны с понятием цели. Ценной

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

цели.

Один из способов измерения ценности информации, сформулированный в

рамках статистической теории информации, был предложен А. А. Харкевичем

[З]. Ценность информации может быть выражена через приращение

вероятности достижения цели. Если значение априорной вероятности достиже-

ния цели обозначить через р

, а апостериорной — через p

, •то ценность

полученной информации можно определить как

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

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

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

решения в пользу Xi. Тогда относительно этой цели ценность сведений,

, Р(Xi|Yi)

содержащихся в принятом у,, равна log—-————, где

P(Xi)

р(Xi) — априорная вероятность передачи Хг; p(xi\yj) — вероятность того, что

было передано Xi после принятия Yi,. При такой формулировке цели ценность

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

определено выше.

Таким образом, количество информации, которое Yi, несет об Xi, равно

, Р(Xi|Yi)

I (Xi,Yi)= log—-————

P(Xi)

Умножая числитель и знаменатель под логарифмом на p(Xi) и учитывая

равенства

log

log1

⎟

⎠

⎞

⎜

⎝

⎛

−

log

переходамодульeгде

xxx

_log

,0log)11(log)

(log)1

(log)(

111

−−

=−=−=−≤−

∑∑∑

−−=

Р (Xi | Уi)Р (Уi)=Р (Xi, У,)=Р ( Хi | Yi)

получим

Отсюда следует. что у, несет об Xi такое же количество информации, какое Xi

несет об yj (свойство симметрии). Поэтому I (Xi,Yi) называется взаимным

количеством информации между i-м символом множества Х и j-м символом

множества У. Взаимное количество информации I (Xi,Yi) может быть

положительным p(Xi y:)>p(Xi) отрицательным p(Xi y:)<p(Xi) и равным нулю

(p(Xi|yj)=p(xi)). Отрицательная информация называется дезин-фо р м а цт; е и.

СОБСТВЕННАЯ ИНФОРМАЦИЯ И ЭНТРОПИЯ

Пусть в канале отсутствуют помехи Тогда между элементами множеств X

и Y имеет место взаимно однозначное соответствие и Р p(Xi|y)=1 при i=j. В

этих условиях количество информации, которое Yi (j=i) доставляет об Хi,

согласно '(3) равно

I(Xi)=-logp (Xi,) —— log р (Yi).

Эта величина называется собственным количеством v н ф о р м а ц и и, которое

несет символ Xi, причем всегда I(Xi )>0. Усредняя / (Xi) по всему множеству X,

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

множества X. Среднее значение совпадает с энтропией

где pi=p(Xi).

ВЗАИМНАЯ ИНФОРМАЦИЯ

Источник информации и приемник можно рассматривать как подснстемь;

одной сложной системы. Взаимную информацию между состояниями

подсистем, используя (3), можно записать в виде

I(Yi, Xi) =— log р (Xi) — [— log p (Xi | Yi,) ] =

=—logp(Xi)—logp(Yi)—[—logp(Xi, Yi)]-

——logp(Yi,)-[-logp(Yi|Xi)]=. I(Xi,Yi,) (4)

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

состояние, определяемое парой чисел, (Xi,Yi,) то I(Xi,Yi,) будет случайной

величиной, которую можно усреднить по всему множеству состояний. В

)3)(|(

)(

)|(

log

)()(

),(

log

)(

)|(

log)|(

результате почленного усреднения (4) получим выражение для средней

(полной) взаимной информации:

I(У, X)=H(X)-H(X|Y)=H(X}+H(Y)-H(X, У)= =H{Y}-H(Y|X)=-l(X, У),

где

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

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

приемника.

Поэтому энтропии Н(Х) н H(Y) можно интерпретировать как информацию,

которая поступает в канал связи, а условные энтропии H(X\Y), H(Y\X) как

информацию, которая рассеивается в канале. В [1] доказано, что I(X,Y)>=0

При выполнении указанного неравенства из (5) следует, что

H(X\Y)<=H(X),

H(Y\X)<=H(Y),

Н(Х, Y)<=H(X)+H(Y}.

I ====

) (5

);|(log),()|(

);(log),()|(

);(),()|(

pXYH

pYXH

pXYI

∑∑

S pi log p„

1=1

где

,log)()(

∑∑

−==

Условную энтропию можно представить в виде

где величина

называется ч а с т н о и у с л о в н о и э н т р о п и е и. Она характеризует

неопределенность состояния системы А в случае, когда известно состояние y-j

наблюдаемой системы В. Зафиксировав состояние yj системы В, мы тем самым

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

Это обнаруживается как изменение вероятности реализации события Хi (i=1,n)

(имеет место статистическая зависимость). Если до изменения условий

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

после изменения условий она стала равной условной вероятности p{xi\yi). При

отсутствии статистической_зависи

H(X|yi)=H(X), поскольку p(xi|yj)=p(xi)

Таблица 1

X1 X2 P(yi)

0,5

0,25

0,5

P(yi)

0,25

0,75

Таблица 2

X1 X2

0,5

∑∑∑

===

=−=

XHpp

ppYXH

Iij

yyy

111

)|()()(log)|()()|(

∑

−=

ppcXH

)|(log)|()|(

При наличии статистической зависимости энтропия H(X|yj) может оказаться

как

меньше, так и больше Н(Х). Напомним, что для энтропии H{X|Y) всегда

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

H{X\Y)<=H(X).

В качестве примера вычислим энтропии H(Х), H(X\Y), Н(X|Y) и взаимную

информацию 1(Х|Y), когда системы A и В описываются двумерным

распределением p(xi, yi) заданным в виде табл. 1.

Вычисленные значения условной вероятности

)

),(

( y

p =

записаны в табл. 2.

Используя записанные в таблицах значения вероятностей, получим