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

Материал из Викиконспекты
Перейти к: навигация, поиск
Строка 18: Строка 18:
 
}}
 
}}
 
* '''Код переменной длины''' (variable-length code) {{---}} кодирование производится с помощью строк переменной длины. Также называется ''неравномерным кодом''.
 
* '''Код переменной длины''' (variable-length code) {{---}} кодирование производится с помощью строк переменной длины. Также называется ''неравномерным кодом''.
* '''Разделимый код''' (однозначно декодируемый) {{---}} код, в котором никаким двум словам кодируемого алфавита не может быть сопоставлен один и тот же код.
+
* '''Разделимый код''' (однозначно декодируемый) {{---}} код, в котором любое слово составленное из кодовых слов можно декодировать только единственным способом.
 
* '''Префиксный код''' {{---}} код, в котором, никакое кодовое слово не является началом другого.
 
* '''Префиксный код''' {{---}} код, в котором, никакое кодовое слово не является началом другого.
 
{{Утверждение
 
{{Утверждение
Строка 44: Строка 44:
 
  <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>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>;  
 
Заметим, что если среди кодовых слов будут одинаковые, то однозначно декодировать этот код мы уже не сможем.
 
Заметим, что если среди кодовых слов будут одинаковые, то однозначно декодировать этот код мы уже не сможем.
{{Определение
 
|neat = 1
 
|definition=Слово <tex>\bar{b} \in B^*</tex> называется неприводимым, если <tex>\bar{b}</tex> декодируется неоднозначно, однако, при выбрасывании из <tex>\bar{b}</tex> любого связного непустого куска получается слово, которое декодируется не более, чем одним способом.
 
}}
 
Где <tex>B</tex> — кодовый алфавит, а <tex>B^*</tex> — строчки (слова) из <tex>B</tex>.
 
 
{{Теорема
 
|id=идентификатор (необязательно), пример: th1.
 
|author=Марков А.А.
 
|statement=Пусть <tex>\phi : a_i \rightarrow B_i \ (i = 1,2,..,r)</tex> - некоторое кодирование.<br>
 
Пусть <tex>W</tex> — максимальное число кодовых слов, которые «помещаются» подряд внутри кодового слова. Пусть <tex>l_i</tex> - длина слова <tex>B_i</tex> и <tex>L = \sum_{i=1}^r l_i</tex>. Тогда если кодирование <tex>\phi</tex> не взаимно однозначно, то существуют два различных слова <tex>a' \in A^*</tex>, <tex>a'' \in A^*</tex>, <tex>|a'| \leqslant \left \lfloor \frac{(W+1)(L-r+2)}{2} \right \rfloor</tex>, <tex>|a''| \leqslant  \left \lfloor \frac{(W+1)(L-r+2)}{2} \right \rfloor</tex> и <tex>\phi (a') = \phi (a'')</tex>
 
|proof=Пусть <tex>\phi</tex> не является взаимно однозначным. Тогда существует некоторое слово <tex>\bar{b_1}</tex>, которое допускает две расшифровки. Если слово <tex>\bar{b_1}</tex> не является неприводимым, то выбрасывая из <tex>\bar{b_1}</tex> куски несколько раз, получим неприводимое слово <tex>\bar{b}</tex>; иначе, положим <tex>\bar{b} = \bar{b_1}</tex>. Очевидно, это всегда можно сделать. Рассмотрим любые две декодировки слова <tex>\bar{b}</tex>. Разрежем слово <tex>\bar{b}</tex> в концевых точках кодовых слов каждого из разбиений. Слова нового разбиения разделим на два класса: к I классу отнесём слова, являющиеся элементарными кодами, а ко II классу — все остальные слова (то есть слова, являющиеся началами кодовых слов одного разбиения и концами слов второго разбиения).
 
{{Лемма
 
|statement=Если <tex>\bar{b}</tex> — неприводимое слово, то все слова <tex>\beta_1, \beta_2,..,\beta_m</tex> II класса различны.
 
|proof=Пусть <tex>\beta' = \beta''</tex>. Тогда, очевидно, слово <tex>\bar{b}</tex> не будет неприводимым, поскольку при выкидывании отрезка между <tex>\beta'</tex> и <tex>\beta''</tex>, вместе с любым из этих слов, получим снова две различные расшифровки этого слова.
 
}}
 
Таким образом, все <tex>\beta_1, \beta_2,..,\beta_m</tex> разные. Тогда число слов второго класса не превосходит числа непустых начал элементарных кодов, то есть не превосходит <tex>(l_1 – 1) + (l_2 – 1) + ... + (l_r – 1) = L – r</tex>. Слова из второго класса разбивают слово не более чем на <tex>L – r + 1</tex> кусков. Рассмотрим пары соседних кусков. Тогда согласно одному разбиению в одной половинке уложится не более одного кодового слова, а в другой — не более <tex>W</tex> (согласно второму разбиению ситуация симметрична). Всего пар кусков не больше, чем <tex>\left \lceil \frac{L-r+1}{2} \right \rceil \leqslant \frac{L-r+1}{2}</tex>, а в каждом из них укладывается слов не более чем <tex>W + 1</tex>. Отсюда число кодовых слов в любом разбиении не превосходит <tex>\frac{L-r+1}{2}</tex><tex>(W+1)</tex>, а поскольку число целое, то не превосходит и целой части <tex>\left \lfloor \frac{(W+1)(L-r+2)}{2} \right \rfloor</tex>. Теорема доказана.
 
}}
 
  
 
==== Не префиксный и не постфиксный однозначно декодируемый код ====
 
==== Не префиксный и не постфиксный однозначно декодируемый код ====
Строка 95: Строка 77:
 
поэтому он является префиксным.
 
поэтому он является префиксным.
  
==== Преимущества приефиксных кодов ====
+
==== Преимущества префиксных кодов ====
 
* Однозначно декодируемый и разделимый
 
* Однозначно декодируемый и разделимый
 
* Возможности декодировки сообщения, не получая его целиком, а по мере его поступления.
 
* Возможности декодировки сообщения, не получая его целиком, а по мере его поступления.

Версия 09:03, 12 января 2012

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

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

Код

Определение:
Пусть [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]; 

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

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

Пример:

[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]11212311[/math]
Мы можем ее однозначно декодировать, т.к. знаем, что слева от двойки и справа от тройки всегда стоит единица.

Алгоритм декодировки:

1. Найдем в кодовой строке все двойки и заменим последовательность [math]12[/math] на символ [math]b[/math]
2. Найдем в кодовой строке все тройки и заменим последовательность [math]31[/math] на символ [math]c[/math]
3. Все оставшиеся единички декодируем как символ [math]a[/math]

В таком случае получаем:

[math]abbca[/math]

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

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

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

Также префиксный код иногда называют мгновенным кодом (instantaneous codes)[1].

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

Пример:

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

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

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

См. также

Примечания

  1. Джеймс Андерсон. «Дискретная математика и комбинаторика», 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
  • Алексеев В.Б. «Дискретная математика (II семестр)»