<< Предыдущая

стр. 11
(из 50 стр.)

ОГЛАВЛЕНИЕ

Следующая >>


Сумма по всем символам Х\ при заданном состоянии Si равна энтро-
пии г-го подисточника
N
= bgP(x/|S0 = Y,«(iW(X\Si) (-9
57 )
^(i/j^PMSi)
Si «=1
Xt


и утверждение (5.72) доказано.
Шаг 2.
До сих пор мы исходили из фиксированного начального состоя-
ния. Для того, чтобы определить энтропию, марковского источника
через математическое ожидание, будем считать начальное состояние
случайным
N N
(5.80)
H(X,\Xi-!, ...,XO,ZO) = Y1 Y,PZoti)n(i/J)H(X\Si).
j=it=i


Сумма по j включает в себя все переходы в г-ое состояние, что да-
ет в результате вероятность г-го состояния на {-ом шаге. Учитывая
стационарность источника, получаем
N

Y,PZoti)Mi/J)=Po°(i)- (5.81)
3=1
65 ,
5-4- Энтропия стационарного марковского источника

Окончательно имеем
N
(5.82)
H{Xl\Xl_u...,X0,ZQ) = ^Poo(i)H(X\Si).

Заметим, что условная энтропия стационарного марковского источ-
ника не зависит от числа символов I. Первые части равенств (5.82) и
(5.71) одинаковы. Остается доказать равенство левых частей (5!82)
и (5.71) при / — сю.
»

Ш а г 3.
Рассмотрим выражение для энтропии при известном начальном
состоянии и преобразуем его с помощью «правила цепочки»

X0\Z0) = j[H(Xo\Zo) + • • • + (5.83)
j-H(XL,..., + H(Xi\X0,2b)
+H(XL\XL-u...,Xo,Zo)].

Так как марковский источник стационарен, все слагаемые правой
части равны и определяются в соответствии с (5.82). Если имеется
L слагаемых, то для любого натурального L получаем
N
1
ton TH(XL,... ,X0\Z0) = Y,Poo(i)H(X\Si). . (5.84)

Условие в левой части еще не нарушено. Используя универсальное
соотношение
(5.85)
Н{Х) = I(X; Y) + H(X/Y),
получим

(5.86)
H(XL,...,Xo\Zo) = B(XL,...,Xo)-I{XL,...,Xo;Zo).
Из (5.84) следует
N.
lim [H(XL,...,X0) (5.87)
- I{XL,...,Xo;Zo)] = TPoo(i)H(X\Si).
L—>CXD f—'
С другой стороны, используя универсальное соотношение

(5.88)
I(X;Y) = H(Y)-H(Y/X),

получим

(5.89)
...,Xo;Zo) = H(Zo)-H(Zo/XL,...,Xo).
66 Глава 5. Стационарные дискретные источники с памятью

Для энтропии имеет место оценка

О < H(Z0\XL,...,X0)< H(ZQ) < logN, (5.90)

следовательно

. (5.91)
0<I(XL,...,X0;Z0)<H{Z0)<\ogN

и в предельном случае получим

lim yI(XL,...,Xo;Zo)<0. (5.92)
L >o L
—o
Используя (5.92), из (5.87) для энтропии стационарного марковского
источника окончательно получаем (5.71). •

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



Энтропия близка к единице, так как символы почти равновероятны.
2. Марковский источник с памятью г = 1
Рассмотрим апроксимацию первоначального источника источни-
ком с г <= 1, который состоит из двух нодисточников. С учетом ве-
роятностей (см. рис. 5.8), получаем


^ (5-94)

-тг (1) (2/1)1о ё2 7г (1 >(2/1) = -3/7 log2 3 / 7 - 4 / 7 log2 4 / 7 » 0,985



(5-95)

-7rW(2/2)log27r(1)(2/2) = -3/51og 2 3/5-2/51og 2 2/5» 0,971.

Таким образом, энтропия марковского источника с г = 1 равна



21 20
= — 0,985 + — 0,971 и 0,979. (5.96)
5.5. Кодирование стационарных марковских источников

По сравнению с (1), энтропия немного уменьшилась.
3. Марковский источник с памятью г = 2.
В этом случае мы должны принимать во внимание 4 подисточ-
ника (см. рис. 5.7). Для состояния Si имеем

Hi (X/Z = Si) = 0 бит. (5.97)

Так как подисточник 2 постоянно вырабатывает символ «1», энтро-
пия в состоянии S2 равна

H2{X/Z = S2) = 1 бит. (5.98)

Подисточники 3 и 4 обладают энтропией соответственно


-I Iog 2 J«0,918 (5.99)



В результате получаем энтропию источника с г = 2, равную

4

г=1

= — ( 8 + 12-0,918+ 12-0,811) бит « 0,701 бит. (5.101)
41
Итак, мы видим, что по сравнению с марковским источником с па-
мятью г = 1, энтропия уменьшилась.


5.5. Кодирование стационарных марковских
источников
Прежде всего напомним теорему кодирования источников, сформу-
лированную в теореме 5.2.1. В этой теореме рассматриваются блоки,
содержащие L символов. Теорема утверждает, что в случае, когда
L стремится к бесконечности, для блоков длины L существует пре-
фиксный код, в котором средняя длина кодового слова на один сим-
вол как угодно близка к совместной энтропии Hi(X).
В случае марковского источника с памятью г, совместная энтро-
пия для блока длины L = г является предельным случаем и теорема
кодирования может быть сформулированна следующим образом:
Глава 5. Стационарные дискретные источника с памятью

Теорема 5.5.1. Теорема кодирования стационарных марковских ис-
точников с памятью г и энтропией Н^х).
Для блока длины L > г существует D-ичный префиксный код, в
котором средняя длина кодового слова п удовлетворяет неравенству


L

Из разложения марковского источника на иодисточники без па-
мяти непосредственно вытекает стратегия оптимального кодирова-
ния.
Если начальные состояния известны, то при кодировании источ-
ников все последующие состояния однозначно определены. При этом
в передатчике и приемнике для каждого множества нодисточников
возможно провести кодирование и декодирование Хаффмана, учи-
тывая распределение вероятностей символов и состояний.
Практическая реализация кодов Хаффмана показывает, что для
достижения существенного кодового выигрыша, необходимо кодиро-
вать блоки достаточно большой длины. Кроме этого, базовые со-
стояния всегда должны определяться г символами для того, чтобы
переход к блокам большей длины был относительно несложным.
Предлагаемая простая стратегия полностью учитывает память
источника и, следовательно, в предельном случае, позволяет полу-
чить оптимальный префиксный код.
Кодирование стационарного марковского источника X с памя-
тью г и энтропией, равной Н^Х).

1. Объединить в блоки / = г + 1 символов источника.

2. Провести кодирование Хаффмана для блоков.

3. Если средняя длина кодового слова на символ существенно от-
личается от энтропии НЖ(Х), то увеличить длину блока за счет
последующих символов. Провести кодирование Хаффмана для
блоков большей длины. Продолжить этот процесс до удовле-
творительного приближения средней длины кодового слова к
энтропии.

Пример: Кодирование марковского источника с памятью г = 2
(продолжение).
Проверим эффективность предложенного алгоритма на числен-
ном примере из предыдущего раздела.
5.5. Кодирование стационарных марковских источников


В соответствии с памятью источника г = 2, объединим в блоки
каждые три символа источника и проведем кодирование Хаффмана.
Необходимые вероятности состояний для блоков определяются
стационарным распределением вероятностей (5.58) и матрицей пере-
ходных вероятностей (5.58) или графом состояний (рис. 5.7). Веро-
ятность блока 001, например, равна

Рш = -P(SI)TT(3/1) = Роо(1)тг(3/1) = 9/41 • 1 = 1-. (5.103)

Можно так же заметить, что блок 000 никогда не появляется и, сле-
довательно, не должен кодироваться.
Из таблицы 5.1. находим, что средняя длина кодового слова на
символ равна 0,911. Поэтому эффективность кодирования относи-
тельно мала


Путем построения блоков большей длины, эффективность коди-
рования может быть существенно повышена. Повторим кодирование
Хаффмана для блоков, длина которых равна 4 (табл. 5.2). Из табли-
цы 5.1. следует, что средняя длина кодового слова на символ равна
0, 744. Эффективность кодирования уже равна
Яоо(ж) 0,701
4
= -П˜ * 0 ^ 4 " ° ' 9 4 (5105)


и мы, в основном, реализовали большую часть возможностей коди-
рования, однако, дальнейшим увеличением длины блока можно уве-
личить выигрыш от кодирования.
Пример: Марковский источник первого порядка.
На рис. 5.9 задан граф состояний марковского источника первого
порядка.
1. Дополните недостающие вероятности рис. 5.9 и найдите стаци-
онарное распределение вероятностей состояний.




Р и с . 5.9. Граф состояний марковского источника первого
порядка.
Глава 5. Стационарные дискретные источники с памятью
Таблица 5.1. Кодирование Хаффмана для марковского ис-
точника с памятью г = 2 и длиной блока 3.

Символы Pi Кодовая конструкция Кодовое слово л, "iPi
001 9/41 00 2 18/41
о

<< Предыдущая

стр. 11
(из 50 стр.)

ОГЛАВЛЕНИЕ

Следующая >>