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

Материал из Викиконспекты
Перейти к: навигация, поиск
(Не префиксный однозначно декодируемый код)
 
(не показана 61 промежуточная версия 7 участников)
Строка 1: Строка 1:
 
{{Определение
 
{{Определение
 
|id=def1
 
|id=def1
|definition='''Кодирование информации''' — процесс преобразования информации из одной формы в другую.
+
|definition='''Кодирование информации''' (англ. ''information coding'') отображение данных на кодовые слова.
 
}}
 
}}
 
Обычно в процессе кодирования информация преобразуется из формы, удобной для непосредственного использования, в форму, удобную для передачи, хранения или автоматической обработки.
 
Обычно в процессе кодирования информация преобразуется из формы, удобной для непосредственного использования, в форму, удобную для передачи, хранения или автоматической обработки.
 
В более узком смысле кодированием информации называют представление информации в виде кода.
 
В более узком смысле кодированием информации называют представление информации в виде кода.
 
Средством кодирования служит таблица соответствия знаковых систем, которая устанавливает взаимно однозначное соответствие между знаками или группами знаков двух различных знаковых систем.
 
Средством кодирования служит таблица соответствия знаковых систем, которая устанавливает взаимно однозначное соответствие между знаками или группами знаков двух различных знаковых систем.
 
Рассмотрим пример кодирования с помощью [[http://neerc.ifmo.ru/mediawiki/index.php/Кодирование_информации#.D0.9F.D1.80.D0.B5.D1.84.D0.B8.D0.BA.D1.81.D0.BD.D1.8B.D0.B9_.D0.BA.D0.BE.D0.B4: префиксного кода]].
 
 
Пусть U {{---}} множество исходных символов, Z {{---}} кодовый алфавит, Z* {{---}} строчки из Z.
 
Код {{---}} отображение c : U <tex>\rightarrow</tex> Z*. c* : U* <tex>\rightarrow</tex> 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
 
поэтому он является префиксным.
 
  
 
== Код ==
 
== Код ==
 
{{Определение
 
{{Определение
 
|id=def2
 
|id=def2
|definition='''Код''' — правило (алгоритм) сопоставления каждому конкретному сообщению строго определённой комбинации символов (знаков или сигналов). Кодом также называется отдельная комбинация таких символов (знаков) — слово. Для различия этих терминов, код в последнем значении ещё называется ''кодовым словом''.
+
|definition=Пусть <tex>U</tex> {{---}} множество исходных символов, <tex>Z</tex> {{---}} кодовый алфавит, <tex>Z^*</tex> {{---}} множество всех строк конечной длины из <tex>Z</tex>.<br> '''Код''' (англ. ''code'') {{---}} отображение <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>
 
}}
 
}}
 
==== Виды кодов ====
 
==== Виды кодов ====
* [http://neerc.ifmo.ru/mediawiki/index.php/Представление_символов,_таблицы_кодировок: '''Код фиксированной длины'''] (fixed-length code) {{---}} кодирование каждого символа производится с помощью строк одинаковой длины. Также он называется ''равномерным'' или ''блоковым'' кодом.
+
* '''[[Представление символов, таблицы кодировок | Код фиксированной длины]]''' (англ. ''fixed-length code'') {{---}} кодирование каждого символа производится с помощью строк одинаковой длины. Также он называется ''равномерным'' или ''блоковым'' кодом.
* '''Код переменной длины''' (variable-length code) {{---}} кодирование производится с помощью строк переменной длины. Также называется ''неравномерным кодом''.
+
* '''Код переменной длины''' (англ. ''variable-length code'') {{---}} кодирование производится с помощью строк переменной длины. Также называется ''неравномерным кодом''.
* '''Разделимый код''' {{---}} код, в котором любое слово, составленное из элементарных кодов, единственным образом разлагается на элементарные коды.
+
** [[Кодирование информации#Префиксный код | '''Префиксный код''']] {{---}} код, в котором, никакое кодовое слово не является началом другого. Аналогично, можно определить '''постфиксный код''' — это код, в котором никакое кодовое слово не является концом другого.
 +
 
 +
Все вышеперечисленные коды являются [[Кодирование информации#Однозначно декодируемый код | '''однозначно декодируемыми''']]  — для такого кода любое слово, составленное из кодовых слов, можно декодировать только единственным способом.
  
 
==== Примеры кодов ====
 
==== Примеры кодов ====
* Азбука Морзе
+
* [[Представление символов, таблицы кодировок#Кодировки стандарта ASCII | ASCII]] — блочный.
* ASCII
+
* [[Алгоритм Хаффмана | Код Хаффмана]] (''англ. Huffman code'') — префиксный.
 +
* Азбука Морзе — не является ни блочным, ни префиксным, тем не менее, однозначно декодируемый засчет использования пауз.
 +
 
 +
== Однозначно декодируемый код ==
 +
{{Определение
 +
|id=def3
 +
|definition='''Однозначно декодируемый код''' (англ. ''uniquely decodable code'') — код, в котором любое слово составленное из кодовых слов можно декодировать только единственным способом.
 +
}}
 +
Пусть есть код заданный следующей кодовой таблицей:
 +
 
 +
<tex>a_1 \rightarrow b_1</tex>
 +
 
 +
<tex>a_2 \rightarrow b_2</tex>
 +
 
 +
<tex> \dots </tex>
 +
 
 +
<tex>a_k \rightarrow b_k</tex>
 +
 
 +
Код является однозначно декодируемым, только тогда, когда для любых строк, составленных из кодовых слов, вида:
 +
 
 +
<tex>b_{i_1} b_{i_2} \dots b_{i_n} = b_{j_1} b_{j_2} \dots 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> \dots </tex>
 +
 
 +
<tex> b_{i_n} = b_{j_m}</tex>
 +
 +
Заметим, что если среди кодовых слов будут одинаковые, то однозначно декодировать этот код мы уже не сможем.
  
 
== Префиксный код ==
 
== Префиксный код ==
 
{{Определение
 
{{Определение
|id=def3
+
|id=def4
|definition='''Префиксный код''' — код, в котором никакое кодовое слово не является префиксом какого-то другого кодового слова.
+
|definition='''Префиксный код''' (англ. ''prefix code'') — код, в котором никакое кодовое слово не является префиксом какого-то другого кодового слова.
 
}}
 
}}
Любой префиксный код является однозначно декодируемым и разделимым. Также префиксный код иногда называют ''мнгновенным кодом''.
 
Оптимальное сжатие данных, которого можно достичь с помощью кодов, всегда достижимо при использовании префиксного кода.
 
  
Предпочтение префиксным кодам отдается из-за того, что они упрощают декодирование. Поскольку никакое кодовое слово не выступает в роли префикса другого, кодовое слово, с которого начинается закодированный файл, определяется однозначно. Начальное кодовое слово, с которого начинается закодированный файл, определяется однозначно. Начальное кодовое слово легко идентифицировать, преобразовать его в исходный символ и продолжить декодирование оставшейся части закодированного файла.
+
Предпочтение префиксным кодам отдается из-за того, что они упрощают декодирование. Поскольку никакое кодовое слово не выступает в роли префикса другого, кодовое слово, с которого начинается файл, определяется однозначно, как и все последующие кодовые слова.
 +
 
 +
=== Пример кодирования ===
 +
 
 +
<tex>U = \{ a, b, c \}</tex>
 +
 
 +
<tex>  Z = \{ 0, 1 \}</tex>
 +
 
 +
<tex> c(a) = 00 </tex>
 +
 
 +
<tex> c(b) = 01 </tex>
 +
 
 +
<tex> c(c) = 1 </tex>
 +
 
 +
Закодируем строку <tex>abacaba</tex> :
 +
 
 +
<tex>c^*(abacaba) = 0001001000100</tex>
 +
 
 +
Такой код можно однозначно разбить на слова:
 +
 
 +
<tex>00\ 01\ 00\ 1\ 00\ 01\ 00</tex>
 +
 
 +
=== Преимущества префиксных кодов ===
 +
* Однозначно декодируемый и разделимый
 +
* Удается получить более короткие коды, чем с помощью кода фиксированной длины.
 +
* Возможности декодировки сообщения, не получая его целиком, а по мере его поступления.
  
==== Недостатки префиксных кодов ====
+
=== Недостатки префиксных кодов ===
* Так как префиксные коды являются кодами переменной длины, а данные, в основном, считываются блочно, код приходится считывать побитово, что значительно значительно замедляет скорость считывания данных
 
 
* При появлении ошибок в кодовой комбинации, при определенных обстоятельствах, может привести к неправильному декодированию не только данной, но и последующей кодовой комбинации, в отличии от равномерных кодов, где ошибка в кодовой комбинации приводит к неправильному декодированию только ее.
 
* При появлении ошибок в кодовой комбинации, при определенных обстоятельствах, может привести к неправильному декодированию не только данной, но и последующей кодовой комбинации, в отличии от равномерных кодов, где ошибка в кодовой комбинации приводит к неправильному декодированию только ее.
Пример:
+
 
Возьмём строку abacaba, и закодируем ее аналогично предыдущему примеру.
+
=== Пример неудачного декодирования ===
c*(abacaba) = 0001001000100
+
Предположим, что последовательность <tex>abacaba</tex> из примера передалась неверно и стала:
Предположим, что последовательность передалась неверно и стала:
+
 
0001001'''1'''00100
+
<tex>c^{**}(abacaba) = 0001001\ 1\ 00100</tex>
Разобьем ее согласно словарю:
+
 
00 01 00 1 1 00 1 00
+
Разобьем ее согласно словарю:
a b a c c a c a
+
 
 +
<tex> 00\ 01\ 00\ 1\ 1\ 00\ 1\ 00</tex>
 +
 
 +
<tex>a\quad b\quad a\ c\ c\quad a\ c\ a</tex>
 +
 
 
Полученная строка совпадает только в битах, которые находились до ошибочного, поэтому декодирование неравномерного кода, содержащего ошибки, может дать абсолютно неверные результаты.
 
Полученная строка совпадает только в битах, которые находились до ошибочного, поэтому декодирование неравномерного кода, содержащего ошибки, может дать абсолютно неверные результаты.
* Необходимость хранить словарь декодировки символов.
 
  
==== Примеры префиксных кодов ====
+
=== Не префиксный однозначно декодируемый код ===
* Код Хаффмана
+
Как уже было сказано, префиксный код всегда однозначно декодируем. Обратное в общем случае неверно:
* Код Шеннона-Фано
+
 
* UTF-8 {{---}} префиксный, так как является блоковым.
+
<tex>U = \{ a, b, c \}</tex>
 +
 
 +
<tex>Z = \{ 1, 2, 3 \}</tex>
 +
 
 +
<tex> c(a) = 1 </tex>
 +
 
 +
<tex> c(b) = 12 </tex>
 +
 
 +
<tex> c(c) = 31 </tex>
 +
 
 +
Закодируем <tex>abbca</tex>, получим кодовую строку: <tex>11212311</tex>
 +
 
 +
Мы можем ее однозначно декодировать, так как знаем, что слева от двойки и справа от тройки всегда стоит единица.
 +
 
 +
После декодирования получаем: <tex>abbca</tex>
 +
 
 +
== См. также ==
 +
* [[Представление символов, таблицы кодировок]]
 +
* [[Неравенство Крафта]]
 +
* [[Неравенство Макмиллана]]
  
== Литература ==
+
== Источники информации ==
* Томас Кормен, Чарльз Лейзерсон, Рональд Ривест, Клиффорд Штайн. Алгоритмы. Построение и анализ {{---}} Издательство: «Вильямс», 2011 г. - 1296 стр. {{---}} ISBN 978-5-8459-0857-5, 5-8459-0857-4, 0-07-013151-1
+
* [http://en.wikipedia.org/wiki/Prefix_code  Wikipedia {{---}} Prefix code]
* Джеймс Андерсон. Дискретная математика и комбинаторика {{---}} Издательство: «Вильямс», 2004 г. - 960 стр. {{---}} ISBN 978-0-13-086998-2
+
* Томас Кормен, Чарльз Лейзерсон, Рональд Ривест, Клиффорд Штайн. «Алгоритмы. Построение и анализ» {{---}} «Вильямс», 2011 г. {{---}} 1296 стр. {{---}} ISBN 978-5-8459-0857-5, 5-8459-0857-4, 0-07-013151-1
* Ф. А. Новиков. Дискретная математика для программистов {{---}} Издательство: «Питер», 2001 г. - 304 стр. {{---}} ISBN 5-94723-741-5 978-5-94723-741-2
+
* Джеймс Андерсон. «Дискретная математика и комбинаторика» {{---}} «Вильямс», 2004 г. {{---}} 960 стр. {{---}} ISBN 978-0-13-086998-2
 +
* Новиков. Ф.А. «Дискретная математика для программистов» {{---}} «Питер», 2001 г. {{---}} 304 стр. {{---}} ISBN 5-94723-741-5 978-5-94723-741-2
 +
* Алексеев В.Б. «Дискретная математика (II семестр)»
 
[[Категория: Дискретная математика и алгоритмы]]
 
[[Категория: Дискретная математика и алгоритмы]]
 
[[Категория: Представление информации]]
 
[[Категория: Представление информации]]

Текущая версия на 10:14, 13 сентября 2018

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

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

Код[править]

Определение:
Пусть [math]U[/math] — множество исходных символов, [math]Z[/math] — кодовый алфавит, [math]Z^*[/math] — множество всех строк конечной длины из [math]Z[/math].
Код (англ. code) — отображение [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] \dots [/math]

[math]a_k \rightarrow b_k[/math]

Код является однозначно декодируемым, только тогда, когда для любых строк, составленных из кодовых слов, вида:

[math]b_{i_1} b_{i_2} \dots b_{i_n} = b_{j_1} b_{j_2} \dots 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] \dots [/math]

[math] b_{i_n} = b_{j_m}[/math]

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

Префиксный код[править]

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


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

Пример кодирования[править]

[math]U = \{ a, b, c \}[/math]

[math] Z = \{ 0, 1 \}[/math]

[math] c(a) = 00 [/math]

[math] c(b) = 01 [/math]

[math] 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 = \{ a, b, c \}[/math]

[math]Z = \{ 1, 2, 3 \}[/math]

[math] c(a) = 1 [/math]

[math] c(b) = 12 [/math]

[math] 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 семестр)»