277
правок
Изменения
Нет описания правки
{{Определение
|id=def2
|definition=Пусть <tex>U</tex> {{---}} множество исходных символов, <tex>Z</tex> {{---}} кодовый алфавит, <tex>Z^*</tex> {{---}} строчки из <tex>Z</tex>.<br> '''Код''' — правило {{---}} отображение <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) {{---}} кодирование каждого символа производится с помощью строк одинаковой длины. Также он называется ''равномерным'' или ''блоковым'' кодом.
Пусть есть код заданный следующей кодовой таблицей.
<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>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>
В таком случае получаем:
|definition='''Префиксный код''' — код, в котором никакое кодовое слово не является префиксом какого-то другого кодового слова.
}}
Предпочтение префиксным кодам отдается из-за того, что они упрощают декодирование. Поскольку никакое кодовое слово не выступает в роли префикса другого, кодовое слово, с которого начинается файл, определяется однозначно, как и все последующие кодовые слова. Поэтому можно декодировать сообщение не получая его целиком, а по мере его поступления. Благодаря этому, префиксный код еще называют ''мгновенно декодируемым''. Использование префиксного кода очень выгодно для кодирования больших аудио/видео файлов, в этом случае мы сможем слушать/смотреть файл по мере скачивания.
Пример:
<tex>00\ 01\ 00\ 1\ 00\ 01\ 00</tex>
поэтому он является префиксным.
==== Преимущества приефиксных кодов ====
* Однозначно декодируемый и разделимый
* Возможности декодировки сообщения, не получая его целиком, а по мере его поступления.
==== Недостатки префиксных кодов ====
<tex>a\quad b\quad a\ c\ c\quad a\ c\ a</tex>
Полученная строка совпадает только в битах, которые находились до ошибочного, поэтому декодирование неравномерного кода, содержащего ошибки, может дать абсолютно неверные результаты.
==== Примеры префиксных кодов ====
