1632
правки
Изменения
м
Пусть <tex>U</tex> {{---}} множество исходных ==== Виды кодов ====* '''[[Представление символов, <tex>Z</tex> таблицы кодировок | Код фиксированной длины]]''' (англ. ''fixed-length code'') {{---}} кодовый алфавит, <tex>Z^кодирование каждого символа производится с помощью строк одинаковой длины. Также он называется ''равномерным'' или ''блоковым'' кодом.*</tex> '''Код переменной длины''' (англ. ''variable-length code'') {{---}} строчки из <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) {{---}} кодирование производится с помощью строк переменной длины. Также называется ''неравномерным кодом''.* '''Разделимый код''' (однозначно декодируемый) {{---}} код]] — для такого кода любое слово, составленное из кодовых слов, в котором никаким двум словам кодируемого алфавита не может быть сопоставлен один и тот же кодможно декодировать только единственным способом.
Пусть есть код заданный следующей кодовой таблицей.: <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>b_{i_n} = b_{j_m}</tex>; Заметим, что если среди кодовых слов будут одинаковые, то однозначно декодировать этот код мы уже не сможем.
{{Теорема|statement=Зная кодовые слова, мы может определить можно ли составить из них однозначно декодируемый код<reftex>Яблонский С.В "Введение в дискретную математику".\dots </reftex>}}
==== Не префиксный и не постфиксный однозначно декодируемый код ====Пример: <tex>U = \mathcal b_{fi_n} a, b, c \mathcal {g}</tex>; <tex>Z = \mathcal {f} 1, 2, 3 \mathcal b_{gj_m}</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>Ноесли среди кодовых слов будут одинаковые, такой то однозначно декодировать этот код используется очень редко, потому что для его декодировки нужно получить все сообщение целикоммы уже не сможем.
Любой префиксный код является однозначно декодируемым и разделимым. Также префиксный код иногда называют ''мгновенным кодом''<ref>Джеймс Андерсон. "Дискретная математика и комбинаторика", 2004г. Глава 18. Теория кодов. стр. 754</ref>.
Использование префиксного кода очень выгодно для кодирования больших аудио<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>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>
* Необходимость хранить словарь декодировки символов.
rollbackEdits.php mass rollback
{{Определение
|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>
}}
==== Примеры кодов ====
* [[Представление символов, таблицы кодировок#Кодировки стандарта ASCII | ASCII]] — блочный.* [[Алгоритм Хаффмана | Код Хаффмана]] (''англ. Huffman code'') — префиксный.* Азбука Морзе* ASCII— не является ни блочным, ни префиксным, тем не менее, однозначно декодируемый засчет использования пауз.
== Однозначно декодируемый код ==
{{Определение
|id=def3
|definition='''Однозначно декодируемый код''' (англ. ''uniquely decodable code'') — код, в котором любое слово составленное из кодовых слов можно декодировать только единственным способом.
}}
<tex> b_{i_2} = b_{Теорема|statement=Для любого однозначно декодируемого кода выполняется [[Неравенство Крафта]]<ref>Новиков Ф.А. "Дискретная математика для программистов"j_2} </reftex>}}
== Префиксный код ==
{{Определение
|id=def4
|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>00\ 01\ 00\ 1\ 00\ 01\ 00</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>
== См. также ==
* [[Неравенство Макмиллана]]
== Примечания Источники информации ==<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* Новиков. Ф.А. Дискретная «Дискретная математика для программистов программистов» {{---}} Издательство: «Питер», 2001 г. {{--- }} 304 стр. {{---}} ISBN 5-94723-741-5 978-5-94723-741-2* Алексеев В.Б. «Дискретная математика (II семестр)»
[[Категория: Дискретная математика и алгоритмы]]
[[Категория: Представление информации]]