Кpиптогpафия от папиpуса до компьютеpа


Характеристики сообщений - часть 2


где Pi - частота появления символа i, a Ld- двоичный логарифм. Отметим три особенности такого определения информации.

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

2. В нем предполагается независимость вероятности появления знаков от их предыстории.

3. Заранее известна знаковая система, в которой передается сообщение, то есть язык, способ кодирования.

В каких единицах выражается значение количества информации по Шеннону? Точнее всего ответ на этот вопрос дает теорема кодирования, утверждающая, что любое сообщение можно закодировать символами 0 и 1 так, что полученная длина сообщения будет сколь угодно близка сверху к Н. Эта теорема позволяет назвать и единицу информации - бит.
     Каждый, кто использовал, работая на персональном компьютере, архиваторы, знает, как лихо они ужимают текстовые файлы, ничего при этом не теряя. Их работа лучшим образом демонстрирует теорему кодирования в действии. Так как для русского текста, переданного лишь прописными буквами, Н=4.43, то это означает, что в принципе в русском алфавите можно было бы обойтись лишь 22 буквами или на 45% сократить длину файлов в формате ASCII. Таким образом, сообщения языка занимают места больше, чем это необходимо. Это явление называют избыточностью языка. Благодаря ему искажения отдельных символов сообщения зачастую не разрушают содержания, что случилось бы при отсутствии избыточности. Заметьте, у компьютера наиболее часто встречаемые символы ETOANIRSHDLU (даны в порядке убывания частот в английском языке) вынесены в центр клавиатуры, чтобы при наборе текстов движение пальцев было бы минимальным. Это расположение клавиш было предложено изобретателем линотипа Оттомаром Мергенталером, который использовал избыточность языка для облегчения работы.
     Утверждение, что вероятность появления символа в связном тексте не зависит от его предыстории, неверно и статистически, и лингвистически. Уже давно литераторы заметили, что обычно за согласной буквой следует гласная, а за гласной согласная. Поэтому в конце XIX века петербургский математик Марков предложил текст рассматривать как цепочку символов, где вероятность появления буквы зависит от предыдущей и только от нее. Таким образом, он стал рассматривать не вероятности Pj появления в сообщении знака i, а вероятности Pij появления знака j при условии, что перед ним стоит знак i. Теория марковских цепей оказалась чрезвычайно продуктивной для криптографии, и к отдельным ее применениям мы будем возвращаться позже. Пока же достаточно отметить, что первое свое опробование она имела при анализе текстов "Евгения Онегина" самим Андреем Андреевичем Марковым. Объем информации в одном символе марковской цепи определяется следующей формулой:
    




- Начало -  - Назад -  - Вперед -