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) {{---}} кодирование каждого символа производится с помощью строк одинаковой длины. Также он называется ''равномерным'' или ''блоковым'' кодом.{{Утверждение|statement=Любой равномерный код является взаимно однозначным.}}* '''Код переменной длины''' (variable-length code) {{---}} кодирование производится с помощью строк переменной длины. Также называется ''неравномерным кодом''.* '''Разделимый код''' (однозначно декодируемый) {{---}} код, в котором никаким двум словам кодируемого алфавита не может быть сопоставлен один и тот же код.* декодируемыми'''Префиксный код''' {{---}} код]] — для такого кода любое слово, в которомсоставленное из кодовых слов, никакое кодовое слово не является началом другого.{{Утверждение|statement=Любое префиксное кодирование является взаимно однозначным.}}* '''Постфиксный код''' (суффиксный) {{---}} код, в котором никакое кодовое слово не является концом другого.{{Утверждение|statement=Любое постфиксное кодирование является взаимно однозначнымможно декодировать только единственным способом.}}
Пусть есть код заданный следующей кодовой таблицей.: <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>; Заметим, что если среди кодовых слов будут одинаковые, то однозначно декодировать этот код мы уже не сможем.{{Определение|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 \rfloordots </tex>. Теорема доказана.}}
==== Не префиксный и не постфиксный однозначно декодируемый код ====Пример: <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'') — код, в котором любое слово составленное из кодовых слов можно декодировать только единственным способом.
}}
== Префиксный код ==
{{Определение
|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 семестр)»
[[Категория: Дискретная математика и алгоритмы]]
[[Категория: Представление информации]]