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

Материал из Викиконспекты
Перейти к: навигация, поиск
(Виды кодов)
м (rollbackEdits.php mass rollback)
 
(не показано 38 промежуточных версий 7 участников)
Строка 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'') {{---}} кодирование производится с помощью строк переменной длины. Также называется ''неравномерным кодом''.
|statement=Любой равномерный код является взаимно однозначным.
+
** [[Кодирование информации#Префиксный код | '''Префиксный код''']] {{---}} код, в котором, никакое кодовое слово не является началом другого. Аналогично, можно определить '''постфиксный код''' — это код, в котором никакое кодовое слово не является концом другого.
}}
+
 
* '''Код переменной длины''' (variable-length code) {{---}} кодирование производится с помощью строк переменной длины. Также называется ''неравномерным кодом''.
+
Все вышеперечисленные коды являются [[Кодирование информации#Однозначно декодируемый код | '''однозначно декодируемыми''']]  — для такого кода любое слово, составленное из кодовых слов, можно декодировать только единственным способом.
* '''[[Кодирование информации#Однозначно декодируемый код|Разделимый код]]''' (однозначно декодируемый) {{---}} код, в котором любое слово составленное из кодовых слов можно декодировать только единственным способом.
 
* '''Префиксный код''' {{---}} код, в котором, никакое кодовое слово не является началом другого.
 
{{Утверждение
 
|statement=Любое префиксное кодирование является взаимно однозначным.
 
}}
 
* '''Постфиксный код''' (суффиксный) {{---}} код, в котором никакое кодовое слово не является концом другого.
 
{{Утверждение
 
|statement=Любое постфиксное кодирование является взаимно однозначным.
 
}}
 
  
 
==== Примеры кодов ====
 
==== Примеры кодов ====
* Азбука Морзе
+
* [[Представление символов, таблицы кодировок#Кодировки стандарта ASCII | ASCII]] — блочный.
* ASCII
+
* [[Алгоритм Хаффмана | Код Хаффмана]] (''англ. Huffman code'') — префиксный.
 +
* Азбука Морзе — не является ни блочным, ни префиксным, тем не менее, однозначно декодируемый засчет использования пауз.
  
 
== Однозначно декодируемый код ==
 
== Однозначно декодируемый код ==
 
{{Определение
 
{{Определение
 
|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>
 +
 
Заметим, что если среди кодовых слов будут одинаковые, то однозначно декодировать этот код мы уже не сможем.
 
Заметим, что если среди кодовых слов будут одинаковые, то однозначно декодировать этот код мы уже не сможем.
 
==== Не префиксный и не постфиксный однозначно декодируемый код ====
 
Пример:
 
<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>11212311</tex>
 
Мы можем ее однозначно декодировать, т.к. знаем, что слева от двойки и справа от тройки всегда стоит единица.
 
Алгоритм декодировки:
 
1. Найдем в кодовой строке все двойки и заменим последовательность <tex>12</tex> на символ <tex>b</tex>
 
2. Найдем в кодовой строке все тройки и заменим последовательность <tex>31</tex> на символ <tex>c</tex>
 
3. Все оставшиеся единички декодируем как символ <tex>a</tex>
 
В таком случае получаем:
 
<tex>abbca</tex>
 
Но, такой код используется очень редко, потому что для его декодировки нужно получить все сообщение целиком.
 
  
 
== Префиксный код ==
 
== Префиксный код ==
 
{{Определение
 
{{Определение
 
|id=def4
 
|id=def4
|definition='''Префиксный код''' — код, в котором никакое кодовое слово не является префиксом какого-то другого кодового слова.
+
|definition='''Префиксный код''' (англ. ''prefix code'') — код, в котором никакое кодовое слово не является префиксом какого-то другого кодового слова.
 
}}
 
}}
Также префиксный код иногда называют ''мгновенным кодом (instantaneous codes)''<ref>Джеймс Андерсон. «Дискретная математика и комбинаторика», 2004г. Глава 18. Теория кодов. стр. 754</ref>.
 
  
 
Предпочтение префиксным кодам отдается из-за того, что они упрощают декодирование. Поскольку никакое кодовое слово не выступает в роли префикса другого, кодовое слово, с которого начинается файл, определяется однозначно, как и все последующие кодовые слова.
 
Предпочтение префиксным кодам отдается из-за того, что они упрощают декодирование. Поскольку никакое кодовое слово не выступает в роли префикса другого, кодовое слово, с которого начинается файл, определяется однозначно, как и все последующие кодовые слова.
  
Пример:
+
=== Пример кодирования ===
<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>
 +
 
 +
=== Преимущества префиксных кодов ===
 
* Однозначно декодируемый и разделимый
 
* Однозначно декодируемый и разделимый
 +
* Удается получить более короткие коды, чем с помощью кода фиксированной длины.
 
* Возможности декодировки сообщения, не получая его целиком, а по мере его поступления.
 
* Возможности декодировки сообщения, не получая его целиком, а по мере его поступления.
  
==== Недостатки префиксных кодов ====
+
=== Недостатки префиксных кодов ===
* Так как префиксные коды являются кодами переменной длины, а данные, в основном, считываются блочно, код приходится считывать побитово, что значительно замедляет скорость считывания данных
 
 
* При появлении ошибок в кодовой комбинации, при определенных обстоятельствах, может привести к неправильному декодированию не только данной, но и последующей кодовой комбинации, в отличии от равномерных кодов, где ошибка в кодовой комбинации приводит к неправильному декодированию только ее.
 
* При появлении ошибок в кодовой комбинации, при определенных обстоятельствах, может привести к неправильному декодированию не только данной, но и последующей кодовой комбинации, в отличии от равномерных кодов, где ошибка в кодовой комбинации приводит к неправильному декодированию только ее.
  
Предположим, что предыдущая последовательность передалась неверно и стала:
+
=== Пример неудачного декодирования ===
<tex>0001001'1'00100</tex>
+
Предположим, что последовательность <tex>abacaba</tex> из примера передалась неверно и стала:
Разобьем ее согласно словарю:
+
 
<tex>00\ 01\ 00\ 1\ 1\ 00\ 1\ 00</tex>
+
<tex>c^{**}(abacaba) = 0001001\ 1\ 00100</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 = \{ 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>
  
 
== См. также ==
 
== См. также ==
Строка 101: Строка 130:
 
* [[Неравенство Макмиллана]]
 
* [[Неравенство Макмиллана]]
  
== Примечания ==
+
== Источники информации ==
<references/>
+
* [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
== Литература ==
+
* Джеймс Андерсон. «Дискретная математика и комбинаторика» {{---}} «Вильямс», 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 семестр)»
 
* Алексеев В.Б. «Дискретная математика (II семестр)»
 
[[Категория: Дискретная математика и алгоритмы]]
 
[[Категория: Дискретная математика и алгоритмы]]
 
[[Категория: Представление информации]]
 
[[Категория: Представление информации]]

Текущая версия на 19:14, 4 сентября 2022

Определение:
Кодирование информации (англ. 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 семестр)»