3.1     Основные определения. Примеры кодов

Рассмотрим множество А = {а\,..., ап}, состоящее из п элементов. Мно­жество А назовем алфавитом объема п, а его элементы будем называть символами или буквами алфавита. Например, русские буквы образуют ал­фавит объема 33, а латинские буквы составляют алфавит объема 27. По­следовательность из букв алфавита А длины га щг ... щт назовем словом длины га.

Определение [12]. Любое непустое множество слов, записанное в алфа­вите А, называется кодом в этом алфавите. Мощность этого множества называется объемом кода, а его элементы называются кодовыми словами. Код называется равномерным, если его кодовые слова имеют одинаковую длину га (га называется длиной равномерного кода).

Упражнение. Доказать, что объем равномерного кода длины га не превосходит пт = О'"1""'".

Пусть X = {х\,..., хе} - конечное множество. Скажем, что X является дискретным ансамблем сообщений, если на X задано распределение веро­ятностей р{х). т.е. каждому элементу х-, £ X.       у < с. сопоставлено число

_ е

/у(:/;/). При этом /у(;/;/) > 0, г = 1,е и ^ /->(•''/) = 1. Каждому подмножеству

г=\

У С X сопоставим вероятность (число

Р(У) = ^Р(Х;

ж€ У

Определение [12]. Произвольное отображение

(р : X -ч> К

дикретного ансамбля X в код К алфавита А называется кодированием X.

Пример 1 [12]. Предположим, что на телеграфе имеется автоматическая обработка телеграмм, с объемом запоминающегося устройства, равным N двоичным ячейкам. Рассмотрим 2 способа кодирования телеграмм: побу-квенное и кодирование целых слов. В первом случае каждой букве русского алфавита (будем отождествлять буквы ь, ъ) ставится в соответствие слово длины 5 в алфавите {0,1}, равное номеру этой буквы в русском алфа­вите, который записывается в двоичной системе счисления. Например, а -ч» (00001), б -ч> (00010), в -ч> (00011), г -> (00100). Мы получаем однородное кодирование. Если допустить, что каждая телеграмма в среднем содержит 20 слов, а средняя длина слова 5 букв, то в запоминающее устройство мож­но записать N/500 телеграмм.

Во втором случае можно составить словарь из 213 = 8192 слов, которые обычно используются при составлении телеграмм. Каждому такому слову в русском языке можно поставить в соответствие слово длины 13 в алфа­вите {0,1}. Ясно, что в запоминающее устройство можно записать N/260 телеграмм (т.е. объем памяти запоминающего устройства при втором ко­дировании почти в два раза больше).

Определение [12]. Код называется декодируемым (или префиксным), если ни одно кодовое слово не совпадает с началом другого кодового слова.

Например, равномерный код декодируемый.

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

Рассмотрим несколько примеров кодирования слов русского языка.

Способ 1 (подстановочный шифр). Отождествим буквы е и ё, а также ь и ъ. Тогда мы получим алфавит, состоящий из 31 буквы. Если в романе Л.Н.Толстого "Война и мир" подсчитать частоту вхождения каждой буквы, то получится следующая таблица

N

Буква

Относительная частота

N

Буква

Относительная частота

1

а

0,062

18

с

0,045

2

б

0,014

19

т

0,053

3

в

0,038

20

У

0,021

4

г

0,013

21

ф

0,002

5

Д

0,025

22

X

0,009

6

е,ё

0,072

23

Ц

0,004

7

ж

0,007

24

ч

0,012

8

3

0,016

25

ш

0,006

9

и

0,062

26

Щ

0,003

10

й

0,010

27

ы

0,016

11

к

0,028

28

ь,ъ

0,014

12

л

0,035

29

э

0,003

13

м

0,026

30

ю

0,006

14

н

0,053

31

я

0,018

15

О

0,090

 

 

 

16

п

0,023

 

 

 

17

р

0,040

 

 

 

Из таблицы следует, что буква " о" наиболее встречаемая в русском тексте (достаточно большой длины). Это можно учитывать, например, при игре в "Поле чудес". Заметим также, что промежуток между словами имеет относительную частоту 0,175. Если рассмотреть инъективное отображение русского алфавита (с дополнительным символом, означающим промежу­ток между словами) в произвольное множество мощности > 32, а затем подставить в текст вместо каждой буквы его образ в этом множестве, томы получим подстановочную криптограмму, расшифровать которую лег­ко, исходя из нашей таблицы, если текст достаточно большой. Примером такого шифра является так называемый шифр Цезаря. Он состоит в сле­дующей кодировке букв алфавита: а->я, б->а, в->би т.д., т.е. вместо каждой буквы подставляем предшествующую ей в русском алфавите.

Упражнение. Закодировать шифром Цезаря фразу "математика ум в порядок приводит" (Ответ: лясдлясзйл тл б онпюгнй опзбнгзс).

Для расшифровки текста, закодированного шифром Цезаря, применя­ется "метод полосок". Каждая полоска состоит из выписанных верти­кально (подряд) букв русского алфавита. Далее, для расшифровки слова "лясдлясзйл" в нашем упражнении берутся десять полосок и прикладыва­ются друг к другу так, чтобы получить это слово. Ниже этого слова будет стоять ответ. Под шифром Цезаря понимается сдвиг алфавита не только на 1 букву назад, а на произвольное фиксированное число букв вниз или вверх. Например, следующая кодировка тоже называется шифром Цезаря: а —г, б —д, в —у, ... , ю —б, я —в, т.е образом каждой буквы является третья снизу от неё.

Способ 2 (перестановочный шифр). Данный способ предложен в работе Л.С.Хилла ("Concerning certain linear transformation apparatas of cryptog­raphy," Amer. Math. Monthly, v.38, 1931, p. 135-154; см. также [27]).

Предположим, что нам необходимо зашифровать сообщение

"встреча состоится через неделю". (3.1)

Поставим в соответствие каждой букве её номер в алфавите, а промежутку между словами число 32. Тогда нашему сообщению соответствует после­довательность чисел

3,18,19,17, 6, 24,1, 32,18,15,18,19,15,9,19, 18, 31,32, 24,6,17,6,8, 32,14,6, 5,6,12,30. (3.2)

Рассмотрим эту последовательность в кольце Z^- Возьмем в этом кольцепроизвольный обратимый элемент, например, 3 £ ^зг(3 • 11 = 1). Умножим каждый член этой последовательности на 3:

9, 22, 25,19,18,8, 3,32, 22,13, 22, 25,13, 27, 25,

22, 29, 32,8,18,19,18, 24, 32,10,18,15,18,4, 26. (3.3)

Таким образом, наше сообщение кодируется в виде

ихштсзв хмхшмышхэ зстсч йсосгщ (3-4)

Чтобы расшифровать сообщение (3.4), необходимо переписать его в виде (3.3), а затем умножить последовательность (3.3) на 11 = З^1 (в кольце ^32). Мы придем к последовательности (3.2). Подставляя вместо чисел соответствующие буквы, мы восстановим наш текст.

Усложним вышеприведенный метод, используя невырожденные матрицы над кольцом ^з2. Разобьем последовательность (3.2) на пары:

 

32

Умножим данные столбцы на матрицу А = I I £ М2(^з2), для

 

6 -7

которой существует обратная А   = е М2(^з2

3 2

Получим новую последовательность из столбцов 4\   / -3 \   / 20 \   / 2 \   / 13 \   / 9 13    '    30    ' 1-3    '     4     ' 28

 

 

(3.5)

-2 \   / 26 \   /   12   \   / 16 \   / 6  \   / 20 \ /10

3 ) ' ^ -4 ) ' ^ -15 ) ' \ 14 ) ' V 26 / ' V 21 ) ' V 16

Возвращаясь к буквам, мы получим следующую закодированную инфор мацию

гвэмуюбэмгиьовгтювщьлрпнещуфйп (3.6

Чтобы её расшифровать, надо знать матрицу А. Действительно, так как порядок А равен 2 х 2, то подставляя в (3.6) вместо букв их номера в алфавите и разбивая полученные числа на пары, мы получим стоблцы (3.5). Умножая эту последовательность столбцов на А^1 (слева), мы восстановим наш текст.

Мы можем усложнить данный метод, разбив нашу исходную последова­тельность чисел (номеров) на 6 столбцов

/ 3 \

18 19 17

V 6 /

/24\ 1

32 18

V15/

/ 18\

19 15 9

V19/

/ 18\

31 32 24

V 6 /

/17\

6 8

32 V14/

/ 6 \

5 6 12

V30/

а затем умножить слева на фиксированную обратимую матрицу из кольца -^5(^32)• Например, можно взять матрицу

А =

/ 1 1 1 1 1 \

0 1111

0 0 111

0 0 0 1 1

0 0 0 0 1

\

А~1 =

/

/ 1 31 о о о \

0 1 31 о о

0 0 1 31 о

0 0 0 1 31

0 0 0 0 1

\

/

Итак, для кодирования этим методом достаточно знать "ключевую" обра­тимую матрицу в кольце Mn{Z^i)i а количество букв и промежутков в тек­сте должно делиться на п.

Замечание. Известный пример "казнить нельзя помиловать" показыва­ет, что для более точного восприятия текста на русском языке необходимо ввести некоторые символы для точки и запятой. В этом случае мы будем работать над кольцом Z34.

Способ 3 (перестановочный код). Как отмечено в книге [27], ниже­следующий код был предложен в 1976 г. A.Shamir, L.Adleman, R.Rivest.

Рассмотрим естественную нумерацию букв русского алфавита:

а    б    в    ...  ю   я (интервал) 01  02  03  ...  30  31 00,

записывая каждый номер в виде пары цифр и обозначая интервал между словами парой 00. Предположим, что нам необходимо закодировать слово "наступать". Перепишем его, подставляя вместо букв их номера

140118192016011926. (3.7)

В исходном слове 9 букв. Выберем любое число г < 9. Например, г = 2. Разобьем последовательность (3.7) на блоки, состоящие из 2-х букв

1401,      1819,      2016,      0119,      2600. (3.8)

Пусть q - простое число большее любого 4-х значного числа. Выберем целое число в такое, что (.%•. у{(і)) = 1. Тогда существует натуральное число Ї такое, что в/; = 1(гаое^(д)). В частности, для любого числа гп, взаимно простого с д, имеем (/г*)' = и){тоа1а). Заменим каждое из 5 чисел в (3.8) на его 5-ю степень (по тооїа) :

(1401)*, (1819)*, (2016)*, (0119)*, (2600)* (3.9)

Мы получили искомую закодированную последовательность. Чтобы ее дешифровать, необходимо каждое число в (3.9) возвести в степень Ї (по тооїа). Конечно, в основе этого метода лежит теорема Ферма-Эйлера: а<р(я) = \(гпоаІа)і если (а, д) = 1. Вернемся к нашему примеру. Возьмем г = 1 и д = 101. Тогда <^(д) = 100 и в = З, Ї = 67. Имеем


143

= 17

(тоЛОІ)

І3

= 1

(тоЛОІ)

183

= 75

(тоЛОІ)

193

= 92

(тоЛОІ)

203

= 21

(тоЛОІ)

163

= 70

(тоЛОІ)

І3

= 1

(тоЛОІ)

193

= 92

(тоЛОІ)

263

= 2

(тоЛОІ)

Итак, кодированное сообщение принимает вид 17 01 75 92 21 70 0192 02. К сожалению, здесь мы не можем числа (пары цифр) заменить на буквы. Чтобы расшифровать его, необходимо возвести каждое число в степень 67 (по тооІІОІ). Ключом к данному шифру являются числа г, д, в и і.

Упражнение. Закодировать указанным методом слово "код", взяв г = 1,г = 2иг = 3.

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

п

У

ш

к

и

Н

4

5

6

2

1

3

3

Е

л

ь

м

А

н

О

в

л

А

У

р

Е

А

т

Ф

И

л

д

С

О

В

С

к

О

й

п

Р

Е

м

и

и

 

 

 

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

МАФВРЬЛТОПАУИСЕЗНРЛКМЕОДОИЛВАСЙИ,

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

Упражнение. Декодировать сообщение, пользуясь ключевым словом "ПУШКИН":

РСГЕАДЕЮМЖЧЗЬАНОЛСОПВОДАТРОЛВОЮЬОЗЯЫМСЯВ. ОТВЕТ:     ПОЗДРАВЛЯЮ С НОВЫМ ГОДОМ ЖЕЛАЮ СЧАСТЬЯ ЗДОРОВЬЯ.

Способ 5 (шифр Тритемиуса [1]). Рассмотрим нумерацию букв русско­го алфавита от 1 до 31. Выберем некоторое ключевое слово, например, "ПУШКИН". Чтобы закодировать некоторый текст, например, "Поздра­вляю Вас с днем рождения", рассмотрим запись:

ПОЗДРАВЛЯЮВАССДНЕМРОЖДЕНИЯ

ПУШКИНПУШКИНПУШКИНПУШКИНПУ.

Подставив вместо букв числа, получим таблицу:

 

 

16

15

8

5

17

1

3

12

31

30

3

1

18

 

16

20

25

11

9

14

16

20

25

11

9

14

16

 

18

5

14

6

13

17

15

7

5

6

14

9

31

20

25

11

9

14

16

20

25

11

9

14

16

20

Сложив соответствующие числа в первый и во второй строках (в кольце Zзl), получим последовательность чисел 1, 4, 2, 16, 26, 15, 19, 1, 25, 10, 12, 15, 3, 7, 30, 25, 15, 27, 2, 4, 1, 16, 15, 28, 25, 20.

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

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

Способ 6. Рассмотрим произвольное инъективное отображение <р рус­ского алфавита в N х N. Кодирование каждого слова заключается в замене каждой буквы х её образом <р(х). Например, пусть отображение <р задано в виде таблицы 6x6:

 

1

2

3

4

5

6

1

а

о

н

м

л

к

2

и

б

 

 

 

й

3

Р

я

в

Щ

 

и

4

с

ю

ы

г

ш

3

5

т

э

ь

ч

Д

ж

6

У

ф

X

Ц

 

е

Тогда слову "университет" соответствует упорядоченный набор пар ((6,1), (1,3), (3,6), (3,3), (6,6), (3,1), (4,1), (3,6), (5,1), (6,6),(5,1)) или чи-ело 61 13 36 33 66 31 41 36 51 66 51, по которому однозначно декодируется исходное слово, если, конечно, знать таблицу. Очевидно, что это подстано­вочный шифр.

Упражнение. Пользуясь вышеприведенной таблицей, расшифровать сообщение

14 11 51 66 14 11 51 36 16 11 64 11 31 36 64 11 13 11 61 16. ОТВЕТ: математика - царица наук.

Следующим примером может служить т.н. азбука Морзе - подстановоч­ный код, использущый алфавит объема 2 (точка, тире) и применяемый для телеграфных сообщений (придуман Самуэлем Морзе; при передаче точка соответствует кратковременному импульсу тока, тире соответствует дли­тельному импульсу тока).

Задача 1. Сколько существует двоичных слов длины п, не содержащих несколько нулей подряд?

УКАЗАНИЕ. Ясно, что нулей д = тг —т; < п/2. Удалив из каждого такого слова по одной единице между любыми соседними нулями, мы получим слово длины п — (д — 1), содержащее ровно д нулей. Это соответствие биективно. Поэтому искомое число равно С, = С'/1г/•

Задача 2. Используя код Цезаря, декодировать криптограмму:

елфиррлм феихоюм зиря носрофв н еиыиуц рсксеюи хцынл фхсво-леюфснс е вфосп риди л нгкгося ри тоюол плпсг цшсзлол е фгпцб жоцдя огкцул