Кодирование информации
Определение: |
Кодирование информации — отображение данных на кодовые слова. |
Обычно в процессе кодирования информация преобразуется из формы, удобной для непосредственного использования, в форму, удобную для передачи, хранения или автоматической обработки. В более узком смысле кодированием информации называют представление информации в виде кода. Средством кодирования служит таблица соответствия знаковых систем, которая устанавливает взаимно однозначное соответствие между знаками или группами знаков двух различных знаковых систем.
Содержание
Код
Определение: |
Пусть Код (англ. code) — отображение и так, что | — множество исходных символов, — кодовый алфавит, — множество всех строк конечной длины из .
Виды кодов
- Код фиксированной длины (англ. fixed-length code) — кодирование каждого символа производится с помощью строк одинаковой длины. Также он называется равномерным или блоковым кодом.
- Код переменной длины (англ. variable-length code) — кодирование производится с помощью строк переменной длины. Также называется неравномерным кодом.
- Префиксный код — код, в котором, никакое кодовое слово не является началом другого. Аналогично, можно определить постфиксный код — это код, в котором никакое кодовое слово не является концом другого.
Все вышеперечисленные коды являются однозначно декодируемыми — для такого кода любое слово, составленное из кодовых слов, можно декодировать только единственным способом.
Примеры кодов
- ASCII — блочный.
- Код Хаффмана (англ. Huffman code) — префиксный.
- Азбука Морзе — не является ни блочным, ни префиксным, тем не менее, однозначно декодируемый засчет использования пауз.
Однозначно декодируемый код
Определение: |
Однозначно декодируемый код (англ. uniquely decodable code) — код, в котором любое слово составленное из кодовых слов можно декодировать только единственным способом. |
Пусть есть код заданный следующей кодовой таблицей:
Код является однозначно декодируемым, толька тогда, когда для любых строк, составленных из кодовых слов, вида:
Всегда выполняются равенства:
и ; ; ... ;
Заметим, что если среди кодовых слов будут одинаковые, то однозначно декодировать этот код мы уже не сможем.
Префиксный код
Определение: |
Префиксный код (англ. prefix code) — код, в котором никакое кодовое слово не является префиксом какого-то другого кодового слова. |
Предпочтение префиксным кодам отдается из-за того, что они упрощают декодирование. Поскольку никакое кодовое слово не выступает в роли префикса другого, кодовое слово, с которого начинается файл, определяется однозначно, как и все последующие кодовые слова.
Пример кодирования
;
Закодируем строку:
Такой код можно однозначно разбить на слова:
Преимущества префиксных кодов
- Однозначно декодируемый и разделимый
- Удается получить более короткие коды, чем с помощью кода фиксированной длины.
- Возможности декодировки сообщения, не получая его целиком, а по мере его поступления.
Недостатки префиксных кодов
- При появлении ошибок в кодовой комбинации, при определенных обстоятельствах, может привести к неправильному декодированию не только данной, но и последующей кодовой комбинации, в отличии от равномерных кодов, где ошибка в кодовой комбинации приводит к неправильному декодированию только ее.
Пример неудачного декодирования
Предположим, что последовательность
из примера передалась неверно и стала:
Разобьем ее согласно словарю:
Полученная строка совпадает только в битах, которые находились до ошибочного, поэтому декодирование неравномерного кода, содержащего ошибки, может дать абсолютно неверные результаты.
Не префиксный однозначно декодируемый код
Как уже было сказано, префиксный код всегда однозначно декодируем. Обратное в общем случае неверно:
; ;
Закодируем
, получим кодовую строку Мы можем ее однозначно декодировать, так как знаем, что слева от двойки и справа от тройки всегда стоит единица.После декодирования получаем:
См. также
Источники информации
- 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 семестр)»