Однозначно декодируемый код — это код, в котором любое сообщение может быть расшифровано единственным способом.
Равномерное кодирование (все кодовые слова одинаковой длины) всегда обеспечивает однозначное декодирование.
Неравномерное кодирование (кодовые слова разной длины) требует выполнения специальных условий для однозначности:
условие Фано (прямое). Никакое кодовое слово не должно быть началом (префиксом) другого кодового слова;
обратное условие Фано. Никакое кодовое слово не должно быть окончанием (суффиксом) другого кодового слова.
Построение кодов с помощью дерева. Вася передаёт сообщение, которое состоит из букв В, А, С, Я. Закодируйте букву Я, если В = 1, А = 01, С = 001.
Решение. Для кодирования используем условие Фано и строим дерево, свободный лист которого и будет являться кодом для буквы Я.
Ответ. Я = 000.
Граф Маркова используется для анализа и построения эффективных кодов, учитывающих вероятности символов. Вершины графа соответствуют состояниям кодирования, рёбра — переходам между состояниями при обработке символов. Это позволяет оптимизировать длину кодовых слов для частых символов.
