離散無記憶信道的容量

1、離散無記憶信道的容量,第十一講,,信道容量,信道容量,離散無記憶,達(dá)到C充要條件,輸入概率矢量,達(dá)到轉(zhuǎn)移概率為,的DMC的容量C的充要條件為,其中，,定理3 對于準(zhǔn)對稱DMC信道（1）達(dá)到信道容量的最佳輸入分布為等概分布；（2）信道容量為,,,,準(zhǔn)對稱信道的容量,最佳輸入分布為等概分布,準(zhǔn)對稱DMC信道,,,,準(zhǔn)對稱信道容量計(jì)算公式,,對稱DMC信道,,,,例 KSC信道,其中0<p<1。稱p為錯(cuò)誤概率。特別當(dāng)

2、K=2時(shí)，記為BSC,,例 KSC信道容量,對稱信道最佳輸入分布為等概分布當(dāng)輸入等概時(shí)，輸出分布 也為等概信道容量,例 KSC信道容量,例 二元刪除信道容量,當(dāng)q=0時(shí)，簡化為BSC。當(dāng)p=0時(shí)，簡化為純刪除信道。達(dá)到信道容量時(shí)的最佳輸入分布為等概分布。信道容量是轉(zhuǎn)移概率矩陣任何一行所對應(yīng)的半平均互信息量。,它為準(zhǔn)對稱信道，,達(dá)到C的分布為等概分布，即,解：,BSC(q=0) C=1-H(p)純刪除信道(p

3、=0) C=1-q,例 二元刪除信道容量,DMC的輸入為X，X的所有事件為{0, 1, …, K-1}；DMC的噪聲為Z，Z的所有事件為{0, 1, …, K-1}；DMC的輸出為Y，Y的所有事件為{0, 1, …, K-1}；X與Z相互獨(dú)立；Y=X+Z(modK)。,例 模K加性噪聲信道,,求信道容量C,若記P(Z=z)=sz，則轉(zhuǎn)移概率矩陣為,例 模K加性信道容量,顯然，模K加性噪聲信道是對稱DMC，則信道容量為,p(y

4、|x)=P(Y=y|X=x) =P(X+Z(modK)=y|X=x) =P(x+Z(modK)=y|X=x) =P(Z=y-x(modK)|X=x) =P(Z=y-x(modK))。,假定所有輸入字母的概率,，則,,由,,可得,即,,,可逆矩陣信道容量,,令,，得,可以看成是有J個(gè)未知數(shù) 的線性方程組。由假設(shè)P是非奇異矩陣，故必有唯一解。,令,是其解，由上假

5、設(shè),又,，可得,可逆矩陣信道容量,對上面得到的解進(jìn)行驗(yàn)證。,特別注意,可逆矩陣信道容量,計(jì)算wj,計(jì)算Qk,求解方程組,驗(yàn)證,若 即所得到的解是正確的,否則滿足條件的最大值在邊界上，于是,令某個(gè),為0，,再次進(jìn)行試解。,,可逆矩陣信道容量,列方程組,計(jì)算信道容量,驗(yàn)證,對上面得到的解進(jìn)行驗(yàn)證。,特別注意,可逆矩陣信道容量,計(jì)算wj,計(jì)算Qk,求解方程組,驗(yàn)證,若 即所得到的解是正確的,否則滿足

6、條件的最大值在邊界上，于是,令某個(gè),為0，,再次進(jìn)行試解。,多解,有時(shí)要令多個(gè),為0，進(jìn)行試解,特別,,例 題,DMC信道的轉(zhuǎn)移概率矩陣為,,求其信道容量C。,非奇異矩陣,例 題,根據(jù),列方程組,,得,,從而,,例 題,驗(yàn)證,，求得,,再根據(jù),，得到方程組,可得,,經(jīng)驗(yàn)證,，因此結(jié)果正確,最佳分布為,根據(jù),N次擴(kuò)展信道容量,,,有：,【定理】：DMC,,,,,無記憶信道,,,證明,注：等號成立條件,,,,無記憶信道,,,證明,注：等號成

7、立條件,,,,,,,注：當(dāng)輸入字母序列中各字母統(tǒng)計(jì)獨(dú)立時(shí)，等號成立。,,由信道容量的定義知，對于任意n，有,注：若對每個(gè)n，輸入分布 可使 極大，則有 ，從而等式成立。,,,DMC，有問題：對有記憶信道上式是否成立？,例： 模2加性噪聲信道考慮滿足的 二元對稱信道，其中 表示模2加法運(yùn)算，

8、并且假設(shè) 具有分布 但不一定相互獨(dú)立。假設(shè)Zn與輸入Xn相互獨(dú)立，C=1-H(p).則有：,該結(jié)論的證明，用到互信息的當(dāng) （信道無記憶）時(shí)，有當(dāng) （信源無記憶）時(shí)，有當(dāng)信源和信道都是無記憶時(shí)，有,證明：假設(shè)信源無記憶，有

9、因此，有,,,組合信道,若信道1和信道2同時(shí)傳送信息，則組合信道的輸入集由所有的有序?qū)?組成，其中,輸出集由所有的有序?qū)?組成，其中,,轉(zhuǎn)移概率 ，稱這樣組成的信道為信道1和信道2的獨(dú)立并行信道或積信道。信道1和信道2稱作積信道的分信道。,積信道,,定理 獨(dú)立并行信道的容量C為各分信道容量之和,,證明：

10、,,,,,,,,,,由此得,特別注意,時(shí)等號成立。,條件下，相當(dāng)于要求,即要求兩個(gè)分信道的輸入彼此獨(dú)立。這樣對于積信道的最佳利用是將兩個(gè)信道獨(dú)立地使用，并使每個(gè)分信道的輸入分布為最佳，就能保證到達(dá)信道容量。,推論（N個(gè)獨(dú)立信道構(gòu)成的并行信道）設(shè)每個(gè)分信道的輸入空間、輸出空間和轉(zhuǎn)移概率分 布相應(yīng)為Xn，Yn和Pn，則合成的積信道的輸入、輸出空間及轉(zhuǎn)移概率分布和容量分別為,和,【例】DMC的N次擴(kuò)展信道,,積信道,若任一單位時(shí)間可隨

11、機(jī)地選用信道1或信道2中的一個(gè)（兩者不能同時(shí)選用）。選用信道1的概率為p1，選用信道2的概率為p2,且p1+p2=1。組合信道的輸入空間為,稱此組合信道為和信道，或稱作并信道。,,輸出空間為 ，轉(zhuǎn)移概率分布為,,和信道,【例】,,此時(shí)和信道的轉(zhuǎn)移概率矩陣為,,和信道的互信息為,其中,定理 信道1和信道2的和信道的容量C滿足,,證明：,,,,令,,所以,,解之,,,,,,又

12、 ,則,,,或,,回代 入關(guān)系式,,,,則,,,,可得,推論（N個(gè)獨(dú)立信道的和信道）,若各分信道的輸入、輸出空間、轉(zhuǎn)移概率和容量分別為Xn，Yn和Pn和Cn，則和信道的信道容量為,每個(gè)信道被利用的概率為,和信道,【例】求解信道 的容量C,,解,和信道,最佳分布,若將

13、信道1的輸出作為信道2的輸入，信道1的輸入集就是組合信道的輸入集，信道2的輸出集就是組合信道的輸出集。稱這樣組成的信道為級聯(lián)信道，又稱串行信道。,,,,,級聯(lián)信道,轉(zhuǎn)移概率,,,將信道1與信道2級聯(lián)，組成級聯(lián)信道，求其信道容量和最佳輸入分布。,,,,信道1,信道2,BSC信道，C=1-H(0.2)，最佳分布為等概分布。,級聯(lián)信道,級聯(lián)條件下，可能以為合成信道容量為 但事實(shí)

14、上，它并不成立。通過級聯(lián)以后的轉(zhuǎn)移概率趨 于兩個(gè)信道轉(zhuǎn)移概率的平均值 因而傳信能力將減少，這與信息不增原理相一致?？?以證明，若將N個(gè)轉(zhuǎn)移概率相同的BSC信道依次級聯(lián) 當(dāng) ，級聯(lián)信道容量,提 示,,,,,,,編碼器,,,,信道,信源輸出：U,X,Y,組合信道編解碼信道,組合信道編解碼信

15、道,譯碼器,,V,例：組合信道編解碼信道考慮BSC，p=0.1,碼長為3的重復(fù)碼{000,111}。經(jīng)信道編解碼后，輸出0和1.該信道仍為BSC，p’=0.93 +3*0.92*0.1=0.972原信道的信道容量C1=1-H(0.1)=0.531 bit/原符號信道編解碼信道的容量C3=1-H(0.972)=0.81574bit/符號組合信道不會增加信道容量，提高可靠性。,3.反饋信道4.編碼反饋信道,作 業(yè),4.