Префиксное кодирование

Кодирование с минимальной избыточностью

При равномерном кодировании общая длина кода зависит от длины сообщения. Возникает необходимость произвести неравномерное кодирование так, чтобы избыточность была минимальной.

Пусть задан алфавит А, и мы назначили неравномерные коды этому алфавиту. Например, букве А – 4 – битный код; Б – 6 – битный код; Ъ – 2 – битный код; О – 7 – битный код и так далее. Ясно, что в обычном тексте Ъ встречается реже буквы О, следовательно, если мы переназначим коды: О – 2 – битный код, Ъ – 7 – битный код, то общая длина кода уменьшится.

Алгоритм для сообщения S:

1) Находим частоту появления каждой буквы в заданном сообщении.

2) Элементарный код наименьшей длины ставим в соответствие букве с наибольшей частотой и так далее.

Замечание:

Это кодирование применимо для данного сообщения S. Для другого сообщения частота появления букв может быть другой, следовательно, элементарные коды могут быть другими.

Пусть имеется алфавит А. Таблица соответствия буквам алфавита А элементарных кодов, называется схемой кодирования.

Схема кодирования называется префиксной, если не один элементарный код не является префиксом другого элементарного кода.

Например:

А={a,b}; B={0,1};

={ а0; b01} – не префиксная схема.

={ a0; b10} - префиксная схема.

Схема кодирования называется разделимой, если любой код однозначным образом разбивается на элементарные коды, то есть если код =, ,…, =, ,…, , то =и k=, т.е. возможно однозначное декодирование.

Теорема. Префиксные схемы разделимы.

Доказательство:

Пусть схема ={α_iβ_i}|префиксная, но неразделима. Так как схема неразделима, то существует некоторое t такое, что . А это значит, что есть такое , что или =, то есть элементарный код содержит и , а значит, является префиксом, следовательно, кодирование – не префиксное. Пришли к противоречию, означающее, что наше утверждение о неразделимости схемы неверно, следовательно, схема разделима.

Что и требовалось доказать.

Замечание: утверждение о том, что из разделимости схемы следует её префиксносность, неверно.

Пример:

А={a, b}; B={0, 1};

: {а0; b01} – схема не префиксная. Покажем, что она разделима.

Сообщение: ab 001. Будем декодировать. Первая цифра 0 может быть кодом буквы а, а может быть префиксом буквы b. Но следующая цифра тоже 0. Значит, первый 0 не является префиксом буквы b, т.е. это код буквы а. Если предположить, что второй 0 . это код буквы а, то следующий код начинается с 1, а таких кодов у нас нет, и мы вынуждены признать, что имеем код 01, т.е. букву b. Таким образом, получили 001 ab.

Декодирование можно начать и с конца. Если последний символ 1, то рассмотрим предпоследний. Если он 0, то эти два символа соответствуют букве b. Если он 1, то кодирование произведено неверно. В нашем случае 01 соответствует b.

Исключаем из рассмотрения эти два символа. Следующий символ от конца 0. А 0 – это а. Если у нас есть еще символы – продолжаем.

Еще пример для той же схемы:

aabbaba 0001010010.

Первый символ 0. Это значит, что он может соответствовать а или являться префиксом b. Рассмотрим следующий. Если он 1, то первые два символа являются элементарным кодом b, но не а, т.к. с 1 код начинаться не может. После этого рассматриваем третий аналогично первому. Так как второй символ у нас 0, то первый символ – это элементарный код буквы а. Рассматриваем второй аналогично первому. И т.д.

Замечание: кодирование произведено неверно, если код начинается с 1 или две 1 стоят подряд внутри кода.