Статистические коды

Статистические коды

Учитывая статистические свойства источника сообщений, можно минимизировать среднюю длину кодовых сообщений. Это можно осуществить с помощью, так называемых, статистических кодов. Такие коды являются неравномерными. Длина кодовой комбинации статистического кода зависит от вероятности появления сообщения, соответствующего этой кодовой комбинации.. Сообщениям с большими вероятностями соответствуют более короткие кодовые комбинации, а а сообщениям с меньшими вероятностями – более длинные. В результате сокращается средняя длина кодовой комбинации.

По количеству переносимой информации данные коды приближается к оптимальному коду, т.е. на каждый элемент этого кода приходится около 1 бита информации. А избыточность таких кодов стремится к нулю (но не равна нулю). Поэтому такое кодирование часто называют экономным, а сами коды называют экономными или квазиоптимальными (т.е. подобные оптимальным).

Средняя длина кодовой комбинации определяется выражением

,

где M - количество кодовых комбинаций, - длина i-ой кодовой комбинации, - вероятность появления i-ой кодовой комбинации.

Количество информации приходящейся на один элемент кода определяется выражением

,

где - средняя длина кодовой комбинации, - энтропия источника сообщений.

Согласно теореме Шеннона об оптимальном кодировании в каналах без помех средняя длина кодовой комбинации статистического кода не может быть меньше величины n_min, которая определяется выражением

,

где K - объем алфавита кода, - некоторая малая величина.

Это минимально возможное значение интересно при сравнении эффективности кодов, полученных по различным алгоритмам. Чем ближе средняя длина кодовой комбинации кода к значению n_min, тем эффективнее код. При решении практических задач значением можно пренебречь и пользоваться приближенной формулой.

.

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

.

Рассмотрим алгоритмы построения двух квазиоптимальных кодов.

Код Шеннона-Фано

Алгоритм кодирования Шеннона-Фано заключается в следующем.

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

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

Далее первая группа делится снова на две, по возможности, равновероятные подгруппы. Всем сообщениям первых подгрупп в качестве второго кодового символа приписывается «1», а всем сообщениям вторых подгрупп в качестве второго кодового символа приписывается «0». Процесс деления на подгруппы и присвоения значений элементам кода продолжается до тех пор, пока в каждой из подгрупп не останется по одному сообщению. На этом процесс кодирования прекращается.

Рассмотрим пример.

Дискретный источник выдает сообщения из ансамбля {X_j}, где j = 1, 2, …, 10 с вероятностями, приведенными в таблице

Xj	X1	X2	X3	X4	X5	X6	X7	X8	X9	X10
P(xj)	0,25	0,12	0,10	0,06	0,03	0,02	0,05	0,12	0,17	0,08

Закодировать данные сообщения кодом Шеннона-Фано. Определить среднюю длину кодовой комбинации, количество информации, содержащееся в одном элементе кода, минимальную длину кодовой комбинации и избыточность кода. При определении минимальной длины кодовой комбинации следует воспользоваться приближенной формулой.

Решение.

Таблица, иллюстрирующая процесс построение кода

X1	0,25	1	1					11
X9	0,17	1	0	1				101
X2	0,12	1	0	0				100
X8	0,12	0	1	1				011
X3	0,10	0	1	0				010
X10	0,08	0	0	1	1			0011
X4	0,06	0	0	1	0			0010
X7	0,05	0	0	0	1			0001
X5	0,03	0	0	0	0	1		00001
X6	0,02	0	0	0	0	0		00000

Определение энтропии источника

бит

Определение средней длины кодовой комбинации

элемента

Определение среднего количества информации, приходящейся на один элемент кода

бит/элемент

Определение минимальной средней длины кодовой комбинации

элемента

Определение избыточности кода

Код Хаффмана

Алгоритм кодирования Хаффмана заключается в следующем.

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

В полученном упорядоченном ансамбле сообщений выбираются два сообщения с наименьшими вероятностями их появления. Одному из них (с большей вероятностью) в качестве элемента кодовой комбинации приписывается «1», а другому (с меньшей вероятностью) в качестве элемента кодовой комбинации приписывается «0». Выбранные сообщения объединяют в “промежуточное” сообщения, вероятность которого равна сумме вероятностей объединяемых. Это “промежуточное” сообщение помещают в списке сообщений на место, соответствующее его вероятности. При равенстве вероятностей, как правило, в списке сначала помещают отдельное сообщение, а “промежуточное” после. Потом снова выбирают два сообщения с наименьшими вероятностями и выполняют вышеописанную процедуру. Такой процесс объединения и присвоения значений элементам кода продолжается до тех пор, пока не будет получено одно объединенное сообщение, вероятность которого равна 1. Если получилось больше или меньше единицы, то это означает, что либо была допущена ошибка при суммировании, либо исходные данные некорректны.

Графическое отображение описанного процесса называется графом кода или деревом кода. Кодовая комбинация, соответствующая какому-либо сообщению строится путем обхода по линиям графа кода слева направо и записи элементов кода слева направо, начиная от сообщения для которого эта комбинация строится.

Рассмотрим пример.

Дискретный источник выдает сообщения из ансамбля {X_j}, где j = 1, 2, …, 10 с вероятностями, приведенными в таблице

Xj	X1	X2	X3	X4	X5	X6	X7	X8	X9	X10
P(xj)	0,25	0,12	0,10	0,06	0,03	0,02	0,05	0,12	0,17	0,08

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

Решение.

Построение графа кода

код
10	X1	0,25
111	X9	0,17
011	X2	0,12
010	X8	0,12
001	X3	0,10
1101	X10	0,08
1100	X4	0,06
0001	X7	0,05
00001	X5	0,03
00000	X6	0,02

Определение энтропии источника

бит

Определение средней длины кодовой комбинации

элемента

Определение среднего количества информации, приходящейся на один элемент кода

бит/элемент

Определение минимальной средней длины кодовой комбинации

элемента

Определение избыточности кода

Алгоритм создания кода Хаффмана называется методом “снизу-вверх”, а Шеннона-Фано – методом “сверху-вниз”. Анализ результатов приведенных примеров позволяет сделать вывод, что эффективность полученных кодов одинакова. Однако, это частный случай. В общем случае метод Хаффмана является более эффективным. И при определенном распределении вероятностей в ансамбле сообщения может давать лучший результат, чем метод Шеннона-Фано.

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

Статистическим кодам свойственны недостатки оптимальных кодов, т.е. наличие ошибки в кодовой комбинации не может быть определено на приемной стороне. Поэтому при использовании таких кодов необходимы качественные каналы передачи информации.

Не следует думать, что квазиоптимальные коды представляет число теоретический интерес. Метод Хаффмана и его модификация – метод адаптивного кодирования (динамическое кодирование Хаффмана) – нашли широчайшее применение в программах-архиваторах, программах резервного копирования файлов и дисков, в системах сжатия информации в модемах и факсах.

5