Теория информации и надежная связь - Галлагер Р.
Скачать (прямая ссылка):
R (d*).
Это среднее будет существовать, если при любом выборе v0 функция d(и; и0) будет измеримой на борелевском поле множеств входных последовательностей, на котором вероятностная мера источника определена. Этот класс содержит любую функцию, представляющую какой-либо интерес для практических целей.
505
Теорема 9.8.1.
inf RL(d*)= lim RL(d*). (9.8.4)
L L->oo
Доказательство. Пусть L и n — произвольные положительные целые числа и для заданного d* пусть PL (vL | uL) и Рп (v„ | и„) — переходные вероятности, на которых достигаются RL (d*) и Rn (d*) соответственно. Рассмотрим тест-канал, по которому передаются L + п символов и используется PL для первых L символов и независимо Рп — для последних п, т. е.
РL + n (VL + n | Ul+«) =
~Pl(vl I Ul) Pn (vl+ i, •••, Vl+п I Ul+ i , ... , n). (9.8.5)
Обозначим через U* ансамбль первых L букв источника иъ ..., иь и через U2 ансамбль последующих п букв uL+1, ..., иь+п. Аналогично, пусть Vx и V2 обозначают ансамбли первых L и последующих п букв адресата соответственно. С помощью тех же рассуждений, как в теореме 4.2.1, имеем
/ (ихи2; ад = я (ад--Я (ViV, [ иги2), я (ад < я (V0 + я (v2).
А также из независимости каналов вытекает [см. (9.8.5)]
Я (ViVa ] UxUa) = Я (V, | Ux) + Я (V21 U2).
Отсюда следует, что
/ (ихи2; ад < 1 (Ui; Vx) + / (U2; V2). (9.8.6)
По определению Pt и Pn и в силу стационарности источника правая часть (9.8.6) равна LRl (d*) +nRn (d*). Также из (9.8.1) вытекает, что общее среднее искажение L + п символов равно общему среднему искажению первых L символов, сложенному с общим средним искажением последних п символов. Следовательно, среднее искажение на символ для L + п символов не более d*, и (L + п) RL+n (d*) является нижней границей левой части (9.8.6). Следовательно,
(I + п) Rl+п (d*) < LRl (d*) + nRn (d*).
Теорема вытекает из леммы 4А.2. |
Теперь легко видеть,что функция R (d*), так же как и RL (d*), не отрицательная не возрастающая с d* и выпуклая
Обращение теоремы кодирования для источника, данное в теореме 9.2.2, применимо без изменения для источников и мер искажения, рассмотренных здесь. Однако сама теорема кодирования требует некоторых дополнительных рассмотрений. Сначала установим вспомогательный результат, который полезен сам по себе.
Теорема 9.8.2. Пусть Rx (d*) — скорость как функция искажения первого порядка для дискретного эргодического источника с аддитивной инвариантной во времени мерой искажения. Для любого d*, тако-506
го, что Ri (d*) < оо, любого 8>0 и любого достаточно большого L существует блоковый код источника длины L с М ^ ехр [LRx (d*) + + L8] кодовыми словами, для которого среднее искажение на букву удовлетворяет неравенству
dL^d* + 8. (9.8.7)
Для доказательства теоремы нам потребуется следующая лемма. Лемма 9.8.1. Пусть выход ..., и_ъ и0, иъ ... дискретного эр-годического источника пропускается через дискретный канал без памяти с выходом ..., v_x, v0, vx.... Тогда совместный процесс ...,
u0vо, UxVx, ... является эргодическим.
Мы опустим формальное доказательство этой леммы, обобщение которой доказано Вольфовицем (1961) (§ 10.3) и Файнстейном (1958). Идея доказательства состоит в следующем. Пусть и \ — любая частная последовательность I букв источника и v'; — какая-либо последовательность I выходов канала. Так как источник эргодический, то относительная частота появления и'г на всех начальных позициях в последовательности источника длины L > I стремится к Qi (и'г), т. е. к вероятности и'и с вероятностью 1 при L -у оо. Так как канал без памяти, то относительная частота у'г по тем начальным позициям, где u'i появляется, стремится к Pi (v'; | u'() с вероятностью 1. Следовательно, относительная частота u'b v'; сходится к Qi (u'i)Pi (v';/и'г), что достаточно для эргодичности.
Доказательство теоремы. Пусть Р (/ [ k) — переходная вероятностная мера, на которой достигается Rx (d*) для заданного d*, и пусть Q (k) обозначает вероятность отдельной буквы источника. Пусть
со (D = IiQ(k)Pij\k).
k
Для любого L рассмотрим ансамбль кодов с М =|_______ехр ILRx (d*)+L6]____]
кодовыми словами, в которых каждая буква каждого кодового слова выбрана независимо с распределением вероятностей со (/). В любом коде из ансамбля каждая последовательность источника и отображается в кодовое слово, которое минимизирует искажение с и. Пусть
L
Pl(vl\Ul)= П P(t>i\ui)>
i = 1
пусть
L
wl(vl) --= п “(иг) i = 1
и определим
Р, (\, I иЛ
