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

Каквидно из рис. 5.1, значение двух соседних чисел близки друг к другу, т.к. телефонный сигнал передается в узкой полосе частот. Изза временной связи соседних отсчетов, то есть памяти отсчета, егонеопределенность (информация) снижается по сравнению с аналоговым источником без памяти, поэтому основной задачей методовсжатия, особенно при передаче видеосигналов, является снижениеизбыточности.III!!i iiiJfi%j •ITi:;;;I i!лi:\yr({ i[\\\cloРис. 5.1. Непрерывный сигнал.Возникает вопрос о том, каким образом определить энтропиюдискретного источника с памятью. Начнем с постановки задачи.Определение 5.1.1. Дискретный источник X можно представитькак дискретный во времени стохастический процесс, реализацией5.1.

Энтропиякоторого является последовательность событий хп, принадлежащихалфавиту источника X = {оц, «2,..., адг}Замечание. Во избежание путаницы, мы обозначили содержимоеалфавита греческими буквами. В этом случае на месте переменнойхп п-го события может быть поставленно любое число из алфавита X.Определение 5.1.2. Дискретный источник является стационарным, если совместные вероятности последовательностей событий независят от выбора начальной точки отсчета времени.Замечание. Независимость наблюдений от точки отсчета означает, что мы можем начинать выборку с любого момента-времени, то есть статистика не зависит от времени начала наблюде}шй.Определение 5.1.3.

Стационарный дискретный источник математически полностью описан, если известны все совместные вероя т н о с т и р(хП1,хП2,...,хпм)д л я л ю б о й в ы б о р к и пх,П2,...,пм,гдеМ —> оо.Определение энтропии стационарного дискретного источника спамятью следует из двух подходов, приводящих к одинаковому результату. При первом подходе мы используем понятие совместной энтропии, при втором - условной энтропии.

В обоих случаях мы ищемответ на следующий вопрос: «Если память источника распространяется на несколько последовательных событий, то какую дополнительную информацию несет отдельное событие в том случае, еслиблок предшествующих событий уже известен?»Подход 1. Совместная энтропия.Совместная энтропия двух источников Х\ и xi с одинаковымиалфавитами и одинаковыми распределениями вероятностей событийопределяется какм мH(X1,X2) = -^2^2p(Xi,Xj)log2P(Xi,Xj).(5.1)Распространим это определение на L последовательных источниковXi и найдем энтропию источника Xi какi^,(5.2)Глава 5. Стационарные дискретные источники с памятью/jгде вектор X = (х\,х2, • • • ,£/,) и суммирование производится по вс^мвозможным компонентам вектора X.

Устремляя L к бесконечнос+и,мы полностью охватим память источника и получим предельное значение Hi(X) (если оно существует), равноеiЯоо(Х) = lim H(XL).(5.3)L—юоПодход 2. Условная энтропия.Условная энтропия L-того события в случае, если L — 1 предшествующих событий уже известны, определяется какlim H(XL/X1,X2,...,XL_1).(5.4)L—tooХотя в левых частях равенств (5.3) и (5.4) мы уже использовали одинаковое обозначение энтропии отдельного события, этот факт предстоит доказать. Проведем это доказательство за 4 шага.НО0{Х)=Теорема 5.1.1. Для стационарного дискретного источника с Hi{x) <ос имеет место:1.

H(Xi\Xi, X2, • • •, XL^I) не возрастает с ростом длины блока L;2.HL(X)>H(XL\Xi,X2,...,XL-1);3. HL(X) не возрастает с ростом длины блока L;4. Энтропия стационарного дискретного источника HL(X)lim HL(X) = lim ff(Xt|Xi,X2,...,XL_i) = Я о о Р 0 .L—tooL—tooДоказательство.1. Из определения энтропии, как меры неопределенности источника, непосредственно следует, что возрастание числа ограниченийне может повлечь за собой рост неопределенности, а следовательнои энтропии.2.

Из «правила цепочки» для совместной энтронии следуетj[H(X1)Li+ H(X2\X1)+ --- +.(5.5)+H(XL\X1,X2,...,XL^)].Замечание. «Правило цепочки» для совместной энтропии следуетиз «правила цепочки» для вероятностей. Простейший пример «правила цепочки» для вероятностей р(х, у) = р(х/у)р(у) и р(х, у, 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.