2.2.3. Элементы теории информации

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

Достаточно общие выводы о свойствах таких систем можно сделать в рамках разработанной К.Шенноном теории информации.

Далее мы кратко рассмотрим основные понятия этой теории.

Пусть дана дискретная случайная величина , принимающая значения a₁, a₂, … a_r с вероятностями P₁, P₂, … P_r.

Определение. Энтропия случайной величины  определяется равенством

H() =  , (2.11)

где полагается 0log0 = 0.

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

Если логарифм натуральный – то единица измерения энтропии называется нат, в случае десятичных логарифмов – дит.

При r = 2, полагая P₁ = p, P₂ = 1  p, энтропию можно представить в виде:

H() = (plogp + (1  p)log(1  p)). (2.12)

График энтропии для этого случая показан на рис. 2.1.

H()

1

0 0,5 1 p

Рис. 2.1.

Рассмотрим некоторые свойства энтропии.

Теорема 2.3. Энтропия обладает следующими свойствами:

1) H()  0;

2) H()  logr;

3) H() = logr при P_i = 1/r, i = 1,2,...,r.

Д о к а з а т е л ь с т в о.

Первое свойство очевидно.

Второе и третье свойства докажем для случая r = 2. Общий случай анализируется аналогично.

Исследуем график энтропии H(p), предполагая, что логарифм натуральный.

Первая производная H/p = lnp + ln(1p) принимает нулевое значение при р = 0,5. Вторая производная ²H/p² = (p^1 + (1p)^1) отрицательна, следовательно, в указанной точке достигается максимум.

Вернемся к логарифму по основанию 2 (очевидно, что это не уменьшает общности рассуждений). Получим: maxH(p) = H(0,5) = = = log2 = =1.

Физический смысл энтропии состоит в том, что она может рассматриваться в качестве меры неопределенности.

Проиллюстрируем этот тезис примером. Рассмотрим три случайные величины ¹, ², ³ при r=2. Это может соответствовать, например, такой ситуации: есть три источника сообщений, которые порождают случайные последовательности букв двухбуквенного алфавита {a₁, a₂}. Генерация каждой очередной буквы данной i-ой последовательности осуществляется независимо от других букв и интерпретируется как получение очередного значения величины ⁱ. Пусть вероятности появления различных букв в этих трех последовательностях таковы:

¹ : Р(a₁) = 1; Р(a₂) = 0;

² : Р(a₁) = 0,5; Р(a₂) = 0,5;

¹ : Р(a₁) = 0,01; Р(a₂) = 0,99;

Интуитивно ясно, что неопределенность величины ₁ равна 0. Формальное соотношение (2.12) приводит к тому же результату.

Также интуитивно ясно, что неопределенность величины ² должна быть больше неопределенности величины ³. Расчет по формуле (2.12) подтверждает это:

H(²) = 1 бит; H(³)  0,08 бит.

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

Подобно (2.11), определение энтропии можно дать для многомерной случайной величины. Пусть рассматривается векторная случайная величина  = (₁, ..., _n) при условии, что i-ый компонент вектора (его можно рассматривать как отдельную случайную величину) принимает значения (состояния) из дискретного множества мощности r_i. Тогда:

H(₁, ..., _n) = (2.13)

где индекс j_i перебирает множество номеров состояний компонента _i, а  вероятность реализации соответствующего набора состояний.

Рассмотрим двухмерный случай. Пусть множество значений величины ₁ – (а₁, ..., а_r), а величины ₂ – (b₁, ..., b_s). Пусть при оценке значения случайной величины ₂ значение случайной величины ₁ известно. Тогда можно определить условную энтропию:

H(₂ | ₁) = (2.13а)

где .

Прокомментируем соотношение (2.13а). Если реализуется конкретное событие ₁ = а_i (i  фиксировано), то условные вероятности реализации событий ₂ = b_j, j = 1,..., s равны . Отсюда по общим принципам расчета энтропии получим энтропию для условного процесса – когда i фиксировано (внутренняя сумма в (2.13а)). После этого усредняем эту условную энтропию (внешняя сумма).

Теорема 2.4. Свойства двухмерной энтропии:

H(₁, ₂) = H(₁) + H(₂ | ₁), (2.14)

в частности, для независимых случайных величин:

H(₁, ₂) = H(₁) + H(₂). (2.15)

Интерпретация теоремы: пусть в первом опыте порождаются значения величины ₁, а во втором – величины ₂. Тогда общая неопределенность должна быть равна неопределенности первого опыта плюс условная неопределенность второго опыта. В случае независимости опытов знание результатов одного опыта не несет никакой информации о другом опыте, что и отображено в формуле (2.15).

Рассмотрим теперь n-мерную случайную величину. Тогда аналогичные (2.14) и (2.15) соотношения имеют вид:

общий случай: H(₁, ..., _n) = H(₁) + H(₂ | ₁) + H(₃ | ₁, ₂) + H(_n | ₁, ..., _n1); (2.16)

для независимых случайных величин: H(₁, ..., _n) = . (2.17)

Последовательность случайных величин ₁, ..., _n, где _i  A, A = {а₁, ..., а_r} – некоторый алфавит, можно рассматривать как некоторый стационарный процесс (в узком смысле). Тогда свойства энтропии можно изучать, пользуясь теорией таких процессов.

Введем понятие удельной (на одну букву) энтропии n-го порядка.

h⁺_n = H(₁, ..., _n)/n. (2.18)

Определим также величину

h^_n = H(_n | ₁, ..., _n1). (2.19)

Можно доказать следующие свойства введенных величин:

h ⁺_n  h⁺_n1 , n > 1;

h^_n  h⁺_n (2.20)

h^_n  h^_n1 , n > 1;

Если рассматривается процесс без памяти (то есть величины ₁, ..., _n независимы), то h⁺_n = h^_n = h.

Теорема 2.5. Для стационарного случайного процесса существуют пределы h⁺_n и h^_n, причем эти пределы равны. Далее этот предел будем обозначать символом h_.

Для процесса без памяти maxH(_i) = logr.

Поэтому, с учетом теоремы 2.5, соотношений (2.17), (2.18) и неравенств (2.20), получим

maxh_ = logr, (2.21)

причем максимум достигается для процессов без памяти, у которых все буквы порождаются с равными вероятностями 1/r.

Введем величину:

R = logr  h_, (2.22)

называемую избыточностью на одну букву сообщения.

Неформально эту величину можно интерпретировать как меру неиспользованной части алфавита, а точнее, это мера взаимной зависимости символов и их "неравновероятности".

В связи с введением этой величины вспомним пример, в котором алгоритм шифрования задавался соотношением (2.3), а сообщениями были пятизначные десятичные числа. В этом примере все цифры сообщения были независимы и равновероятны. Поэтому избыточность R = 0 и именно поэтому даже такой примитивный шифр оказался невскрываемым (далее мы достаточно строго докажем правомерность этого утверждения – см. комментарий к теореме 2.6).