1. Кодирование - история и первые шаги

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

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

Секретные шифры являются неотъемлемой принадлежностью многих детективных романов, в которых действуют изощренные в хитрости шпионы. Писатель-романтик Эдгар По, которого иногда причисляют к создателям детективного жанра, в своем рассказе "Золотой жук" в художественной форме изложил простейшие приемы шифрования и расшифровки сообщений. Эдгар По относился к проблеме расшифровки оптимистически, вложив в уста своего героя следующую фразу: "...едва ли разуму человека дано загадать та кую загадку, которую разум другого его собрата, направленный должным образом, не смог бы раскрыть. Прямо скажу, если текст зашифрован без грубых ошибок и документ в приличной сохранности, я больше ни в чем не нуждаюсь; последующие трудности для меня просто не существуют". Столетие спустя это высказывание было опровергнуто ученым, заложившим основы теории информации, Клодом Шенноном. Шеннон показал, как можно построить криптограмму, которая не поддается никакой расшифровке, если, конечно, не известен способ ее составления.

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

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

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

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

Двоичное кодирование тесно связано с принципом дихотомии (деления пополам). Поясним этот принцип на примере.

Некто задумал число, заключенное между 0 и 7. Угадывающему разрешено задавать вопросы, ответы на которые даются лишь в форме "да" или "нет". Каким образом следует задавать вопросы, чтобы возможно быстрее узнать задуманное число?

Самый бесхитростный путь - перебирать числа в любом порядке, надеясь на удачу. В этом случае при везении может хватить и одного вопроса, но если не повезет, то может понадобиться и целых семь. Поэтому не будем рассчитывать на везение и постараемся построить такую систему вопросов, чтобы любой из ответов - "да" или "нет" - давал нам одинаковую (пусть сначала и неполную) информацию о задуманном числе. Например, первый вопрос может быть таким: "Заключено ли задуманное число в пределах от 0 до 3?" Оба ответа - и "да" и "нет" - одинаково приближают нас к цели: в любом случае остаются четыре возможности для неизвестного числа (а первоначально их было восемь).

Если на первый вопрос получен утвердительный ответ, то во второй раз можно спросить: "Не является ли задуманное число нулем или единицей?"; если же ответ был отрицательным, спросим: "Не является ли задуманное число четверкой или пятеркой"? В любом случае после ответа на второй вопрос останется выбор из двух возможностей. Для того чтобы его осуществить, достаточно одного вопроса. Итак, для угадывания задуманного числа, каким бы оно ни было, достаточно трех вопросов (каждый из них выясняет, содержится ли задуманное число в "нижней" половине заключающего его промежутка). Можно показать, что меньшего числа вопросов недостаточно.

Если возможные ответы "да" или "нет" обозначить условно символами 0 и 1, то ответы запишутся в виде последовательности, состоящей из нулей и единиц. Так, например, если задуманное число было нулем, то на каждый из трех вопросов ответом будет "да". Трем "да" соответствует последовательность 000.

Если было задумано число 3, то ответами будут "да", "нет", "нет", т. е. числу 3 соответствует последовательность 011. По результатам ответов можно составить следующую таблицу:

Таблица 1

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

Заметим, что вместо множества чисел от 0 до 7 можно рассматривать любое множество из восьми сообщений, и каждое из них мы можем закодировать последовательностями из нулей и единиц длины 3. Если использовать более длинные двоичные последовательности, то ими в принципе можно закодировать любое конечное множество сообщений.

Действительно, число двоичных последовательностей длины 3 равно 2³ = 8 (все они приведены в таблице 1), двоичных последовательностей длины 4 вдвое больше - число их равно 2⁴ = 16. Вообще, число двоичных последовательностей длины n равно 2ⁿ. Поэтому, если требуется закодировать нулями и единицами, к примеру, 125 сообщений, то для этого с избытком хватит двоичных последовательностей длины 7 (их в нашем распоряжении имеется 2⁷ = 128). Из этого примера становится ясно, что М сообщений можно закодировать двоичными последовательностями длины п тогда и только тогда, когда выполняется условие 2ⁿ ≥ М, т. е. когда n ≥ log₂M.

Первый, кто понял, что для кодирования достаточно двух символов, был Фрэнсис Бэкон. Двоичный код, который он использовал в криптографических целях, содержал пятиразрядные (как и в коде Бодо) слова, составленные из символов 0, L.

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