Изменения

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

Пусть <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=Любое постфиксное кодирование является взаимно однозначнымможно декодировать только единственным способом.}}

* [[Представление символов, таблицы кодировок#Кодировки стандарта ASCII | ASCII]] — блочный.* [[Алгоритм Хаффмана | Код Хаффмана]] (''англ. Huffman code'') — префиксный.* Азбука Морзе* ASCII— не является ни блочным, ни префиксным, тем не менее, однозначно декодируемый засчет использования пауз.

|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>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>Ноесли среди кодовых слов будут одинаковые, такой то однозначно декодировать этот код используется очень редко, потому что для его декодировки нужно получить все сообщение целикоммы уже не сможем.

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

=== Пример неудачного декодирования ===Предположим, что предыдущая последовательность <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> 

===Не префиксный однозначно декодируемый код = Примеры префиксных кодов ==Как уже было сказано, префиксный код всегда однозначно декодируем. Обратное в общем случае неверно: <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