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

Материал из Викиконспекты
Перейти к: навигация, поиск
м (Преимущества префиксных кодов)
(Не префиксный однозначно декодируемый код)
(не показаны 22 промежуточные версии 3 участников)
Строка 1: Строка 1:
 
{{Определение
 
{{Определение
 
|id=def1
 
|id=def1
|definition='''Кодирование информации''' — отображение данных на кодовые слова.
+
|definition='''Кодирование информации''' (англ. ''information coding'') — отображение данных на кодовые слова.
 
}}
 
}}
 
Обычно в процессе кодирования информация преобразуется из формы, удобной для непосредственного использования, в форму, удобную для передачи, хранения или автоматической обработки.
 
Обычно в процессе кодирования информация преобразуется из формы, удобной для непосредственного использования, в форму, удобную для передачи, хранения или автоматической обработки.
Строка 10: Строка 10:
 
{{Определение
 
{{Определение
 
|id=def2
 
|id=def2
|definition=Пусть <tex>U</tex> {{---}} множество исходных символов, <tex>Z</tex> {{---}} кодовый алфавит, <tex>Z^*</tex> {{---}} множество всех строк конечной длины из <tex>Z</tex>.<br> '''Код''' {{---}} отображение <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>
+
|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>
 
}}
 
}}
 
==== Виды кодов ====
 
==== Виды кодов ====
* '''[[Представление символов, таблицы кодировок | Код фиксированной длины]]''' (fixed-length code) {{---}} кодирование каждого символа производится с помощью строк одинаковой длины. Также он называется ''равномерным'' или ''блоковым'' кодом.
+
* '''[[Представление символов, таблицы кодировок | Код фиксированной длины]]''' (англ. ''fixed-length code'') {{---}} кодирование каждого символа производится с помощью строк одинаковой длины. Также он называется ''равномерным'' или ''блоковым'' кодом.
* '''Код переменной длины''' (variable-length code) {{---}} кодирование производится с помощью строк переменной длины. Также называется ''неравномерным кодом''.
+
* '''Код переменной длины''' (англ. ''variable-length code'') {{---}} кодирование производится с помощью строк переменной длины. Также называется ''неравномерным кодом''.
 
** [[Кодирование информации#Префиксный код | '''Префиксный код''']] {{---}} код, в котором, никакое кодовое слово не является началом другого. Аналогично, можно определить '''постфиксный код''' — это код, в котором никакое кодовое слово не является концом другого.
 
** [[Кодирование информации#Префиксный код | '''Префиксный код''']] {{---}} код, в котором, никакое кодовое слово не является началом другого. Аналогично, можно определить '''постфиксный код''' — это код, в котором никакое кодовое слово не является концом другого.
  
Все вышеперечисленные коды являются [[Кодирование информации#Однозначно декодируемый код | '''однозначно декодируемыми''']] (''англ. uniquely decodable'') — для такого кода любое слово, составленное из кодовых слов, можно декодировать только единственным способом.
+
Все вышеперечисленные коды являются [[Кодирование информации#Однозначно декодируемый код | '''однозначно декодируемыми''']] — для такого кода любое слово, составленное из кодовых слов, можно декодировать только единственным способом.
  
 
==== Примеры кодов ====
 
==== Примеры кодов ====
 
* [[Представление символов, таблицы кодировок#Кодировки стандарта ASCII | ASCII]] — блочный.
 
* [[Представление символов, таблицы кодировок#Кодировки стандарта ASCII | ASCII]] — блочный.
* [[Алгоритм Хаффмана | Код Хаффмана]] — префиксный.
+
* [[Алгоритм Хаффмана | Код Хаффмана]] (''англ. Huffman code'') — префиксный.
 
* Азбука Морзе — не является ни блочным, ни префиксным, тем не менее, однозначно декодируемый засчет использования пауз.
 
* Азбука Морзе — не является ни блочным, ни префиксным, тем не менее, однозначно декодируемый засчет использования пауз.
  
Строка 27: Строка 27:
 
{{Определение
 
{{Определение
 
|id=def3
 
|id=def3
|definition='''Однозначно декодируемый код''' — код, в котором любое слово составленное из кодовых слов можно декодировать только единственным способом.
+
|definition='''Однозначно декодируемый код''' (англ. ''uniquely decodable code'') — код, в котором любое слово составленное из кодовых слов можно декодировать только единственным способом.
 
}}
 
}}
Пусть есть код заданный следующей кодовой таблицей.
+
Пусть есть код заданный следующей кодовой таблицей:
<tex>a_1 \rightarrow b_1</tex>; <tex>a_2 \rightarrow b_2</tex>; ... <tex>a_k \rightarrow b_k</tex>;
+
 
Код является однозначно декодируемым, толька тогда, когда для любых строк, составленных из кодовых слов, вида:
+
<tex>a_1 \rightarrow b_1</tex>  
<tex>b_{i_1} b_{i_2} ... b_{i_n} = b_{j_1} b_{j_2} ... b_{j_m}</tex>
+
 
Всегда выполняются равенства:
+
<tex>a_2 \rightarrow b_2</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>;
+
 
 +
<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>
 +
 
Заметим, что если среди кодовых слов будут одинаковые, то однозначно декодировать этот код мы уже не сможем.
 
Заметим, что если среди кодовых слов будут одинаковые, то однозначно декодировать этот код мы уже не сможем.
  
Строка 46: Строка 66:
  
 
=== Пример кодирования ===
 
=== Пример кодирования ===
<tex>U = \mathcal {f} a, b, c \mathcal {g}</tex>; <tex>Z = \mathcal {f} 0, 1 \mathcal {g}</tex>
+
 
<tex>c(a) = 00; c(b) = 01; c(c) = 1;</tex>
+
<tex>U = \{ a, b, c \}</tex>
Закодируем строку: <tex>abacaba</tex>
+
 
<tex>c^*(abacaba) = 0001001000100</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>
+
 
 +
<tex>00\ 01\ 00\ 1\ 00\ 01\ 00</tex>
  
 
=== Преимущества префиксных кодов ===
 
=== Преимущества префиксных кодов ===
Строка 59: Строка 91:
  
 
=== Недостатки префиксных кодов ===
 
=== Недостатки префиксных кодов ===
* Так как префиксные коды являются кодами переменной длины, а данные, в основном, считываются блочно, код приходится считывать побитово, что значительно замедляет скорость считывания данных
 
 
* При появлении ошибок в кодовой комбинации, при определенных обстоятельствах, может привести к неправильному декодированию не только данной, но и последующей кодовой комбинации, в отличии от равномерных кодов, где ошибка в кодовой комбинации приводит к неправильному декодированию только ее.
 
* При появлении ошибок в кодовой комбинации, при определенных обстоятельствах, может привести к неправильному декодированию не только данной, но и последующей кодовой комбинации, в отличии от равномерных кодов, где ошибка в кодовой комбинации приводит к неправильному декодированию только ее.
  
==== Пример неудачного декодирования ====
+
=== Пример неудачного декодирования ===
Предположим, что последовательность из примера передалась неверно и стала:
+
Предположим, что последовательность <tex>abacaba</tex> из примера передалась неверно и стала:
<tex>0001001\ 1\ 00100</tex>
+
 
 +
<tex>c^{**}(abacaba) = 0001001\ 1\ 00100</tex>
 +
 
 
Разобьем ее согласно словарю:
 
Разобьем ее согласно словарю:
<tex>00\ 01\ 00\ 1\ 1\ 00\ 1\ 00</tex>
+
 
<tex>a\quad b\quad a\ c\ c\quad a\ c\ a</tex>
+
<tex> 00\ 01\ 00\ 1\ 1\ 00\ 1\ 00</tex>
 +
 
 +
<tex>a\quad b\quad a\ c\ c\quad a\ c\ a</tex>
 +
 
 
Полученная строка совпадает только в битах, которые находились до ошибочного, поэтому декодирование неравномерного кода, содержащего ошибки, может дать абсолютно неверные результаты.
 
Полученная строка совпадает только в битах, которые находились до ошибочного, поэтому декодирование неравномерного кода, содержащего ошибки, может дать абсолютно неверные результаты.
  
 
=== Не префиксный однозначно декодируемый код ===
 
=== Не префиксный однозначно декодируемый код ===
 
Как уже было сказано, префиксный код всегда однозначно декодируем. Обратное в общем случае неверно:
 
Как уже было сказано, префиксный код всегда однозначно декодируем. Обратное в общем случае неверно:
<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>abbca</tex>, получим кодовую строку <tex>11212311</tex>
 
Мы можем ее однозначно декодировать, так как знаем, что слева от двойки и справа от тройки всегда стоит единица.
 
  
После декодирования получаем:
+
<tex>U = \{ a, b, c \}</tex>
<tex>abbca</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>
  
 
== См. также ==
 
== См. также ==
Строка 85: Строка 130:
 
* [[Неравенство Макмиллана]]
 
* [[Неравенство Макмиллана]]
  
== Литература ==
+
== Источники информации ==
 +
* [http://en.wikipedia.org/wiki/Prefix_code  Wikipedia {{---}} Prefix code]
 
* Томас Кормен, Чарльз Лейзерсон, Рональд Ривест, Клиффорд Штайн. «Алгоритмы. Построение и анализ» {{---}} «Вильямс», 2011 г. {{---}} 1296 стр. {{---}} ISBN 978-5-8459-0857-5, 5-8459-0857-4, 0-07-013151-1
 
* Томас Кормен, Чарльз Лейзерсон, Рональд Ривест, Клиффорд Штайн. «Алгоритмы. Построение и анализ» {{---}} «Вильямс», 2011 г. {{---}} 1296 стр. {{---}} ISBN 978-5-8459-0857-5, 5-8459-0857-4, 0-07-013151-1
 
* Джеймс Андерсон. «Дискретная математика и комбинаторика» {{---}} «Вильямс», 2004 г. {{---}} 960 стр. {{---}} ISBN 978-0-13-086998-2
 
* Джеймс Андерсон. «Дискретная математика и комбинаторика» {{---}} «Вильямс», 2004 г. {{---}} 960 стр. {{---}} ISBN 978-0-13-086998-2

Версия 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 семестр)»