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

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

ОГЛАВЛЕНИЕ

Следующая >>

(первый шаг).

Эти эвристические рассуждения обобщены в следующем опреде-
лении.

Определение 5.3.5. Конечный дискретный марковский источник
с памятью г полностью определяется следующими условиями:
1. Задано непустое множество состояний S = {S\,S2, • • • ,SN},
причем, S содержит векторы длины г;
2. Каждое состояние Sj соответствует дискретному источнику без
памяти с алфавитом Xi = {2:1,0:2,.. • ,хм} и вероятностями j -
ых символов алфавита p^'(j);
5.3. Конечные цепи Маркова

3. Состояние S[n] = (х[п — г], х[п — г + 1],..., х[п — 1]) из г — 1
последовательных символов и очередной символ х[п] образуют
новое состояние S[n + 1] = (х[п — г + 1], х[п — г + 2],..., х[п]);
4. Задано начальное распределение состояний
РО = (РО(1).РО(2),...,РО(ЛО).

Мы видим, что память г охватывает г последовательных симво-
лов, так как на вероятность очередного символа оказывает влияние
в точности г предыдущих символов. Поясним это более подробно на
примере.
Пример: Марковский источник с памятью г = 2.
Рассмотрим двоичный источник с алфавитом X = {0,1}. Комби-
нации двух символов дают четыре состояния

S = {S, * (0,0),5 2 ? (1,1), S3 = (0,1),5 4 = (1,0)}. (5.55)

Переходные вероятности между состояниями задаются величинами


P s , = ( 0 , l ) , p s 2 = (1/2,1/2), (5.56)
Р5з = (2/3,1/3),р Л = (3/4,1/4).

Если задать еще и начальное распределение состояний

(5-57)
Ро = (РО(1),И>(2),РО(3),РО(4)),
то все требования из 5.3.5 выполнены и конечный марковский источ-
ник определен. Условия (5.55) и (5.56) являются достаточными для
построения графа состояний, который изображен на рис. 5.7.



1:1/2




Рис. 5.7. Граф состояний марковского источника с памя-
тью г.
Глава 5. Стационарные дискретные источники с памятью

Проанализируем матрицу переходных вероятностей и исследуем
ее на регулярность. Матрица переходных.вероятностей строится по
графу состояний рис. 5.7 и имеет вид
/
0 010
0 1/2 0 1/2
(5.58)
П= 0 1/3 0 2/3
V 3/4 0 1/4 0
Регулярность проверяется с помощью предельной матрицы. Со-
гласно определению 5.3.4

9 i1 12 12
э г} 12
12
(5.59)
9 iS 12 12
9 {1 12 12
Замечание. Предельная матрица была найдена с помощью про-
граммной системы MatLab (http://www.mathworks.com).
Все строки предельной матрицы равны, следовательно она явля-
ется регулярной. Соответствующее предельное распределение имеет
вид
˜ (5.60)

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

Теорема 5.3.2. Стационарный марковский источник с памятью г
может быть аппроксимирован стационарным марковским источни-
ком с памятью I, где 0 < / < г.
Если величина г заранее известна, то на нервом шаге аппрокси-
мации рассматривается источник без памяти.
Модель источника без памяти полностью описывается распреде-
лением вероятностей символов. Средняя вероятность символов - это
вероятность, которую оценивает наблюдатель, не зная, в каком со-
стоянии Находится источник, поэтому, она определяется стационар-
ным распределением вероятностей состояний Роо и вероятностями
символов а\,...,ам в состояниях S\,..., б1^



,p(aM))=pa (5.61)

\PsN(ai)pSN(a2) • • • PsN(aM)J
61
5.3. Конечные цепи Маркова


Пример: Марковский источник с памятью г = 2 (продолжение).

• Источник без памяти (I = 0). В числовом примере для а\ = 0
и П2 = 1 получаем

/0 1
(р(0),р(1)) = ^-(9,8,12,12) • 2/з J/
V 3/4 1/4
• Стационый марковский источник с памятью I = 1. В этом слу-
чае модель источника имеет два состояния. Соответствующий
граф состояний изображен на рис. 5.8.



л
0;3/7 [ °1 ] Iг 1; 2/5
)




Р и с . 5.8. Гр?1ф состояний аппроксимирующего марковско-
го источника.

Определим соответствующие графу вероятности. Вероятности со-
стояний равны "


и Р(5< 1} ) = р(1)-= ^ .
P(S\l)) = р(0) = | (5.63)

Совместные вероятности пар символов можно непосредственно
оценить по первоначальному источнику. Они будут равны вероятно-
стям состояний (5.57)

р(0,0)=р о о (1) = | р(1,1)=Роо(2) = ^
[

(5.64)



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

=*М, (5.65)
.62 Глава 5. Стационарные дискретные источники с памятью

получаем матрицу переходных вероятностей

(566)
3/5 2/5
Регулярность проверяем путем нахождения предельной матрицы

/ 0,5122 0,4878 \
{1)=
ш (
\ 0,5122 0,4878 )
°° '

Так как строки предельной матрицы равны, мы имеем регулярную
марковскую цепь с предельным распределением

р?> и (0,5122,0,4878). (5.68)

Так как состояния соответствуют символам 0 и 1, должно выпол-
няться
р ^ « (21/41,20/41). (5.69)



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

Теорема 5.4.1. Стационарный марковский источник с алфави-
том из М символов, имеющий N состояний, т.е iV подисточников,
энтропия каждого из которых равна
м
Ps,(xm) l o g 2 ( p s , ( * m ) ) бит, (5.70)
H(X\Si) = -J2
m=l

обладает энтропией, равной математическому ожиданию энтропии
подисточников

(5.71)
Нос(х) = Y,P°°H(X/Si).
г=1

В дальнейшем будет показано, что эвристический подход (5.71)
соответствует общему свойству энтропии стационарного дискретного
источника в утверждении 5.1.1.
5.4- Энтропия стационарного марковского источника

Замечание. Доказательство утверждения достаточно сложно,
поэтому его можно опустить без ущерба для понимания последу-
ющих разделов.
Доказательство. Энтропия марковского источника [10].
Доказательство проводится в три шага.
Шаг 1.
На первом шаге покажем, что при известном состоянии ZQ = Sj
условная энтропия марковского источника определяется как
N
= Si), (5.72)
H(Xi\Xi_u ..., Хо, Zo = Sj) = Y, n(i/j)H(X/Z


где через Xi обозначен 1-ый подисточник, а через Zi - состояние на
шаге /.
Для того, чтобы доказать (5.72), рассмотрим и преобразуем лежа-
щие в основе энтропии условные вероятности P(xi/xi-\, • • • ,хо, ZQ =
Sj). В качестве дальнейшего ограничения введем состояние Zi

P{xi\xi-U • • • .*о, Zo = Sj) = Pfo|Z,,a:,_i,.. .,xo,-Zo = Sj). (5.73)

Так как Z/ полностью определяется начальным состоянием Zo и сим-
волами хо, • • •, xi-\, дополнительное ограничение не влияет на услов-
ную вероятность, т.е. равенство справедливо. Второе преобразование
следует из предполагаемого свойства марковского источника, соглас-
но которому 1-ый символ зависит от 1-го состояния

P{xt\Zi,!,_,, ...,xo,Z0 = Sj) = P(x,\Z,). (5.74)

Для того, чтобы найти условную энтропию (5.72), требуется умно-
жить условные вероятности, лежащие в основе энтропии, на соот-
ветствующие вероятности и найти математическое ожидание

H(X[\Xi-x,..., XQ, ZQ = Sj) _
бит



x log2 P(xi\xi-U. (5.75)
• • \xo,Zo = Sj).

Величины Z; не оказывают влияния на совместные вероятности, так
как распределения суммы по всем состояниям Z( является гранич-
Глава 5. Стационарные дискретные источники с памятью

ным. Учитывая правую часть (5.74), окончательно получаем

= Sj) _
H(Xi\Xj-\,...,Хр,Zg
бит-
= J2 РЫZt\Zo = Sj) log2P{xt\Zi). (5.76)
xt,z,
Вероятность символа Х\ на /-ом временном шаге при заданных ZQ И
SJ равна вероятности Sj в Si при условии, что в состоянии Si задан
символ xi
Р{ц, Zi\ZQ = Sj) = P(i||Sj)7r,(i/j), (5.77)

поэтому, для (5.76) мы можем написать

,Zt\Z0 = Sj)log2P{xi/Zt) =
Y

^ ( х | ^ ) . (5.78)
(



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

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

ОГЛАВЛЕНИЕ

Следующая >>