Кодирование информации — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
м (информация не мусор)
Строка 1: Строка 1:
'''Кодирование информации''' — процесс преобразования информации из одной формы в другую.
+
{{Определение
 +
|id=def1
 +
|definition='''Кодирование информации''' — процесс преобразования информации из одной формы в другую.
 +
}}
 
Обычно в процессе кодирования информация преобразуется из формы, удобной для непосредственного использования, в форму, удобную для передачи, хранения или автоматической обработки.
 
Обычно в процессе кодирования информация преобразуется из формы, удобной для непосредственного использования, в форму, удобную для передачи, хранения или автоматической обработки.
 
В более узком смысле кодированием информации называют представление информации в виде кода.
 
В более узком смысле кодированием информации называют представление информации в виде кода.
Строка 5: Строка 8:
  
 
== Код ==
 
== Код ==
 
+
{{Определение
'''Код''' — правило (алгоритм) сопоставления каждому конкретному сообщению строго определённой комбинации символов (знаков или сигналов). Кодом также называется отдельная комбинация таких символов (знаков) — слово. Для различия этих терминов, код в последнем значении ещё называется ''кодовым словом''.
+
|id=def2
 
+
|definition='''Код''' — правило (алгоритм) сопоставления каждому конкретному сообщению строго определённой комбинации символов (знаков или сигналов). Кодом также называется отдельная комбинация таких символов (знаков) — слово. Для различия этих терминов, код в последнем значении ещё называется ''кодовым словом''.
'''Код фиксированной длины''' (fixed-length code) {{---}} кодирование каждого символа производится с помощью строк одинаковой длины. Также он называется ''равномерным'' или ''блоковым'' кодом.
+
}}
 
+
==== Виды кодов ====
'''Код переменной длины''' (variable-length code) {{---}} кодирование производится с помощью строк переменной длины. Также называется ''неравномерным кодом''.
+
* '''Код фиксированной длины''' (fixed-length code) {{---}} кодирование каждого символа производится с помощью строк одинаковой длины. Также он называется ''равномерным'' или ''блоковым'' кодом.
 
+
* '''Код переменной длины''' (variable-length code) {{---}} кодирование производится с помощью строк переменной длины. Также называется ''неравномерным кодом''.
'''Разделимый код''' {{---}} код, в котором любое слово, составленное из элементарных кодов, единственным образом разлагается на элементарные коды.
+
* '''Разделимый код''' {{---}} код, в котором любое слово, составленное из элементарных кодов, единственным образом разлагается на элементарные коды.
  
 
==== Примеры кодов ====
 
==== Примеры кодов ====
Строка 19: Строка 22:
  
 
== Префиксный код ==
 
== Префиксный код ==
 +
{{Определение
 +
|id=def3
 +
|definition='''Префиксный код''' — код, в котором никакое кодовое слово не является префиксом какого-то другого кодового слова.
 +
}}
  
'''Префиксный код''' — код, в котором никакое кодовое слово не является префиксом какого-то другого кодового слова.
 
 
Любой префиксный код является однозначно декодируемым и разделимым. Также префиксный код иногда называют ''мнгновенным кодом''.
 
Любой префиксный код является однозначно декодируемым и разделимым. Также префиксный код иногда называют ''мнгновенным кодом''.
 
 
Оптимальное сжатие данных, которого можно достичь с помощью кодов, всегда достижимо при использовании префиксного кода.
 
Оптимальное сжатие данных, которого можно достичь с помощью кодов, всегда достижимо при использовании префиксного кода.
  
Строка 57: Строка 62:
 
* Код Шеннона-Фано  
 
* Код Шеннона-Фано  
 
* UTF-8 {{---}} префиксный, так как является блоковым.
 
* UTF-8 {{---}} префиксный, так как является блоковым.
 
== Ссылки ==
 
* [http://ru.wikipedia.org Википедия — свободная энциклопедия]
 
  
 
== Литература ==
 
== Литература ==

Версия 23:11, 19 ноября 2011

Определение:
Кодирование информации — процесс преобразования информации из одной формы в другую.

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

Код

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

Виды кодов

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

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

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

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

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


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

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

Рассмотрим пример кодирования с помощью префиксного кода.

Пусть U — множество исходных символов, Z — кодовый алфавит, Z* — строчки из Z. 
Код — отображение c : U [math]\rightarrow[/math] Z*. c* : U* [math]\rightarrow[/math] Z*. c*(x1x2..xn) = c(x1)c(x2)..c(xn)
U = {a,b,c}; Z = {0,1};
c(a) = 00; c(b) = 01; c(c) = 1;
Закодируем строку: abacaba
c*(abacaba) = 0001001000100

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

00 01 00 1 00 01 00

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

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

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

Пример:

Возьмём строку abacaba, и закодируем ее аналогично предыдущему примеру.
c*(abacaba) = 0001001000100
Предположим, что последовательность передалась неверно и стала:
0001001100100
Разобьем ее согласно словарю:
00 01 00 1 1 00 1 00
a  b  a  c c a  c a

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

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

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

  • Код Хаффмана
  • Код Шеннона-Фано
  • UTF-8 — префиксный, так как является блоковым.

Литература

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