Тема: Кодирование с минимальной избыточностью.

План лекции.

1. Постановка задачи.

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

Постановка задачи.

На практике важно, чтобы коды сообщений имели по возможности наименьшую длину. Алфавитное кодирование пригодно для любых сообщений, если же про множество всех слов алфавита А ничего не известно, то точно сформулировать задачу оптимизации трудно. Однако на практике часто доступна дополнительная информация. Например, для сообщений, представленных на естественном языке, такой дополнительной информацией может быть распределение вероятности появления букв в сообщении. Тогда задача построения оптимального кода приобретает точную математическую формулировку и строгое решение.

Пусть задана некоторая разделимая схема алфавитного кодирования:

Тогда любая схема

где упорядоченный набор есть перестановка упорядоченного набора , также будет разделимой. В таком случае, если длины элементарных кодов равны, то их перестановка в схеме не влияет на длину закодированного сообщения. В том случае, если длины элементарных кодов различны, то длина кода сообщения напрямую зависит и от того, какие элементарные коды каким буквам поставлены в соответствие, и от того, каков состав букв в сообщении.

Если заданы конкретное сообщение и конкретная схема кодирования, то можно подобрать такую перестановку кодов, при которой длина кода сообщения будет минимальной.

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

Алгоритм назначения элементарных кодов, при котором длина кода фиксированного сообщения S будет минимальна при фиксированной схеме s:

− отсортировать буквы в порядке убывания количества вхождений;

− отсортировать элементарные коды в порядке возрастания длины;

− поставить коды в соответствие буквам в установленном порядке.

Пусть задан алфавит:

A = {a₁, a₂, … , a_n}

и вероятности появления букв в сообщении:

P = (p₁, p₂, … , p_n),

где р_i – вероятность появления буквы a_i, причем буквы с нулевой вероятностью появления в сообщении исключены и буквы упорядочены по убыванию вероятности их появления:

p₁ ≥ p₂ ≥ … ≥ p_n > 0.

Для разделимой схемы:

алфавитного кодирования при распределении вероятностей Р существует так называемая средняя цена, или длина кодирования, – это математическое ожидание длины закодированного сообщения, которая обозначается l_s и определяется как:

l_s(P) = p₁· l(b₁) + p₂· l(b₂) + … + p_n· l(b_n) .