Вероятность: основные понятия, структура, методы. - Скороход A.B.
Скачать (прямая ссылка):
такие кодирование и декодирование, для которых тЛ-^еЛ^,
Доказательство этой теоремы мы рассмотрим отдельно для
детерминированных каналов связи и для каналов связи с
шумом.
а) Детерминированный канал связи. В этом
случае р{х,у) равно либо нулю, либо 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-"™-б)