Алгоритм оптимального кодирования Хаффмена

Метод Фано обеспечивает построение префиксных кодов, стоимость которых весьма близка к оптимуму. Хаффмен предложил несколько более сложный, индуктивный метод, в результате применения которого получается префиксный код, стоимость которого оптимальна. Метод Хаффмена опирается на несколько лемм и теорем, важнейшими из которых являются следующие.

Лемма. Пусть – схема оптимального кодирования для распределения вероятностей . Тогда, если , то .

Теорема. Если – схема оптимального префиксного кодирования для распределения вероятностей и , причем , то кодирование со схемой

является оптимальным префиксным кодированием для распределения вероятностей .

Данная теорема определяет следующий способ построения оптимального кода. В исходном, упорядоченном по убыванию списке вероятностей, отбрасываются две последние (наименьшие) вероятности, а их сумма вставляется в список таким образом, чтобы получающийся список из вероятностей снова был упорядочен по убыванию. Затем эта же процедура повторяется со списком из вероятностей и т.д. до тех пор, пока не получится список из двух вероятностей. Первой из получившихся вероятностей приписывается символ 0, а второй – символ 1.

Затем согласно вышеприведенной теореме из оптимального кода для двух букв строится оптимальный код для трех букв при соответствующем списке вероятностей и т.д. до тех пор, пока не получится оптимальный код при исходном списке вероятностей. Описанный метод Хаффмена иллюстрируется в таблице 4.4. последовательностью преобразований вероятностей для того же примера, что и в случае с алгоритмом Фано. Схема кодирования и средняя цена кодирования приведены в таблице 4.3. Цена оптимального кодирования по Хаффмену составляет 0.20*2+0,20*2+0.19*3+0.12*3+0.11*3+0.09*4+0.09*4=2.78, что несколько лучше, чем для схемы, полученной с помощью алгоритма Фано.

Таблица 4.4.

4.2.6. Помехоустойчивое кодирование

Хотя надежность электронных устройств все время возрастает, в их работе возможны ошибки. Сигнал в канале связи может быть искажен помехой, поверхность магнитного носителя может быть повреждена, в разъеме может быть потерян контакт. Ошибки аппаратуры ведут к искажению или потере данных. При определенных условиях можно применять методы кодирования, позволяющие правильно декодировать исходное сообщение, несмотря на ошибки в данных кода. В качестве исследуемой модели достаточно рассмотреть канал связи с помехами, потому что к этому случаю легко сводятся остальные.

Пусть имеется канал связи , содержащий источник помех:

,
где – множество переданных, а – соответствующее множество принятых по каналу сообщений. Кодирование , обладающее таким свойством, что

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

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

Ошибки в канале могут быть следующих типов:

0®1, 1®0 – ошибка типа замещение разряда;

0®L, 1®L – ошибка типа выпадения разряда;

L®0, 1®L – ошибка типа вставки разряда.

Канал характеризуется верхними оценками количества ошибок каждого типа. Общая характеристика ошибок канала (то есть их количество и типы) обозначается как .

Пример. Характеристика означает, что в канале возможна одна ошибка типа замещения разряда при передаче сообщения длины n.

Пусть – множество слов, которые могут быть получены из слова в результате всех возможных комбинаций допустимых в канале ошибок, т.е. . Если , то та конкретная последовательность ошибок, которая позволяет получить из слова слово , обозначается .

Теорема. Чтобы существовало помехоустойчивое кодирование с исправлением всех ошибок, необходимо и достаточно, чтобы , т.е. необходимо и достаточно, чтобы существовало разбиение множества на подмножества , такое, что и при этом выполнялись условия .

Говоря проще, у каждого слова s должна существовать своя собственная «область», никакая ошибка не должна выводить слово за пределы этой области и разные области не должны пересекаться. Понятно, что чем больше размеры этой области, тем надежнее может быть распознавание слова. Соответственно нужна мера, имеющая характер расстояния между словами. Обычно в математике такая мера носит название метрики.