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

Материал из Викиконспекты
Перейти к: навигация, поиск
м (→‎См. также)
Строка 1: Строка 1:
 
{{Определение
 
{{Определение
 
|id=def1
 
|id=def1
−
|definition='''Кодирование информации''' — процесс преобразования информации из одной формы в другую.
+
|definition='''Кодирование информации''' — отображение данных на кодовые слова.
 
}}
 
}}
 
Обычно в процессе кодирования информация преобразуется из формы, удобной для непосредственного использования, в форму, удобную для передачи, хранения или автоматической обработки.
 
Обычно в процессе кодирования информация преобразуется из формы, удобной для непосредственного использования, в форму, удобную для передачи, хранения или автоматической обработки.
Строка 12: Строка 12:
 
|definition='''Код''' — правило (алгоритм) сопоставления каждому конкретному сообщению строго определённой комбинации символов (знаков или сигналов). Кодом также называется отдельная комбинация таких символов (знаков) — слово. Для различия этих терминов, код в последнем значении ещё называется ''кодовым словом''.
 
|definition='''Код''' — правило (алгоритм) сопоставления каждому конкретному сообщению строго определённой комбинации символов (знаков или сигналов). Кодом также называется отдельная комбинация таких символов (знаков) — слово. Для различия этих терминов, код в последнем значении ещё называется ''кодовым словом''.
 
}}
 
}}
−
  Пусть U {{---}} множество исходных символов, Z {{---}} кодовый алфавит, Z* {{---}} строчки из Z.  
+
  Пусть <tex>U</tex> {{---}} множество исходных символов, <tex>Z</tex> {{---}} кодовый алфавит, <tex>Z^*</tex> {{---}} строчки из <tex>Z</tex>.  
−
  Код {{---}} отображение c : U <tex>\rightarrow</tex> Z*. c* : U* <tex>\rightarrow</tex> Z*. c*(x1x2..xn) = c(x1)c(x2)..c(xn)
+
  Код {{---}} отображение <tex>c : U \rightarrow Z^*</tex>. <tex>c^* : U^* \rightarrow Z^*</tex>. <tex>c^*(x_1 x_2 ... x_n) = c(x_1)c(x_2)..c(x_n)</tex>
  
 
==== Виды кодов ====
 
==== Виды кодов ====
Строка 23: Строка 23:
 
* Азбука Морзе
 
* Азбука Морзе
 
* ASCII
 
* ASCII
 +
 +
== Однозначно декодируемый код ==
 +
{{Определение
 +
|id=def3
 +
|definition='''Однозначно декодируемый код''' — код, в котором любое слово составленное из кодовых слов можно декодировать только единственным способом.
 +
}}
 +
Пусть есть код заданный следующей кодовой таблицей.
 +
<tex>a_1 \rightarrow b_1</tex>; <tex>a_2 \rightarrow b_2</tex>; ... <tex>a_k \rightarrow b_k</tex>;
 +
Составим слово из кодов с использование операции конкатенации:
 +
<tex>b_{i_1} b_{i_2} ... b_{i_n} = b_{j_1} b_{j_2} ... b_{j_m}</tex>
 +
В этом случае, если код однозначно декодируемый, то <tex>n = m</tex> и выполняется равенство:
 +
<tex>b_{i_1} = b_{j_1}</tex>; <tex>b_{i_2} = b_{j_2}</tex>; ... <tex>b_{i_n} = b_{j_m}</tex>;
 +
Заметим, что если среди кодовых слов будут одинаковые, то однозначно декодировать этот код мы уже не сможем.
 +
 +
{{Теорема
 +
|statement=Для любого однозначно декодируемого кода выполняется [[Неравенство Крафта]]<ref>Доказательство этой и других теорем вы можете найти в книге Яблонского С.В "Введение в дискретную математику".</ref>
 +
}}
 +
 +
==== Не префиксный и не постфиксный однозначно декодируемый код ====
 +
Пример:
 +
<tex>U = \mathcal {f} a, b, c \mathcal {g}</tex>; <tex>Z = \mathcal {f} 1, 2, 3 \mathcal {g}</tex>;
 +
<tex>c(a) = 1; c(b) = 12; c(c) = 31;</tex>
 +
Возьмём кодовую строку: <tex>Z^* = (11212311)</tex>
 +
Мы можем ее однозначно декодировать, т.к. знаем, что слева от двойки и справа от тройки всегда стоит единица.
 +
Алгоритм декодировки:
 +
1. Найдем в кодовой строке все двойки и заменим последовательность <tex>Z(12)</tex> на символ <tex>b</tex>
 +
2. Найдем в кодовой строке все тройки и заменим последовательность <tex>Z(31)</tex> на символ <tex>c</tex>
 +
3. Все оставшиеся единички декодируем как символ <tex>a</tex>
 +
В таком случае получаем:
 +
<tex>abbca</tex>
 +
Но, такой код используется очень редко, потому что для его декодировки нужно получить все сообщение целиком.
  
 
== Префиксный код ==
 
== Префиксный код ==
 
{{Определение
 
{{Определение
−
|id=def3
+
|id=def4
 
|definition='''Префиксный код''' — код, в котором никакое кодовое слово не является префиксом какого-то другого кодового слова.
 
|definition='''Префиксный код''' — код, в котором никакое кодовое слово не является префиксом какого-то другого кодового слова.
 
}}
 
}}
−
Любой префиксный код является однозначно декодируемым и разделимым. Также префиксный код иногда называют ''мгновенным кодом''<ref>Джеймс Андерсон. Дискретная математика и комбинаторика, 2004г. Глава 18. Теория кодов. стр. 754</ref>.
+
Любой префиксный код является однозначно декодируемым и разделимым. Также префиксный код иногда называют ''мгновенным кодом''<ref>Джеймс Андерсон. "Дискретная математика и комбинаторика", 2004г. Глава 18. Теория кодов. стр. 754</ref>.
 +
 
 +
Предпочтение префиксным кодам отдается из-за того, что они упрощают декодирование. Поскольку никакое кодовое слово не выступает в роли префикса другого, кодовое слово, с которого начинается файл, определяется однозначно, как и все последующие кодовые слова. Поэтому можно декодировать сообщение не получая его целиком, а по мере его поступления. Благодаря этому, префиксный код еще называют ''мгновенно декодируемым''.
  
−
Предпочтение префиксным кодам отдается из-за того, что они упрощают декодирование. Поскольку никакое кодовое слово не выступает в роли префикса другого, кодовое слово, с которого начинается файл, определяется однозначно, как и все последующие кодовые слова. Поэтому мы можем сразу преобразовать его в исходный символ и продолжить декодирование оставшейся части файла.
+
Использование префиксного кода очень выгодно для кодирования больших аудио/видео файлов, в этом случае мы сможем слушать/смотреть файл по мере скачивания.
  
 
Пример:
 
Пример:
−
  U = {a,b,c}; Z = {0,1};
+
  <tex>U = \mathcal {f} a, b, c \mathcal {g}</tex>; <tex>Z = \mathcal {f} 0, 1 \mathcal {g}</tex>
−
  c(a) = 00; c(b) = 01; c(c) = 1;
+
  <tex>c(a) = 00; c(b) = 01; c(c) = 1;</tex>
−
  Закодируем строку: abacaba
+
  Закодируем строку: <tex>abacaba</tex>
−
  c*(abacaba) = 0001001000100
+
  <tex>c^*(abacaba) = 0001001000100</tex>
 
Такой код можно однозначно разбить на слова:
 
Такой код можно однозначно разбить на слова:
−
  00 01 00 1 00 01 00
+
  <tex>00 01 00 1 00 01 00</tex>
 
поэтому он является префиксным.
 
поэтому он является префиксным.
  
Строка 47: Строка 80:
  
 
  Предположим, что предыдущая последовательность передалась неверно и стала:
 
  Предположим, что предыдущая последовательность передалась неверно и стала:
−
  0001001'''1'''00100
+
  <tex>0001001'1'00100</tex>
 
  Разобьем ее согласно словарю:
 
  Разобьем ее согласно словарю:
−
  00 01 00 1 1 00 1 00
+
  <tex>00 01 00 1 1 00 1 00</tex>
−
  a  b  a  c c a  c a
+
  <tex>a  b  a  c c a  c a</tex>
 
Полученная строка совпадает только в битах, которые находились до ошибочного, поэтому декодирование неравномерного кода, содержащего ошибки, может дать абсолютно неверные результаты.
 
Полученная строка совпадает только в битах, которые находились до ошибочного, поэтому декодирование неравномерного кода, содержащего ошибки, может дать абсолютно неверные результаты.
 
* Необходимость хранить словарь декодировки символов.
 
* Необходимость хранить словарь декодировки символов.

Версия 11:54, 18 декабря 2011

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

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

Код

Определение:
Код — правило (алгоритм) сопоставления каждому конкретному сообщению строго определённой комбинации символов (знаков или сигналов). Кодом также называется отдельная комбинация таких символов (знаков) — слово. Для различия этих терминов, код в последнем значении ещё называется кодовым словом.
Пусть [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];

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

Теорема:
Для любого однозначно декодируемого кода выполняется Неравенство Крафта[1]

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

Пример: 

[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]

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

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

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

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

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

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

Пример: 

[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  b  a  c c a  c a[/math]

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

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

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

См. также

Примечания

  1. ↑ Доказательство этой и других теорем вы можете найти в книге Яблонского С.В "Введение в дискретную математику".
  2. ↑ Джеймс Андерсон. "Дискретная математика и комбинаторика", 2004г. Глава 18. Теория кодов. стр. 754

Литература

  • Томас Кормен, Чарльз Лейзерсон, Рональд Ривест, Клиффорд Штайн. Алгоритмы. Построение и анализ — Издательство: «Вильямс», 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
Источник — «http://neerc.ifmo.ru/wiki/index.php?title=Кодирование_информации&oldid=14809»