Вернер М. Основы кодирования (2004) (1151849), страница 13
Текст из файла (страница 13)
Основополагающее значение величины I(X; Y) будет подробно раскрыто в следующих разделах.98Глава 7. Дискретные каналы без памятиТаблица 7.2. Дискретные источники без памяти X и У с символами х £ X — {ж1,Ж2, • • • ,хм} и у 6 Y ={уьУ2, ••-,!/w}Теория вероятностейТеория информацииВероятность отдельного символа(априорная вероятность)Информация отдельного символа/(x) = -!og 2 p(z)6HTр(х)Совместнаясимволоввероятностьдвухр{х,у)Р{У)р(у/х) = У(х,у)Информация пары символов(7.31)Условная вероятность (апостериорная вероятность)р(х/у) =(7.30)Условная информация(7.33)1(у/х) = - log2 p(y/x) бит(7.32)Взаимная информация/ ( * ; » ) = •апостериорная инф.бит =априорная информ.(7.34)р(х)р(х)Обозначенияр(х) = Рх (х.) для х, 6 Xр(х/у) = Px/r(xi/yj)битНекоторые важные соотношения, используемые для расчетов]Гр(х) = 1;для Xi € X53 Р(УЖ.
У)= р(^); 5ZX74- Выводы99)Таблица 7.3. Описание «в среднем» дискретных источников без памяти с символами х £ X =иу GY ={XI,X2,--.,XM}Энтропия ч{уиУ2,-.-,ук}-Н(Х) = — 2_, р(х) log2p(x) бит(7.35)XH{Y) = — У ' Р{у) 1°ёг Р(У) ^итуСовместная энтропияH(X,Y) = -££p(i,J/)log2p(x,y)Условная энтропия(7.36)УXH{X/Y) = -££p(x,s/)log2p(x/!/)X(7.37)УЯ(У/Х) = -££p(*,2/)l°g2p(!//x)XПередача информации7(ЛГ;У-) =(7.38)v^ v ^ ,ч,апостериорная вер.> > р(х, у) log2——х Yаприорная вер.XРУхНекоторые важнейшиезависимости(знакравенства справедливтолько для независимых источников)У^ '' ) ^ х -'уН{Х) > H(X/Y) и Я(У) > H(Y/X)Н(Х, Y)=Н(Х) + H(Y/X) ==H(Y) + H(X/Y)Н(Х, Y) = Н{Х) + H(Y) - I(X; Y)I(X;Y)>0(7.39)(7.40)(7.41)(7.42)Глава 7. Дискретные каналы без памяти7.5.
Пропускная способность каналаВеличина I(X; Y) играет особую роль в теории информации и описывает передачу информации по каналу связи. Из определения (7.9)следует, что I(X; Y) зависит как от переходных вероятностей канала, так и от распределения вероятностей символов на входе канала.Для дальнейших рассуждений рассмотрим дискретный канал безпамяти с фиксированными переходными вероятностями и зададимся вопросом: Какое максимальное количество информации можнопередать по данному каналу?Пропускная способность канала с заданными переходными вероятностями равна максимуму передаваемой информации но всем входным распределениям символов источника XС = max I{X\Y).(7.43)Замечание.
Размерность пропускной способностибит/символ.Если, например, по каналу передается один символ в сек, то можнотакже говорить о размерности бит/сек.Так как максимум ищется но всем допустимым входным источникам, то пропускная способность зависит только от переходных вероятностей канала.С математической точки зрения, поиск пропускной.способностидискретного канала без памяти сводится к поиску распределения вероятностей входных символов источника, обеспечивающего максимум информации I(X;Y).При этом, на вероятности входных символов х € X накладываются ограниченияО < р{х) < 1 и ^р(х)х= 1.(7.44)В принципе, определение максимума 1(х, у) при ограничениях (7.44)возможно при использовании мультипликативного метода Лагранжа. Однако, такое решение требует чрезмерно больших затрат.
Вчастном случае (симметричные каналы) найти пропускную способность помогает следующая теорема [10].Теорема 7.5.1. В симметричных дискретных каналах без памятипропускная способность достигается при равномерном распределении вероятностей входных символов источника X.Замечание. В [10} приводится также метод, позволяющий определить, является ли канал симметричным или нет.7.5. Пропускная способность канала1017.5.1.
Пропускная способностьДвоичный дискретный симметричный канал без памяти (ДСК)определяется с помощью матрицы переходных вероятностей канала(7.2). Единственным параметром, характеризующим ДСК, является вероятность ошибки е. Из равномерного распределения входныхсимволов и симметрии переходов канала следует равномерное распределение выходных символов, т.ер(Х1) = р(х2) = р(У1) = р(й) = 1/2.(7.45)Используя (7.9), получаемгjПодставляя числовые значения, имеем- £ ^ = (l-e)lo g 2 (2(l- £ ))+elog 2 (24==(7.47)1 + (1 - e)log2(l - g) + 21og2e.Энтропия ДСК определяется через (2.32)Нь{е= -(1 - е) lo g 2 (l - е) - eloga(e).бит(7.48)Окончательно получаем пропускную способность ДСК в компактнойформеС д с к = 1 бит - Я ь (е)(7.49)Интересными являются два граничных случая:1. Передача информации по бесшумному каналу:Щ(е = 0) = 0 и С д с к = 1 бит.2.
Канал полностью зашумлен:Нь(е = 1/2) = 1 бит и СДСК = 0 бит.Глава 7. Дискретные каналы без памяти7.5.2. Пропускная способность двоичногосимметричного канала со стираниямиВажным частным случаем ДСК является двоичный симметричныйканал со стираниями (ДСКС) или двоичный канал со стираниями (Binary Erasure Channel, ВЕС - англ.). Как и ДСК, двоичныйканал со стираниями может служить упрощенной моделью передачи информации по каналу с аддитивным белым гауссовским шумом(АБГШ).
Правило принятия решения в ДСКС приведено на рис.7.11.Из рисунка видно, что наряду с решениями о переданном символе«О» или «1», здесь иногда принимается решение о стирании принятого символа «е»(Erasure-англ.). Стирание происходит в случае, если продетектированный аналоговый сигнал V попадает в зону, длякоторой значения условных функций плотности распределения вероятностей /(V/0) и f(V/l) оказываются близкими к нулю./(v/l)Переданный символР и с . 7.11. Условные функции плотности распределения вероятностей продетектированного сигнала и области принятия решений.Замечание. В двоичном канале со стираниями, вместо однозначно«жесткого» решения о принятом символе «О» или «1» принимается, так называемое, «мягкое» решение.
В этом случае, мы дополнительно имеем некоторую информацию о надежности принятогодвоичного символа. В связи с этим, в технике передачи данных,говорят о приеме с «жестким» и «мягким» решением. «Мягкое»решение в сочетании с подходящим кодированием, информации позволяет в некоторых случаях осуществить более надежную передачу данных. Один из примеров использования «мягкого» решенияможно найти во второй части этой книги.(03 ,7.5. Пропускная способность каналаИсточник Xl-p-qИсточник YJt,="O"Уз="1"Р и с . 7.12.
Двоичный симметричный канал со стираниями.Обозначим вероятность стирания через q, а вероятность ошибкинестертого символа через р.Диаграмма переходов для канала с двумя входными и тремя выходными символами приведена на рис. 7.12. Соответствующая матрица канала, содержащая переходные вероятности, имеет видрдсксY/X/1-Р-?\pяqр\1 -, р - д. J( 7 5 0 )Найдем пропускную снособность канала со стираниями. Так как канал симметричен, пропускная снособность достигается при равномерном распределении входных символов= 1/2.(7.51)Отсюда следует, что вероятности выходных символов равныР Ы = -^~,РЫ= Я,р{Уъ) = ~^г-(7.52)Теперь все необходимые вероятности известны. Воспользовавшись(7.9), имеемО«™битЛ Л ...*нЫ* 32 3» 3Используя свойство симметрии канала, получаем.(7 53)Глава 7.
Дискретные каналы без памятиQJXCKCбиткr/г,\(7.54)1 —р — I1-9Как мы видим, пропускная способность канала со стираниями зависит только от вероятностей р и q. График С = /(р, 9) представляетсобой пространственную трехмерную поверхность, расположеннуюнад плоскостью (p,q). Здесь мы ограничимся только рассмотрениемдвух важных частных случаев.1. При 9 = 0, мы имеем двоичный симметричный канал, уже рассмотренный ранее. Подставляя q = 0 в (7.59) мы, как и ожидалось,получаем (7.49).2.
В канале присутствуют только стирания, т.е. при р = 0 - ошибки или не присутствуют, или мы ими пренебрегаем. В этом случаеС д с к с = (1 - q) бит.(7.55)На рис. 7.13 показаны пропускные способности ДСК (7.49) и двоичного канала со стираниями (р = 0). Нужно отметить, что при малых вероятностях ошибки, выбором оптимальных областей стиранийв ДСКС можно достичь существенно больших пропускных способностей, чем в обычных двоичных каналах.Замечание.
Здесь возникает вопрос о возможности увеличенияпропускной способности при приеме со стираниями на практике. В.этом месте обнаруживается слабость теории информации. Теория информации зачастую не может предложить конструкцию,реализующую теоретически достижимые границы. Тем не менее,небольшой пример, подробно рассмотренный во второй части этойкниги, показывает, что введение стираний может иногда снижатьвероятность ошибки. Рассмотрим этот пример на интуитивномуровне. Разобьем поток передаваемой информации на блоки, содержащие 7 двоичных символов (7 бит).
К каждому блоку добавимодин бит (•«в» или «1*) проверки на четность. Закодированные таким образом блоки из восьми двоичных символов всегда будут содержать четное число единиц. Пусть вероятность ошибки в ДСКдостаточно мала. Введем зону стирания (рис.7.11) таким образом,7.5. Пропускная способность каналачтобы ошибки, в основном, перешли в стирания. При этом, вероятность «нестертой» ошибки будет пренебрежимо мала, а вероятность стирания будет оставаться достаточно малой. Мы получимстирающий канал (ДСКС), в котором блоки из восьми двоичныхсимволов в подавляющем большинстве случаев или будут принятыправильно или будут содержать только один стертый двоичныйсимвол. Качество приема существенно улучшится, так как одностирание в блоке с четным числом единиц всегда может быть исправлено.бит0,60,40,200,10,20,3q,E.• 0,5Р и с .
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
