Равномерные и неравномерные коды. Декодирование сообщений, записанных с помощью неравномерных кодов

Сообщение, зашифрованное неравномерным кодированием (кодовые комбинации имеют различную длину), расшифровывается однозначно, если:

• выполняется условие Фано для декодирования сообщения с начала (никакое кодовое слово не может быть началом другого кодового слова);
• выполняется обратное условие Фано для декодирования сообщения с конца (никакое кодовое слово не может быть концом другого кодового слова).

Методы построения неравномерных кодов: Хаффмана или Шеннона-Фано (данные с известной статистикой), арифметическое кодирование (высокая степень сжатия), адаптивные методы (изменяющиеся данные), LZW (текстовые данные).

Неравномерные коды можно декодировать посимвольно, то есть производить последовательный анализ битов с поиском совпадений по кодовой таблице.

Оценка эффективности производится по формуле Шеннона $H=-\sum _{i=1}^n{p}_i{\text{log}}_2{p}_i,$ где H — энтропия источника информации (количество информации в одном символе, бит/символ), $p_i$ — вероятность появления i-го символа, а n — количество различных символов.

Пример. Вася передаёт со­об­ще­ние, которое состоит из букв В, А, С, Я. Закодируйте букву Я, если В = 1, А = 01, С = 001.
Решение. Для кодирования используем условие Фано и строим дерево, свободный лист которого и будет являться кодом для буквы Я.
Ответ. Я = 000.