Алфавитное неравномерное двоичное кодирование с равной длительностью элементарных сигналов. Префиксные коды
Более оптимальным способом неравномерного двоичного кодирования является такое, при котором выделение из него каждого отдельного знака (т.е. декодирование) оказывается однозначным без специальных указателей разделения знаков. Наиболее простыми и употребимыми кодами такого типа являются так называемые префиксные коды, которые удовлетворяют условию Фано: неравномерный код может быть однозначно декодирован, если никакой из кодов не совпадает с началом (префиксом) какого-либо иного более длинного кода.
Например, если имеется код 110, то уже не могут использоваться коды 1, 11, 1101, 110101 и пр. Если условие Фано выполняется, то при декодировании сообщения путем сопоставления со списком кодов всегда можно точно указать, где заканчивается один код и начинается другой.
Например, требуется декодировать сообщение: 00100010000111010101110000110. И мы знаем, что буква м закодирована комбинацией 00, а буква а – 10.
Тогда декодирование производится циклическим повторением следующих действий.
1. отрезать от текущего сообщения крайний левый символ, присоединить к рабочему кодовому слову;
2. сравнить рабочее кодовое слово с кодовой таблицей; если совпадения нет, перейти к (1);
3. декодировать рабочее кодовое слово, очистить его;
4. проверить, имеются ли еще знаки в сообщении; если "да", перейти к (1).
Применение данного алгоритма дает:
Таким образом, использование префиксного кодирования позволяет делать сообщение более коротким, поскольку нет необходимости передавать разделители знаков.
Однако условие Фано не устанавливает способа формирования префиксного кода и, в частности, наилучшего из возможных.
Префиксный код Шеннона-Фано
Все буквы записываются в порядке убывания их вероятностей, причем должно выполняться условие 
. Затем делятся на две группы таким образом, чтобы вероятности обеих групп были приблизительно равны. Одна из групп кодируется нулем, другая - единицей. Затем каждая из групп делится на равновероятные подгруппы, которые также кодируются 0 и 1 и так далее, пока не будут получены коды каждой из букв. Пример построения префиксного кода Шеннона-Фано приведен на рисунке. 
Средняя длина полученного кода будет равна
Недостатком применения кода является тот факт, что вероятности появления 0 и 1 не всегда одинаковы. Например, в следующем случае вероятность появления 0 – 0,35%, а 1 – 0,65%:
Префиксный код Хаффмана
Данный метод основан на идее построения промежуточных алфавитов.
Сначала все знаки алфавита выписываются в порядке убывания вероятностей. При построении промежуточного алфавита:
1. два знака алфавита с наименьшими вероятностями объединяются в одну группу (их вероятности тоже суммируются);
2. полученные (n-1) знаков упорядочиваются по величине вероятностей; переход к пункту 1.
3. Пункты 1 и 2 повторяются до тех пор, пока во вспомогательнолм алфавите не останутся два знака.
Например: пусть имеется первичный алфавит A, состоящий из шести знаков a1, ..., a6 с вероятностями появления в сообщении, соответственно, 0,3; 0,2; 0,2; 0,15; 0,1; 0,05.
Создадим новый вспомогательный алфавит A(1), объединив два знака с наименьшими вероятностями (a5 и a6) , их суммарная вероятность будет равна 0,1+0,05 = 0,15; остальные знаки исходного алфавита включим в новый без изменений. Общее число знаков в новом алфавите, очевидно, будет на один меньше, чем в исходном.
Аналогичным образом продолжим создавать новые алфавиты, пока в последнем не останется два знака. Ощее число таких шагов будет равно N – 2, где N – число знаков исходного алфавита (в нашем случае N = 6, следовательно, необходимо построить 4 вспомогательных алфавита).
В промежуточных алфавитах каждый раз будем переупорядочивать знаки по убыванию вероятностей.
Всю процедуру построения представим в виде таблицы:
Теперь в обратном направлении проведем процедуру кодирования.
Двум знакам последнего алфавита присвоим коды 0 и 1 (верхний знак будет иметь код 0, а нижний – 1).
В нашем примере знак a1(4) алфавита A(4), имеющий вероятность 0,6 , получит код 0, а a2(4) с вероятностью 0,4 – код 1.
В алфавите A(3) знак a1(3) с вероятностью 0,4 сохранит свой код (1); коды знаков a2(3) и a3(3), объединенных знаком a1(4) с вероятностью 0,6 , будут уже двузначным: их первой цифрой станет код связанного с ними знака (т.е. 0), а вторая цифра – как условились – у верхнего 0, у нижнего – 1; таким образом, a2(3) будет иметь код 00, а a3(3) – код 01. Полностью процедура кодирования представлена в следующей таблице:
Из самой процедуры построения кодов легко видеть, что они удовлетворяют условию Фано и, следовательно, не требуют разделителя. Средняя длина кода при этом оказывается:
Применение описанного метода для букв русского алфавита дает следующие коды:
Код Хаффмана оказывается самым экономичным. Доказано, что ни для какого метода кодирования длина кода не может оказаться меньше, чем код Хаффмана.
Метод Хаффмана и его модификация – метод адаптивного кодирования (динамическое кодирование Хаффмана) – применяется в программах-архиваторах, программах резервного копирования файлов и дисков, в системах сжатия информации в модемах и факсах.