7. Об избыточности, шумах и криптограмме, которую нельзя расшифровать

Напомним читателю, что при кодировании сообщений нужно заботиться о том, чтобы их передача была достаточно быстрой, удобной и надежной. До сих пор мы интересовались лишь требованием быстроты. В этой связи были рассмотрены различные эффективные методы кодирования: коды Фано, Шеннона, Хаффмена. Последний, как было выяснено, является даже оптимальным при заданном множестве сообщений с заданными вероятностями. Указанные методы можно рассматривать как своего рода искусственные языки, предназначенные для экономной передачи информации. Оказывается, что привычные нам естественные языки (русский, английский и т. д.) являются в этом плане слишком расточительными и не выдерживают конкуренции с искусственными языками. Подтвердим это следующим мысленным экспериментом. Произвольный русский текст разобьём на куски одинаковой длины n (промежуток между словами можно по желанию либо игнорировать, либо считать отдельным символом). Получающиеся при этом различные буквосочетания из n букв будут встречаться, как это отмечалось прежде, не одинаково часто. Представим себе, что мы располагаем таблицей, в которой указаны всевозможные n-буквенные сочетания и их вероятности в русском тексте. Применяя метод Фано, закодируем их кодовыми словами, также использующими русский алфавит. Возвращаясь к исходному тексту, заменим каждый его кусок длины n соответствующим ему кодовым словом. Расчеты показывают, что действуя таким образом, мы смогли бы при достаточно большом n сократить исходный текст более, чем наполовину, сохранив при этом всю содержащуюся в нем информацию.

Было бы однако неосторожным на основе сказанного обвинить русский язык или другие естественные языки в несовершенстве. В теории информации имеется понятие, именуемое избыточностью языка или текста. Избыточность, точного определения которой мы не приводим, можно представлять себе как долю тех символов текста, которые могут быть искажены или стерты без ущерба для его понимания, или иначе, как степень возможного "сжатия" текста в случае применения к нему методов оптимального кодирования. Мы вправе сказать поэтому, что естественные языки обладают высокой избыточностью (более 50%). Напротив, оптимально закодированные тексты имеют избыточность, близкую к нулю. Но именно высокая избыточность естественных языков позволяет с легкостью пользоваться ими в письменной и устной речи, например, свободно вникать в смысл написанного, несмотря на содержащиеся в тексте сокращения или опечатки, без особого труда понимать человека, говорящего с акцентом или на каком-нибудь диалекте и т. д. Герои известного романа Жюля Верна "Дети капитана Гранта" счастливой развязкой своих приключений также во многом обязаны избыточности языка.

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

Возьмем последовательность сообщений A₂A₃A₅A₅A₁A₄ и отвечающий ей кодовый текст 011011111100110. Пусть произошло искажение одного только первого символа. Получившаяся тогда кодовая последовательность 111011111100110 после расшифровки будет воспринята как последовательность сообщений А₅А₂А₅А₄А₂А₃.

Произошла непоправимая путаница, и ее виновником был всего лишь один неверно принятый кодовый символ. Аналогично обстоит дело с любым оптимальным кодовым текстом: ошибки (одна или несколько) переводят его в другой также вполне осмысленный кодовый текст, но смысл получившегося текста может быть совершенно отличен от первоначального. Такова расплата за оптимальность кода.

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

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

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

В этом равенстве m_i и l_i по-прежнему являются номерами i-ой буквы шифруемого текста и криптограммы соответственно, а каждое k_i выбирается случайным образом среди чисел 0, 1, 2, ..., 30 - так что выбор любого из этих чисел в качестве k_i одинаково возможен.

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

Существуют, однако, системы шифрования, не использующие случайного ключа, и в то же время близкие к совершенно секретным. Необходимая система, например, может быть получена усовершенствованием шифра бегущего ключа (см. дополнение 4 к § 2). Она состоит в том, что на предварительно сжатый передаваемый текст накладывается другой текст, также предварительно сжатый.

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