Теория информации |
Конспект лекций |
4. ОПТИМАЛЬНОЕ ПОБУКВЕННОЕ КОДИРОВАНИЕ
4.1 Определения и примеры
При кодировании сообщений считается, что символы сообщения порождаются некоторым источником информации. Источник считается заданным полностью, если дано вероятностное описание процесса появления сообщений на выходе источника. Это означает, что в любой момент времени определена вероятность порождения источником любой последовательности символов . Такой источник называется дискретным вероятностным источником.
Определение. Если вероятностный источник с алфавитом порождает символы алфавита независимо друг от друга, т.е. знание предшествующих символов не влияет на вероятность последующих, то такой источник называется бернуллиевским. Тогда для любого сообщения
,
, порождаемого источником, выполняется равенство:
где P(x) – вероятность появления символа x, – вероятность появления последовательности
.
Для другого класса источников (марковских) существует статистическая взаимосвязь между порождаемыми символами. В дальнейшем будем рассматривать кодирование стационарных (с неизменным распределением вероятностей) бернуллиевских дискретных источников без памяти.
Пусть имеется дискретный вероятностный источник без памяти, порождающий символы алфавита с вероятностями
. Основной характеристикой источникаявляется энтропия, которая представляет собой среднее значение количества информации в сообщении источника и определяется выражением (для двоичного случая)
.
Энтропия характеризует меру неопределенности выбора для данного источника.
Пример 4.1.1. Если , т.е. источник может породить только символ
, то неопределенности нет, энтропия
.
Источник с равновероятными символами , будет иметь максимальную энтропию
.
Определение. Величина называется энтропией на символ последовательности длины L, где
- множество всех сообщений источника длины L в алфавите A.
Определение. Обозначим через предел энтропии
при
. Эту величину называют предельной энтропией источника. Показано, что для стационарного бернуллиевского источника
Для практических применений важно, чтобы коды сообщений имели по возможности наименьшую длину. Основной характеристикой неравномерного кода является количество символов, затрачиваемых на кодирование одного сообщения.
Определение. Пусть имеется разделимый двоичный побуквенный код для источника, порождающего символы алфавита с вероятностями
, состоящий из n кодовых слов с длинами
. Средней длиной кодового слова называется величина
, которая показывает среднее число кодовых букв на одну букву источника.
Пример 4.1.2. Пусть имеются два источника с одним и тем же алфавитом и разными вероятностными распределениями
и
, которые кодируются одним и тем же кодом
.
Средняя длина кодового слова для разных источников будет различной
Определение. Побуквенный разделимый код называется оптимальным, если средняя длина кодового слова минимальна среди всех побуквенных разделимых кодов для данного распределения вероятностей символов.
Определение. Избыточностью кода называется разность между средней длиной кодового слова и предельной энтропией источника сообщений
Избыточность кода является показателем качества кода, оптимальный код обладает минимальной избыточностью. Задача эффективного неискажающего сжатия заключается в построении кодов с наименьшей избыточностью, у которых средняя длина кодового слова близка к энтропии источника. К таким кодам относятся классические коды Хаффмана, Шеннона, Фано, Гилберта-Мура и арифметический код.