Кодирование информации

Определение:

Кодирование информации — отображение данных на кодовые слова.

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

Код

Определение:

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

Пусть [math]U[/math] — множество исходных символов, [math]Z[/math] — кодовый алфавит, [math]Z^*[/math] — строчки из [math]Z[/math]. 
Код — отображение [math]c : U \rightarrow Z^*[/math]. [math]c^* : U^* \rightarrow Z^*[/math]. [math]c^*(x_1 x_2 ... x_n) = c(x_1)c(x_2)..c(x_n)[/math]

Виды кодов

• Код фиксированной длины (fixed-length code) — кодирование каждого символа производится с помощью строк одинаковой длины. Также он называется равномерным или блоковым кодом.

Утверждение:

Любой равномерный код является взаимно однозначным.

• Код переменной длины (variable-length code) — кодирование производится с помощью строк переменной длины. Также называется неравномерным кодом.
• Разделимый код (однозначно декодируемый) — код, в котором никаким двум словам кодируемого алфавита не может быть сопоставлен один и тот же код.
• Префиксный код — код, в котором, никакое кодовое слово не является началом другого.

Утверждение:

Любое префиксное кодирование является взаимно однозначным.

• Постфиксный код (суффиксный) — код, в котором никакое кодовое слово не является концом другого.

Утверждение:

Любое постфиксное кодирование является взаимно однозначным.

Примеры кодов

• Азбука Морзе
• ASCII

Однозначно декодируемый код

Определение:

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

Пусть есть код заданный следующей кодовой таблицей.
[math]a_1 \rightarrow b_1[/math]; [math]a_2 \rightarrow b_2[/math]; ... [math]a_k \rightarrow b_k[/math];
Составим слово из кодов с использование операции конкатенации:
[math]b_{i_1} b_{i_2} ... b_{i_n} = b_{j_1} b_{j_2} ... b_{j_m}[/math]
В этом случае, если код однозначно декодируемый, то [math]n = m[/math] и выполняется равенство:
[math]b_{i_1} = b_{j_1}[/math]; [math]b_{i_2} = b_{j_2}[/math]; ... [math]b_{i_n} = b_{j_m}[/math]; 

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

Определение:

Слово [math]\bar{b} \in B^*[/math] называется неприводимым, если [math]\bar{b}[/math] декодируется неоднозначно, однако, при выбрасывании из [math]\bar{b}[/math] любого связного непустого куска получается слово, которое декодируется не более, чем одним способом.

Где [math]B[/math] — кодовый алфавит, а [math]B^*[/math] — строчки (слова) из [math]B[/math].

Теорема (Марков А.А.):

Пусть [math]\phi : a_i \rightarrow B_i \ (i = 1,2,..,r)[/math] - некоторое кодирование. Пусть [math]W[/math] — максимальное число кодовых слов, которые "помещаются" подряд внути кодового слова. Пусть [math]l_i[/math] - длина слова [math]B_i[/math] и [math]L = \sum_{i=1}^r l_i[/math]. Тогда если кодирование [math]\phi[/math] не взаимно однозначно, то существуют два различных слова [math]a' \in A^*[/math], [math]a'' \in A^*[/math], [math]|a'| \leqslant \left \lfloor \frac{(W+1)(L-r+2)}{2} \right \rfloor[/math], [math]|a''| \leqslant \left \lfloor \frac{(W+1)(L-r+2)}{2} \right \rfloor[/math] и [math]\phi (a') = \phi (a'')[/math]

Доказательство:

[math]\triangleright[/math]

Пусть [math]\phi[/math] не является взаимно однозначным. Тогда существует некоторое слово [math]\bar{b_1}[/math], которое допускает две расшифровки. Если слово [math]\bar{b_1}[/math] не является неприводимым, то выбрасывая из [math]\bar{b_1}[/math] куски несколько раз, получим неприводимое слово [math]\bar{b}[/math]; иначе, положим [math]\bar{b} = \bar{b_1}[/math]. Очевидно, это всегда можно сделать. Рассмотрим любые две декодировки слова [math]\bar{b}[/math]. Разрежем слово [math]\bar{b}[/math] в концевых точках кодовых слов каждого из разбиений. Слова нового разбиения разделим на два класса: к I классу отнесём слова, являющиеся элементарными кодами, а ко II классу — все остальные слова (то есть слова, являющиеся началами кодовых слов одного разбиения и концами слов второго разбиения). Лемма: Если [math]\bar{b}[/math] — неприводимое слово, то все слова [math]\beta_1, \beta_2,..,\beta_m[/math] II класса различны. Доказательство: [math]\triangleright[/math] Пусть [math]\beta' = \beta''[/math]. Тогда, очевидно, слово [math]\bar{b}[/math] не будет неприводимым, поскольку при выкидывании отрезка между [math]\beta'[/math] и [math]\beta''[/math], вместе с любым из этих слов, получим снова две различные расшифровки этого слова. [math]\triangleleft[/math] Таким образом, все [math]\beta_1, \beta_2,..,\beta_m[/math] разные. Тогда число слов второго класса не превосходит числа непустых начал элементарных кодов, то есть не превосходит [math](l_1 – 1) + (l_2 – 1) + ... + (l_r – 1) = L – r[/math]. Слова из второго класса разбивают слово не более чем на [math]L – r + 1[/math] кусков. Рассмотрим пары соседних кусков. Тогда согласно одному разбиению в одной половинке уложится не более одного кодового слова, а в другой — не более [math]W[/math] (согласно второму разбиению ситуация симметрична). Всего пар кусков не больше, чем [math]\left \lceil \frac{L-r+1}{2} \right \rceil \leqslant \frac{L-r+1}{2}[/math], а в каждом из них укладывается слов не более чем [math]W + 1[/math]. Отсюда число кодовых слов в любом разбиении не превосходит [math]\frac{L-r+1}{2}[/math][math](W+1)[/math], а поскольку число целое, то не превосходит и целой части [math]\left \lfloor \frac{(W+1)(L-r+2)}{2} \right \rfloor[/math]. Теорема доказана.

[math]\triangleleft[/math]

Не префиксный и не постфиксный однозначно декодируемый код

Пример:

[math]U = \mathcal {f} a, b, c \mathcal {g}[/math]; [math]Z = \mathcal {f} 1, 2, 3 \mathcal {g}[/math];
[math]c(a) = 1; c(b) = 12; c(c) = 31;[/math]
Возьмём кодовую строку: [math]Z^* = (11212311)[/math]
Мы можем ее однозначно декодировать, т.к. знаем, что слева от двойки и справа от тройки всегда стоит единица.

Алгоритм декодировки:

1. Найдем в кодовой строке все двойки и заменим последовательность [math]Z^*(12)[/math] на символ [math]b[/math]
2. Найдем в кодовой строке все тройки и заменим последовательность [math]Z^*(31)[/math] на символ [math]c[/math]
3. Все оставшиеся единички декодируем как символ [math]a[/math]

В таком случае получаем:

[math]abbca[/math]

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

Префиксный код

Определение:

Префиксный код — код, в котором никакое кодовое слово не является префиксом какого-то другого кодового слова.

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

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

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

Пример:

[math]U = \mathcal {f} a, b, c \mathcal {g}[/math]; [math]Z = \mathcal {f} 0, 1 \mathcal {g}[/math]
[math]c(a) = 00; c(b) = 01; c(c) = 1;[/math]
Закодируем строку: [math]abacaba[/math]
[math]c^*(abacaba) = 0001001000100[/math]

Такой код можно однозначно разбить на слова:

[math]00\ 01\ 00\ 1\ 00\ 01\ 00[/math]

поэтому он является префиксным.

Недостатки префиксных кодов

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

Предположим, что предыдущая последовательность передалась неверно и стала:
[math]0001001'1'00100[/math]
Разобьем ее согласно словарю:
[math]00\ 01\ 00\ 1\ 1\ 00\ 1\ 00[/math]
[math]a\quad b\quad a\ c\ c\quad a\ c\ a[/math]

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

• Необходимость хранить словарь декодировки символов.

Примеры префиксных кодов

• Код Хаффмана
• Код Шеннона-Фано

См. также

• Представление символов, таблицы кодировок
• Неравенство Крафта
• Неравенство Макмиллана

Литература

• Томас Кормен, Чарльз Лейзерсон, Рональд Ривест, Клиффорд Штайн. Алгоритмы. Построение и анализ — Издательство: «Вильямс», 2011 г. - 1296 стр. — ISBN 978-5-8459-0857-5, 5-8459-0857-4, 0-07-013151-1
• Джеймс Андерсон. Дискретная математика и комбинаторика — Издательство: «Вильямс», 2004 г. - 960 стр. — ISBN 978-0-13-086998-2
• Новиков. Ф.А. Дискретная математика для программистов — Издательство: «Питер», 2001 г. - 304 стр. — ISBN 5-94723-741-5 978-5-94723-741-2