Научная литература
booksshare.net -> Добавить материал -> Математика -> Скороход A.B. -> "Вероятность: основные понятия, структура, методы." -> 100

Вероятность: основные понятия, структура, методы. - Скороход A.B.

Скороход A.B. Вероятность: основные понятия, структура, методы. — , 1989. — 279 c.
Скачать (прямая ссылка): skorohod.djvu
Предыдущая << 1 .. 94 95 96 97 98 99 < 100 > 101 102 103 104 105 106 .. 110 >> Следующая

такие кодирование и декодирование, для которых тЛ-^еЛ^,

Доказательство этой теоремы мы рассмотрим отдельно для
детерминированных каналов связи и для каналов связи с
шумом.

а) Детерминированный канал связи. В этом
случае р{х,у) равно либо нулю, либо 1. Пусть УхаУ— мно-
жество тех Уь которые могут появляться на выходе канала:
для у£У\ найдется такое хаХ, что р(х,у) = \. Выберем для каж-
дого г/б У] одно такое х, и пусть ХхсХ— множество выбран-
ных х. Канал связи переводит Хх в У\ взаимно однозначно.
Легко подсчитать, что пропускная способность канала равна
\og2fni, где гп\ — число элементов У] (оно равно числу элемен-
тов Х\). Это будет количество информации (за единицу вре-
/мени), которая содержится в последовательности {т)„} о после-
довательности {\п}, если £п принимает значения из Х\ с веро-
ятностями 1 ///11. По предположению #<к^2Ш1. На основании
теоремы 1 для всякого е>0 можно указать такое пЕ1 , что
для всех п>пч найдется 2пв цепочек вида гь гг, ...,гц таких,
что сумма вероятностей Р{%1=ги £2 = 22, • • •, Х,п = 2п} по всем

И

= -2p{Si=2}bg2p {Si=2}.

2gz

Р{Цк = у/1к = х}=р(х,у), xtX, г/ЄУ.

этим цепочкам не менее 1—еь а 5б(Я, к^2АП1— б), где Я+б<
<\о%2тх. Для передачи цепочек сообщений (ги г2,...,гп) из
указанной совокупности (это подмножество 1п обозна-
чим Zn) будем использовать последовательности хих2,...,хп,
где х£Х\. Таких последовательностей будет т1 = 2пХо%'т> > 2"*.
Поэтому множество цепочек Zn можно взаимно однозначно ото-
бразить в множество X". Х\ каналом связи взаимно однозначно
переводится в У", а У" —взаимно однозначно в Zn. Если (гь...
...,гп)^„, отобразим ее в некоторую одну последовательность
из X", не входящую в образ Zn, а отвечающую ей последова-
тельность (Уг,...,уп) декодируем произвольным образом. Вероят-
ность того, что сообщение длины п будет передано без ошибки
больше, чем 1—8]. Если имеется сообщение длины Ы~>п, то
разобьем его на части длины п и каждый отрезок длины п пере-
дадим указанным выше способом. Так как передача ведется от-
резками длины п, то запаздывание Тд,<:/г. Вероятность ошибки

меньше, чем 1ги где / — целая часть от Выбирая теперь 81 и

/ так, чтобы /8!<е, 77<у<8> получим требуемое утверждение,

п

уУе — любое, удовлетворяющее неравенству уУе>—'-.

б) Канал с шумом. Как было видно из доказательст-
ва в предыдущем пункте, достаточно установить, что для вся-
кого е>0 можно указать такое пе, что при я>пе можно пере-
дать одно из 2n(н+'e, сообщений, выработанных источником ин-
формации за время п с вероятностью ошибки, меньшей чем 8,
5>0— некоторое произвольно выбранное положительное чис-
ло. Пусть распределение величины £ в X выбрано так, чтобы
для пары |, т], для которой

Р{1 = х, ц = х}=Р& = х}р(х,у),

С>Щ,г\)>Н. Пусть НЦ) —энтропия распределения |.
Возьмем в Хп подмножество Хп тех (хи х2,... ,хп)^Х, для ко-
торых при некотором а>1

к=\

а, х£Х. (29)

Легко проверить, что число точек в Хп будет 2"<Я(6)+8п), где
е„-*-0. Пусть теперь {цк(х), х£,Х) независимы при различных
Р {Чк(х) = у}= р {х, у). Энтропия последовательности (х^, ...
Пп(хп) при (хи х2, хп)£Х будет

2

12 у)1о&р(Х\,У)

х у ^

(мы воспользовались (29)). Для достаточно больших п для каж-
дой точки (хх, ..хп)аХп можно указать множество
5("5,...,.Г;г)СК" такое, что

Р{(Л1 (•*,)> • ... к\п(хпМ8Ц\,...,хп)}> 1-е, (30)

и число точек в .....^ не больше 2'г(Я№)+6). Так как

Н (|) > 7 (|, л) > Я, то в Х„ можно выбрать подмножество Л"„,
число точек которого равно числу сообщений, которые нужно
передать (их не более 2«(Н+6)). Можно считать, что Я+2б<
</(|, т)). Правило декодирования будет таким: если на выходе
канала наблюдается последовательность (уи у2,...,уп), то по-
лагаем

если (г/ь уп)е и _ «^й,...,*„), если же (ух,...,уп)
не попадает в это множество, 6у (Уи - ..,Уп) определяем произ-

п

вольным образом. Оценим вероятность ошибки передачи «у .
Имеем

п

(мы воспользовались (30)), здесь р(х\,...,хп) вероятность
того, что передается сообщение, закодированное последователь-
ностью (х\,... ,хп). Как вытекает из доказательства теоремы 3,
для достаточно больших п будет

р(хи ...,хп)<2-»1»-*1

Точно так же

П/?(^,^<2-"™-б)

Предыдущая << 1 .. 94 95 96 97 98 99 < 100 > 101 102 103 104 105 106 .. 110 >> Следующая

Реклама

c1c0fc952cf0704ad12d6af2ad3bf47e03017fed

Есть, чем поделиться? Отправьте
материал
нам
Авторские права © 2009 BooksShare.
Все права защищены.
Rambler's Top100

c1c0fc952cf0704ad12d6af2ad3bf47e03017fed