Изменения
→Не префиксный однозначно декодируемый код
{{Определение
|id=def1
|definition='''Кодирование информации''' (англ. ''information coding'') — отображение данных на кодовые слова.
}}
Обычно в процессе кодирования информация преобразуется из формы, удобной для непосредственного использования, в форму, удобную для передачи, хранения или автоматической обработки.
{{Определение
|id=def2
|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'') {{---}} кодирование каждого символа производится с помощью строк одинаковой длины. Также он называется ''равномерным'' или ''блоковым'' кодом.* '''Код переменной длины''' (англ. ''variable-length code'') {{---}} кодирование производится с помощью строк переменной длины. Также называется ''неравномерным кодом''.
** [[Кодирование информации#Префиксный код | '''Префиксный код''']] {{---}} код, в котором, никакое кодовое слово не является началом другого. Аналогично, можно определить '''постфиксный код''' — это код, в котором никакое кодовое слово не является концом другого.
Все вышеперечисленные коды являются [[Кодирование информации#Однозначно декодируемый код | '''однозначно декодируемыми''']] (''англ. uniquely decodable'') — для такого кода любое слово, составленное из кодовых слов, можно декодировать только единственным способом.
==== Примеры кодов ====
* [[Представление символов, таблицы кодировок#Кодировки стандарта ASCII | ASCII]] — блочный.
* [[Алгоритм Хаффмана | Код Хаффмана]] (''англ. Huffman code'') — префиксный.
* Азбука Морзе — не является ни блочным, ни префиксным, тем не менее, однозначно декодируемый засчет использования пауз.
{{Определение
|id=def3
|definition='''Однозначно декодируемый код''' (англ. ''uniquely decodable code'') — код, в котором любое слово составленное из кодовых слов можно декодировать только единственным способом.
}}
Заметим, что если среди кодовых слов будут одинаковые, то однозначно декодировать этот код мы уже не сможем.
=== Пример кодирования ===
Такой код можно однозначно разбить на слова:
=== Преимущества префиксных кодов ===
=== Недостатки префиксных кодов ===
* При появлении ошибок в кодовой комбинации, при определенных обстоятельствах, может привести к неправильному декодированию не только данной, но и последующей кодовой комбинации, в отличии от равномерных кодов, где ошибка в кодовой комбинации приводит к неправильному декодированию только ее.
Разобьем ее согласно словарю:
Полученная строка совпадает только в битах, которые находились до ошибочного, поэтому декодирование неравномерного кода, содержащего ошибки, может дать абсолютно неверные результаты.
=== Не префиксный однозначно декодируемый код ===
Как уже было сказано, префиксный код всегда однозначно декодируем. Обратное в общем случае неверно:
<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>
== См. также ==
* [[Неравенство Макмиллана]]
== Литература Источники информации ==* [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
