Декодирование эффективных кодов

Особенностью эффективных кодов является переменное число двоичных разрядов в получаемых кодовых комбинациях. Это затрудняет процесс декодирования.

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

Пусть кодовая таблица имеет вид:

а закодированное сообщение - 001000011101.

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

Тогда имеем:

00 10 00 10 11 01

a c a b d b

Таким образом, в исходном сообщении содержится текст acabdb. Декодирование выполнено.

Для декодирования кодов переменной длины рассмотренный подход не годится. Тем не менее закодированные сообщения могут декодироваться благодаря свойству префиксности эффективных кодов: ни одна более короткая кодовая комбинация не является началом более длинной кодовой комбинации.

Для раскрытия данного тезиса воспользуемся построенными ранее эффективными кодами:

a - 1;

b - 01;

c - 001;

d - 000.

Здесь самым коротким кодом является код для символа a со значением 1. Как видно, ни один другой код (более длинный) не имеет в начале символ 1.

Второй по длине код для символа b имеет значение 01 и, как показывает анализ, не является началом ни для кода 001, ни для кода 000. Таким образом, данный код является префиксным.

Свойство префиксности позволяет декодировать сообщения, закодированные эффективными кодами.

Пусть получено сообщение 1010010001, составленное из кодов

a - 1;

b - 01;

c - 001;

d - 000.

Выполним его декодирование.

В сообщении слева направо выделяется по одному двоичному символу и делается попытка декодирования в соответствии с заданной таблицей кодов. Если попытка успешна, двоичный символ (или символы) исключается из исходной цепочки и заменяется соответствующим исходным символом. Если попытка не удается, во входной цепочке выделяется следующий двоичный символ и уже с двумя двоичными символами делается попытка их декодирования по таблице кодов. Если попытка и тогда неудачна, выделяют следующий третий и т.д.

Итак, имеем (направление просмотра цепочки слева направо):

↓	↓	↓	↓	↓	↓	↓	↓	↓	↓
a	-	-	-	a
b	-	-
		c	d

Здесь знак «-» означает, что попытка декодирования не удалась.

Таким образом, при декодировании получили строку abcda.

Отметим, что методы Шеннона-Фано и Хаффмена строят префиксные коды.

Поиск по сайту: