Изменения

Перейти к: навигация, поиск

Кодирование информации

567 байт убрано, 19:14, 4 сентября 2022
м
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'') — код, в котором любое слово составленное из кодовых слов можно декодировать только единственным способом.
}}
Пусть есть код заданный следующей кодовой таблицей.:  <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> <tex>b_{i_n} = b_{j_m}</tex>;
Заметим, что если среди кодовых слов будут одинаковые, то однозначно декодировать этот код мы уже не сможем.
 
==== Не префиксный и не постфиксный однозначно декодируемый код ====
Пример:
<tex>U = \mathcal {f} a, b, c \mathcal {g}</tex>; <tex>Z = \mathcal {f} 1, 2, 3 \mathcal {g}</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>
Но, такой код используется очень редко, потому что для его декодировки нужно получить все сообщение целиком.
== Префиксный код ==
{{Определение
|id=def4
|definition='''Префиксный код''' (англ. ''prefix code'') — код, в котором никакое кодовое слово не является префиксом какого-то другого кодового слова.
}}
Также префиксный код иногда называют ''мгновенным кодом (instantaneous codes)''<ref>Джеймс Андерсон. «Дискретная математика и комбинаторика», 2004г. Глава 18. Теория кодов. стр. 754</ref>.
Предпочтение префиксным кодам отдается из-за того, что они упрощают декодирование. Поскольку никакое кодовое слово не выступает в роли префикса другого, кодовое слово, с которого начинается файл, определяется однозначно, как и все последующие кодовые слова.
=== Пример:кодирования ===  <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>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> 
Полученная строка совпадает только в битах, которые находились до ошибочного, поэтому декодирование неравномерного кода, содержащего ошибки, может дать абсолютно неверные результаты.
===Не префиксный однозначно декодируемый код = Примеры префиксных кодов ==Как уже было сказано, префиксный код всегда однозначно декодируем. Обратное в общем случае неверно: <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 семестр)»
[[Категория: Дискретная математика и алгоритмы]]
[[Категория: Представление информации]]
1632
правки

Навигация