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

Материал из Викиконспекты
Перейти к: навигация, поиск
(Виды кодов)
м (rollbackEdits.php mass rollback)
 
(не показано 45 промежуточных версий 8 участников)
Строка 1: Строка 1:
 
{{Определение
 
{{Определение
 
|id=def1
 
|id=def1
|definition='''Кодирование информации''' — отображение данных на кодовые слова.
+
|definition='''Кодирование информации''' (англ. ''information coding'') — отображение данных на кодовые слова.
 
}}
 
}}
 
Обычно в процессе кодирования информация преобразуется из формы, удобной для непосредственного использования, в форму, удобную для передачи, хранения или автоматической обработки.
 
Обычно в процессе кодирования информация преобразуется из формы, удобной для непосредственного использования, в форму, удобную для передачи, хранения или автоматической обработки.
Строка 10: Строка 10:
 
{{Определение
 
{{Определение
 
|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>
 
}}
 
}}
Пусть <tex>U</tex> {{---}} множество исходных символов, <tex>Z</tex> {{---}} кодовый алфавит, <tex>Z^*</tex> {{---}} строчки из <tex>Z</tex>.  
+
==== Виды кодов ====
Код {{---}} отображение <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'') {{---}} кодирование каждого символа производится с помощью строк одинаковой длины. Также он называется ''равномерным'' или ''блоковым'' кодом.
 +
* '''Код переменной длины''' (англ. ''variable-length code'') {{---}} кодирование производится с помощью строк переменной длины. Также называется ''неравномерным кодом''.
 +
** [[Кодирование информации#Префиксный код | '''Префиксный код''']] {{---}} код, в котором, никакое кодовое слово не является началом другого. Аналогично, можно определить '''постфиксный код''' — это код, в котором никакое кодовое слово не является концом другого.
  
==== Виды кодов ====
+
Все вышеперечисленные коды являются [[Кодирование информации#Однозначно декодируемый код | '''однозначно декодируемыми''']]  — для такого кода любое слово, составленное из кодовых слов, можно декодировать только единственным способом.
* '''[[Представление символов, таблицы кодировок | Код фиксированной длины]]''' (fixed-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>n = m</tex> и выполняется равенство:
+
<tex>a_2 \rightarrow b_2</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>
{{Определение
+
 
|neat = 1
+
<tex>a_k \rightarrow b_k</tex>
|definition=Слово <tex>\bar{b} \in B^*</tex> называется неприводимым, если <tex>\bar{b}</tex> декодируется неоднозначно, однако, при выбрасывании из <tex>\bar{b}</tex> любого связного непустого куска получается слово, которое декодируется не более, чем одним способом.
+
 
}}
+
Код является однозначно декодируемым, только тогда, когда для любых строк, составленных из кодовых слов, вида:
Где <tex>B</tex> — кодовый алфавит, а <tex>B^*</tex> — строчки (слова) из <tex>B</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>
|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>. Теорема доказана.
 
}}
 
  
==== Не префиксный и не постфиксный однозначно декодируемый код ====
+
<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>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=def4
 
|id=def4
|definition='''Префиксный код''' — код, в котором никакое кодовое слово не является префиксом какого-то другого кодового слова.
+
|definition='''Префиксный код''' (англ. ''prefix code'') — код, в котором никакое кодовое слово не является префиксом какого-то другого кодового слова.
 
}}
 
}}
Любой префиксный код является однозначно декодируемым и разделимым. Также префиксный код иногда называют ''мгновенным кодом''<ref>Джеймс Андерсон. "Дискретная математика и комбинаторика", 2004г. Глава 18. Теория кодов. стр. 754</ref>.
 
  
Предпочтение префиксным кодам отдается из-за того, что они упрощают декодирование. Поскольку никакое кодовое слово не выступает в роли префикса другого, кодовое слово, с которого начинается файл, определяется однозначно, как и все последующие кодовые слова. Поэтому можно декодировать сообщение не получая его целиком, а по мере его поступления. Благодаря этому, префиксный код еще называют ''мгновенно декодируемым''.
+
Предпочтение префиксным кодам отдается из-за того, что они упрощают декодирование. Поскольку никакое кодовое слово не выступает в роли префикса другого, кодовое слово, с которого начинается файл, определяется однозначно, как и все последующие кодовые слова.
 +
 
 +
=== Пример кодирования ===
 +
 
 +
<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>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>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>
  
 
== См. также ==
 
== См. также ==
Строка 121: Строка 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
+
* Алексеев В.Б. «Дискретная математика (II семестр)»
* Новиков. Ф.А. Дискретная математика для программистов {{---}} Издательство: «Питер», 2001 г. - 304 стр. {{---}} ISBN 5-94723-741-5 978-5-94723-741-2
 
 
[[Категория: Дискретная математика и алгоритмы]]
 
[[Категория: Дискретная математика и алгоритмы]]
 
[[Категория: Представление информации]]
 
[[Категория: Представление информации]]

Текущая версия на 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 семестр)»