277
правок
Изменения
Нет описания правки
{{Определение
|id=def1
|definition='''Кодирование информации''' — процесс преобразования информации из одной формы в другуюотображение данных на кодовые слова.
}}
Обычно в процессе кодирования информация преобразуется из формы, удобной для непосредственного использования, в форму, удобную для передачи, хранения или автоматической обработки.
|definition='''Код''' — правило (алгоритм) сопоставления каждому конкретному сообщению строго определённой комбинации символов (знаков или сигналов). Кодом также называется отдельная комбинация таких символов (знаков) — слово. Для различия этих терминов, код в последнем значении ещё называется ''кодовым словом''.
}}
Пусть <tex>U </tex> {{---}} множество исходных символов, <tex>Z </tex> {{---}} кодовый алфавит, <tex>Z^* </tex> {{---}} строчки из <tex>Z</tex>. Код {{---}} отображение <tex>c : U <tex>\rightarrowZ^*</tex> Z*. <tex>c^* : U^* <tex>\rightarrowZ^*</tex> Z*. <tex>c^*(x1x2x_1 x_2 ...xnx_n) = c(x1x_1)c(x2x_2)..c(xnx_n)</tex>
==== Виды кодов ====
* Азбука Морзе
* ASCII
== Однозначно декодируемый код ==
{{Определение
|id=def3
|definition='''Однозначно декодируемый код''' — код, в котором любое слово составленное из кодовых слов можно декодировать только единственным способом.
}}
Пусть есть код заданный следующей кодовой таблицей.
<tex>a_1 \rightarrow b_1</tex>; <tex>a_2 \rightarrow b_2</tex>; ... <tex>a_k \rightarrow b_k</tex>;
Составим слово из кодов с использование операции конкатенации:
<tex>b_{i_1} b_{i_2} ... b_{i_n} = b_{j_1} b_{j_2} ... 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=Для любого однозначно декодируемого кода выполняется [[Неравенство Крафта]]<ref>Доказательство этой и других теорем вы можете найти в книге Яблонского С.В "Введение в дискретную математику".</ref>
}}
==== Не префиксный и не постфиксный однозначно декодируемый код ====
Пример:
<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>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>
Но, такой код используется очень редко, потому что для его декодировки нужно получить все сообщение целиком.
== Префиксный код ==
{{Определение
|id=def3def4
|definition='''Префиксный код''' — код, в котором никакое кодовое слово не является префиксом какого-то другого кодового слова.
}}
Любой префиксный код является однозначно декодируемым и разделимым. Также префиксный код иногда называют ''мгновенным кодом''<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; 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>0001001'''1'''00100</tex>
Разобьем ее согласно словарю:
<tex>00 01 00 1 1 00 1 00</tex> <tex>a b a c c a c a</tex>
Полученная строка совпадает только в битах, которые находились до ошибочного, поэтому декодирование неравномерного кода, содержащего ошибки, может дать абсолютно неверные результаты.
* Необходимость хранить словарь декодировки символов.
