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

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^2=b^2 можно сказать, что оно несет меньшую информацию, чем первое, т.к. из первого следует второе, но не наоборот. Равенство a^3=b^3 несет в себе информацию по объему такую же, как и первое;

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

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

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

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

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

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

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

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

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

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

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

Для непрерывных случайных величин, и , заданных плотностями распределения вероятностей 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.$

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

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

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

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

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) , то - функция от . Если - инъективная функция1) от , то .

Логарифмированием из очевидного для всех неравенства $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$ для всех и , т.е. при независимости и . Если и независимы, то $p_{ij}=p_iq_j$ и, следовательно, аргументы логарифмов равны 1 и, следовательно, сами логарифмы равны 0, что означает, что I(X,Y)=0 ;

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

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

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

$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) , то для каждого $p_{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\}$ , что возможно только в случае, когда - функция от .

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

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

Пусть заданы дискретное случайные величины X_1 , X_2 и . 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.}}}}$

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

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.$

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

$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 и будет

$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-го свойства, а не определения, обычно требует меньше вычислений.

Рассмотрим более простой пример. Пусть дискретная случайная величина равна количеству очков, выпавших на игральной кости, а дискретная случайная величина равна 0, если выпавшее количество очков нечетно, и 1, если выпавшее количество очков четно. Найти I(X,Y) и I(Y,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...6 p_i=P(X=i)=1/6 и, соответственно, при j=0...1 q_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-го свойства информации следует, что информация об полностью определяет , но не наоборот, т.к. I(X,Y)
e I(X,X) = 1+log_23 approx 2.58 бит/сим. Действительно, функционально зависит от , а от функционально не зависит.

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

$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 Найти энтропию дискретной случайной величины , заданной распределением

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 определяются подбрасыванием двух идеальных монет, а дискретная случайная величина равна сумме количества "гербов", выпавших при подбрасывании этих монет. Сколько информации об X_1 содержится в ?

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

Упражнение 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=X_1+X_2 . Вычислить I(X_1,Y) , HX_1 и .

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

Упражнение 11 Дискретная случайная величина X_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 , .

Упражнение 12 Найти энтропии дискретных случайных величин , , и количество информации, содержащейся в Z=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$

| Оглавление|

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

Содержание