7. ОБ ИЗБЫТОЧНОСТИ, ШУМАХ И КРИПТОГРАММЕ, КОТОРУЮ НЕЛЬЗЯ РАСШИФРОВАТЬ

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

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

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

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

 

 

последовательность сообщений

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

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

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

 

 

 

 

В этом равенстве ть и /г по-прежнему являются номе­рами «'-ой буквы шифруемого текста и криптограммы соот­ветственно, а каждое выбирается случайным образом сре­ди чисел 0, 1,2, ... , 30 — так что выбор любого из этих чи­сел в качестве кг одинаково возможен.

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

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

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