Главная Обратная связь Поможем написать вашу работу!

Дисциплины:

Архитектура (936)
Биология (6393)
География (744)
История (25)
Компьютеры (1497)
Кулинария (2184)
Культура (3938)
Литература (5778)
Математика (5918)
Медицина (9278)
Механика (2776)
Образование (13883)
Политика (26404)
Правоведение (321)
Психология (56518)
Религия (1833)
Социология (23400)
Спорт (2350)
Строительство (17942)
Технология (5741)
Транспорт (14634)
Физика (1043)
Философия (440)
Финансы (17336)
Химия (4931)
Экология (6055)
Экономика (9200)
Электроника (7621)






Анализ и кодирование источника



Источник сообщений называют источником без памяти, если вероятность появления на его выходе очередного символа никак не зависит от предыстории. Энтропия дискретного источника без памяти с алфавитом A={a1, a2, … aM} размерности M и вероятностями символов P(ai) равна

 

бит/символ. (2.1)

 

Избыточность такого источника

 

. (2.2)

Информационная производительность источника

 

бит/с, (2.3)

 

где ТИ – длительность одного элемента сообщения на выходе источника.

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

В настоящее время наиболее эффективным методом статистического кодирования источников без памяти считается код Хаффмана [13, с. 29–34]. Данный код относится к префиксным кодам с переменной длиной кодового слова и позволяет уменьшить среднее количество кодовых символов, передаваемых по каналу связи за счет сопоставления чаще встречающимся символам источника более коротких кодовых комбинаций канала. В префиксном коде никакое завершенное кодовое слово не может быть началом другого кодового слова, что позволяет обеспечить возможность разделения символов и однозначного декодирования без передачи каких-либо разделителей.

Алгоритм построения кода кодa Хаффмана включает 3 этапа:

1. Упорядочение. Символы алфавита источника располагаются в порядке убывания их вероятностей.

2. Редукция. Объединяются 2 знака с наименьшими вероятностями в один составной знак. Символы переупорядочиваются для соблюдения правила убывания вероятностей. Данный этап повторяется циклически до полного объединения всех символов в один.



3. Кодирование. Начинается с последнего объединения. Приписать первой компоненте составного знака символ «0», а второй – символ «1». Продолжать процесс, пока все простые знаки будут закодированы.

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

Пример построения кода Хаффмана. Пусть объем алфавита источника равен M = 6, а символы источника и их вероятности приведены в первых двух строках таблицы 2.1.

Таблица 2.1

ai a1 a2 a3 a4 a5 a6
P(ai) 0,05 0,15 0,05 0,4 0,2 0,15
i(ai), бит 4,32 2,74 4,32 1,32 2,32 2,74
Код
ni

Используя формулу найдем количество информации в каждом символе источника. Результаты расчета внесены в третью строку таблицы 2.1. В соответствии с формулами (2.1) – (2.2) энтропия источника и его избыточность соответственно равны: H(A) ≈ 2,25 бит/символ, η ≈ 0,13. Избыточность велика, статистическое кодирование целесообразно.

Процесс построения кода Хаффмана для рассматриваемого примера иллюстрируется рисунком 2.2. На шаге 0 символы расположены в порядке убывания вероятностей. На шаге 1 наименее вероятные символы a1 и a3 объединяются в составной символ a1 + a3 c вероятностью P(a1 + a3) = P(a1) + P(a3) = 0,1. Теперь в дальнейших объединениях вместо символов a1 и a3 участвует составной символ a1 + a3 со своей вероятностью. На шаге 2 наименьшие вероятности имеют символы a1 + a3 и a6, которые и объединяются в новый символ a1 + a3 + a6, имеющий вероятность P(a1 + a3 + a6) = P(a1 + a3) + P(a6) = 0,25. К шагу 3 самыми маловероятными оказываются символы a2 и a5, они и объединяются на этом шаге в составной символ a2 + a5. Дальнейшие объединения проходят аналогично вплоть до слияния всех символов в один, имеющий единичную вероятность.



 

Рис. 2.2. Построение кода Хаффмана

 

Далее приписываем ветвям верхним ветвям объединений символ «0», а нижним – «1». В результате путь от конечного узла объединений к каждому из исходных символов ai может быть описан как последовательность символов «0» или «1» проходимых на этом пути ветвей. Так, например, символу a6 будет соответствовать цепочка 110. В четвертой строке таблицы 2.1 приведены цепочки кодовых символов (кодовые группы) для всех символов алфавита источника, которые и составляют код.

Как и следовало ожидать, кодовые группы имеют разную длину ni (см. пятую строку таблицы 2.1). Средняя длина кодовой группы равна

Отношение . Таким образом, отклонение средней длины кодовой группы от энтропии составляет всего 2% и эффективность кодирования достаточно высока.

Повысить эффективность статистического кодирования при необходимости можно путем предварительного группирования символов источника в блоки по k символов и переходом к новому источнику с алфавитом объема . Для этого нового источника можно рассчитать вероятности символов и построить код Хаффмана аналогично вышеприведенному.

Примеры построения кода Шеннона-Фано приведены в [5, с. 164–167; 8, с 184–193; 9, с.169–176].



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

Глубина памяти Марковского источника r – это предельное расстояние между последовательными символами на его выходе, для которых имеет место взаимозависимость. Значение r = 1 означает, что текущий символ зависит только от предыдущего и не зависит от предшествовавших ему.

Как и для источников без памяти, минимальная средняя длина кодовой комбинации, приходящаяся на один символ источника с памятью, ограничивается энтропией источника. Чтобы определить эту энтропию, источник разделяют на подисточники, каждый из которых соответствует некоторому возможному исходному состоянию источника перед очередным шагом изменения этого состояния. При этом глубина охвата подисточником предыдущих состояний источника должна соответствовать глубине его памяти [13, с. 42–72].

При r = 1 анализ упрощается и в качестве подисточников можно взять только варианты текущего состояния источника без предыстории. Для двоичного источника таких состояний всего 2 – «0» и «1», обозначим их соответственно S0 и S1.

Энтропия источника с памятью может быть найдена путем статистического усреднения энтропий подисточников:

, (2.4)

 

где P(S0) и P(S1) – безусловные вероятности срабатывания одного и другого подисточника, H0(A) и H1(A) – энтропии подисточников.

Энтропии подисточников равны

 

(2.5)

 

Здесь P(Si|Sj) – условные вероятности перехода на очередном шаге из состояния Sj в состояние Si. Поскольку подисточник охватывает только один символ на выходе источника, то эти условные вероятности равны заданным переходным вероятностям P(Si|Sj) = P(ai|aj).

Входящие в (2.4) безусловные вероятности состояний для стационарной цепи Маркова могут быть найдены по формулам:

 

(2.6)

 

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

 

(2.7)

 

Память источника может только снизить его энтропию, поэтому H(A) ≤ HБП(A) и по разнице этих величин это снижение можно оценить количественно.

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

1. Определяется начальная длина кодируемых цепочек символов с выхода источника l = (r + 1).

2. Составляются все возможные цепочки символов длиной l, рассчитывается вероятность каждой цепочки.

3. Цепочки принимаются в качестве алфавита некоторого эквивалентного источника без памяти и кодируются методом Хаффмана или Шеннона-Фано.

4. Вычисляется средняя длина кодовой комбинации, делится на l и сравнивается с ранее вычисленной энтропией источника. Если расхождение велико, l увеличивается на единицу и этапы 2–4 повторяются.

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

.

Подставив значения условных вероятностей в (2.6) и (2.5), найдем безусловные вероятности P(S0) = 0,6, P(S1) = 0,4 и энтропии подисточников H0(A) = 0,722, H1(A) = 0,881. Энтропия источника с памятью в соответствии с (2.4) будет равна H(A) = 0,786. Энтропия эквивалентного источника без памяти определяется выражением (2.7) и равна HБП(A) = 0,971. Таким образом, относительное снижение энтропии за счет памяти источника равно (HБП(A) − H(A))/HБП(A) = 0,19.

Выбираем l = 2, тогда цепочки символов, их вероятности и полученный код Хаффмана будут соответствовать таблице 2.2.

Таблица 2.2

Цепочка Вероятность Код Длина
P00 = P(S0)P(S0|S0) = 0,48
P01 = P(S0)P(S1|S0) = 0,12
P10 = P(S1)P(S0|S1) = 0,12
P11 = P(S1)P(S1|S1) = 0,28

 

Средняя длина кодовой комбинации , а в расчете на один символ алфавита источника , что значительно больше энтропии H(A) = 0,786. Следовательно, необходимо увеличить l на единицу и повторить процедуру кодирования.

Для l = 3 цепочки символов и код Хаффмана приведены в таблице 2.3.

Таблица 2.3

Цепочка Вероятность Код Длина
P000 = P(S0)P(S0|S0)P(S0|S0) = 0,384
P010 = P(S0)P(S1|S0)P(S0|S1) = 0,036
P100 = P(S1)P(S0|S1)P(S0|S0) = 0,096
P110 = P(S1)P(S1|S1)P(S0|S1) = 0,084
P001 = P(S0)P(S0|S0)P(S1|S0) = 0,096
P011 = P(S0)P(S1|S0)P(S1|S1) = 0,084
P101 = P(S1)P(S0|S1)P(S1|S0) = 0,024
P111 = P(S1)P(S1|S1)P(S1|S1) = 0,196

 

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


Просмотров 543

Эта страница нарушает авторские права




allrefrs.ru - 2021 год. Все права принадлежат их авторам!