Изменения

|definition='''Кодирование информации''' (англ. ''information coding'') — процесс преобразования информации из одной формы в другуюотображение данных на кодовые слова.

|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>

* [http://neerc.ifmo.ru/mediawiki/index.php/Представление_символов,_таблицы_кодировок '''[[Представление символов, таблицы кодировок | Код фиксированной длины]]'''] (англ. ''fixed-length code'') {{---}} кодирование каждого символа производится с помощью строк одинаковой длины. Также он называется ''равномерным'' или ''блоковым'' кодом.* '''Код переменной длины''' (англ. ''variable-length code'') {{---}} кодирование производится с помощью строк переменной длины. Также называется ''неравномерным кодом''.* * [[Кодирование информации#Префиксный код | '''Разделимый Префиксный код''' ]] {{---}} код, в котором , никакое кодовое слово не является началом другого. Аналогично, можно определить '''постфиксный код''' — это код, в котором никакое кодовое слово не является концом другого. Все вышеперечисленные коды являются [[Кодирование информации#Однозначно декодируемый код | '''однозначно декодируемыми''']] — для такого кода любое слово, составленное из элементарных кодовкодовых слов, можно декодировать только единственным образом разлагается на элементарные кодыспособом.

* [[Представление символов, таблицы кодировок#Кодировки стандарта ASCII | ASCII]] — блочный.* [[Алгоритм Хаффмана | Код Хаффмана]] (''англ. Huffman code'') — префиксный.* Азбука Морзе— не является ни блочным, ни префиксным, тем не менее, однозначно декодируемый засчет использования пауз. == Однозначно декодируемый код =={{Определение|id=def3|definition='''Однозначно декодируемый код''' (англ. ''uniquely decodable code'') — код, в котором любое слово составленное из кодовых слов можно декодировать только единственным способом.}}Пусть есть код заданный следующей кодовой таблицей: <tex>a_1 \rightarrow b_1</tex>  <tex>a_2 \rightarrow b_2</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> * ASCII<tex> b_{i_n} = b_{j_m}</tex> Заметим, что если среди кодовых слов будут одинаковые, то однозначно декодировать этот код мы уже не сможем.

|id=def3def4|definition='''Префиксный код''' (англ. ''prefix code'') — код, в котором никакое кодовое слово не является префиксом какого-то другого кодового слова.

Предпочтение префиксным кодам отдается из-за того, что они упрощают декодирование. Поскольку никакое кодовое слово не выступает в роли префикса другого, кодовое слово, с которого начинается закодированный файл, определяется однозначно, как и все последующие кодовые слова. Начальное кодовое слово === Пример кодирования === <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>00\ 01\ 00\ 1\ 00\ 01\ 00</tex> === Преимущества префиксных кодов ===* Однозначно декодируемый и разделимый* Удается получить более короткие коды, чем с помощью кода фиксированной длины. Начальное кодовое слово легко идентифицировать* Возможности декодировки сообщения, не получая его целиком, преобразовать а по мере его в исходный символ и продолжить декодирование оставшейся части закодированного файлапоступления.

==== Недостатки префиксных кодов ====* Так как префиксные коды являются кодами переменной длины, а данные, в основном, считываются блочно, код приходится считывать побитово, что значительно значительно замедляет скорость считывания данных

 === Пример: Возьмём строку abacaba, и закодируем ее аналогично предыдущему примеру. c*(abacaba) неудачного декодирования === 0001001000100 Предположим, что последовательность <tex>abacaba</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> 

==== Примеры префиксных кодов =Не префиксный однозначно декодируемый код ===* Код ХаффманаКак уже было сказано, префиксный код всегда однозначно декодируем. Обратное в общем случае неверно:* Код Шеннона-Фано * UTF-8 <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* Новиков. Ф. А. Новиков. Дискретная «Дискретная математика для программистов программистов» {{---}} Издательство: «Питер», 2001 г. {{- --}} 304 стр. {{---}} ISBN 5-94723-741-5 978-5-94723-741-2* Алексеев В.Б. «Дискретная математика (II семестр)»