Главная arrow Двоичный код arrow Декодирование кодов
Как начинался компьютер
Компьютерная революция
Двоичный код
Разработки военных лет
Интегральные микросхемы
Микрокомпьютер
Персоны
Сеть
Язык компьютера
Развитие ПО
Гибкие системы
Средства разработки
Информатика
Вычислительная наука
Операционные системы
Искусственный интеллект
Предыстория
Поиск
Знания и рассуждения
Логика
Робототехника
 

 
Декодирование кодов Печать

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

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

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

Исходные символы

Двоичные коды

a

00

b

01

c

10

d

11

а закодированное сообщение - 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.

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

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