Основы криптографии Учебное пособие - Алферов А.П.
ISBN 5-85438-025-0
Скачать (прямая ссылка):
Легко видеть, что если Pl=Xjn при всех / = 1,и, то H0 = H(?) = Iog2 п . Кроме того, в общем случае имеет место неравенство Н(?) > О, причем Н(?) = Ob том и только в том случае, когда P1 =X для некоторого / и Pj = 0 для всех
4 =
(О
энтропия Н(^) определяется формулой
п
(2)
J**-
157
і лава 7
Мерой среднего количества информации, приходящейся на одну букву открытого текста языка A (рассматриваемого как источник случайных текстов), служит величина Ha , называемая энтропией языка Л . Естественно вычислять ее последовательными приближениями: H0, H1, где Hx — энтропия позначной модели открытого текста, то есть величина (2), в которой P1 совпадает с вероятностью появления буквы
я, в открытом тексте. Для английского языка, H0 ® 4,70,
H1 = //(?)«4Д4. В качестве следующего, более точного приближения, энтропия вероятностного распределения биграмм, деленная на 2 (нас интересует энтропия на знак). В общем случае следует взять энтропию вероятностной схемы на r-граммах, деленную на г. Соответствующие вычисления
Н2
для английского языка дают отношения -----------------«3,56,
2 jj
® 3,30, и так далее. Исследования показывают, что с рос-Hr
том г отношение —- стремится к некоторому пределу. Этот г
предел и принимается за определение энтропии Ha языка Л5:
Яд =Iim^. (3)
Г—>00
При этом формула
5 Существование предела (3) строго доказывается для стационарных эр-годических источников сообщений.
158
надежность шифров
Iog2W
(4)
определяет избыточность языка Ra .
Термин “избыточность языка” возник в связи с тем, что максимальная информация, которую в принципе могла бы нести каждая буква сообщения, равна H0 = Iog0 п (где п —
число букв в алфавите). Как было отмечено выше, так было бы в случае, если буквы сообщения появлялись случайно и равновероятно. В то же время средняя энтропия буквы в открытом тексте значительно меньше и, следовательно, буква несет меньше информации, чем Ioga п. Величина
Ioga п - Hx характеризует, таким образом, неиспользованные
возможности в передаче информации с помощью текста, а отношение
в некотором смысле показывает, какую часть букв открытого текста можно опустить без потери содержания. Имеется в виду, что потерянная информация будет восстановлена другими буквами сообщения вследствие закономерностей языка.
К. Шеннон предложил оригинальный метод оценивания отношения Hjг для осмысленных текстов с позиции меры неопределенности опыта, состоящего в угадывании г-й буквы текста, при условии, что предшествующие его буквы известны [Ягл73]. Эксперимент по угадыванию r-й буквы текста легко может быть поставлен. Для этого достаточно выбрать осмысленный отрезок открытого текста длины г —I и предложить кому-либо угадать следующую букву. Подобный опыт может быть повторен многократно, при этом сложность угадывания г -й буквы может быть оценена с помощью среднего
Iog2W
Iog2W
159
І лава /
значения числа попыток Fr, требующихся для нахождения правильного ответа. Ясно, что величины Fr для разных значений г являются определенными характеристиками статистической структуры языка. Очевидно, что среднее число попыток Fr с ростом г может лишь уменьшаться. Прекращение этого уменьшения будет свидетельствовать о том, что соответствующие опыты имеют одинаковую неопределенность, то есть что отвечающая им величина Hr/г практически уже достигла своего предельного значения Ha .
Исходя из этих рассуждений, К. Шеннон произвел ряд подобных экспериментов, в которых г принимало значения
1,15 и 100. При этом он обнаружил, что отгадывание сотой буквы по 99 предшествующим заметно более просто, чем угадывание 15-й буквы по 14 предыдущим. Опыты показали, что с ростом г величина Hr/г убывает вплоть до г «30, а при дальнейшем росте г она уже практически не меняется.
Согласно исследованиям Б. Б. Пиотровского [Ягл73], имеют место следующие приближения величины Ha :
Таблица 8
Яд (бит/букву) Ra (в процентах)
Русский язык Франц. язык Русский язык Франц. язык
Язык в целом 1,37 1,40 72,6 70,6
Разговорная речь 1,40 1,50 72,0 68,4
Литературный текст 1,19 1,38 76,2 71,0
Деловой текст 0,83 1,22 83,4 74,4
160
Надежность шифров
Из приведенной таблицы видно, что языки имеют весьма большую избыточность. Что означает, например, избыточность, составляющая 75%? Это не означает буквально то, что любые 3 из 4 букв текста можно вычеркнуть без потери информации. Более точно это означает, что при оптимальном кодировании текста (при использовании, например, кода Хаффмена, кода Фано или другого оптимального кода [ШенбЗ]) его можно сжать до четверти длины без потери информации.
Сделаем замечание о другом возможном подходе к определению величины ЯЛ для литературных текстов. А. Н. Колмогоров, не согласившись с тем, что теоретикоинформационные рассмотрения игнорируют вопрос о смысловом содержании литературных текстов, предложил так называемый комбинаторный подход [Ягл73]. Суть такого подхода к определению энтропии текста состоит в следующем.
