1632
правки
Изменения
м
Пусть есть код заданный следующей кодовой таблицей.: <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>11212311</tex> Мы можем ее однозначно декодировать, т.к. знаемЗаметим, что слева от двойки и справа от тройки всегда стоит единица.Алгоритм декодировки: 1. Найдем в кодовой строке все двойки и заменим последовательность <tex>12</tex> на символ <tex>b</tex> 2. Найдем в кодовой строке все тройки и заменим последовательность <tex>31</tex> на символ <tex>c</tex> 3. Все оставшиеся единички декодируем как символ <tex>a</tex>В таком случае получаем: <tex>abbca</tex>Ноесли среди кодовых слов будут одинаковые, такой то однозначно декодировать этот код используется очень редко, потому что для его декодировки нужно получить все сообщение целикоммы уже не сможем.
Также префиксный код иногда называют ''мгновенным кодом (instantaneous codes)''<ref>Джеймс Андерсон. «Дискретная математика и комбинаторика», 2004г. Глава 18. Теория кодов. стр. 754</ref>.
<tex>00\ 01\ 00\ 1\ 00\ 01\ 00</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>
}}
==== Виды кодов ====
* '''[[Представление символов, таблицы кодировок | Код фиксированной длины]]''' (англ. ''fixed-length code'') {{---}} кодирование каждого символа производится с помощью строк одинаковой длины. Также он называется ''равномерным'' или ''блоковым'' кодом.{{Утверждение|statement=Любой равномерный код является взаимно однозначным.}}* '''Код переменной длины''' (англ. ''variable-length code'') {{---}} кодирование производится с помощью строк переменной длины. Также называется ''неравномерным кодом''.* '''Разделимый * [[Кодирование информации#Префиксный код''' (однозначно декодируемый) {{---}} код, в котором никаким двум словам кодируемого алфавита не может быть сопоставлен один и тот же код.* | '''Префиксный код''' ]] {{---}} код, в котором, никакое кодовое слово не является началом другого.{{Утверждение|statement=Любое префиксное кодирование является взаимно однозначным.}}* Аналогично, можно определить '''Постфиксный постфиксный код''' (суффиксный) {{---}} — это код, в котором никакое кодовое слово не является концом другого.{{УтверждениеВсе вышеперечисленные коды являются [[Кодирование информации#Однозначно декодируемый код |statement=Любое постфиксное кодирование является взаимно однозначным'''однозначно декодируемыми''']] — для такого кода любое слово, составленное из кодовых слов, можно декодировать только единственным способом.}}
==== Примеры кодов ====
* [[Представление символов, таблицы кодировок#Кодировки стандарта ASCII | ASCII]] — блочный.* [[Алгоритм Хаффмана | Код Хаффмана]] (''англ. Huffman code'') — префиксный.* Азбука Морзе* ASCII— не является ни блочным, ни префиксным, тем не менее, однозначно декодируемый засчет использования пауз.
== Однозначно декодируемый код ==
{{Определение
|id=def3
|definition='''Однозначно декодируемый код''' (англ. ''uniquely decodable code'') — код, в котором любое слово составленное из кодовых слов можно декодировать только единственным способом.
}}
== Префиксный код ==
{{Определение
|id=def4
|definition='''Префиксный код''' (англ. ''prefix code'') — код, в котором никакое кодовое слово не является префиксом какого-то другого кодового слова.
}}
Предпочтение префиксным кодам отдается из-за того, что они упрощают декодирование. Поскольку никакое кодовое слово не выступает в роли префикса другого, кодовое слово, с которого начинается файл, определяется однозначно, как и все последующие кодовые слова.
=== Пример:кодирования === <tex>U = \mathcal {f} a, b, c \mathcal {g}</tex>; <tex> Z = \mathcal {f} 0, 1 \mathcal {g}</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 = \{ 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 семестр)»
[[Категория: Дискретная математика и алгоритмы]]
[[Категория: Представление информации]]