Элементы теории кодирования

ify">     Исследованием и разработкой математических методов конфиденциальной информации, передаваемой отправителем получателю по общедоступным каналам связи, занимается криптология, одной из составляющих которой является криптография. Криптография разрабатывает методы защиты информации, т.е. представляет один из классов кодирования с целенаправленным изменением открытого текста, которое затрудняет получение содержащейся в нем конфиденциальной информации. 
 
 
 

§ 2. Алфавитное кодирование

2. 1. Понятие алфавитного кодирования

      В различных задачах, связанных с обработкой, передачей и хранением информации, а также в связи с потребностями техники возникает необходимость преобразования информации в более удобной форме. Кодирование, применяемое для этих целей, называется алфавитным кодированием. Алфавитное кодирование — это представление информации в стандартной форме, при которой элементарным синтаксическим единицам языка сообщений (буквам алфавита) последовательно сопоставляются кодовые комбинации символов из некоторого заданного алфавита. Под информацией здесь понимаем линейную последовательность букв (слова). Примером алфавитного кодирования может служить известный код Морзе (азбука Морзе), в котором слова кодируются побуквенно. А буквам сопоставляются слова в алфавите из трех символов {•, —, ˄}, где ˄ — пробел.

     Другим примером алфавитного кодирования является десятичная система счисления.

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

2. 2. Математическое изучение алфавитного кодирования

     Пусть задан алфавит сообщений А = {а₁,a₂, ...,a_n}, состоящий из конечного числа букв: конечное множество. Конечная последовательность букв из А α = а_i1a_i2…a_ik называется словом в алфавите А, а число k — длиной слова а; если k = 0, то слово называют пустым и обозначают ˄.

     Множество всех непустых слов конечной длины в алфавите А обозначим через А*.

     Если S — подмножество множества А*, то слова из S называются сообщениями, а объект, порождающий слова из S, — источником сообщений. Источником сообщений может быть человек, автомат и т. д.

      Пусть, кроме алфавита А, задан еще алфавит В = {b₁, b₁,…, b_т}. Зададим отображение f, которое каждому слову α ϵ S ставит в соответствие словоβϵ В*, где В* — множество всех непустых слов конечной длины в В.

     Слово β будем называть кодом сообщения α, а процесс перехода от слова α к слову β — кодированием.

     Алфавитное кодирование определяется следующим образом. В множестве В* выбираются некоторым образом r слов β₁ , β₂ ,…,β_r , называемых элементарными кодами.

      По определению получаем, что f(a_i) = β_i , i = 1, 2,…,r. Тогда код любого слова α = a_i1a_i2…a_ik ϵ A* есть следующее слово:

   Β(α) = f(a_i1)f(a_i2)…f(a_ik) =  β_i1β_i2…β_ip.

      Схема, определяющая отображение f на буквах алфавита А, называется схемой кодирования, обозначается ∑ и оформляется в виде таблицы:

 

     Множество кодовых слов {β₁, β₂,…, β_r} будем обозначать С(∑).

   2. 3. Проблема взаимной однозначности

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

     Возникает вопрос: возможно ли по схеме алфавитного кодирования узнать, обладает ли алфавитное кодирование свойством однозначности или нет? Если решать эту задачу, исходя из определения, то нужно перебрать бесконечное число слов, так как для каждого кода нужно установить, допускает или не допускает этот код однозначное кодирование. 

2. 4. Достаточный признак взаимной однозначности алфавитного кодирования

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

        Введем следующие понятия.

     Если β = β҆ β”, то β҆ называется началом, или постфиксом, слова β.

     Если β҆ ≠ ˄, то β҆ называется собственным началом.

     Если β” ≠˄, то β” называется собственным окончанием слова β.

        Определение: алфавитного кодирования обладает свойствами префикса, если ни один элементарный код не является префиксом другого  элементарного кода.

       Теорема 1: Если схема ∑ алфавитного кодирования обладает свойством префикса, то алфавитное кодирование взаимно однозначно.

Доказательство: Допустим, что некоторое слово β ϵ В* допускает два декодирования. Это значит, что β можно представить в двух видах: β₁ = β_i1 β_i2 … β_ik; β₂ = β_j1 β_j2 … β_jl.

      Так как эти представления различны, то существует такое р, что 1 ≤ р ≤ min(k, l), для которого β_ip ^ β_ip. Но тогда одно из слов β₁ и β₂ есть префикс другого. Это противоречит условию теоремы. Следовательно, наше утверждение о существовании двух декодирований неверно. Теорема доказана.

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

     Определение: Слово b_in b_in-1… b_i1 будем называть обратным к слову β = b_i1b_i2b_in и обозначать β^-1.

     Определение: Схема кодирования, полученную из схемы кодирования ∑{β₁,…, β_r} заменой каждого элементарного кода β_i на  β_i^-1,будем называть обратной к схеме ∑ и обозначать ∑^-1. Введённое понятие позволяет усилить теорему 1.

     Теорема 2: Если схема ∑ или схема ∑^-1 обладает свойством префикса, то тогда алфавитное кодирование, определяемое схемой ∑(∑^-1), будет взаимно однозначным.

      Доказательство: Очевидно, что алфавитные кодирования, задаваемые схемами Z и Z^-1, одновременно или обладают, или не обладают свойством взаимной однозначности. Отсюда немедленно следует справедливость теоремы 2.

      Заметим, что условие теоремы 2 не является необходимым, так как существуют схемы кодирования ∑, со свойством взаимной однозначности, но такие, что ни ∑, ни ∑^-1 не обладают свойством префиксности.

   2. 5. Общий критерий взаимной однозначности

     Для вывода общего критерия взаимной однозначности понадобится 
следующее понятие. 

     Представление элементарного кода Р; схемы алфавитного кодирова- 
ния ∑ в виде β_i = β҆ β_i1… β_ik β”, где слово β҆ не может оканчиваться на элементарный код, а слово Р" начинаться с элементарного кода, будем называть нетривиальным разложением элементарного кода. При этом одно из слов β҆ или β” может быть пустым (˄).

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

1. Для каждого элементарного кода выписываем все нетривиальные 
   разложения.
2. Выписываем множество М₁, состоящее из слов β҆, которые входят 
   в качестве начал в нетривиальные разложения элементарных кодов.
3. Выписываем множество М₂, состоящее из всех слов β”, которые 
   являются окончанием нетривиальных разложений элементарных кодов.
4. встречающихся как в качестве начала, так и в качестве окончания в не 
   тривиальных разложениях элементарных кодов.
5. Выписываем все разложения элементарных кодов, связанных с 
   множеством М, т. е. все разложения элементарных кодов вида:                       β_i = β҆ β_i1… β_ik β”, где β҆, β" ϵ М, a k может быть равно 0.   

6. По разложениям, полученным в пункте 5, строится ориентиро- 
ванный граф G_∑ следующим образом. Вершины графа отождествляют с 
элементами множества М. Пара вершин β' и β" соединяются ориентиро- 
ванными ребрами в том и только в том случае, если существует разло- 
жение β'β_i1…β_ikβ". При этом ребру (β',β") приписывается слово β_i1…β_ik, 
соответствующее этому разложению.

7. По полученному графу G_∑ легко проверить, обладает или нет исход- 
ная схема кодирования свойством взаимной однозначности.

  Справедлива следующая теорема.

     Теорема 3: Алфавитное кодирование со схемой ∑ не обладала свойством взаимной однозначности тогда и только тогда, когда граф G_∑ содержит ориентированный цикл (контур), проходящий через вершину ˄. Т.е. алфавитное кодирование является взаимно однозначным тогда и только тогда, когда в графе G_∑ отсутствуют контуры и петли, проходящие через вершины ˄.

     Замечание: Напомним, что если схема алфавитного кодирования ∑ не обладает свойством взаимной однозначности, то это означает, что существуют слова из В*, допускающие два кодирования. Одно из таких слов β легко находится по графу _∑.

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

§ 3. Двоичный алфавит

   3. 1. Понятие двоичного алфавита

     В современных компьютерах любая информация представляется в виде двоичных кодов, т. е. упорядоченных наборов двух различных символов, которые обычно обозначаются через 0 и 1. Таким образом, алфавит, в котором записываются сообщения, считаем состоящим из двух символов {0,1}. Он называется двоичным алфавитом.

      Тогда сообщение есть конечная последовательность символов этого алфавита.

     Это простейшее алфавитное кодирование, которое является взаимнооднозначным, так как каждому символу исходного алфавита ставится в соответствие определенное двоичное число.

                            A = a_n2^n-1 + a_n-12^n-2 + a_n-22^n-3 + …+ a₂2¹ + a₁2⁰ ,                     где: a_0, a₁, a₂,…, a_n – цифры, n – количество цифр в записи числа.

         Например, натуральному числу 23 соответствует двоичное число 10111,поскольку

23 = 1 • 2⁴ + 0 • 2³ + 1 • 2² + 1 • 2¹ + 1 • 2°.

      Полезно запомнить запись в двоичной системе первых шестнадцати натуральных чисел