Задачи, решаемые посредством кодирования:

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

2. Защита информации от несанкционированного доступа.

3. Обеспечение помехоустойчивости при передаче данных по каналам связи.

4. Сжатие информации.

5. Трансляция и компиляция кода программ.

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

$1.1. Понятие кодирования.

Пусть A={ a₁, a₂, …, a_n} - конечное упорядоченное множество символов, называемое алфавитом. Под словом в алфавите A будем понимать любую конечную последовательность символов из A. Длиной слова назовем количество букв его составляющих.

Обозначим через A* - множество слов в алфавите A.

Кодом назовем любую конечную совокупность слов {x₁, x₂, ... , x_k} в некотором алфавите A.

Определение. Кодирование - операция отождествления символов или групп символов одного кода с символами или группами символов другого кода.

Пример. Арабская запись целых чисел  формат integer.

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

Пусть A,B – алфавиты, S – конечная последовательность слов в алфавите А. Назовем S сообщением.

Тогда с математической точки зрения кодирование - отображение F: S->B*.

Если |B|=m, то мы имеем m-ичное кодирование. Например, B={0,1}, m=2, – имеем двоичное кодирование.

Функция F^-1,если существует, называется декодированием.

Типичная задача кодирования - при данных алфавитах А и В и множестве сообщений S, найти такое кодирование F, которое обладает определенными свойствами и оптимально в некотором смысле.

В качестве основных свойств кодирования назовем следующие:

- существование декодирования;

- помехоустойчивость или исправление ошибок: функция декодирования обладает таким свойством, что F^-1(b)=F^-1(b’) , если b’ в определенном смысле близко к b;

- заданная сложность или простота кодирования и декодирования. Например в криптографии(шифровании) изучаются такие функции F, что F – достаточно простая функция, а F^-1 требует очень сложных вычислений.

$1.2. Алфавитное кодирование

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

Таким образом, АК задается схемой r = {a₁ => x₁, a₂=>x₂, ... , a_k=>x_k}, где А={a₁, a₂, ... , a_k} – алфавит, x_i – элементарные коды.

Примеры.

1. A={0,1,2,...,9}, B={0,1}

r = (1=>1, 2=>10, 3=>101, ..., 9=>1001) – неоднозначна: F_r(333)=F_r(77)

2. A={0,1,2,...,9}, B={0,1}

r = (1=>0001, 2=>0010, 3=>0101, ..., 9=>1001) – двоично- десятичное кодирование.

Понятия: равномерное кодирование – кодирование, при котором длины элементарных кодов букв равны.

$ 1.3. Разделимые и префиксные схемы кодирования

Схема кодирования(код) называется разделимой, если любое слово, составленное из элементарных кодов, единственным образом разлагается на элементарные коды.

Схема кодирования(код) называется префиксной, если элементарный код каждой буквы не является началом(префиксом) элементарного кода другой буквы. Так, код {a,bc,cc} является префиксным, в отличие от кода {a,ab,cc}.

Если рассматривать префиксный код в двоичном алфавите, т.е. в алфавите, состоящем из двух символов, то такой код называется двоичным (или бинарным) префиксным кодом. Например, префиксный код {+,--,-+} является двоичным.

Ниже будем рассматривать только бинарные схемы кодирования. В дальнейшем слово "бинарные" может быть опущено.

Как же можно получить префиксные коды? Существует несколько методов. Мы рассмотрим метод двоичных деревьев, метод Левенштейна, кодирование Хаффмена.

Бинарные деревья и бинарные префиксные коды.

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

Справедливо утверждение. Префиксная схема является разделимой.