1679
правок
Изменения
Нет описания правки
==== Примеры кодов ====
* [[Представление символов, таблицы кодировок#Кодировки стандарта ASCII | ASCII]] — блочный.
* [[Алгоритм Хаффмана | Код Хаффмана]] — префиксный.
* Азбука Морзе — не является ни блочным, ни префиксным, тем не менее, однозначно декодируемый засчет использования пауз.
<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>;
Заметим, что если среди кодовых слов будут одинаковые, то однозначно декодировать этот код мы уже не сможем.
== Префиксный код ==
{{Определение
|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; c(b) = 01; c(c) = 1;</tex>
Такой код можно однозначно разбить на слова:
<tex>00\ 01\ 00\ 1\ 00\ 01\ 00</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 =\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>abbca</tex>, получим кодовую строку <tex>11212311</tex> Мы можем ее однозначно декодировать, так как знаем, что слева от двойки и справа от тройки всегда стоит единица. * [[Алгоритм Хаффмана | Код Хаффмана]]После декодирования получаем:* Код Шеннона-Фано <tex>abbca</tex>
== См. также ==
* [[Неравенство Макмиллана]]
== Литература ==
