Бабаш А.В., Шанкин Г.П. Криптография (распознано не всё)

201

Параграф 4.1 Основные понятия и теоремы математической тео­

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

Ограничимся случаем дискретной информации, где сообщение, по­ длежащее передаче через канал связи, состоит из последовательности дискре­ тных символов, каждый из которых выбран из некоторого конечного множес­ тва(алфавита) букв сообщения. В случае непрерывной информации рекомен­ дуем прочитать пособие Ю.С. Харина, В.И. Берника, Г.В. Матвеева «Матема­ тические основы криптологии», Минск, БГУ, 1999, 319 стр.

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

Пусть задана конечная вероятностная схема

_ ( \	2	...	п Л
1р0)	Р(2)	-	р(п),

1, 2,..., а ,..., п - исходы (буквы, сообщения) вероятностной схемы из множес­

тва(алфавита) А= {1,2,..., а ,..., п}, р(1), р (2),..., р(а),..., р(п) - вероятности

п

этихсообщений, Е р (а ) = 1 -

а=1

Основоположником теории численной оценки меры неопределенности вероятностных схем является американский инженер и математик Клод Шеннон. Ниже приводятся его основные идеи в решении данной задачи. .

/ Если имеется такая мера (обозначим ее через Н=Н(А)= =Н(р(1),р(2),...,р(а),...,р(п)), то разумно аксиоматически потребовать, чтобы онаобладала следующими свойствами:

1)Н должна быть непрерывной относительно р(а), аеЛ;

2)Н должна быть симметрична относительно своих аргументов (т. е. Н(р(1),р(2),..., р(п))= Н(р(11),р(12),..., рОп)) д л я любой перестановки индексов);

3)если выбор распадается на два последовательных выбора, то первона­ чальная Н должна быть взвешенной суммой индивидуальных значений Н, т. е. при р(1)+р(2)>0 справедливо тождество:

Н(р(1),р(2),..., р(п))=

=Н(р(1)+р(2),р(3),...,р(п))+ (р(1)+р(2)) Н(	Р0)	, ■•	• )■
	р(1) + р(2) р(1) + р(2)

Смысл третьего свойства иллюстрируется на следующем рисунке:

	202
1/3	2/3
Т	4
•-> 1/6	• -> 1/2 •->1/3
4	4
1/2	1/2

Слева имеются три возможности р(1)=1/3, р(2)=1/6, р(3)=1/2. Справа проводится выбор сначала между двумя возможностями, причем каждая име­ ет вероятность 1/2, и в случае осуществления первой возможности производи­

тся еще один выбор между двумя возможностями с вероятностями 2/3 и 1/3. Окончательные результаты имеют те же самые вероятности: р(1)=1/2х2/3=1/3, р(2)=1/2х1/3=1/6, р(3)=1/2, как и прежде. В этом конкретном случае по свойс­ тву 3 требуют, чтобы

Н(1/3,1/6,1/2)=Н(1/2,1/2) + ^-Н(2/3,1/3).

Весовой множитель 1/2=(р(1)+р(2)) введен из-за того, что второй выбор осу­ ществляется в половине случаев.

Оказывается, что приведенные три условия с точностью до постоянно­ го коэффициента «с» определяют функцию Н(р(1),р(2),..., р(п)):

п

Н(р(1),р(2),..., р(п))= -с ^ р (а ) 1о§<, р (а),

а=1

где с=сопз1>0. Выбор константы равносилен выбору основания (1 логарифма, а ее значение и значение основания можно трактовать как определение масшта­ ба единицы количества неопределенности. Таким образом, окончательное вы­ ражение для Н имеет вид

п

Н(р(1),р(2),..., р(п))= - ^ р (а ) 1о§р(а),

а=1

при оговоренном основании логарифма.

Определение. Количеством информации (неопределенности) в со­ общении аеЛ называется число Ь(а), определяемое соотношением

Ь(а)=-1о§р(а).

Определение. Среднее значение количества информации

Н(А)— ^ р ( а ) 1о§р(а)

(1)

а=1

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

Термин количество информации Н применяют исходя из предположе­ ния, что произошла реализация (некоторый исход) в вероятностной схеме, в

203

результате чего мы получаем информацию об исходе реализации вероятност­ ной схемы, мера неопределенности Н употребляется в связи с измерением неопределенности возможных не реализованных исходов вероятностной схе­ мы. Не придавая житейского смысла этой величине, а имея в виду математи­ ческую формализацию Н, говорят об энтропии вероятностной схемы.

Отметим, что при использовании десятичных логарифмов, что обеспе­ чивает удобство расчетов с помощью таблиц, в качестве единицы количества информации (неопределенности) принимают энтропию равновероятной схе­

мы с 10 исходамй (р(а)=1 /10, ае 1,1 0 ), так как

10 1 1

Н = - У — 1§— =1.

П а 1 0 1 0

Чаще за единицу неопределенности принимают неопределенность, со­ держащуюся в альтернативном ответе «да-нет», соответствующему вероятно­ стной схеме (р(1)=1/2, р(2)=1/2). В этом случае основание логарифма должно быть равно двум:

н - ( 1 юь 1 + 1 юй 1 и .

Эту единицу называют «битом», она в 3,32=1о§2Ю раза меньше деся­ тичной единицы измерения информации.

Из определенйя энтропии конечной вероятностной схемы следует, что онавсегда неотрицательна: Н(р(1),р(2),..., р(п))>0. Важное свойство энтропии конечной вероятностной схемы (р(1),р(2),..., р(п)) заключается в том, что она

максимальна й равна 1о§п при р(а)=1/п, ае 1, п . Минимального значения

энтропия достигает на вероятностной схеме, где имеется сообщение с вероят­ ностью, равной единице.

Неравенство 0^Н(А)^1о§п позволяет качественно толковать понятие энтропия как.меру неопределенности в эксперименте с возникновением того или иного случайного сообщения.

Использование численной меры неопределенности Н(р(1),р(2),..., р(п)) вероятностной схемы оказалось очень удобным для весьма многих целей. От­ метим, однако, что эта мера не претендует на полный учет всех факторов, оп­ ределяющих «неопределенность опыта» в любом практическом смысле, так как приведенная мера неопределенности зависит лишь от значений вероятно­ стей р(1),р(2),..., р(п) различных исходов, но вовсе не зависит от того, каковы

сами эти исходы - являются ли они в некотором смысле «близкими» один к другому или очень «далекими», насколько различны или одинаковы послед­ ствия этих исходов.

204

Ранее мы отмечали, что Основание, по которому берется логарифм в определении энтропии, влияет на единицу измерения количества информа­ ции.

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

Объединенная энтропия двух конечных схем. Условная энтропия.

Рассмотрим наряду со схемой
М	2 ...	п	4
А=
ЧР(1)	Р(2) -	р(п)
схему
' 1	2 ...	ш	Л
В=	я<2) ...	4(тХ
Л (1)

Схемы А и В могут быть зависимы между собой в том смысле, что для вероятности р(а,Ъ) одновременного выполнения событий а, Ь выполняется не­ равенство: р(а,Ь)^р(а)я(Ь). Рассмотрим объединенную схему С=АВ вида

	С=Г (1 1 )	(12 )...	(аЬ)	(п т)	; р(а)= X	Р(аЬ) ’ я(Ъ)= X р(аЬ).
	1р(П)	Р(12)...	р(аЬ)	р(пт)
					Ь=1	а=1

Определение. В соответствии с определением (1), энтропия

Н(АВ)= - 5 ] р(аЬ) 1о§ р(аЬ) а,Ь

называется энтропией объединенной схемы АВ.

Обозначая через р(Ъ/а)=р(аЪ)/р(а), ЪеВ условные вероятности сообще­ ний схемы В при условии сообщения а, можно рассмотреть ряд «условных» вероятностных схем •

(	1	2	...	т
В/аЛ р ( 1 /а )		р(2 / а)	...	р ( т /а ) Г
Для каждой из этих схем согласно (1) можно определить энтропию
	Ш
Н (В /а)= -^ р (Ь /а)1о§			р(Ъ /а).
	Ь=1
Определение. Среднее значение					|
п	п	ш
Н (В /А )=2]р(а)Н (В /а) = - Х р ( а ) ^ р (Ь /а )1 о § р (Ь /а )					(2)
а=1	а=1	Ь=1

называется условной энтропией схемы В при условии схемы А.

V .

205

Взаимная информация между вероятностными схемами.

Исходя из установленного выше понятия энтропии как меры неопре­ деленности случайного сообщения, введем меру количества информации о сообщении «а», содержащемся в сообщении «Ъ», как разность между количе­ ством неопределенности (априорной) в сообщении «а» и количеством не­ определенности в сообщении «а» при известном сообщении «Ь».

Определение. Количеством информации о сообщении «а», содер­

жащемся в сообщении «Ъ», называется величина 1(аЬ)=Ь(а)-Ь(а/Ь)=1о§2р(а/Ь)/р(а).

Определение. Среднее значение

1(АВ)= X	р(аЪ)1(аЪ) = 2 ] р(аЬ) 1о§ 2(р(а / Ъ)/ р(а)).
а>ь	а,Ь

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

Введем в рассмотрение вероятностную схему В с вероятностями исхо­

дов

я(Ь)=Х р(а)р(ь /а )

а

\

Тогда величину 1(АВ) можно выразить через энтропийные характеристики следующим образом:

1(АВ)=Н(А)-Н(А/В)=Н(В)-Н(В/А).

Свойства энтропии.

1. Н(В/А)= Н(АВ) - Н(А).

(3)

Действительно,

Н(В/А)=

- & ( а)р(Ь/а)10§2[р(Ь/а)р(а)р_1 (а)]=- ^ р(Ь/ а)р(а) 1о§2 р(Ь/ а)р(а) +

а,Ь а,Ъ

+ ^ р(аЬ) 1о § 2 р(а) =Н(АВ) - Н(А).

а,Ь
2. Н(В/А)<Н(В),	(4)
Нетрудно показать, что выполняется неравенство 1пх-х+1<0. Действи­
тельно, для функции Т(х)=1пх-х первая производная Т'(х) = 1 / х - 1	обращает­

ся в 0 в точке х=1, причем Т(1)=0, а Т"(х) = —1 / х 2 < 0 для всех х>0. Следова­

206

тельно, Г(х) имеет единственную) точку максимума при х=1. Для двоичного логарифма имёем:

1о§2Х=1пх/1п2=(х-1)1о§2в.

Тогда

		<			Щ
	Н (В /А )-Н (В )= -]Г р м 1о§ 2 р С )/1 )+ Х ^ 1о8 2 Ч] =
		у			;=1
	“ 2	Ри 1о§2 Р(3/ 0 + Е р м		1о8 г <1, =
	У		У
	' Е р 1 > 8 г - ^ Ы Е р ‘-'				1п2 е = 0
					ч Р С К О УУ
	|,л	1 4 .1 ' Ч	ч у

3. Пусть на алфавите А вероятностной схемы А задано отображение <р(.) в множество С. Это отображение определяет вероятностную схему С с

алфавитом С, для которой р(с)=	р(а). Тогда выполняется неравенство
	а:<р(а)=с

Н(С)<Н(А), и знак равенства имеет место в том случае, когда отображение ф(.) обратимо.

Легко видеть, что условное распределение р(с/а)=1, если <р(а)=с и р(с/а)=0 в противном случае. Следовательно, Н(С/А)=0. Далее, нетрудно про­ верить, что

Н(С)-Н(С/А)=Н(А)-Н(А/С)	. ,
и, следовательно,
Н(С)+Н(А/С)=Н(А)+Н(С/А).
Тогда,
Н(С)< Н(С)+Н(А/С)=Н(А)+Н(С/А)= Н(А)

и равенство имеет место в том случае, когда отображение ф(.) обратимо и Н(А/С)=0, Н(С)=Н(А).

4. Н(АВ)<Н(А)+Н(В), причем равенство достигается в том и только в том случае, когда А и В независимы. Это свойство непосредственно следует из свойств 2 и р.

Если мы имеем А(Ь- А 2А 2...А1^- ш независимых объединений схемы

А, то

Н (А (Ь))= — Х р ( а 1а 2---а ь ) 1оё 2 Р(а 1а 2---а ь) =

	а,а2...аь
= “ X	Р (а,)р(а2)...р (а ь)]Г 1о§ 2 р(ак) =ЬН(А)
а,а2...аь	к

и в этом случае____________

207

—Н(А(Ь)) = Н(А).

Ь

Смысл введенного понятия энтропии становится ясен из следующих двух теорем Шеннона, относящихся к созданию сообщений с помощью неза­ висимых испытаний из конечной вероятностной схемы А.

Теоремы Шеннона.

Обозначим через Аь последовательность а ^ .- .а ^ полученную с по­ мощью независимых испытаний из конечной вероятностной схемы

а=Г 1	2	■"	п 1
А 1 р(1)	р(2)	-	р (п )/

Р(Аь)= р(а, )р(а2)...р (а ь ) - вероятность последовательности Аь. Оказывает­

ся, что при больших Ъ все последовательности (за исключением сколь угодно малой их доли) имеют приблизительно одинаковую вероятность, величина которой зависит от энтропии Н(А). Качественное объяснение этого факта дос­ таточно простое. Так как символы в последовательности Аь независимы, то

	п
энтропия на символ текста равна Н(А)=	р(а) 1о§2 Р(а) • Предположим,
	а=1

что рассматривается длинное сообщение, то есть Ь велико. Тогда последова­ тельность Аь будет, так сказать, «с большой вероятностью содержать р(а)Ь

раз» символ а€ 1,п . Вероятность конкретной последовательности А^ есть

Р(А ь) = П р (а )''-.

а=1

где V» - частота буквы «а» в последовательности Аь. Заменяя уа на р(а)Ь, по­ лучаем «приближенное равенство»

Р(Аь)= П р (а )ьР(а),

а=1

п

а 1о§2Р(Аь) =Ь ^ р(а) 1о§2 р(а) =-ЬН(А), откуда

а=1

1°§ 2	----
н(А)2 _ ^ | ( А	О .

Это приближенное равенство остается верным и для любого стационарного источника (стационарной последовательности). Распространение ука­

208

занного утверждения на цепь Маркова осуществил Хинчин А.Я., а на произ­ вольный стационарный источник - Макмиллан. Пусть, как и прежде, А={1,2,...а,...п} - конечное множество исходов, соответсвующее вероятнос­ тной схеме

' 1	2
ЧР(1)	Р(2)

Первая теорема Шеннона.

Для любых 8 > 0, Г| > 0 существует Ь0такое, что при любом Ь > Ь 0

множество Аь всех последовательностей длины Ь алфавита А разбиваются на группы (Аь)* и (А1")** такие, что

1) для любой Аье(Аь)*

2) Х Р(А ь ) < 8 -

Аье(АьГ

ДОКАЗАТЕЛЬСТВО. Нетрудно видеть, что

п

а=1

где уа - частота буквы «а» в последовательности А^ Отнесем к первой группе (Аь)* те и только те последовательности Аь в которых

для некоторой 5>0. Ко второй группе отнесем все остальные последователь­ ности.

Покажем, что при достаточно большом Ьо это разбиение удовлетворяет обоим условиям теоремы. Действительно, для А 1^е (А Г ) 4е

0 а <1, а = 1,п.

а=1

Отсюда нетрудно показать, что

п

Н(А)=-б2>,1о8гр(а).

а=1

209

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

Полагая

получаем первое утверждение теоремы.

Рассмотрим вторую группу (А1')**. Нетрудно видеть, что вероятность

Р((А1 ) " ) = Р ( [ ) ^ ,	- Ь р ( а ) |г 1 4 < 2 > ( |У а -Ь р (а)|^ Ь 5 ).
а=1	а=1

По неравенству Чебышева

откуда следует, что

р « а 1- ) ~ ) й - 2г .

Ь62

Полагая Ь0=п/82е, получаем второе утверждение теоремы.

Следствие. Если Ь>Ьо, то для любой А ье (А ь)* выполняется неравенс­

тво

- Ц Н (А ) + Л) < 1оё2 Р(А ь) < -Ц Н (А ) - ц) .

Таким образом, при достаточно больших Ь вероятность каждой по­ следовательности из (А1')* (за исключением последовательностей весьма ма­ ловероятного класса) заключена между 2'1(Н+п} и 2~1(Н~п>.

Важно бывает знать мощности обоих групп последовательностей (см. первую теорему Шеннона). В частности, возникает вопрос о числе «наиболее вероятных» последовательностей, вероятности которых приблизительно рав-

Занумеруем все последовательности в порядке убывания их вероя­ тностей:

Р (А ^ ) > Р(А[2)) > ... > Р С А ^ ), N = пь .

Выберем X, 0<Х<1. Пусть ^(А.) - число последовательностей, опре­

деляемых из неравенства N1

210

В это число войдет некоторое число последовательностей Аь второй группы, у которых Р(Аь)>2ЦН(А)-г|), но в основном оно определяется после­ довательностями первой группы.

Вторая теорема Шеннона.

Для любого фиксированного значения X, 0<Я<1 справедливо соотно­

шение

Иш у- 1о§ 2 Ы, (Х) = Н (А ).

Ь—>°о Ь

ИМЕННО В ЭТОМ СМЫСЛЕ ПИШУТ, что МЬ(Х)=2Ш(А). Как следует из формулы, этот предел не зависит от X и поэтому можно полагать X сколь угодно близким к 1, Х=1-Д и тогда пь- КД1-Д) есть число последовательнос­

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

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

Таким образом в.первой и второй теоремах Шеннона устанавливается замечательное свойство «равнораспределенности» длинных сообщений, по­ рождаемых независимыми испытаниями схемы А. '

Это свойство устанавливает, грубо говоря, тот факт, что всего та­ ких сообщений

М,*2ЬН(А)

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

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

Для этого необходимо,, во-первых, ввести математическую модель ос­ мысленных сообщений, а во-вторых, определить, в соответствии с (1), энтро­

пию на одну букву осмысленного сообщения. В качестве математической мо­ дели осмысленных сообщений обычно рассматривают последовательности, получаемые с помощью так называемых марковских процессов. Среди таких процессов имеется важная группа процессов называемая стационарными эргодическими процессами. В таких процессах каждая создаваемая процессом последовательность имеет одни и те же статистические свойства. Поэтому относительные частоты различных комбинаций исходов (букв, биграмм и т. п.), полученные из частных последовательностей будут стремиться с увели­ чением длин последовательностей к определенным пределам, не зависящим от этих частных последовательностей. Таким образом, для эргодического процесса возможно отождествление средних значений различных комбинаций исходов вдоль некоторой последовательности со средними значениями по ан-