Теория:
Все коды можно разделить на два больших класса.
• 'A' → \(01000001\).
• 'B' → \(01000010\).
Плюсы равномерного кодирования
• Простота декодирования. Если мы точно знаем, что длина каждого символа — \(8\) бит, то, получив поток битов, мы просто делим его на группы по \(8\) и смотрим по таблице, что это за символ. Декодер не должен думать, где заканчивается один код и начинается другой.
• Прямой доступ. Зная номер символа в сообщении, мы можем сразу вычислить его позицию в битовом потоке.
Минус
• Код часто получается избыточным. Например, если нам нужно закодировать всего \(4\) символа (A, B, C, D), то нам хватило бы длины \(2\) бита (\(00\), \(01\), \(10\), \(11\)). Использование равномерного кода длиной \(8\) бит приведёт к тому, что \(6\) бит в каждом символе будут лишними, что увеличивает размер файлов и время передачи.
Сообщения получаются более короткими. Наиболее частые символы кодируются короткими словами, а редкие — длинными. Самый известный пример — код Морзе.
• Буква E (самая частая в английском) → «·» (точка) — один сигнал.
• Буква Q (редкая) → «--·-» (тире-тире-точка-тире) — четыре сигнала.
• А → \(0\).
• Б → \(01\).
• В → \(10\).
• Г → \(11\).
Главная проблема неравномерных кодов
Представим, что мы получили последовательность: \(01011\).
Как её декодировать?
• Вариант \(1\): \(0\) \(10\) \(11\) → А В Г.
• Вариант \(2\): \(01\) \(0\) \(11\) → Б А Г.
• Вариант \(3\): \(0\) \(1\) \(0\) \(1\) \(1\)... (а это вообще бессмыслица).
Мы получили неоднозначность декодирования. Приёмник не может понять, где заканчивается код одного символа и начинается код другого. Чтобы этого избежать, нужно соблюдать специальное условие.
Условие Фано
Это условие является достаточным для того, чтобы неравномерный код можно было однозначно декодировать.
Коды, которые подчиняются этому правилу, называются префиксными.
\(1\). Нарушение условия Фано (плохой код):
А → \(0\);
Б → \(01\) (код А «\(0\)» является началом кода Б «\(01\)»);
В → \(10\);
Г → \(11\).
Получив \(01\), мы не можем сразу понять: это буква А или буква Б? Декодирование останавливается.
А → \(0\);
Б → \(10\);
В → \(110\);
Г → \(111\).
Проверка: код «\(0\)» не является началом «\(10\)» (\(10\) начинается с \(1\)). Код «\(10\)» не является началом «\(110\)» (\(110\) начинается с \(11\), но первые два бита \(11\), а не \(10\)). Код «\(110\)» не является началом «\(111\)». Условие выполнено.
Декодирование: если декодер видит \(0\), он сразу понимает, что это буква А. Если он видит \(1\), он не может принять решение сразу, он смотрит следующий бит. Увидел \(10\) — это Б, \(110\) — В, \(111\) — Г. Никакой путаницы.
Обратное условие Фано
Существует также обратное условие, которое гарантирует декодирование «с конца».