信息論基礎(chǔ)離散信道及其信道容量

1、信息論基礎(chǔ)離散信道及其信道容量1第1頁，共101頁，2022年，5月20日，1點20分，星期一3離散信道及其信道容量3.1 信道的數(shù)字模型及分類3.2 平均互信息及平均條件互信息3.3 平均互信息的特性3.4 信道容量及其一般計算方法3.5信道容量的迭代算法3.6離散無記憶擴展信道及其信道容量3.7獨立并聯(lián)信道及其信道容量2第2頁，共101頁，2022年，5月20日，1點20分，星期一3離散信道及其信道容量3.8 串聯(lián)信道的互信息和數(shù)據(jù)處理定理3.9信源與信道的匹配3第3頁，共101頁，2022年，5月20日，1點20分，星期一3.1 信道的數(shù)字模型及分類在信息論中，信道中指信息傳輸?shù)耐ǖ?。?/p>

2、是信息論中與信源并列的另一個主要研究對象。典型例子：實際通信中物理通道：電纜、光纖、電波傳布空間、載波線路等；在時間上將信息進行傳輸?shù)男诺溃捍艓А⒐獗P等；為了某種目的而使信息不得不經(jīng)過的通道：分類器、緩沖器等。4第4頁，共101頁，2022年，5月20日，1點20分，星期一信道分類根據(jù)信道的用戶多少：兩端(單用戶)信道 多端(多用戶)信道根據(jù)信道輸入端和輸出端的關(guān)聯(lián)：無反饋信道 反饋信道根據(jù)信道的參數(shù)與時間的關(guān)系：固定參數(shù)信道 時變參數(shù)信道根據(jù)輸入和輸出信號的特點：(表2.2)5第5頁，共101頁，2022年，5月20日，1點20分，星期一表2.2幅度時間信道名稱離散離散離散信道( Discr

3、ete channel )/ 數(shù)字信道(Digital channel)連續(xù)連續(xù)波形信道( Waveform channel )/ 模擬信道( Analog channel )連續(xù)離散連續(xù)信道( Continuous channel )離散連續(xù)（理論和實用價值均很?。?第6頁，共101頁，2022年，5月20日，1點20分，星期一信道按其輸入輸出之間關(guān)系的記憶性來劃分：有記憶信道無記憶信道信道按其輸入輸出信號之間的關(guān)系是否是確定關(guān)系來劃分：有噪聲信道無噪聲信道7第7頁，共101頁，2022年，5月20日，1點20分，星期一本章我們只討論無反饋、固定參數(shù)的單用戶無擾和有擾離散信道。8第8頁，共1

4、01頁，2022年，5月20日，1點20分，星期一信道模型信息論不研究信道傳輸特性的獲得問題，而假定傳輸特性是已經(jīng)知道的，并在此基礎(chǔ)上研究信道的傳輸問題。輸入輸出統(tǒng)計關(guān)系輸入量X(隨機過程)輸出量Y(隨機過程)信道9第9頁，共101頁，2022年，5月20日，1點20分，星期一離散信道的數(shù)學(xué)模型輸入輸出統(tǒng)計關(guān)系輸入量X(隨機矢量)輸出量Y(隨機矢量)信道10第10頁，共101頁，2022年，5月20日，1點20分，星期一根據(jù)信道的統(tǒng)計特性即條件概率的不同，離散信道又可分成如下幾種情況11第11頁，共101頁，2022年，5月20日，1點20分，星期一無干擾(無噪)信道：有噪信道： 不是0，1分

5、布，稱為有噪信道12第12頁，共101頁，2022年，5月20日，1點20分，星期一 這種信道存在干擾，為實際中常見的信道類型，其輸出符號與輸入符號之間沒有確定的對應(yīng)關(guān)系，但信道任一時刻的輸出符號僅統(tǒng)計依賴于對應(yīng)時刻的輸入符號，而與非對應(yīng)時刻的輸入符號及其它任何時刻的輸出符號無關(guān)，是無記憶信道。離散有干擾無記憶信道：簡稱DMC13第13頁，共101頁，2022年，5月20日，1點20分，星期一 單符號離散信道的數(shù)學(xué)模型用圖描述:可以用概率空間 描述，其中 稱為信道的(前向)轉(zhuǎn)移概率.14第14頁，共101頁，2022年，5月20日，1點20分，星期一信道的轉(zhuǎn)移概率：信道的(前向)轉(zhuǎn)移概率矩陣：

6、15第15頁，共101頁，2022年，5月20日，1點20分，星期一記 則信道傳遞矩陣為該矩陣又稱信道矩陣，可作為單符號離散信道的另一種數(shù)學(xué)模型的形式。16第16頁，共101頁，2022年，5月20日，1點20分，星期一幾個重要的單符號離散信道對稱離散信道：信道矩陣中的行元素集合相同，列元素集合也相同的信道，稱為對稱信道。 17第17頁，共101頁，2022年，5月20日，1點20分，星期一例：二元對稱信道Binary Symmetric Channel (BSC)001118第18頁，共101頁，2022年，5月20日，1點20分，星期一幾個重要的單符號離散信道準(zhǔn)對稱信道：若信道轉(zhuǎn)移矩陣按列

7、可以劃分成幾個互不相交的子集合，而每個子矩陣（由子集所對應(yīng)的信道轉(zhuǎn)移矩陣中的列所組成）具有下述性質(zhì)：（1） 每一行都是第一行的一種排列（2） 每一列都是第一列的一種排列例：19第19頁，共101頁，2022年，5月20日，1點20分，星期一幾個重要的單符號離散信道強對稱信道（均勻信道）r=s=n20第20頁，共101頁，2022年，5月20日，1點20分，星期一幾個重要的單符號離散信道二進制刪除信道（Binary Erasure Channel,簡稱BEC）“刪除”是指在信宿中，見“e”就刪去，既不作“1”，也不作“0” 21第21頁，共101頁，2022年，5月20日，1點20分，星期一例：

8、二元刪除信道Binary Erasure Channel (BEC)0011e22第22頁，共101頁，2022年，5月20日，1點20分，星期一單符號離散信道的一些概率關(guān)系對于信道 X, P, Y ，輸入和輸出符號的聯(lián)合概率根據(jù)聯(lián)合概率可得輸出符號的概率 其矩陣形式：根據(jù)貝葉斯定律可得后驗概率先驗概率后驗概率23第23頁，共101頁，2022年，5月20日，1點20分，星期一3.2平均互信息在闡明了離散單符號信道的數(shù)學(xué)模型，即給出了信道輸入與輸出的統(tǒng)計依賴關(guān)系后，我們將深入研究在此信道中信息傳輸?shù)膯栴}24第24頁，共101頁，2022年，5月20日，1點20分，星期一信道疑義度（損失熵） 信

9、道輸入信源 X 的熵（先驗熵）： 是在接收輸出 Y 以前，關(guān)于輸入變量 X 先驗不確定性的度量，所以稱為先驗熵。25第25頁，共101頁，2022年，5月20日，1點20分，星期一接收到輸出符號bj后關(guān)于X的后驗熵：當(dāng)沒有收到輸出Y 時，已知輸入變量X 的概率分布為P(x)；而當(dāng)接收到輸出符號y=bj 后，輸入符號的概率分布發(fā)生了變化，變成后驗概率P(x|bj )。那么，接收到輸出符號y=bj 后，關(guān)于X的平均不確定性為26第26頁，共101頁，2022年，5月20日，1點20分，星期一后驗熵在輸出Y 的取值范圍內(nèi)是個隨機量，將后驗熵對隨機變量Y 求期望，得條件熵為（即信道疑義度）27第27頁

10、，共101頁，2022年，5月20日，1點20分，星期一信道疑義度的物理含義：信道疑義度表示在輸出端收到輸出變量Y全部符號后，對于輸入端的變量X尚存在的平均不確定性（存在疑義）。這個對X尚存在的不確定性是由于干擾（噪聲）引起的，它表示信源符號通過有噪信道傳輸后所引起的信息量的損失，故也稱為損失熵。28第28頁，共101頁，2022年，5月20日，1點20分，星期一噪聲熵 定義條件熵H（Y/X）為該信道的噪聲熵。29第29頁，共101頁，2022年，5月20日，1點20分，星期一噪聲熵H（Y/X）表示在已知輸入變量X的條件下，對隨機變量Y尚存在的不確定性。噪聲熵完全是由于信道中噪聲引起的，也稱為

11、散布度，它反映了信道中噪聲源的不確定性。30第30頁，共101頁，2022年，5月20日，1點20分，星期一平均互信息互信息：信道輸出端接收到某消息y（或某消息序列y）后獲得關(guān)于輸入端某消息x（或某消息序列x）的信息量 31第31頁，共101頁，2022年，5月20日，1點20分，星期一平均互信息：互信息在其概率空間中的數(shù)學(xué)期望32第32頁，共101頁，2022年，5月20日，1點20分，星期一平均互信息與各類熵的關(guān)系及含義： I (X; Y )=H( X ) - H(X |Y ) = H( Y ) - H(Y |X ) = H( X ) + H( Y ) - H(XY )平均互信息的物理含義

12、：33第33頁，共101頁，2022年，5月20日，1點20分，星期一平均互信息的特性（1）對稱性：（2）非負(fù)性：（3）極值性：34第34頁，共101頁，2022年，5月20日，1點20分，星期一（4）凸函數(shù)性平均互信息量 I (X; Y ) 是輸入信源概率分布 P(x) 的上凸函數(shù)（研究信道容量的理論基礎(chǔ)）。 平均互信息量 I (X; Y ) 是信道轉(zhuǎn)移概率 P(y|x)的下凸函數(shù)（研究信源的信息率失真函數(shù)的理論基礎(chǔ)）。35第35頁，共101頁，2022年，5月20日，1點20分，星期一例：BSC的輸入概率空間36第36頁，共101頁，2022年，5月20日，1點20分，星期一3.3 平均條

13、件互信息設(shè)三個離散概率空間X、Y、Z； 滿足37第37頁，共101頁，2022年，5月20日，1點20分，星期一38第38頁，共101頁，2022年，5月20日，1點20分，星期一定義：對于三個離散隨機變量X、Y、Z，在已知Z的條件下，X和Y之間的平均條件互信息為：39第39頁，共101頁，2022年，5月20日，1點20分，星期一書例3.3：四個等概分布消息M1、M2、M3、M4被送入一個二元無記憶對稱信道進行傳送。通過編碼使M1=00，M2=01，M3=10，M4=11。而BSC信道如圖所示。試問，輸入是M1和輸出是符號0的互信息是多少？如果知道第二個符號也是0，這時帶來多少附加信息量？4

14、0第40頁，共101頁，2022年，5月20日，1點20分，星期一3.4信道容量及其一般計算方法信息傳輸率(比特/符號)：信息傳輸速率(比特/秒)：41第41頁，共101頁，2022年，5月20日，1點20分，星期一信道容量：最大信息傳輸率42第42頁，共101頁，2022年，5月20日，1點20分，星期一一、無噪無損信道的信道容量無噪無損信道：輸入輸出一一對應(yīng)，信道矩陣為單位陣疑義度H（X/Y）=0，噪聲熵H（Y/X）=043第43頁，共101頁，2022年，5月20日，1點20分，星期一a1a2anb1b2bn信道容量：I（X；Y）= H（X）= H（Y） ，則 C = max H（X）=

15、 max H（Y）44第44頁，共101頁，2022年，5月20日，1點20分，星期一二、無噪有損信道（確定信道）： H（X/Y）0，H（Y/X）=0信道輸出端接收到某個bj后不能判定是哪個輸入符號ai a1a2a3a4a5b1b245第45頁，共101頁，2022年，5月20日，1點20分，星期一信道容量： I（X；Y）= H（Y） ，則 C = max H（Y）,這時的輸入分布應(yīng)該是使得信道輸出分布為等概分布。46第46頁，共101頁，2022年，5月20日，1點20分，星期一三、有噪無損信道： H（X/Y）= 0，H（Y/X）0a1a2b1b2b3b4b50.30.60.10.50.54

16、7第47頁，共101頁，2022年，5月20日，1點20分，星期一信道容量： I（X；Y）= H（X），則 C = max H（X）。 這時的輸入分布為等概分布。48第48頁，共101頁，2022年，5月20日，1點20分，星期一一般離散信道是既有噪又有損的。這種情況下信道容量的計算將十分復(fù)雜。我們先討論一種特殊的有損有噪信道對稱離散信道的信道容量。然后討論一般離散信道的信道容量。結(jié)論：凡損失熵等于零的信道稱為無損信道；凡噪聲熵等于零的信道稱為無噪信道。49第49頁，共101頁，2022年，5月20日，1點20分，星期一1、定義：如果轉(zhuǎn)移概率矩陣P的每一行包含同樣元素，則為輸入對稱矩陣；如果轉(zhuǎn)

17、移概率矩陣P的每一列包含同樣元素，則為輸出對稱矩陣；如果輸入輸出都對稱，則為對稱DMC信道。3.4.2 對稱DMC信道例如：50第50頁，共101頁，2022年，5月20日，1點20分，星期一2、信道容量前提：輸入符號和輸出符號均等概。51第51頁，共101頁，2022年，5月20日，1點20分，星期一例題3.5：已知信道轉(zhuǎn)移矩陣為計算信道容量。解：52第52頁，共101頁，2022年，5月20日，1點20分，星期一例題：已知信道轉(zhuǎn)移矩陣為該信道輸入符號和輸出符號的個數(shù)相同，都為n，且正確的傳輸概率為1-，錯誤概率被均勻分給n-1個輸出符號，此類信道稱為強對稱信道或均勻信道，計算信道容量。解：

18、53第53頁，共101頁，2022年，5月20日，1點20分，星期一3.4.3、準(zhǔn)對稱DMC信道例如：1、定義：如果轉(zhuǎn)移概率矩陣P是輸入對稱而輸出不對稱，即轉(zhuǎn)移概率矩陣的每一行包含同樣元素，而各列的元素可以不同，則為準(zhǔn)對稱矩陣。54第54頁，共101頁，2022年，5月20日，1點20分，星期一準(zhǔn)對稱信道另一種定義：若信道轉(zhuǎn)移矩陣按列可以劃分成幾個互不相交的子集合，而每個子矩陣（由子集所對應(yīng)的信道轉(zhuǎn)移矩陣中的列所組成）具有下述性質(zhì)：（1） 每一行都是第一行的一種排列（2） 每一列都是第一列的一種排列55第55頁，共101頁，2022年，5月20日，1點20分，星期一方法二：將轉(zhuǎn)移概率矩陣劃分為

19、若干個互不相交的對稱的子集。方法一：根據(jù)信道容量的定義式來計算。2、準(zhǔn)對稱DMC信道信道容量的求解方法：可以證明：計算準(zhǔn)對稱DMC信道的信道容量即為輸入等概時的平均互信息量。56第56頁，共101頁，2022年，5月20日，1點20分，星期一根據(jù)下面的公式來計算。57第57頁，共101頁，2022年，5月20日，1點20分，星期一例題：已知信道轉(zhuǎn)移矩陣為，計算信道容量。方法一： 該信道為準(zhǔn)對稱DMC信道，計算信道容量即為輸入等概時的平均互信息量。P(x,y) y1 y2 y3x1x20.25 0.15 0.10.15 0.25 0.1 輸入等概時，由信道轉(zhuǎn)移矩陣可得聯(lián)合概率：由信道轉(zhuǎn)移矩陣可得

20、條件熵容易得到輸出符號的概率分別為 0.4，0.4，0.2。所以 58第58頁，共101頁，2022年，5月20日，1點20分，星期一所以，59第59頁，共101頁，2022年，5月20日，1點20分，星期一例題：已知信道轉(zhuǎn)移矩陣為，計算信道容量。方法二：將上面的信道矩陣分解為兩個子集：根據(jù)下面的公式60第60頁，共101頁，2022年，5月20日，1點20分，星期一所以，信道容量為61第61頁，共101頁，2022年，5月20日，1點20分，星期一例3.7：設(shè)某信道的轉(zhuǎn)移矩陣為：求其信到容量。解：分析該轉(zhuǎn)移矩陣，可知這是一個準(zhǔn)對稱信道。 62第62頁，共101頁，2022年，5月20日，1點

21、20分，星期一一般離散信道的信道容量分析根據(jù)信道容量定義就是在固定信道的條件下，對所有可能的輸入概率分布P（x）求平均信息的極大值。63第63頁，共101頁，2022年，5月20日，1點20分，星期一定理：一般離散信道的平均互信息 達到極大值（即等于信道容量）的充要條件是輸入概率分布 滿足： 這時C就是所求的信道容量。信道容量的定理64第64頁，共101頁，2022年，5月20日，1點20分，星期一對于一般離散信道，我們很難利用上面定理來求信道容量和對應(yīng)的輸入概率分布。介紹一種求方程組的方法： 65第65頁，共101頁，2022年，5月20日，1點20分，星期一前提：設(shè)r=s，信道傳遞矩陣P是

22、非奇異矩陣，則信道容量的求解方法如下：由方程組：求出由求出C由求出由求出最佳輸入概率分布 信道容量的方程組解法：66第66頁，共101頁，2022年，5月20日，1點20分，星期一例：設(shè)某離散無記憶信道的輸入X的符號集為0,1,2,輸出Y的符號集為0,1,2，如圖所示， 其信道轉(zhuǎn)移矩陣為求其信道容量及其最佳的輸入概率分布。并求當(dāng) 時的信道容量C。 67第67頁，共101頁，2022年，5月20日，1點20分，星期一3.6離散無記憶擴展信道及其信道容量前幾節(jié)討論了最簡單的離散信道，即信道的輸入和輸出都只是單個隨機變量的信道。然而一般離散信道的輸入和輸出卻是一系列時間(或空間)離散的隨機變量，即為

23、隨機序列。本節(jié)討論多符號離散信道的數(shù)學(xué)模型。68第68頁，共101頁，2022年，5月20日，1點20分，星期一多符號離散信道的定義：若多符號離散信源在N個不同的時刻分別通過單符號離散信道 ，則在輸出端輸出隨機矢量 。于是形成一個新的信道，稱為多符號離散信道。同時，我們也可以把這種信道稱之為單符號離散信道的N次擴展信道。多符號離散信道（單符號離散信道的N次擴展信道）的數(shù)學(xué)模型仍用概率空間來描述。其數(shù)學(xué)模型如圖所示。69第69頁，共101頁，2022年，5月20日，1點20分，星期一多符號離散信道的數(shù)學(xué)模型 70第70頁，共101頁，2022年，5月20日，1點20分，星期一71第71頁，共10

24、1頁，2022年，5月20日，1點20分，星期一與單符號離散信道相比，N次擴展信道的輸入符號數(shù)由r種擴展為 種；輸出符號數(shù)由s種擴展為 72第72頁，共101頁，2022年，5月20日，1點20分，星期一構(gòu)成N次擴展信道的傳遞矩陣它表示在輸入消息 的條件下，輸出消息 的傳遞概率73第73頁，共101頁，2022年，5月20日，1點20分，星期一且滿足74第74頁，共101頁，2022年，5月20日，1點20分，星期一若N次擴展信道的傳遞概率等于N個時刻單符號離散信道的傳遞概率的連乘即 則單符號離散信道稱為離散無記憶信道，相應(yīng)的N次擴展信道稱為離散無記憶信道的N次擴展信道。75第75頁，共101

25、頁，2022年，5月20日，1點20分，星期一離散無記憶N次擴展信道的信道容量76第76頁，共101頁，2022年，5月20日，1點20分，星期一例題注意單位！容易看出，上述信道均為對稱信道，容易計算求得。二次擴展信道：單符號信道：假設(shè)，可以求得：已知單符號信道的轉(zhuǎn)移矩陣為則該BSC信道的二次擴展無記憶信道的轉(zhuǎn)移矩陣為計算它們的信道容量，并比較結(jié)果。解：77第77頁，共101頁，2022年，5月20日，1點20分，星期一結(jié)論：二次擴展無記憶信道的信道容量正好是單符號信道的信道容量的2倍。78第78頁，共101頁，2022年，5月20日，1點20分，星期一離散無記憶擴展信道的信道容量 對于多符號

26、離散信道來說，就會產(chǎn)生這樣一個問題：從總體上看，離散無記憶信道的N次擴展信道把輸入隨機矢量傳輸為輸出隨機矢量的傳輸過程種，傳遞的平均互信息量 ， 與其中各隨機變量的平均互信息之和 之間有什么關(guān)系？這是本節(jié)要討論的問題。79第79頁，共101頁，2022年，5月20日，1點20分，星期一在一般離散信道中，關(guān)于傳輸長為N的隨機序列所獲得的平均信息量，有下述兩個定理。80第80頁，共101頁，2022年，5月20日，1點20分，星期一定理3.5 若信道的輸入隨機序列為X，通過信道傳輸，接收到的隨機序列為Y。假若信道是無記憶的，即信道轉(zhuǎn)移概率滿足或?qū)懗?則存在 式中 和 是隨機序列X和Y中對應(yīng)的第i位

27、隨機變量。 81第81頁，共101頁，2022年，5月20日，1點20分，星期一 證明： 另一方面 82第82頁，共101頁，2022年，5月20日，1點20分，星期一所以所以所以所以則83第83頁，共101頁，2022年，5月20日，1點20分，星期一根據(jù)詹森不等式，得 證得84第84頁，共101頁，2022年，5月20日，1點20分，星期一定理3.6 若信道的輸入隨機序列為X，通過信道傳輸，接收到的隨機序列為Y，而信道的傳遞概率為 ，假若信源是無記憶的，則存在上述兩個定理說明了離散信道中隨機矢量的平均互信息與其中各隨機變量的平均互信息之和之間的關(guān)系。85第85頁，共101頁，2022年，5

28、月20日，1點20分，星期一從定理3.5和定理3.6的證明可知，若信源與信道都是無記憶的，則式（3.141）和（3.142）同時滿足，即它們的等式成立：對于離散無記憶信道的N次擴展信道來說，若信源也是無記憶的話，則有此式說明當(dāng)信源是無記憶時，無記憶的N次擴展信道的平均互信息等于原來信道的平均互信息的N倍。 86第86頁，共101頁，2022年，5月20日，1點20分，星期一離散無記憶的N次擴展信道的信道容量等于原單符號離散信道的信道容量的N倍 。且只有當(dāng)輸入信源是無記憶的及每一輸入變量的分布各自達到最佳分布時，才能達到這個信道容量NC。一般情況下，信息序列在離散無記憶的N次擴展信道中傳輸?shù)男畔?/p>

29、量為87第87頁，共101頁，2022年，5月20日，1點20分，星期一3.7 獨立并聯(lián)信道及其信道容量 N個獨立并聯(lián)信道88第88頁，共101頁，2022年，5月20日，1點20分，星期一這N個信道的聯(lián)合概率傳遞概率滿足故定理3.5推廣得：即聯(lián)合平均互信息不大于各自信道的平均互信息之和。因此得獨立并聯(lián)信道的信道容量89第89頁，共101頁，2022年，5月20日，1點20分，星期一結(jié)論：獨立并聯(lián)信道的信道容量不大于各個信道的信道容量之和。只有當(dāng)輸入符號相互獨立，且輸入符號的概率分布達到各信道容量的最佳輸入分布時，獨立并聯(lián)信道的信道容量才等于各信道容量之和，即90第90頁，共101頁，2022年，5月20日，1點20分，星期一3.8串聯(lián)信道及其信道容量若信道II的