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

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

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

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

Код

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

Пусть [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 — блочный.
• Код Хаффмана (англ. Huffman code) — префиксный.
• Азбука Морзе — не является ни блочным, ни префиксным, тем не менее, однозначно декодируемый засчет использования пауз.

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

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

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

Пусть есть код заданный следующей кодовой таблицей.
[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]; 

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

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

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

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

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

Пример кодирования

[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]abacaba[/math] из примера передалась неверно и стала:

[math]c^{**}(abacaba) = 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]

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

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

Как уже было сказано, префиксный код всегда однозначно декодируем. Обратное в общем случае неверно:

[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]abbca[/math], получим кодовую строку [math]11212311[/math] Мы можем ее однозначно декодировать, так как знаем, что слева от двойки и справа от тройки всегда стоит единица.

После декодирования получаем:

[math]abbca[/math]

См. также

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

Источники информации

• Wikipedia — Prefix_code
• Томас Кормен, Чарльз Лейзерсон, Рональд Ривест, Клиффорд Штайн. «Алгоритмы. Построение и анализ» — «Вильямс», 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
• Алексеев В.Б. «Дискретная математика (II семестр)»