КОДИРОВАНИЕ – ИСТОРИЯ И ПЕРВЫЕ ШАГИ

 

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

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

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

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

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

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

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

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

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

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

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

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

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

Таблица 1

Задуманное число	0	1	2	3	4	Б	6	7
Ответы	ООО	001	010	011	100	101	110	111

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

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

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

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

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

Задачи и дополнения

1. Часто по разным соображениям для кодирования сообщений используют не все последовательности в данном алфавите, а только некоторые из них, удовлетворяющие тем или иным ограничени­ям. Будем рассматривать, например, n-буквенные двоичные слова с фиксированным числом t единиц (или, как говорят, слова постоянного веса 0- Сколько всего таких слов — нетрудно подсчитать. Каждое из них получится, если мы выберем некоторым образом t позиций из п, и запишем в них единицы, а в остальных п—t позициях — нули. Значит, число всех слов постоянного веса совпадает с числом сочетаний из п элементов по t, т. е. равно

2. Сложнее найти число всех двоичных слов длины п, не содержа­щих несколько нулей подряд. Обозначим это число через s_n. Очевидно, Sj = 2, а слова длины 2, удовлетворяющие нашему ограничению, таковы: 10, 01, 11, т. е. S2=3. Пусть ctjOg .. . —такое слово из п сим­

волов. Если символ а_п—1, то Oj ctg .. . а„_х может быть произвольным (п—1)-буквенным словом, не содержащим нескольких нулей подряд. Значит, число слов длины п с единицей на конце равно s„-i-

Если же символ а„=0, то обязательно a_n_!=l, а первые п—2 сим­воламогут быть произвольными с учетом рассматривае­мого ограничения. Следовательно, имеется Sn—2 слов длины п с нулем на конце. Таким образом, общее число интересующих нас слов равно

Из полученного соотношения (подобные соотношения называют рекуррентными) легко можно найти числаs„ для любого п. Поскольку Sj и 4 известны, тои т. д.

Полученная последовательность чисел

2, 3, 5, 8, 13, 21, 34, ... ,

в которой каждый последующий член равен сумме двух предыдущих,— эго хорошо известный в математике ряд Фибоначчи. О многих интерес­ных свойствах чисел Фибоначчи и их разнообразных приложениях мож­но прочесть в популярной брошюре {21], а также в недавно изданной книге 16]. В частности, можно убедиться (см. 121]), что п-ый член ряда Фибоначчи вычисляется по формуле:

8. Соединим оба предыдущих ограничения и найдем число двоичных слов постоянного веса /, не содержащих нескольких нулей подряд.

Рассуждать можно так. Пусть q^ti—/— число иулей в рассматри­ваемых словах. В любом слове имеется q— 1 промежутков между бли­жайшими нулями, в каждом из которых находится одна или несколько единиц (см. рис. 1). Предполагается, конечно, что $<л/2. 6 протезом случае (при q>nl% нет ни одного слова без рядом стоящих нулей.

Если из каждого промежутка удалить ровно по одной единица, то получим слово длины п—9+1, содержащее q нулей. Легко ей деть,

что любое такое слово может быть получено указанным образом из не­которого (и притом только одного) n-буквенного слова, содержащего q нулей, никакие два из которых не стоят рядом. Значит, искомое число совпадает с числом всех слов длины п—0+1, содержащих ровно q нулей, т. е. равно (см. допол­нение 1)

4. Используя результаты дополнений 2, 3, убедиться в справедливости тождества:

(символ [п!2] означает наибольшее целое число, не превосходящее п/2).

5. При каком q число двоичных слов из дополнения 3 максимально?

6. Показать, что число всех п-буквенных d-нчных слов, в которых один из символов встречается фиксированное число t раз, равно c%(d—(ср. дополнение 1).

7. Обобщить результаты дополнений 2 и 3 применительно к Лично­му алфавиту.

Предлагаю ознакомиться с аналогичными статьями: