Основы теории информации и криптографии - -Учебное пособие (В.В. Лидовский)

2. лекция: базовые понятия теории информации

Изучать любую теорию невозможно без неких базовых принципов, на которых строятся дальнейшие исследования. Для теории информации такими понятиями являются: информация, канал связи, шум, кодирование. Способы измерения информации и ее количество являются важными составляющими дальнейшего обучения. Клод Шеннон предложил вероятностный подход к измерению дискретной и непрерывной информации. Предлагаются различные математические выкладки, примеры задач. Много задач для самостоятельной проверки знаний

Информация - нематериальная сущность, при помощи которой с любой точностью можно описывать реальные (материальные), виртуальные (возможные) и понятийные сущности. Информация - противоположность неопределенности.

Канал связи - это среда передачи информации, которая характеризуется в первую очередь максимально возможной для нее скоростью передачи данных (емкостью канала связи).

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

Кодирование - преобразование дискретной информации одним из следующих способов: шифрование, сжатие, защита от шума.

Общая схема передачи информации изображена на рис.2.1.

Емкость канала связи без шума можно приблизительно вычислить, зная максимальную частоту волновых процессов, допустимую в этом канале. Можно считать, что скорость передачи данных может быть не меньше, чем эта частота. Например, при предельной частоте, равной 1000Гц, можно обеспечить скорость передачи данных не меньше 1Кбод.

Примеры каналов связи и связанных с ними предельных частот: телеграф - 140Гц, телефон - до 3.1КГц, короткие волны (10-100м) - 3-30МГц, УКВ (1-10м) - 30-300МГц, спутник (сантиметровые волны) - до 30ГГц, оптический (инфракрасный диапазон) - 0.15-400ТГц, оптический (видимый свет) - 400-700ТГц, оптический (ультрафиолетовый диапазон) - 0.7-1.75ПГц.

Рис. 2.1. 

Типичные современные каналы: телеграфный и телефонный. Перспективные, внедряемые ныне: оптоволоконный (терабоды) и цифровой телефонный (ISDN, Integrated Services Digital Networks) - 57-128 Кбод.

В реальных оптоволоконных системах скорость гораздо ниже теоретических пределов (редко превосходит 1-10Гбод).

Наиболее широко пока используются телефонные линии связи. Здесь достигнута скорость более 50 Кбод!

Способы измерения информации

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

Равенство вещественных переменных a=b, заключает в себе информацию о том, что aравно b. Про равенство a^2=b^2можно сказать, что оно несет меньшую информацию, чем первое, т.к. из первого следует второе, но не наоборот. Равенство a^3=b^3несет в себе информацию по объему такую же, как и первое;

Пусть происходят некоторые измерения с некоторой погрешностью. Тогда чем больше будет проведено измерений, тем больше информации об измеряемой сущности будет получено;

Математическое ожидание некоторой случайной величины, содержит в себе информацию о самой случайной величине, Для случайной величины, распределенной по нормальному закону, с известной дисперсией знание математического ожидания дает полную информацию о случайной величине;

Рассмотрим схему передачи информации. Пусть передатчик описывается случайной величиной, X, тогда из-за помех в канале связи на приемник будет приходить случайная величина, Y=X+Z, где Z- это случайная величина, описывающая помехи. В этой схеме можно говорить о количестве информации, содержащейся в случайной величине, Y, относительно X. Чем ниже уровень помех (дисперсия Zмала), тем больше информации можно получить из Y. При отсутствии помех Yсодержит в себе всю информацию об X.

В 1865 г. немецкий физик Рудольф Клаузиус ввел в статистическую физику понятие энтропии или меры уравновешенности системы.

В 1921 г. основатель большей части математической статистики, англичанин Роналд Фишер впервые ввел термин "информация" в математику, но полученные им формулы носят очень специальный характер.

В 1948 г. Клод Шеннон в своих работах по теории связи выписывает формулы для вычисления количества информация и энтропии. Термин энтропия используется Шенноном по совету патриарха компьютерной эры фон Неймана, отметившего, что полученные Шенноном для теории связи формулы для ее расчета совпали с соответствующими формулами статистической физики, а также то, что "точно никто не знает" что же такое энтропия.

Упражнение 4 Какое из соотношений несет в себе больше информации x=5или x>3?

Вероятностный подход к измерению дискретной и непрерывной информации

В основе теории информации лежит предложенный Шенноном способ измерения количества информации, содержащейся в одной случайной величине, относительно другой случайной величины, Этот способ приводит к выражению количества информации числом.

Для дискретных случайных величи Xи Y, заданных законами распределения P(X=X_i)=p_i, P(Y=Y_j)=q_jи совместным распределением P(X=X_i,Y=Y_j)=p_{ij}, количество информации, содержащейся в Xотносительно Y, равно

I(X,Y)=sum_{i,j}p_{ij}log_2{p_{ij}over
p_iq_j}.

Для непрерывных случайных величин, Xи Y, заданных плотностями распределения вероятностей p_X(t_1), p_Y(t_2)и p_{XY}(t_1,t_2), аналогичная формула имеет вид

I(X,Y)=intlimits_{quadR^2}\!\!\!\!\!
int p_{XY}(t_1,t_2)log_2{p_{XY}(t_1,t_2)over
p_X(t_1)p_Y(t_2)}dt_1dt_2.

Очевидно, что

egin{align*}P(X=X_i,X=X_j) = egin{cases}
0,&	ext{при $i
e j$}\
P(X=X_i),&	ext{при $i=j$}end{cases}end{align*}

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

I(X,X)=sum_ip_ilog_2{p_iover
p_ip_i}=-sum_ip_i
log_2p_i.

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

H(X)=HX=I(X,X).

Свойства меры информации и энтропии:

I(X,Y)ge0, I(X,Y)=0 xLeftrightarrow Xи Yнезависимы;

I(X,Y)=I(Y,X);

HX=0 xLeftrightarrow X- константа;

I(X,Y)=HX+HY-H(X,Y), где H(X,Y)=-sum_{i,j}p_{ij}log_2p_{ij};

I(X,Y)le I(X,X). Если I(X,Y)=I(X,X), то X- функция от Y. Если X- инъективная функция1) от Y, то I(X,Y)=I(X,X).

Логарифмированием из очевидного для всех xнеравенства e^{x-1}ge x(равенство устанавливается только при x=1) получается неравенство x-1geln xили 	extstyle{x-1overln2}gelog_2x.

-I(X,Y)=sum_{i,j}p_{ij}log_2{p_iq_jover p_{ij}}le
sum_{i,j}p_{ij}{{p_iq_jover p_{ij}}-1overln2}=
ifdimhsize<160mm

=fi
sum_{i,j}{p_iq_j-p_{ij}overln2}=
{sum_ip_isum_jq_j-sum_{i,j}p_{ij}overln2}={1-1overln2}=0,

т.е. I(X,Y)=0только при p_{ij}=p_iq_jдля всех iи j, т.е. при независимости Xи Y. Если Xи Yнезависимы, то p_{ij}=p_iq_jи, следовательно, аргументы логарифмов равны 1 и, следовательно, сами логарифмы равны 0, что означает, что I(X,Y)=0;

Следует из симметричности формул относительно аргументов;

Если HX=0, то все члены суммы, определяющей HX, должны быть нули, что возможно тогда и только тогда, когда X- константа;

Из четырех очевидных соотношений

sum_jp_{ij} = p_i,quad sum_ip_{ij} = q_j,

HX = -sum_i p_i log_2 p_i = -sum_{i,j} p_{ij} log_2
p_i,

HY = -sum_j q_j log_2 q_j = -sum_{i,j} p_{ij} log_2
q_j

получается

HX+HY-H(X,Y) = sum_{i,j} p_{ij} (log_2 p_{ij} - log_2 q_j -
log_2 p_i)= I(X,Y);

Нужно доказать I(X,Y)=HX+HY-H(X,Y)le HXили HY-H(X,Y) le 0.

HY-H(X,Y) = -sum_{i,j} p_{ij} log_2 q_j +
sum_{i,j} p_{ij} log_2 p_{ij} = sum_{i,j} p_{ij}
log_2(p_{ij}/q_j),

но p_{ij}=P(X=X_i,Y=Y_j) le q_j=P(Y=Y_j), а значит аргументы у всех логарифмов не больше 1 и, следовательно, значения логарифмов не больше 0, а это и значит, что вся сумма не больше 0.

Если HX=I(X,X)=I(X,Y), то для каждого ip_{ij}равно либо q_j, либо 0. Но из p_{ij} = P(X=X_i,Y=Y_j) = P(X=X_i/Y=Y_j)P(Y=Y_j) in \{q_j, 0\}следует P(X=X_i/Y=Y_j)in \{0,1\}, что возможно только в случае, когда X- функция от Y.

При независимости случайных величин, Xи Yодна из них ничем не описывает другую, что и отражается в том, что для таких случайных величин, I(X,Y)=0.

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

Пусть заданы дискретное случайные величины X_1, X_2и Y. X_1и X_2- количества очков, выпавших соответственно на 1-й и 2-й игральной кости, а Y=X_1+X_2. Найти I(Y,X_1), I(X_1,X_1), I(Y,Y).

Законы распределения вероятностей для дискретной случайной величины X_1и X_2совпадают, т.к. кости одинаковые и без изъянов.

centerline{hbox{vbox{offinterlineskiphalign{&struthfil # hfilcr
X_1& vrule& 1& 2& 3& 4& 5& 6cr

oalign{hrule}
p& vrule& spanspan1/6spanspanspancr}}
vbox{hbox{, т.е. при j=1...6 q_j=P(X_1=j)=1/6.}}}}

Закон распределения вероятностей для дискретной случайной величины Y,

P(Y=i)=P(X_1+X_2=i),quad i=2...12,

вследствие того, что X_1, X_2- независимы и поэтому

P(X_1=n,X_2=m)=P(X_1=n)P(X_2=m),

будет

p_i=P(X_1+X_2=i)=sumlimits_{n+m=iatop1le n,mle6}P(X_1=n)
P(X_2=m)=sumlimits_{n+m=iatop1le n,mle6}1/36.

Таблицы, определяющие Y:

smallskip
setboxzero=vbox{offinterlineskiphalign{&struthfil $#$ hfilcr
_{X_2}s^{X_1}& vrule& 1& 2& 3& 4& 5& 6cr

oalign{hrule}
1& vrule& 2& 3& 4& 5& 6& 7cr
2& vrule& 3& 4& 5& 6& 7& 8cr
3& vrule& 4& 5& 6& 7& 8& 9cr
4& vrule& 5& 6& 7& 8& 9& 10cr
5& vrule& 6& 7& 8& 9& 10& 11cr
6& vrule& 7& 8& 9& 10& 11& 12,cr}}
setboxone=vbox{offinterlineskip
halign{&struthfil $#$ hfilcr
Y=X_1+X_2& vrule& 2& 3& 4& 5& 6& 7& 8& 9& 10& 11& 12cr

oalign{hrule}
omit& omit vrule height1pthfilcr
p& vrule& xfrac1{36}& xfrac2{36}& xfrac3{36}& xfrac4{36}&
     xfrac5{36}& xfrac6{36}& xfrac5{36}& xfrac4{36}&
     xfrac3{36}& xfrac2{36}& xfrac1{36},cr}}
setboxtwo=hbox{quad т.е. при $i=2...12$, $p_i=P(Y=i)=(6-|7-i|)/36$.}
dzero=wdzero advancedzerowdone advancedzero1em
oxzero
smallskip

setboxone=vbox{offinterlineskip
halign{&struthfil $#$ hfilcr
Y=X_1+X_2& vrule& 2& 3& 4& 5& 6& 7& 8& 9& 10& 11& 12cr

oalign{hrule}
omit& omit vrule height1pthfilcr
p& vrule& xfrac1{36}& xfrac2{36}& xfrac3{36}& xfrac4{36}&
     xfrac5{36}& xfrac6{36}& xfrac5{36}& xfrac4{36}&
     xfrac3{36}& xfrac2{36}& xfrac1{36},cr}}
setboxtwo=hbox{quad то есть при $i=2...12$, $p_i=P(Y=i)=(6-|7-i|)/36$.}
dzero=wdzero advancedzerowdone advancedzero1em
ifdim dzero<hsize centerline{hbox{oxzero quad
vbox{oxone vskip4pt oxtwo copystrutbox copystrutbox}}}
else centerline{oxzero}smallskip centerline{oxone}smallskip 
centerline{oxtwo}fi
smallskip

Закон совместного распределения вероятностей дискретной случайной величины X_1и Yбудет

p_{ij}=P(Y=i,X_1=j)=P(Y=i/X_1=j)P(X_1=j),

например,

P(Y=2,X_1=1)=P(Y=2/X_1=1)P(X_1=1)=ifdimhsize<140mm

=fi
P(X_2=1)P(X_1=1)=1/36.В общем случае получится

p_{ij}=P(Y=i,X_1=j)=egin{cases}1/36, &	ext{при $1le i-jle6$,}\
0, &	ext{иначе.}end{cases}

centerline{vbox{offinterlineskip
let~=xfrachalign{&strut $#$ hfilcr
_{X_1}s^Y& vrule& 2& 3& 4& 5& 6& 7& 8& 9& 10& 11& 12cr

oalign{hrule}
omit& omit vrule height1pthfilcr
1& vrule& ~1{36}& ~1{36}& ~1{36}& ~1{36}& ~1{36}& ~1{36}& 0& 0& 0& 0& 0cr
2& vrule& 0& ~1{36}& ~1{36}& ~1{36}& ~1{36}& ~1{36}& ~1{36}& 0& 0& 0& 0cr
3& vrule& 0& 0& ~1{36}& ~1{36}& ~1{36}& ~1{36}& ~1{36}& ~1{36}& 0& 0& 0cr
4& vrule& 0& 0& 0& ~1{36}& ~1{36}& ~1{36}& ~1{36}& ~1{36}& ~1{36}& 0& 0cr
5& vrule& 0& 0& 0& 0& ~1{36}& ~1{36}& ~1{36}& ~1{36}& ~1{36}& ~1{36}& 0cr
6& vrule& 0& 0& 0& 0& 0& ~1{36}& ~1{36}& ~1{36}& ~1{36}& ~1{36}& ~1{36}cr}}}
smallskip

Тогда

I(Y,X_1)=
sum^6_{j=1}sum_{1le i-jle6}p_{ij}log_2{p_{ij}over p_iq_j}=

={1over36}sum^6_{j=1}sum_{1le
i-jle6}log_2{1over6p_i}=

={1over36}(
sum^7_{i=2}log_2{1over6p_i}+sum^8_{i=3}log_2{1over6p_i}+cdots+
sum^{11}_{i=6}log_2{1over6p_i}+sum^{12}_{i=7}log_2{1over6p_i})=

={1over36}((log_2{6over1}+log_2{6over2}+cdots+log_2{6over6})+
cdots+(log_2{6over6}+log_2{6over5}+cdots+log_2{6over1}))=

={1over36}
(underline{2log_26}+4log_23+6log_22+8log_2{3over2}+10log_2{6over5}+
underline{6log_21})=

=(2+2log_23+4log_23+6+8log_23-8+10log_23+10-10log_25)/36=

=(10+24log_23-10log_25)/36approx0.69 hbox{
бит/символ}.

I(X_1,X_1)=I(X_2,X_2)=-sum^6_{j=1}q_jlog_2q_j=log_26=
1+log_23approx2.58  hbox{ бит/символ}.

I(Y,Y)=-sum_{i=2}^{12}p_ilog_2p_i=

={1over36}(2log_236+4log_218+6log_212+8log_29+10log_2{36over5}
+6log_26)=

=(4+4log_23+4+8log_23+12+6log_23+16log_23+20+20log_23-
10log_25+fi6+6log_23)/36=

=fi(46+60log_23-10log_25)/36
approx 3.27 
hbox{ бит/сим}.

Здесь 0 < I(Y,X_1)=I(Y,X_2) < I(X_1,X_1)=I(X_2,X_2) <
I(Y,Y), что соответствует свойствам информации.

Подчеркнутый член {1over36}2log_26 = I(X_1,X_1)/18в расчете I(X_1,Y)соответствует информации о двух случаях из 36, когда Y=2и Y=12, которые однозначно определяют X_1. Шесть случаев, когда Y=7, не несут никакой информации об X_1, что соответствует подчеркнутому члену 6log_21 = 0.

Расчеты можно проводить, используя 4-е свойство информации, через энтропию.

H(Y,X_1) = -sum_{i,j} p_{ij}log_2 p_{ij} = log_236 = 2(1+log_23) 
= 2HX_1 approx 5.17 hbox{ бит/символ}.

I(Y,X_1) = HX_1+HY-H(X_1,Y)=HY-HX_1 approx 
3.27-2.58=0.69 hbox{ бит/символ}.

Расчет количества информации с использованием 4-го свойства, а не определения, обычно требует меньше вычислений.

Рассмотрим более простой пример. Пусть дискретная случайная величина Xравна количеству очков, выпавших на игральной кости, а дискретная случайная величина Yравна 0, если выпавшее количество очков нечетно, и 1, если выпавшее количество очков четно. Найти I(X,Y)и I(Y,Y).

Составим законы распределения вероятностей дискретной случайной величины Xи Y.

setboxzero=vbox{offinterlineskiphalign{&struthfil #\
hfilcr
X& vrule& 1& 2& 3& 4& 5& 6cr

oalign{hrule}
p& vrule& spanspan1/6spanspanspancr}}
setboxone=vbox{offinterlineskiphalign{&struthfil #\
hfilcr
Y& vrule& 0& 1cr

oalign{hrule}
p& vrule&1/2spancr}}
centerline{oxzero hfil oxone}

Таким образом, при i=1...6p_i=P(X=i)=1/6и, соответственно, при j=0...1q_j=P(Y=j)=1/2.

Составим также закон совместного распределения вероятностей этих дискретных случайных величин

centerline{vbox{offinterlineskiphalign{&struthfil #\
hfilcr
X& vrule& 1& 3& 5& 2& 4& 6&& 1& 3& 5& 2& 4& 6cr
Y& vrule& 0& 0& 0& 1& 1& 1&& 1& 1& 1& 0& 0& 0cr

oalign{hrule}
p& vrule& spanspan1/6spanspanspan&&spanspan0spanspanspancr}}}

Таким образом,

p_{ij}=P(X=i,Y=j)=
egin{cases}0, &	ext{hskip-5.5pt если $i+j$ --- четно,}\
       1/6, &	ext{hskip-5.5pt иначе.}
end{cases}

I(X,Y) = sum_{i,j}p_{ij}log_2{p_{ij}over p_iq_j}
=6{1over6}log_22=1 hbox{ бит/символ}.

I(Y,Y) = -sum^1_{j=0}q_jlog_2q_j = 2{1over2}log_22 = 1 hbox{ бит/символ}.

Точное количество выпавших очков дает точную информацию о четности, т.е. 1бит. Из I(X,Y)=I(Y,Y)=1бит/сим и 3-го свойства информации следует, что информация об Xполностью определяет Y, но не наоборот, т.к. I(X,Y) 
e I(X,X) = 1+log_23 approx 2.58бит/сим. Действительно, Yфункционально зависит от X, а Xот Yфункционально не зависит.

Расчеты через энтропию будут следующими

H(X,Y) = -sum_{i,j} p_{ij}log_2 p_{ij} = log_26 = 1+log_23 =
HX,

I(X,Y) = HX+HY-HX = HY = 1 hbox{ бит/символ}.

Упражнение 5 Найти энтропию дискретной случайной величины X, заданной распределением

centerline{vbox{offinterlineskiphalign{&strutquad#cr
X&omit vrule& 1& 2&  3&  4&   5&   6&   7&   8cr

oalign{hrule}
p&omit vrule& 0.1& 0.2& 0.1& 0.05& 0.1& 0.05& 0.3& 0.1.cr}}}
smallskip

Упражнение 6 Значения дискретной случайной величины X_1и X_2определяются подбрасыванием двух идеальных монет, а дискретная случайная величина Yравна сумме количества "гербов", выпавших при подбрасывании этих монет. Сколько информации об X_1содержится в Y?

Упражнение 7 Сколько информации об X_1содержится в дискретной случайной величине Z=(X_1+1)^2-X_2, где независимые дискретные случайные величины X_1и X_2могут с равной вероятностью принимать значение либо 0, либо 1? Найти HX_1и HZ. Каков характер зависимости между X_1и Z?

Упражнение 8 Дискретные случайные величины X_1, X_2- зависимы и распределены также как и соответствующие дискретные случайные величины из предыдущей задачи. Найти I(X_1,X_2), если совместное распределение вероятностей X_1и X_2описывается законом

vbox{offinterlineskiphalign{&strutquad#cr
X_1& omit vrule& 0 & 0 & 1 & 1cr
X_2& omit vrule& 0 & 1 & 0 & 1cr

oalign{hrule}
  p& omit vrule&1/3&1/6&1/6&1/3.cr}}

Упражнение 9 Дискретные случайные величины X_1и X_2определяются подбрасыванием двух идеальных тетраэдров, грани которых помечены числами от 1 до 4. дискретная случайная величина Yравна сумме чисел, выпавших при подбрасывании этих тетраэдров, т.е. Y=X_1+X_2. Вычислить I(X_1,Y), HX_1и HY.

Упражнение 10 Подсчитать сколько информации об X_1содержится в дискретной случайной величине Z=X_1*X_2, а также HZ. Дискретные случайные величины X_1и X_2берутся из предыдущего упражнения.

Упражнение 11 Дискретная случайная величина X_1может принимать три значения -1, 0 и 1 с равными вероятностями. Дискретная случайная величина X_2с равными вероятностями может принимать значения 0, 1 и 2. X_1и X_2- независимы. Y=X_1^2+X_2. Найти I(X_1,Y), I(X_2,Y), HX_1, HX_2, HY.

Упражнение 12 Найти энтропии дискретных случайных величин X, Y, Zи количество информации, содержащейся в Z=X+Yотносительно Y. Xи Y- независимы и задаются распределениями

centerline{vbox{offinterlineskip
halign{&strutquad#cr
X& omit vrule&  0&  1&  3&  4&  qquad& Y& omit\
vrule& -2& 2cr
multispan6hrulefill& omitquadqquad& multispan4hrulefillcr
p& omit vrule& 1/8&1/8&1/4&1/2& qquad& p& omit\
vrule& 3/8& 5/8.cr
}}}
smallskip