Метод Хафмена.


Порядок:
1) упорядочить вероятности символа m1 в порядке убывания;
2) последние n символов объединяем в новый символ с вероятностью, равной сумме вероятностей, объединеннх символов, причем 2<=n<=m2. Для двоичного кода n=2
3) на некоторых и на последнем этапах значение n может находится в пределах 1<=n<=2. Необходимо учесть, что вновь образовавшиеся узлы должны располагаться таким образом, чтобы значения вероятностей в узлах также были упорядочены:
4) в дополнительный символ объединяются только символы, имеющие на данном этапе построения дерева наименьшую вероятность, с учетом вероятности вновь образовавшегося символа:
5) ветвям, выходящим из узлов качественные признаки алфавита m2 в одном и том же порядке, на каждом уровне дерева:
6) кодовая комбинация – это последовательность качественных признаков от корня дерева к конечным вершинам или конечным узлам.
Если записать исходную фразу с учетом построенного кода, то занимаемый ей объем будет равен 98 битам. Преимущества рассмотренных двух методов в том, что можно получить более короткую длину кодовых слов во вторичном алфавите за счет оптимального выбора вершин на каждом уровне дерева.
Эффект достигается благодаря присвоению самых коротких кодовых комбинаций наиболее вероятным символам, и самых длинных – наименее вероятным.
Чтобы обеспечить однозначное декодирование, необходимо, чтобы ни одна комбинация кода не совпадала с началом более длинной комбинации. Такие коды называют префиксными кодами.
Рассмотренные коды Шенона-Фано и Хафмана являются префиксными.
В последнее время предъявляются высокие требования к достоверности передачи обработки и хранения информации, т.е. необходимо такое кодирование, которое бы обеспечивало обнаружение и исправление ошибок.
Кодирование должно осуществляться таким образом, чтобы сигнал, соответствующий принятой последовательности символов после воздействия на него, предполагаемого в качестве помехи, оставался как можно ближе к сигналу, соответствующему конкретной переданной последовательности символов, чем к сигналам, соответствующим другим последовательностям.
Это достигается путем введения при кодировании так называемой избыточности, которая позволяет так выбрать передаваемые последовательности символов, чтобы они удовлетворяли дополнительным условиям, проверка которых на приемной стороне дает возможность обнаружить и исправить ошибку.
Понятие избыточности введено для количественного описания информационного резерва кода, из которого составлено сообщение. Различают естественную и искусственную избыточность.
Естественная избыточность характерна для первичных алфавитов. Искусственная – для вторичных. В свою очередь естественная избыточность делится на семантическую и статическую.
Семантическая избыточность заключается в том, что мысль, выраженная в сообщении может быть выражена короче
Если сообщение можно сократить, а затем восстановить без изменения смысла, то оно обладает семантической избыточностью.
Семантическую избыточность можно устранить, например, заменяя часто повторяющиеся сообщения условными обозначениями, введением абривиатур, свертыванием информации в таблицы, и т. д.
Статистическая избыточность обусловлена неравной вероятностью распределения качественных признаков первичного алфавита (вероятности появления букв в тексте не равны).
Искусственная избыточность получают вводя дополнительные символы во вторичный алфавит. Если в коде n разрядов и nи из них – несут информационную нагрузку, то nк=n–nи называется абсолютной корректирующей избыточностью, а величина Dк=(n-nи)/nи называется относительной корректирующей избыточностью.
Уменьшая избыточность сообщения, можно увеличить скорость его передачи, а увеличивая избыточность – уменьшить вероятность искажения под действием помех.
Помехой называют стороннее возмущение, действующее в системе и препятствующее приему сигнала.
Помехи бывают: промышленные и атмосферные, внутренние и внешние, закономерные и случайные.
Помехоустойчивостью называется способность системы осуществлять прием информации в условиях наличия помех в линиях связи. Коды, обладающие такими свойствами называют помехоустойчивыми и используются для обнаружения и (или) исправления ошибок.
В основном все коды обладают корректирующей способностью за исключением ОНК-кодов (оптимальный неравномерный код) Шеннона Фано, кодов Бадо, Морзе.