Главная страница | Контакты | Случайная страница Автомобили Астрономия Биология География Дом и сад Другие языки Другое Информатика История Культура Литература Логика Математика Медицина Металлургия Механика Образование Охрана труда Педагогика Политика Право Психология Религия Риторика Социология Спорт Строительство Технология Туризм Физика Философия Финансы Химия Черчение Экология Экономика Электроника

Двочное неравномерное кодирование без использования разделителей

Условие Фано:

Неравномерный код может быть однозначно декодирован, если никакой из кодов не совпадает с началом (префиксом) какого-либо иного более длинного кода.

Например, если имеется код 110, то уже не могут использоваться колы 1, 11, 1101, 110101 и пр.

Если условие Фано выполняется, т при прочтении (расшифровке) закодированного сообщения путём сопоставления со списком кодов всегда можно точно указать, где заканчивается одно кодовое слово и начинается другое.

Рассмотрим пример:

Пусть имеется таблица префиксных кодов:

Требуется декодировать сообщение: 00100010000111010101110000110.

Декодирование производится циклическим повторением следующих действий.

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

2. Сравнить рабочее кодовое слово с кодовой таблицей; если совпадения нет, перейти к шагу 1.

3. Декодировать рабочее кодовое слово, очистить его.

4. Проверить, имеются ли ещё знаки в сообщении; если «да», перейти к шагу 1.

Применение этого алгоритма даёт:

Проведя процедуру до конца, получим сообщение: «мама мыла раму».

Таким образом, использование префиксного кодирования позволяет делать сообщение более коротким, поскольку нет необходимости передавать разделители знаков.

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

Способ оптимального префиксного двоичного кодирования был предложен Д. Хаффманом. Метод Хаффмана и его модификация – метод адаптивного кодирования (динамическое кодирование Хаффмана) - нашли широчайшее применение в программах-архиваторах, программах резервного копирования файлов и дисков, в сисиемах сжатия информации в модемах и факсах.

Теоретически имеется огромная возможность для сжатия текста (для английского текста – 67 %). Текстовый файл может быть теоретически быть сжат до размера, составляющего одну треть от первоначального. Однако, чтобы достигнуть этих результатов необходимо использовать сложный процесс кодирования и декодирования. Само по себе кодирование по алгоритму Хаффмана не позволит нам продвинуться значительно вперёд, поскольку даже кодирование 27² =729 пар букв даёт нам всего лишь скромную компрессию по сравнению с тем, что возможно теоретически.