Вернер М. Основы кодирования (2004), страница 8

5.6. Представление источника в виде цепи Маркова(первый шаг).Эти эвристические рассуждения обобщены в следующем определении.Определение 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).Если задать еще и начальное распределение состоянийРо = (РО(1),И>(2),РО(3),РО(4)),(5-57)то все требования из 5.3.5 выполнены и конечный марковский источник определен.

Условия (5.55) и (5.56) являются достаточными дляпостроения графа состояний, который изображен на рис. 5.7.1:1/2Рис. 5.7. Граф состояний марковского источника с памятью г.Глава 5. Стационарные дискретные источники с памятьюПроанализируем матрицу переходных вероятностей и исследуемее на регулярность.

Матрица переходных.вероятностей строится пографу состояний рис. 5.7 и имеет вид/00П =0V 3/40 1 01/201/300 1/41/22/30(5.58)Регулярность проверяется с помощью предельной матрицы. Согласно определению 5.3.49 i1 12 12э г}1212(5.59)9 iS 12 129 {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)J5.3.

Конечные цепи Маркова61Пример: Марковский источник с памятью г = 2 (продолжение).• Источник без памяти (I = 0). В числовом примере для а\ = 0и П2 = 1 получаем/ 01(р(0),р(1)) = ^-(9,8,12,12) • 2/з J/V 3/4 1/4• Стационый марковский источник с памятью I = 1. В этом случае модель источника имеет два состояния. Соответствующийграф состояний изображен на рис. 5.8.0;3/7[ °1I лг])1; 2/5Р и с . 5.8. Гр£1ф состояний аппроксимирующего марковского источника.Определим соответствующие графу вероятности. Вероятности состояний равны"•1}l)P(S\ ) = р(0) = |и Р(5< ) = р(1)-= ^ .(5.63)Совместные вероятности пар символов можно непосредственнооценить по первоначальному источнику. Они будут равны вероятностям состояний (5.57)р(0,0)=р о о (1) = |[р(1,1)=Роо(2) = ^(5.64)Теперь можно определить переходные вероятности для аппроксимирующего источника. В соответствии с их определением=*М,(5.65).62Глава 5.

Стационарные дискретные источники с памятьюполучаем матрицу переходных вероятностей(566)3/5 2/5Регулярность проверяем путем нахождения предельной матрицы{ 1 ) =°°/0,5122\ 0,51220,4878 \0,4878 )ш('Так как строки предельной матрицы равны, мы имеем регулярнуюмарковскую цепь с предельным распределениемр£> и (0,5122,0,4878).(5.68)Так как состояния соответствуют символам 0 и 1, должно выполнятьсяр ^ « (21/41,20/41).(5.69)5.4. Энтропия стационарного марковскогоисточникаЭнтропия стационарного марковского источника вычисляется, исходя из того, что каждое состояние источника является подисточникомбез памяти, обладающим определенной энтропией. Таким образом,энтропия первоначального источника равна математическому ожиданию энтропии подисточников.Теорема 5.4.1. Стационарный марковский источник с алфавитом из М символов, имеющий N состояний, т.е iV подисточников,энтропия каждого из которых равнамH(X\Si)= -J2Ps,(xm) l o g 2 ( p s , ( * m ) ) бит,(5.70)m=lобладает энтропией, равной математическому ожиданию энтропииподисточниковНос(х) = Y,P°°H(X/Si).(5.71)г=1В дальнейшем будет показано, что эвристический подход (5.71)соответствует общему свойству энтропии стационарного дискретногоисточника в утверждении 5.1.1.5.4- Энтропия стационарного марковского источникаЗамечание.

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

В качестве дальнейшего ограничения введем состояние ZiP{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.• • \xo,Zo = Sj).(5.75)Величины Z; не оказывают влияния на совместные вероятности, таккак распределения суммы по всем состояниям Z( является гранич-Глава 5. Стационарные дискретные источники с памятьюным.

Учитывая правую часть (5.74), окончательно получаем= Sj) _H(Xi\Xj-\,...,Хр,Zgбит-= J2 РЫZt\Zoxt,z,= Sj) log2P{xt\Zi).(5.76)Вероятность символа Х\ на /-ом временном шаге при заданных 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)Сумма по всем символам Х\ при заданном состоянии Si равна энтропии г-го подисточникаN= bgP(x/|S0 = Y,«(iW(X\Si)^(i/j^PMSi)Si(5-79)«=1Xtи утверждение (5.72) доказано.Шаг 2.До сих пор мы исходили из фиксированного начального состояния. Для того, чтобы определить энтропию, марковского источникачерез математическое ожидание, будем считать начальное состояниеслучайнымNNH(X,\Xi-!, ...,XO,ZO) = Y1 Y,PZoti)n(i/J)H(X\Si).(5.80)j=it=iСумма по j включает в себя все переходы в г-ое состояние, что дает в результате вероятность г-го состояния на {-ом шаге. Учитываястационарность источника, получаемNY,PZoti)Mi/J)=Po°(i)3=1(5.81)5-4- Энтропия стационарного марковского источника65 ,Окончательно имеемNH{Xl\Xl_u...,X0,ZQ)(5.82)= ^Poo(i)H(X\Si).Заметим, что условная энтропия стационарного марковского источника не зависит от числа символов I.

Первые части равенств (5.82) и(5.71) одинаковы. Остается доказать равенство левых частей (5!82)и (5.71) при / —» сю.Ш а г 3.Рассмотрим выражение для энтропии при известном начальномсостоянии и преобразуем его с помощью «правила цепочки»j-H(XL,...,X0\Z0) = j[H(Xo\Zo)+ H(Xi\X0,2b)+ • • • + (5.83)+H(XL\XL-u...,Xo,Zo)].Так как марковский источник стационарен, все слагаемые правойчасти равны и определяются в соответствии с (5.82). Если имеетсяL слагаемых, то для любого натурального L получаем1ton TH(XL,...N,X0\Z0) = Y,Poo(i)H(X\Si).. (5.84)Условие в левой части еще не нарушено. Используя универсальноесоотношениеН{Х) = I(X; Y) + H(X/Y),(5.85)получимH(XL,...,Xo\Zo) = B(XL,...,Xo)-I{XL,...,Xo;Zo).(5.86)Из (5.84) следуетN .lim [H(XL,...,X0)L—>CXD- I{XL,...,Xo;Zo)]= TPoo(i)H(X\Si).f—'(5.87)С другой стороны, используя универсальное соотношениеI(X;Y) = H(Y)-H(Y/X),(5.88)получим...,Xo;Zo)= H(Zo)-H(Zo/XL,...,Xo).(5.89)66Глава 5.

Стационарные дискретные источники с памятьюДля энтропии имеет место оценкаО < H(Z0\XL,...,X0)<H(ZQ) < logN,(5.90)следовательно0<I(XL,...,X0;Z0)<H{Z0)<\ogN.(5.91)и в предельном случае получимlim yI(XL,...,Xo;Zo)<0.(5.92)L—>oo LИспользуя (5.92), из (5.87) для энтропии стационарного марковскогоисточника окончательно получаем (5.71). •В качестве примера рассмотрим опять марковский источник сг = 2 и его апроксимации из предыдущих разделов.1.

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

С учетом вероятностей (см. рис. 5.8), получаем^(1)(5-94)(1-тг (2/1)1о ё2 7г >(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 равна2120= — 0,985 + — 0,971 и 0,979.(5.96)5.5. Кодирование стационарных марковских источниковПо сравнению с (1), энтропия немного уменьшилась.3. Марковский источник с памятью г = 2.В этом случае мы должны принимать во внимание 4 подисточника (см. рис. 5.7).