Принцип оптимального статистического кодирования

Нетрудно заметить, что менее вероятные сообщения несут большее количество информации и наоборот. Учитывая это при кодировании m-ичным кодом необходимо менее вероятному сообщению присваивать более длинную комбинацию, а менее вероятному –самую короткую. Т.е. длина кодовой комбинации обратно пропорционально зависит от вероятности.

Алгоритм статистического кодирования Шеннона–Фоно:

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

А) Множество сообщений разбивается либо на два равновероятных (или примерно) множества.

Б) Первому подмножеству присваивается символ «1» второму «0».

Полученные подмножества также разбиваются на два равновероятных с присвоением «1» и «0». Эти разбиения продолжают до тех пор, пока в оставшемся множестве не останется одно сообщение.

Пример:

а	P(ai)	Шаг 1	Шаг 2	Шаг 3	Кодовая комбинация.
А1	0.5
А2	0.25
А3	0.125
А4	0.125				000

Определяем энтропию источника Н(а):

Н (а)=1.75 ^бит/_{сообщение.}

Максимальная энтропия Н₀(а):

max H₀(a)=log m=log 4=2 ^бит/_{сообщение.}

Если не применять оптимального статистического кодирования, а кодировать равномерным двоичным кодом, то достаточно использовать комбинации фиксированной длины.

n=2 ^бит/_{сообщение.},отсюда p(a_i)=p(a_j)=1/m,

численно равно: max H(a)= H₀ (a)

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

m=4

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

Существуют и другие алгоритмы оптимального статистического кодирования. Например, кодирование по алгоритму Хаффмана.

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

Тогда разбиение можно выполнить в виде графа дерева. По-прежнему сообщения должны быть упорядочены (как и вероятности).

Ниже представлен граф, полученный при кодировании предыдущего примера:

a1

a2

a3

Пропускная способность канала передачи без шумов.