Лабораторная работа №3. «Оптимальное кодирование».

Теоретическая часть.

Определение 3.1. m-значным кодированием сообщений α алфавита А, в кодовом алфавите В, называется отображение , где S – множество сообщений, В^* - множество всех слов в алфавите В, содержащем m символов. F (α) называется кодом сообщения α .

Определение 3.2. Кодирование называется алфавитным, если оно сохраняет произведения слов. Для алфавитного кодирования коды однобуквенных сообщений называются элементарными.

Определение 3.3. Соответствие между буквами алфавита А и их элементарными кодами при алфавитном кодировании называется схемой кодирования.

Определение 3.4. Схема кодирования называется префиксной, если никакой элементарный код не является началом другого элементарного кода.

Определение 3.5. Средней длиной элементарного кода называется , где - длина элементарного кода β_i.

Определение 3.6. Коэффициентом относительной эффективности кодирования называется величина

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

Теорема 3.1. Для любого дискретного источника, характеризующегося вероятностной схемой Х с конечным алфавитом и энтропией Н(Х), существует m-ичный префиксный код, в котором средняя длина кодового слова удовлетворяет неравенству

.

При построении оптимальных кодов можно использовать алгоритмы Шеннона-Фано или Хаффмана.

Алгоритм Шеннона-Фано.

1. Множество сообщений данной вероятностной схемы располагается в порядке убывания вероятностей.

2. Множество сообщений разбивается на части, приблизительно равные по суммарной вероятности. Первой части присваивается ноль, второй единица.

3. К каждой из частей применяются действия пункта 2.

Условием окончания работы алгоритма является наличие одного символа в каждой из подгрупп.

Алгоритм Хаффмана.

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

2. Последние два символа объединяются в один с вероятностью, равной сумме вероятностей объединенных символов.

3. С полученной последовательностью произвести действия пунктов 1 и 2, до образования последовательности из одного символа с суммарной вероятностью равной 1.

4. Строится кодовое дерево, в корне которого стоит символ с вероятностью 1.

ПРИМЕР

Задание. Произвести статистическую обработку данного сообщения, считая, что источник сообщений периодически, достаточно долго выдаёт следующую последовательность символов 12342334551233. Определить энтропию, приходящуюся в среднем на одну букву, длину кода при равномерном кодировании и избыточность. Построить схемы алфавитного кодирования методами Фано и Хаффмана. Найти среднюю длину элементарного кода, эффективность сжатия. Предусмотреть возможность кодирования короткого сообщения в данном алфавите, введённого с клавиатуры, по каждой из схем.

Статистическая обработка приведённого сообщения, была выполнена в предыдущем примере, где и была получена вероятностная схема

Х						∑
n
w

Построим схему кодирования по алгоритму Шеннона-Фано.

символ	Р		код

Средняя длина кодового слова равна

Коэффициент эффективности равен

Построим схему кодирования по алгоритму Хаффмена.

символ	Р		код

Средняя длина кодового слова равна

Коэффициент эффективности равен

практическая часть

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

При выводе на экран в соответствующих таблицах должны присутствовать столбцы: номер по порядку; символ; относительная частота; элементарный код.

Вопросы

10. Кодирование. Алфавитное кодирование. Основные понятия.

11. Префиксные схемы алфавитного кодирования.

12. Неравенство Крафта-Макмиллана.

13. Стохастические источники сообщений. Основные понятия. Теоремы Шеннона.

14. Экономное кодирование. Определение, основные свойства.

15. Методы кодирования Фано и Хаффмана.