Коды и математика (рассказы о кодировании) - Аршинов М.Н.
Скачать (прямая ссылка):
Произошла непоправимая путаница, и ее виновником был всего лишь один неверно принятый кодовый символ. Аналогично обстоит дело с любым оптимальным кодовым текстом: сшибки (одна или несколько) переводят его в другой также вполне осмысленный кодовый текст, ко смысл получившегося текста может быть совершенно отличен от первоначального. Такова расплата за оптимальность кода.
В то же время в реальных каналах связи, по которым происходит передача информации, ошибки неизбежны. Они являются следствием помех или, как иначе говорят, шумов, которые могут иметь самую различную физическую природу. Действие этих шумов на передаваемый текст можно ослабить, но устранить его полностью нельзя. Отсюда вывод: оптимальные кода в чистом виде непригодны для передачи сообщений по каналам связи с шумами, так как передача в этом случае становится ненадежной. С другой стороны, ясно, что надежность можно обеспечить только за счет некоторой избыточности кодового текста. В даль-
38 нейшем речь пойдет как раз о таких системах кодирования, которые предусматривают введение избыточности для борьбы с теми или иными видами ошибок. При построении подобных кодов всегда приходится идти на компромисс: с одной стороны, избыточность (т. е. количество дополнительных, «лишних», символов) не должна быть слишком велика, чтобы не растягивать время передачи; с другой стороны, помехоустойчивость (т. е. способность кода корректировать ошибки) должна быть достаточной, чтобы обеспечить надежность передачи.
Прежде чем переходить к рассмотрению помехоустойчивых кодов, позволим себе еще одно небольшое отступление в криптографию. К этому нас побуждает понятие избыточности, которое, оказывается, имеет прямое отношение к степени секретности криптограммы. Подстановочные криптограммы, например, потому-то и столь легки в расшифровке, что они, по существу, сохраняют избыточность первоначального текста.
Другие методы шифрования уменьшают эту избыточность, но все же не полностью ее устраняют, к тому же появляется избыточность, связанная со специфическими особенностями применяемого ключа. Совершенно секретная, т. е. недоступная для расшифровки, криптограмма должна быть освобождена как от избыточности исходного текста, так и от избыточности ключа. Способ составления такой криптограммы был предложен, как об этом уже упоминалось, К. Шенноном, и состоит он в следующем. Сначала устраняем избыточность текста, применяя к нему какой-нибудь из методов эффективного кодирования. Вслед за этим к получившемуся безызбыточному тексту применяем шифр со случайным ключом. Он похож на шифр Тритемиуса, для которого (применительно к русскому алфавиту)
/г=тг+?г (mod 31).
В этом равенстве тг и I1 по-прежнему являются номерами ('-ой буквы шифруемого текста и криптограммы соответственно, а каждое kt выбирается случайным образом среди чисел 0, 1,2, ... ,30 — так что выбор любого из этих чисел в качестве ki одинаково возможен.
Недостатком такой совершенно секретной системы является то, что вместе с шифрованным сообщением требуется посылать такое же по объему сообщение, содержащее информацию о случайном ключе, поскольку он заранее неизвестен адресату. Поэтому практически эта система малоприемлема.
39 Существуют, однако, системы шифрования, не исполь-1 зующие случайного ключа, и в то же время близкие к совершенно секретным. Необходимая система, например, может быть получена усовершенствованием шифра бегущего ключа (см. дополнение 4 к § 2). Она состоит в том; что на предварительно сжатый передаваемый текст накладывается другой текст, также предварительно сжатый.
Наконец, и от хлопотливой процедуры предварительного сжатия также можно отказаться, если в качестве ключа для шифровки использовать не один, а несколько (три или больше) условленных заранее текстов, прибавляя все их к передаваемому сообщению.
8. КОДЫ - АНТИПОДЫ
Мы выяснили, что при построении помехоустойчивых кодов не обойтись без дополнительных символов. которые должны быть присоединены к кодовым словам безызбыточного кода. Эти символы уже не несут информации о передаваемых сообщениях, но могут дать информацию о происшедших при передаче ошибках. Иными словами, их назначение — контролировать правильность передачи кодового слова. Вводимые дополнительные символы так и называют контрольными (или проверочными).
Самый незатейливый способ, позволяющий исправлять ошибки, состоит в том, что каждый информационный символ повторяется несколько раз, скажем, символ 0 заменяется блоком из п нулей, а символ 1 — блоком из п единиц. При декодировании л-буквенного блока, содержащего, быть может, ошибочные символы, решение принимается «большинством голосов». Если в принятом блоке нулей больше, чем единиц, то он декодируется как 00...О (т. е. считается,' что был послан нулевой символ), в противном случае — как П...1. Такое правило декодирования позволяет верно восстановить посланные символы, если помехи в канале искажают менее половины символов в каждом передаваемом блоке. Если длину блока п выбрать достаточно большой, то мы практически обезопасим себя от возможных ошибок, однако передача сообщений будет идти черепашьими темпами. По этой причине указанный код (его называют кодом с повторением) не имеет большого практического значения, однако правило его декодирования («голосование») содержит в себе весьма полезную идею, которая с успехом применяется в других, практически более интересных помехоустойчивых кодах. Об этом речь пойдет дальше (см.
