Вернер М. Основы кодирования (2004) (1151882), страница 6
Текст из файла (страница 6)
Простейший пример «правила цепочки» для вероятностей р(х, у) = р(х/у)р(у) и р(х, у, z) =p(x/yz)p(y/z)p(z). Так как логарифмическая функция отображлетпроизведение в сумму, получаем «правило цепочки» для совместнойэнтропии.5.1. ЭнтропияAT,, Так как энтропия всегда неотрицательна и имеет место неравенство\откуда следует нижняя оценка 2.3.
Из (5.5) прежде всего следует разложениеHUX)= ^-Н,^(Х)+ jH(XL\X1,X2,LiLJ...,XL-X).(5.7)Используя уже известное соотношение (5.5), получаем неравенствоL.HUX)<(L-l)-HL-l(X)+HL(X).(5.8)После подстановки получаем утверждение 3.HL(X)< HL^{X)..(5.9)4. Утверждения 1., 2. и ограничение Н\{Х) < оо устанавливаютсуществование предела. Используя далее «правило цепочки», получаемттГ LT/ V/V"\VV\|/> -f" 7+ ff(Xi,|Xi, X 2 ,..., X b -i) + Я ( Х ь + 1 | ^ 1 , Jf2, • • •, XL)++ •••+ H(XL+J\XUX2,...,XL+i.i)\.(5.10)Согласно утверждению 1., условная энтропия в правой части .равенства не возрастает, поэтому справедлива оценкаHL+j(X)<1~^l±lH{XL/\X1,Xi,...,XL-1).Lj(5.11)Устремляя j к бесконечности, получимlira HL+j{X)<j-»oolim —"— H(XUX2,..j->oa L+J+• ,XL.-i)+i±±H(XL\X1,X2,...,XL.l),L +Jчто дает для каждого натурального L,Яоо<Я(Хь|А-1,Х 2 ,...
1 Х 1 ,_1),(5.12)(5.13)но, т.к. для любого натурального L выполняется так же и 2., то 5.13превращается в равенство при L —» оо. •Глава 5. Стационарные дискретные источники с памятью5.2. Теорема кодирования источников 2I/Теперь мы можем дополнить теорию информации еще одной теоремой.
Окалывается, что объединяя события источника в блоки длимыL и кодируя эти блоки, средняя длина кодового слова на событиеможет достигнуть энтропию источника Нх(х) при L—>оо как угодноблизко. При этом память источника полностью учитывается.Теорема 5.2.1. Теорема кодирования стационарного дискретного источника с энтропией Hi(X).Для блока длины L существует .D-ичный префиксный код, в котором средняя длина кодового слова на одно событие п удовлетворяетнеравенствуМ § ^ §(5.14)1Теорема (5.14) не нуждается в специальном доказательстве.
Еслимы рассматриваем блоки длины L как новые независимые событияс энтропией, равной L • HL{X) И применяем теорему кодированияисточников 1, то мы имеем^11.(5.15)Разделив все члены неравенства на L, получаем среднюю длину кодового слова на событие) ^ Ш Л .(5.16)При L —» оо, Hi(x) —» Нос(х) = Н(х) мы имеемLHL(X)LHL{X)( 5 1 7 )+6-( 5 Л 8 )Таким образом, для любого сколь угодно малого S, существуетметод кодирования блоков, содержащих L > 1/6 событий, при котором для средней длины кодового слова на событие п выполняетсянеравенство (5.18). Теорема кодирования источников 2 показывает,что увеличивая длину блока L, мы можем как угодно близко подойтик энтропии Н(х) = Ноо(х). Однако, на практике существуют некоторые ограничения. Для того, чтобы блок из L событий мог быть5.3.
Конечные цепи МарковаI' продекодирован, он должен быть полностью принят, что может привести к недопустимым задержкам декодирования и недопустимомуОбъему буфера памяти.5.3. Конечные цепи МарковаВ этом и последующих параграфах будет рассматриваться специальная форма дискретных источников с памятью марковские источники. Их описание сходно с марковскими цепями, которые нашли разнообразное применение в других областях науки и техники.Гак, на основе марковских цепей строятся модели распознавания речи, модели передачи по телефонным коммутируемым каналам.
Цени Маркова1 используются при исследовании моделей сетей связи(каналы Гильберта-Элиота) и в теории управления транспортнымипотоками. Значение цепей Маркова основывается не только на ихполном математическом описании, но также на том факте, что с ихпомощью можно составить математическую модель многих процессов, наиболее близкую к практике.5.3.1. Дискретные во времени цепи МарковаВ этом разделе шаг за шагом вводится понятие конечных дискретных во времени марковских цепей. Мы наглядно поясним это понятие на простейшем примере «случайных блужданий».Пример: Случайные блуждания студента.Нас интересует вопрос о том, доберется ли пьяный студент отдверей пивной до дверей студенческого общежития.
Поставим во-,прос но другому (рис. 5.2): какова вероятность того, что случайныеблуждания на 7 временном шаге приведут студента в пространственное состояние Si? илиР («случайные блуждения» приведут к состоянию Si в моментвремени п = 7).Ситуация, изображенная на рис. 5.2 уже содержит в себе важнейшие признаки цени Маркова. Под марковской цепью понимаетсядискретный во времени и по состоянию марковский процесс S(n).Его реализацией является множество путей, ведущих из состояний5i в состояние S;.'А.
А. Марков (1856 1922) - выдающийся русский математик.Прим. перев.50Глава 5. Стационарные дискретные источники с памятьюШАГИПИВНАЯ0ГЧЖ*~~I TVJ123Щ"74*56Щч*7-'8л5ЯГ 7А.If N,* )*-# м3»5ч1«Lis^.Студенческое общежитие*****Р и с . 5.2. Случайные блуждания студента.Исходным пунктом для описания марковской цепи является множество состояний(5.19)где /V натуральные и стохастический вектор распределения вероятностей состояний в момент времени пРп = (Рп(1),Рп(2),...,Рп(Л г )).(5.20)Для того, чтобы полностью определить цепь Маркова, нам остается задать метод подсчета вероятностей р„(г) для любого моментавремени п.
Из определения вероятности имеем(5.21)г=1Особое значение имеет распределение вероятностей в начале наблюдения, т.е. начальные условияРо = (Ро(1),Ро(2),...,Ро(Л0).(5-22)Смена состояний описывается переходными вероятностямиТад,», 0 7 * ) = P(a[m]= stn s[n2] = Sj).(5.23)Эти переходные вероятности обладают следующими свойствами:1.
Одно из состояний в момент времени п всегда достигается прилюбом Si в момент п\г) = 1-(5.24)5.3. Конечные цепи Маркова512. Граничное распределение, т.е. вероятности j'-ro состояния вмомент времени п2N5Z я'па.щО'Л) = Pmti)-(5-25)3. Рекурсивная формула для переходных вероятностей (частныйслучай уравнения Колмогорова - Чэнмена.)Nтпз.шО'А) = X! 7r "3,n2070Tn 2 ,ni(/A)-(5.26)Дискретное равенство Колмогорова - Чэпмена получается трансформацией «правила цепочки» для вероятностейp{xi,x2)=p(x2/xi)p(xi),(5.27)р(х ь а;2,хз) = p(x3/xi,x 2 )p(x2/xi)p(xi).(5.28)Умножая обе части равенства на \/р(х{), получимр{х2,х3/х3)=р(хз/х1,х2)р(х2/х1).(5.29)Суммируя по всем х2, приходим к дискретной форме уравнения Колмогорова - Чэпменаp(x3/xi) = ^2P(X3'/XI,X2)P(X2/XI).х2(5.30)При преобразовании (5.30) в (5.26), мы предполагаемр(хз/хьх 2 ) =р(х 3 /хг).(5.31)Последнее равенство характеризует марковский процесс.Определение 5.3.1.
Марковским процессом называется процесс, вкотором прошлое не оказывает влияния на будущее, если настоящееизвестно.Замечание. В рассмотренном примере известное прошлое этостохастическая переменная Х\, известное настоящее - Х2, неизвестное будующее - Х3.Применение цепей Маркова сильно упрощается, когда они гомогенны, стационарны и регулярны. Рассмотрим эти три понятия.Глава 5. Стационарные дискретные источники с памятьюОпределение 5.3.2.
Цепь Маркова гомогенна, если переходные ве- /роятности между состояниями не зависят от выбора временной точ-еки отсчета./Таким образом, переходные вероятности зависят только от раз(ности времен отсчетов I.Tr{j/i) = p(s[n] = Si U a[n + I] = Sj) n = 0,1,2,3,... .(5.32)В этом случае для I = ri2 - n\ и т = пз — пг равенство Колмогорова - Чэпмена (5.26) можно записать в виде(5.33)n+m{Jli) =Это равенство может быть представлено в виде суммы покомпонентных произведений векторов-строк на векторы-столбцы. Записав переходные вероятности в виде матрицы, получим уравнение (5.33) вматричной форметг 1 + т (1/1)т+т{2/1)• • • TTl+m(N/l)7г(+т(1/2)тг,+т(2/2)•••n+m(2/N)•••\jrJ+ra(l/JV)7T,(2/1) • • • m(N/l) \JT,(2/2) • • • TrHiV/2)ym(l/N)m(2/N)\m+m(N/2)(5.34)7rl+m(N/N)JI 7T m (l/l) 7Tm(2/l)7r m (l/2) 7r m (2/2)• • • *i{N/N)J\nm(l/N)7rm(2/N)• • • itm(N/N)JЭТОТ процесс может быть начат с первого шага с помощью матрицы переходных вероятностей7T(2/1)п=тг(1/2)TT(2/2)тг(ЛГ/2)7r(l/iV)тг(2/ЛГ)••• 7r(iV/iV)(5.35)Заметим, что матрица П - стохастическая матрица с суммой вероятностей строк равной 1.Многократно применяя такое матричное преобразование к исходному распределению состояний ро, мы можем получить распределение вероятностей рп в любой момент времени прп = р0П".(5.36)5.3.
Конечные цепи МарковаТеорема 5.3.1. Гомогенная цепь Маркова полностью характеризуется матрицей переходных вероятностей и исходным распределением состояний. Приведенные выше рассуждения можно наглядно обобщить припомощи графа состояний (рис. 5.3). Здесь узлы соответствуют состояниям, а пути между ними переходам между состояниями. Каждому пути приписан вес, равный переходной вероятности. Таким образом, граф состояний дает полную информацию о матрице переходных вероятностей.ПереходнаявероятностьР и с . 5.3.
Граф состояний гомогенной цепи Маркова.Пример: Случайные блуждания студента (продолжение).Случайные блуждания (см. рис. 5.2) представлены на рис. 5.4 ввиде графа состояний.Рис. 5.4. Граф состояний для случайных блужданий студента.1—1Графу состояний соответствует матрица переходных вероятностей01001/21/2 00(5.37)П =1/2 0 1/20000Из рис. 5.2 следует, что исходное распределение состоянийРо = (О, 0, 0, 1).(5.38)Глава 5. Стационарные дискретные источники с памятьюВероятность того, что в результате случайных блужданий студентна 7-ом временном шаге окажется у дверей общежития, определяется нервой компонентой вектора состояний на 7 шаге Pj.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
