5.5. Обобщенная теорема кодирования источника и ее смысл.
Обобщенная теорема кодирования для источника, применимая к кодовым словам как фиксированной, так и переменной длины является обобщением теоремы о кодировании источника кодами фиксированной длины.
При заданном конечном ансамбле источника U c энтропией H(U) и кодовым алфавитом из m символов существует возможность создать код, который отвечает свойству префиксности и имеет среднюю длину, удовлетворяющую условию:
.
5.6. Особенности оптимального кода, построенного по статическому алгоритму Хаффмана.
У такого оптимального кода длины слов не убывают, а две наименее вероятные буквы имеют коды одинаковой длины.
.
Можно сказать, что код Хаффмана всегда является самым экономным из всех возможных в том смысле, что при кодировании источника без памяти и формировании кодовых слов с целым количеством кодовых символов (битов) на 1 символ источника ни для какого другого метода кодирования среднее число элемент кодовых символов, приходящихся на 1 букву источника, не может быть меньше того, какое получилось при кодировании по методу Хаффмана.
5.7. Структура кодера и декодера адаптивного кодирования. Проблемы адаптивного кодирования (на примере адаптивного метода Хаффмана).
Структура программы адаптивного кодирования/декодирования:
КОДЕР
ИнициализироватьМодель();
Пока не конец Сообщения
Символ = ВзятьСледующийСимвол();
Закодировать(Символ);
ОбновитьМодельСимволом(Символ);
Конец Пока
ДЕКОДЕР
ИнициализироватьМодель();
Пока не конец БитовогоПотока
Символ = РаскодироватьСледующийСимвол();
ВыдатьСимвол(Символ);
ОбновитьМодельСимволом(Символ);
Конец Пока
Проблемы:
- инициализация модели (специальные символы EOF и ESCAPE);
- переполнение.
5.8. Принципы арифметического кодирования. Преимущество арифметического кодирования перед кодированием по Хаффману.
Метод Хаффмана порождает наилучшие коды переменной длины (коды, у которых средняя длина равна энтропии источника) только в том случае, если вероятности символов алфавита являются степенями двойки. Это имеет особенно большое значение в случае, если источник сообщения характеризуется большим разбросом вероятностей символов.
Арифметическое кодирование решает эту проблему путем присвоения кода не отдельным символам сообщения, а всему передаваемому файлу в целом. Алгоритм читает входной файл посимвольно и добавляет биты к компрессированному потоку, формируя при этом код в виде числа из интервала [0,1).
Общая идея арифметического кодирования заключается в том, что при кодировании более частых символов интервал между нижней и верхней границами будет увеличиваться и можно будет найти более короткое двоичное представление дробной части, которое однозначно будет определять исходное сообщение.
5.9. Понятие унарного кода. Понятие монотонного кода. Назначение унарного и монотонного кода. Принципы кодирования чисел с разделением мантисс и экспонент.
Унарный код неотрицательного целого числа n состоит из (n-1) нулей (единиц), за которыми следует одна единица (ноль).
Монотонный
код
представляет собой префиксно-свободный
код с минимальными длинами кодовых
слов, в котором если
,
то длина кодового слова
для любых
,
принадлежащих алфавиту источника, т.е.
малые значения получают более короткие
кодовые слова, чем большие значения.
Назначение: закодировать число произвольной величины, когда верхняя граница чисел потока источника (которую необходимо знать, чтобы выбрать фиксированное количество битов на число) заранее неизвестна.
Основная идея кодирования: отдельно описывать порядок значения элемента (экспоненту) и отдельно – значащие цифры значения (мантиссу). Декодирование экспоненты позволяет определить, сколько битов отводится для хранения мантиссы.
Примеры (монотонных) кодов: код Левенштейна, Райса, Голомба, Фибоначчи, серия кодов Элайеса.