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

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).

Для состояния 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 бит.41(5.101)Итак, мы видим, что по сравнению с марковским источником с памятью г = 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. Эффективность кодирования уже равна4Яоо(ж)0,701= -П~ * 0 ^ 4 " ° ' 9 4(5105)и мы, в основном, реализовали большую часть возможностей кодирования, однако, дальнейшим увеличением длины блока можно увеличить выигрыш от кодирования.Пример: Марковский источник первого порядка.На рис.

5.9 задан граф состояний марковского источника первогопорядка.1. Дополните недостающие вероятности рис. 5.9 и найдите стационарное распределение вероятностей состояний.Р и с . 5.9. Граф состояний марковского источника первогопорядка.Глава 5. Стационарные дискретные источники с памятьюТаблица 5.1. Кодирование Хаффмана для марковского источника с памятью г = 2 и длиной блока 3.Символы Pi0019/411009/410108/411104/411114/41Oil4/411013/410000Кодовая конструкцияКодовое словоо0о000OfliL170i1518°1 711л,"iPi00218/4110218/41010324/41по312/41111312/41оно416/410111412/41л _ 1 112_бит" 3 41 ~0,9112.