信息論與編碼離散信道

信息論與編碼離散信道第一頁，共九十九頁，編輯于2023年，星期五2023/5/241引言信道是通信系統(tǒng)的重要部分,其任務(wù)是以信號(hào)方式傳輸信息和存儲(chǔ)信息.研究信道就是研究信道中能夠傳送或存儲(chǔ)的最大信息量,即信道容量問題.首先討論離散信道的統(tǒng)計(jì)特性和數(shù)學(xué)模型,然后定量地研究信道傳輸?shù)钠骄バ畔⒓捌湫再|(zhì),并導(dǎo)出信道容量及其計(jì)算方法.只研究一個(gè)輸入和一個(gè)輸出端的信道,即單用戶信道;以無記憶、無反饋、固定參數(shù)的離散信道為重點(diǎn).第二頁，共九十九頁，編輯于2023年，星期五2023/5/2423.1信源的數(shù)學(xué)模型及分類實(shí)際的通信系統(tǒng)中,信道的種類很多,包含的設(shè)備也各式各樣.有線:明線、電纜、波導(dǎo)、光纜無線:長波、中波、短波、超短波、光波信息論不研究信號(hào)在這些信道中傳輸?shù)奈锢磉^程;信號(hào)在信道中傳輸或存儲(chǔ)過程所遵循的不同物理規(guī)律.信息論將各種不同的物理信道抽象成統(tǒng)一的數(shù)學(xué)模型,只研究信息的傳輸和存儲(chǔ)問題.第三頁，共九十九頁，編輯于2023年，星期五2023/5/2433.1信源的數(shù)學(xué)模型及分類從信息傳輸?shù)慕嵌葋砜紤],信道可以分成以下幾種分類:1、根據(jù)信道的用戶多少;2、根據(jù)輸入和輸出信號(hào)的特點(diǎn);3、根據(jù)信道的統(tǒng)計(jì)特性(條件概率);∵噪聲和干擾使信號(hào)通過信道傳輸后產(chǎn)生錯(cuò)誤和失真.∴信道輸入和輸出信號(hào)是統(tǒng)計(jì)依賴關(guān)系,而一般不是確定的函數(shù)關(guān)系.第四頁，共九十九頁，編輯于2023年，星期五2023/5/2441、根據(jù)信道的用戶多少,信道可分:兩端(單用戶)信道:它是只有一個(gè)輸入端和一個(gè)輸出端的單向通信的信道.多端(多用戶)信道:它是在輸入端或輸出端中至少有一端有二個(gè)以上的用戶,并且還可以雙向通信的信道。實(shí)際通信系統(tǒng),如計(jì)算機(jī)通信、衛(wèi)星通信、廣播通信、移動(dòng)通信等.第五頁，共九十九頁，編輯于2023年，星期五2023/5/2452、根據(jù)輸入和輸出信號(hào)的特點(diǎn),信道可分為:離散信道:輸入、輸出變量的取值都是離散的.連續(xù)信道:輸入、輸出變量的取值都是連續(xù)的.半離散或半連續(xù)信道:輸入變量是離散的且輸出變量是連續(xù)的,或者相反.第六頁，共九十九頁，編輯于2023年，星期五2023/5/2462、根據(jù)輸入和輸出信號(hào)的特點(diǎn),信道可分為:波形信道:輸入和輸出的隨機(jī)變量取值都是連續(xù)的,且隨時(shí)間連續(xù)變化,可用隨機(jī)過程來描述.實(shí)際信道的是帶寬受限的,所以輸入、輸出信號(hào)可分解成時(shí)間離散的隨機(jī)序列。隨機(jī)序列中隨機(jī)變量的取值可以是可數(shù)的離散值,也可是不可數(shù)的連續(xù)值.因此,波形信道可分解成離散信道、連續(xù)信道和半離散或半連續(xù)信道來研究。第七頁，共九十九頁，編輯于2023年，星期五2023/5/2473、根據(jù)信道輸入端和輸出端的關(guān)聯(lián),可以分為:無反饋信道.信道輸出端無信號(hào)反饋到輸入端,即輸出端信號(hào)對(duì)輸入端信號(hào)無影響、無作用.反饋信道.信道輸出端的信號(hào)反饋到輸入端,對(duì)輸入端的信號(hào)起作用,影響輸入端信號(hào)發(fā)生變化.第八頁，共九十九頁，編輯于2023年，星期五2023/5/2484、根據(jù)信道的參數(shù)(統(tǒng)計(jì)特性)與時(shí)間的關(guān)系,信道又可以分為:固定參數(shù)信道.信道的參數(shù)(統(tǒng)計(jì)特性)不隨時(shí)間變化而改變.時(shí)變參數(shù)信道.信道的參數(shù)(統(tǒng)計(jì)特性)隨時(shí)間變化而改變.第九頁，共九十九頁，編輯于2023年，星期五2023/5/249離散信道離散信道的數(shù)學(xué)模型一般如圖3.1所示.信號(hào)用隨機(jī)矢量表示.輸入信號(hào)X=(X1,…,Xi,…,XN),輸出信號(hào)Y=(Y1,…,Yi,…,YN),其中i=1,…,N表示時(shí)間或空間的離散值.隨機(jī)變量Xi和Yi分別取值于符號(hào)集A=(a1,…,ar)和B=(b1,…,bs),其中r不一定等于s.條件概率p(y|x)描述了輸入和輸出信號(hào)之間的統(tǒng)計(jì)依賴關(guān)系,反映了信道的統(tǒng)計(jì)特性.第十頁，共九十九頁，編輯于2023年，星期五2023/5/24103、根據(jù)信道統(tǒng)計(jì)特性,離散信道可分成三種情況:(1)無干擾（無噪）信道.信道中沒有隨機(jī)干擾或者干擾很小,輸出信號(hào)Y與輸入信號(hào)X有確定的對(duì)應(yīng)關(guān)系.即y=f(x),且第十一頁，共九十九頁，編輯于2023年，星期五2023/5/2411(2)有干擾無記憶信道.實(shí)際信道中常有干擾(噪聲),輸出與輸入之間無確定關(guān)系。信道輸入和輸出之間的條件概率服從一般的概率分布。輸出符號(hào)統(tǒng)計(jì)依賴于對(duì)應(yīng)時(shí)刻的輸入符號(hào),而與非對(duì)應(yīng)時(shí)刻的輸入和輸出符號(hào)無關(guān),則稱無記憶信道.其條件概率滿足

對(duì)任意N值和任意x、y的取值，上式成立。第十二頁，共九十九頁，編輯于2023年，星期五2023/5/2412(3)有干擾有記憶信道。這是更一般的情況,既有干擾(噪聲)又有記憶.實(shí)際信道往往是這種類型.例如碼字干擾就是由于信道濾波使頻率特性不理想造成的.有記憶信道:輸出符號(hào)不但與對(duì)應(yīng)時(shí)刻的輸入符號(hào)有關(guān),還與以前時(shí)刻輸入及輸出符號(hào)有關(guān),其信道條件概率p(y|x)不再滿足式(3.2)。第十三頁，共九十九頁，編輯于2023年，星期五2023/5/2413(3)有干擾有記憶信道。處理這類有記憶信道時(shí)最直觀的方法是把記憶較強(qiáng)的N個(gè)符號(hào)當(dāng)作一個(gè)矢量符號(hào)來處理,而各矢量符號(hào)之間認(rèn)為是無記憶的,轉(zhuǎn)化成無記憶信道的問題.另一種方法是把p(y|x)看成馬爾可夫鏈的形式,把信道的輸入和輸出序列看成為信道的狀態(tài).那么,信道的統(tǒng)計(jì)特性可用p(ynsn|xnsn-1)來描述.第十四頁，共九十九頁，編輯于2023年，星期五2023/5/2414單符號(hào)離散無記憶信道單符號(hào)離散信道的條件概率(也稱傳遞概率或轉(zhuǎn)移概率)為p(y|x)=p(y=bj|x=ai)=p(bj|ai)i=1,2,…,rj=1,2,…,s信道干擾使輸入x在傳輸中發(fā)生錯(cuò)誤,可用傳遞概率p(bj|ai)來描述干擾影響的大小.信道的干擾(噪聲)使當(dāng)信道輸入為x=ai,輸出y是哪一個(gè)符號(hào)無法確定.但信道輸出一定是b1,b2,…,bs中的一個(gè).即有第十五頁，共九十九頁，編輯于2023年，星期五2023/5/2415單符號(hào)離散無記憶信道因此,單符號(hào)離散信道可以用e[X,p(y|x),Y]三者加以描述.也可用圖來描述,如圖3.2所示。第十六頁，共九十九頁，編輯于2023年，星期五2023/5/2416[例3.1]二元對(duì)稱信道，簡(jiǎn)記為BSC(BinarySymmetricChannel)。一種重要的特殊信道,其傳遞概率p(b1|a1)=p(0|0)=1-pp(b2|a2)=p(1|1)=1-pp(b1|a2)=p(0|1)=pp(b2|a1)=p(1|0)=p且滿足其可用傳遞矩陣來表示,如第十七頁，共九十九頁，編輯于2023年，星期五2023/5/2417[例3.2]二元?jiǎng)h除信道，簡(jiǎn)記為BEC(BinaryEliminateChannel)。其傳遞概率如圖3.4所示,傳遞矩陣為并滿足式(3.4).第十八頁，共九十九頁，編輯于2023年，星期五2023/5/2418這種信道實(shí)際是存在的.假如一個(gè)實(shí)際信道,輸入0和1用兩個(gè)正、負(fù)方波信號(hào)表示,如圖3.5(a)所示.信道輸出送入譯碼器的將是受干擾后的方波信號(hào)R(t),如圖3.5(b)所示.第十九頁，共九十九頁，編輯于2023年，星期五2023/5/2419用積分器I=∫R(t)dt來判別發(fā)送信號(hào).如果I是正的,且大于某一電平,判別為“0”;若I是負(fù)的,且小于某一電平,判別是“1”;而若I的絕對(duì)值很小,不能作出判斷,就認(rèn)為是特殊符號(hào)“2”;信道干擾不是很嚴(yán)重的話,1→0和0→1的可能性要比0→2和1→2的可能性小得多,所以假設(shè)p(y=1|x=0)=p(y=0|x=1)=0是較合理的.第二十頁，共九十九頁，編輯于2023年，星期五2023/5/2420一般離散單符號(hào)信道的傳遞概率可用矩陣形式表示,即為了表述方便,令p(bj|ai)=pij,即第二十一頁，共九十九頁，編輯于2023年，星期五2023/5/2421且滿足該矩陣完全描述了信道的統(tǒng)計(jì)特性,有些概率是信道干擾引起的錯(cuò)誤概率,其他是信道正確傳輸?shù)?所以該矩陣又稱為信道矩陣.第二十二頁，共九十九頁，編輯于2023年，星期五2023/5/2422下面推導(dǎo)一般離散信道的一些概率關(guān)系。(1)輸入符號(hào)概率已知,p(x=ai)=p(ai),i=1,2,…,r,且輸入和輸出符號(hào)聯(lián)合概率為p(x=ai,y=bj)=p(ai,bj).則有p(bj|ai)=p(ai,bj)/p(ai)p(ai|bj)=p(ai,bj)/p(bj)前向概率p(bj|ai):也稱傳遞概率,即發(fā)送為ai,通過信道傳輸接收到為bj的概率.它是由信道噪聲引起的,描述了信道噪聲的特性.后向概率p(ai|bj):已知信道輸出端接收到符號(hào)為bj但發(fā)送的輸入符號(hào)為ai的概率.先驗(yàn)概率p(ai):收到輸出符號(hào)以前,輸入符號(hào)的概率;后驗(yàn)概率p(ai|bj):收到輸出符號(hào)以后,輸入符號(hào)的概率.第二十三頁，共九十九頁，編輯于2023年，星期五2023/5/2423(2)根據(jù)聯(lián)合概率可得輸出符號(hào)的概率

也可寫成矩陣形式，即第二十四頁，共九十九頁，編輯于2023年，星期五2023/5/2424(3)根據(jù)貝葉斯定律可得后驗(yàn)概率

可得上式說明,在信道輸出端接收到任一符號(hào)bj一定是輸入符號(hào)a1,a2,…,ar中的某一個(gè)送入信道.第二十五頁，共九十九頁，編輯于2023年，星期五2023/5/2425第三章離散信道3.1信道的數(shù)學(xué)模型及分類3.2信道疑義度及平均互信息3.3平均互信息的特性3.4離散無記憶的擴(kuò)展信道3.5信道容量及其迭代算法3.6信源與信道的匹配第二十六頁，共九十九頁，編輯于2023年，星期五2023/5/24263.2.1信道疑義度一、先驗(yàn)熵H(X)：在接收到輸出Y以前，關(guān)于輸入變量X的先驗(yàn)不確定性的度量。根據(jù)熵的概念，可計(jì)算出信道輸入信源X的熵如果信道無干擾(噪聲),輸出Y與輸入X一一對(duì)應(yīng)，那么，接收到傳送的符號(hào)Y后就消除了對(duì)發(fā)送符號(hào)X的先驗(yàn)不確定性。第二十七頁，共九十九頁，編輯于2023年，星期五2023/5/24273.2.1信道疑義度二、后驗(yàn)熵H(X|bj)一般信道有干擾(噪聲)存在,接收到輸出Y后對(duì)發(fā)送的符號(hào)X仍有不確定性。怎樣度量接收到Y(jié)后關(guān)于X的不確定性呢？接收到輸出y=bj后,其先驗(yàn)概率p(x)變成后驗(yàn)概率p(x|bj),其先驗(yàn)熵H(X)變成了后驗(yàn)熵H(X|bj)為

接收到輸出為bj后關(guān)于輸入X的信息測(cè)度(不確定性).第二十八頁，共九十九頁，編輯于2023年，星期五2023/5/24283.2.1信道疑義度三、信道疑義度后驗(yàn)熵是隨輸出y變化的隨機(jī)量,對(duì)輸出Y求期望,得條件熵為

這個(gè)條件熵稱為信道疑義度.表示輸出端收到輸出Y的全部符號(hào)后,對(duì)于輸入X尚存在的平均不確定性(疑義).第二十九頁，共九十九頁，編輯于2023年，星期五2023/5/24293.2.1信道疑義度三、信道疑義度對(duì)X尚存的不確定性是信道干擾(噪聲)引起.如果是一一對(duì)應(yīng)信道,收到輸出Y后,對(duì)X的不確定性完全消除,則H(X|Y)=0。由于H(X|Y)<H(X),這說明收到變量Y的所有符號(hào),總能消除一些關(guān)于輸入端X的不確定性，從而獲得了一些信息。第三十頁，共九十九頁，編輯于2023年，星期五2023/5/24303.2.2平均互信息根據(jù)上述可知:收到輸出Y后關(guān)于輸入X的平均不確定性H(X)變成了條件熵H(X|Y).信道傳輸消除了一些不確定性,獲得了一定的信息.I(X;Y)=H(X)-H(X|Y)I(X;Y)稱為X和Y的平均互信息.它代表收到輸出Y后平均每個(gè)符號(hào)獲得的關(guān)于X的信息量。:從定義可進(jìn)一步理解熵只是平均不確定性的描述,而熵差(不確定性的消除)才等于接收端所獲得信息量.因此,信息量不應(yīng)該與不確定性混為一談.第三十一頁，共九十九頁，編輯于2023年，星期五2023/5/24313.2.2平均互信息平均互信息I(X;Y)是緒論中提到的互信息I(x;y)在兩個(gè)概率空間X和Y中求統(tǒng)計(jì)平均的結(jié)果.因此給出互信息I(x;y)的表達(dá)式以示區(qū)別.即第三十二頁，共九十九頁，編輯于2023年，星期五2023/5/24323.2.2平均互信息互信息I(x;y)可取正值,也可取負(fù)值.如果互信息I(x;y)取負(fù)值,說明由于噪聲的存在,收到消息y后,反而使收信者對(duì)消息x是否出現(xiàn)的猜測(cè)難度增加了.獲得的信息量為負(fù)值。但在下一節(jié)，將證明平均互信息I(X;Y)永遠(yuǎn)不會(huì)取負(fù)值。第三十三頁，共九十九頁，編輯于2023年，星期五2023/5/24333.2.3平均互信息與各類熵的關(guān)系從Y中獲得關(guān)于X的平均互信息I(X;Y),等于1)接收到輸出Y的前、后,關(guān)于X的平均不確定性的消除,即I(X;Y)=H(X)-H(X|Y)2)發(fā)X的前、后,關(guān)于Y的平均不確定性的消除,即I(X;Y)=H(Y)-H(Y|X)I(X;Y)=H(X)-H(X|Y)=H(Y)-H(Y|X)=H(X)+H(Y)-H(XY)第三十四頁，共九十九頁，編輯于2023年，星期五2023/5/24343.2.3平均互信息與各類熵的關(guān)系H(XY)=H(X)+H(Y|X)=H(Y)+H(X|Y)=H(X|Y)+I(X;Y)+H(Y|X)第三十五頁，共九十九頁，編輯于2023年，星期五2023/5/24353.2.3平均互信息與各類熵的關(guān)系H(X|Y)是信道疑義度,表示信源X通過有噪信道傳輸后引起的信息量損失,故也稱為損失熵.H(Y|X)表示已知輸入X,對(duì)輸出Y尚存在的不確定性(疑義),這是由信道中噪聲引起的,故稱噪聲熵,或散布度,反映了信道中噪聲源的不確定性.圖中可看出I(X;Y)與I(Y;X)的交互性.可見,“互信息”的命名是恰當(dāng)?shù)?H(X|Y)=H(X)-I(X;Y)H(Y|X)=H(Y)-I(X;Y)第三十六頁，共九十九頁，編輯于2023年，星期五2023/5/24363.2.3條件平均互信息一、推廣到三個(gè)概率空間互信息I(x;y)是求兩個(gè)概率空間中事件之間的互信息.可將這概念推廣到三個(gè)概率空間中求事件之間的互信息.設(shè)三個(gè)離散概率空間X,Y,Z;x∈X,y∈Y,z∈Z,且有概率關(guān)系式:第三十七頁，共九十九頁，編輯于2023年，星期五2023/5/24373.2.3條件平均互信息一、推廣到三個(gè)概率空間 這三個(gè)概率空間可看作為兩個(gè)串接系統(tǒng)1和系統(tǒng)2的輸入和輸出空間,如圖3.6(a)所示.也可考慮為如圖3.6(b),(c)所示,將X作為系統(tǒng)1的輸入空間,而Y和Z作為系統(tǒng)1的輸出空間,其中Y,Z可為并行輸出或按時(shí)間前后的串行輸出。第三十八頁，共九十九頁，編輯于2023年，星期五2023/5/2438二、條件互信息在已知z的條件下,接收到y(tǒng)獲得關(guān)于事件x的條件互信息

與互信息的區(qū)別:其先驗(yàn)概率和后驗(yàn)概率都是在某一特定條件下的取值.第三十九頁，共九十九頁，編輯于2023年，星期五2023/5/2439三、平均條件互信息將條件互信息I(x;y|z)在概率空間XYZ中求統(tǒng)計(jì)平均,得平均條件互信息:第四十頁，共九十九頁，編輯于2023年，星期五2023/5/2440四、互信息從互信息的定義得出,當(dāng)已知y,z后,總共獲得關(guān)于x的互信息

這個(gè)關(guān)系式表明:yz聯(lián)合給出關(guān)于x的互信息量等于y給出關(guān)于x的互信息量與y已知條件下z給出關(guān)于x的互信息量之和.第四十一頁，共九十九頁，編輯于2023年，星期五2023/5/2441五、平均互信息將互信息I(x;yz)在概率空間XYZ中求統(tǒng)計(jì)平均,得平均互信息:第四十二頁，共九十九頁，編輯于2023年，星期五2023/5/2442六、關(guān)系式I(X;Y|Z)=H(X|Z)-H(X|YZ)I(X;YZ)=I(X;Y)+I(X;Z|Y)(3.29)式(3.29)表明,聯(lián)合變量YZ和變量X之間的平均互信息,等于變量X和Y的平均互信息加上在變量Y已知條件下變量X和Z的平均互信息.上述定義和關(guān)系式易于推廣到任意有限維空間的情況.特別是在多用戶信息論中這些關(guān)系式十分有用。第四十三頁，共九十九頁，編輯于2023年，星期五2023/5/2443[例3.3]四個(gè)等概率分布的消息M1,M2,M3和M4被送入一個(gè)二元無記憶對(duì)稱信道(BSC)進(jìn)行傳送.通過編碼使M1=00,M2=01,M3=10和M4=11.而BSC信道如右圖所示.試問,輸入是M1和輸出符號(hào)是0的互信息是多少?如果知道第二個(gè)符號(hào)也是0,這是帶來多少附加信息量?第四十四頁，共九十九頁，編輯于2023年，星期五2023/5/2444解:(1)根據(jù)題意知p(M1)=p(M2)=p(M3)=p(M4)=1/4,而p(0|M1)=p(0|0)=1-p.所以,輸入M1和第一個(gè)輸出符號(hào)0的聯(lián)合概率為根據(jù)信源的概率分布，輸出第一個(gè)符號(hào)為0的概率為根據(jù)互信息的定義，可得第四十五頁，共九十九頁，編輯于2023年，星期五2023/5/2445(2)若輸出符號(hào)為00，可得根據(jù)信道是無記憶的，有同理，可得由式(3.25)可知,當(dāng)已知第一個(gè)符號(hào)為0,第二個(gè)也是0帶來關(guān)于M1的附加信息第四十六頁，共九十九頁，編輯于2023年，星期五2023/5/2446第三章離散信道3.1信道的數(shù)學(xué)模型及分類3.2信道疑義度及平均互信息3.3平均互信息的特性3.4離散無記憶的擴(kuò)展信道3.5信道容量及其迭代算法3.6信源與信道的匹配第四十七頁，共九十九頁，編輯于2023年，星期五2023/5/24473.3平均互信息的特性(1)平均互信息的非負(fù)性.即I(X;Y)≥0.當(dāng)X和Y統(tǒng)計(jì)獨(dú)立時(shí),等式成立.證明:根據(jù)平均互信息的定義,因?yàn)閘ogx是嚴(yán)格∩型凸函數(shù),直接應(yīng)用詹森不等式得第四十八頁，共九十九頁，編輯于2023年，星期五2023/5/24483.3平均互信息的特性(1)平均互信息的非負(fù)性.即I(X;Y)≥0.這個(gè)性質(zhì)說明:1)平均互信息量不會(huì)是負(fù)值.從平均的角度來看,信道傳輸總能消除一些不確定性,接收到一定的信息.2)在統(tǒng)計(jì)獨(dú)立信道(信道輸入和輸出是統(tǒng)計(jì)獨(dú)立)中,接收不到任何信息.因?yàn)閭鬏數(shù)男畔⑷繐p失在信道中,以致沒有任何信息傳輸?shù)浇K端,但也不會(huì)失去已知的信息.第四十九頁，共九十九頁，編輯于2023年，星期五2023/5/2449(2)平均互信息的極值性.即0≤I(X;Y)≤H(X)因?yàn)樾诺酪闪x度H(X|Y)總大于零,所以平均互信息I(X;Y)總是小于熵H(X).只有當(dāng)信道中傳輸信息無損失時(shí),即H(X|Y)=0,接收到Y(jié)后獲得關(guān)于X的信息量才等于符號(hào)集X中平均每符號(hào)所含有的信息量.一般情況下,平均互信息I(X;Y)必在零和H(X)之間.第五十頁，共九十九頁，編輯于2023年，星期五2023/5/2450(3)平均互信息的交互性(對(duì)稱性).即I(X;Y)=I(Y;X)這個(gè)性質(zhì)說明:1)當(dāng)X和Y統(tǒng)計(jì)獨(dú)立時(shí)(即H(X|Y)=H(X)),就不可能從一個(gè)隨機(jī)變量獲得關(guān)于另一個(gè)隨機(jī)變量的信息,所以I(X;Y)=I(Y;X)=0;2)當(dāng)信道輸入X和輸出Y一一對(duì)應(yīng)時(shí),即H(X|Y)=0,從一個(gè)變量就可以充分獲得關(guān)于另一個(gè)變量的信息,即I(X;Y)=I(Y;X)=H(X)=H(Y).第五十一頁，共九十九頁，編輯于2023年，星期五2023/5/2451(4)平均互信息的凸函數(shù)性.平均互信息I(X;Y)只是信源輸入X的概率分布p(x)和信道傳遞概率p(y|x)的函數(shù),因此對(duì)于不同信源和不同信道得到的平均互信息是不同的.第五十二頁，共九十九頁，編輯于2023年，星期五2023/5/2452定理3.1I(X;Y)是信源輸入概率分布p(x)的∩型凸函數(shù).定理3.2I(X;Y)是信道傳遞概率p(y|x)的∪型凸函數(shù).定理3.1意味著,當(dāng)固定某信道時(shí),一定存在有一種信源(某一種概率分布p(x)),使輸出端獲得的平均信息量為最大(因?yàn)椤尚屯购瘮?shù)存在極大值).定理3.2說明:當(dāng)信源(概率空間)固定后,存在一種最差的信道,此信道的干擾(噪聲)最大,而輸出端獲得的信息量最小.第五十三頁，共九十九頁，編輯于2023年，星期五2023/5/2453[證明3.1]根據(jù)∩型凸函數(shù)的定義來證明.首先固定信道,即信道的轉(zhuǎn)移概率p(y|x)是固定的.那么平均互信息I(X;Y)將只是p(x)的函數(shù),簡(jiǎn)寫成I[p(x)].現(xiàn)給定輸入信源X兩種概率分布p1(x)和p2(x),其聯(lián)合概率為p1(xy)=p1(x)p(y|x)和p2(xy)=p2(x)p(y|x),而信道輸出的平均互信息分別為I[p1(x)]和I[p2(x)].令p(x)=θp1(x)+(1-θ)p2(x),其中0<θ<1,其聯(lián)合概率分布為p(xy)=p(x)p(y|x)=θp1(x)p(y|x)+(1-θ)p2(x)p(y|x)=θp1(xy)+(1-θ)p2(xy),

相應(yīng)的平均互信息為I[p(x)].第五十四頁，共九十九頁，編輯于2023年，星期五2023/5/2454因?yàn)閒=logx是∩型凸函數(shù),根據(jù)詹森不等式可得第五十五頁，共九十九頁，編輯于2023年，星期五2023/5/2455因?yàn)?<θ<1,可得即I(X;Y)是輸入信源的概率分布p(x)的∩型凸函數(shù).第五十六頁，共九十九頁，編輯于2023年，星期五2023/5/2456[例3.4](續(xù)例3.1)設(shè)二元對(duì)稱信道的輸入概率空間和信道特性如圖3.3所示.計(jì)算得平均互信息

其中,H(p)是[0,1]區(qū)域上的熵函數(shù).第五十七頁，共九十九頁，編輯于2023年，星期五2023/5/2457根據(jù)可得 p(y=0)=w(1-p)+(1-w)p p(y=1)=wp+(1-w)(1-p)那么,

其中,H(w,p)也是[0,1]區(qū)域上的熵函數(shù).第五十八頁，共九十九頁，編輯于2023年，星期五2023/5/2458當(dāng)信道固定即固定p時(shí),可得I(X

;Y)是w的∩型凸函數(shù),其曲線如圖3.9.從圖中可知,當(dāng)二元對(duì)稱信道的信道矩陣固定后,若輸入變量X的概率分布不同,在接收端平均每個(gè)符號(hào)獲得的信息量就不同.只有當(dāng)輸入變量X是等概率分布,在信道接收端平均每個(gè)符號(hào)才獲得最大的信息量.第五十九頁，共九十九頁，編輯于2023年，星期五2023/5/2459當(dāng)固定信源的概率分布w時(shí),即得I(X

;Y)是p的∪型凸函數(shù),其曲線如圖3.10.從圖中可知,當(dāng)二元信源固定后,存在一種二元對(duì)稱信道(即p=1/2),使在信道輸出端獲得的信息量最小,即等于零.也就是說,信道的信息全部損失在信道中.這是一種最差的信道(其噪聲為最大).第六十頁，共九十九頁，編輯于2023年，星期五2023/5/2460例例4.2.2一個(gè)信源以相等的概率及1000碼元/秒的速率把"0"和"1"碼送入有噪信道,由于信道中噪聲的影響.發(fā)送為"0"接收為"1"的概率為1/16,而發(fā)送為"1"接收為"0"的概率為1/32,求信源熵、條件熵和平均互信息.解：根據(jù)題意,令輸入符號(hào)a0=0,a1=1,輸出符號(hào)b0=0,b1=1,可以首先求出信源熵,即第六十一頁，共九十九頁，編輯于2023年，星期五2023/5/2461由題可知,信道的轉(zhuǎn)移概率矩陣為可得條件概率和聯(lián)合概率分別為第六十二頁，共九十九頁，編輯于2023年，星期五2023/5/2462根據(jù)條件概率和聯(lián)合概率可得條件熵為根據(jù)信源熵和條件熵可得平均互信息為I(X

;Y)=H(X)-H(X|Y)=1-0.27=0.73比特/符號(hào)第六十三頁，共九十九頁，編輯于2023年，星期五2023/5/2463第三章離散信道3.1信道的數(shù)學(xué)模型及分類3.2信道疑義度及平均互信息3.3平均互信息的特性3.4離散無記憶的擴(kuò)展信道3.5信道容量及其迭代算法3.6信源與信道的匹配第六十四頁，共九十九頁，編輯于2023年，星期五2023/5/2464離散無記憶的N次擴(kuò)展信道1、信道模型第六十五頁，共九十九頁，編輯于2023年，星期五2023/5/2465離散無記憶的N次擴(kuò)展信道2、轉(zhuǎn)移概率矩陣第六十六頁，共九十九頁，編輯于2023年，星期五2023/5/2466[例3.5]求例3.1中二元無記憶信道的二次擴(kuò)展信道輸入符號(hào)集A2=[00,01,10,11],輸出符號(hào)集B2=[00,01,10,11];轉(zhuǎn)移概率為轉(zhuǎn)移概率矩陣為第六十七頁，共九十九頁，編輯于2023年，星期五2023/5/2467N次擴(kuò)展信道的平均互信息N次擴(kuò)展信道的平均互信息為定理3.3

如果信道是無記憶的(信源有記憶),即

等式成立條件:信源也無記憶.定理3.4

如果信源是無記憶的(信道有記憶),即

等式成立條件:信道也無記憶.第六十八頁，共九十九頁，編輯于2023年，星期五2023/5/2468定理3.3證明？？？？第六十九頁，共九十九頁，編輯于2023年，星期五2023/5/2469定理3.3說明:信源的有記憶性降低了信源的熵H(XN);[∵I(X;Y)=H(XN)-H(XN|YN)]有記憶信源:信源先后發(fā)出的符號(hào)是互相依賴的定理3.4說明:信道的有記憶性降低了條件熵H(XN|YN);有記憶信道:輸出符號(hào)不但與對(duì)應(yīng)時(shí)刻的輸入符號(hào)有關(guān),還與以前時(shí)刻輸入及輸出符號(hào)有關(guān)第七十頁，共九十九頁，編輯于2023年，星期五2023/5/2470無記憶的N次擴(kuò)展信道的平均互信息若信源和信道都是無記憶的,即定理3.3和3.4同時(shí)成立,那么等式成立,即

若同時(shí)滿足:1)Xi取自同一概率空間(相同符號(hào)集及概率分布);2)相同的信道(信道轉(zhuǎn)移概率矩陣)則有:第七十一頁，共九十九頁，編輯于2023年，星期五2023/5/2471無記憶的N次擴(kuò)展信道的平均互信息對(duì)于無擾一一對(duì)應(yīng)(無噪)信道(H(X|Y)=0),接收到的平均互信息就是輸入信源的熵,定理3.3同時(shí)說明

第七十二頁，共九十九頁，編輯于2023年，星期五2023/5/2472第三章離散信道3.1信道的數(shù)學(xué)模型及分類3.2信道疑義度及平均互信息3.3平均互信息的特性3.4離散無記憶的擴(kuò)展信道3.5信道容量及特殊信道的容量計(jì)算3.6信源與信道的匹配第七十三頁，共九十九頁，編輯于2023年，星期五2023/5/2473信道的信息傳輸率R信道研究的目的:討論信道中平均每個(gè)符號(hào)所能傳送的信息量,即信道的信息傳輸率R.信道的信息傳輸率R就是平均互信息,這是因?yàn)槠骄バ畔(X;Y)就是接收到符號(hào)Y后平均每個(gè)符號(hào)獲得的關(guān)于X的信息量.因此R=I(X;Y)=H(X)-H(X|Y)比特/符號(hào)第七十四頁，共九十九頁，編輯于2023年，星期五2023/5/2474信道容量C定義:最大的信息傳輸率,即

其相應(yīng)的輸入概率分布稱為最佳輸入分布.這是因?yàn)樵谛诺拦潭〞r(shí),I(X;Y)是輸入變量X的概率分布p(x)的∩型凸函數(shù)(見定理3.1).可知:信道容量C與信源概率分布無關(guān),它只是信道傳輸概率的函數(shù),只與信道統(tǒng)計(jì)特性有關(guān).所以,信道容量是完全描述信道特性的參量,是信道能夠傳輸?shù)淖畲笮畔⒘?第七十五頁，共九十九頁，編輯于2023年，星期五2023/5/2475單位時(shí)間內(nèi)的R和C有時(shí)關(guān)心的是信道在單位時(shí)間內(nèi)平均傳輸?shù)男畔⒘?信息傳輸速率Rt:信道每秒鐘傳輸?shù)男畔⒘?若平均傳輸一個(gè)符號(hào)需要t秒),即同理,可得單位時(shí)間內(nèi)平均傳輸?shù)淖畲笮畔⒘康谄呤?，共九十九頁，編輯?023年，星期五2023/5/24763.5.1離散無噪信道從數(shù)學(xué)上說,信道容量計(jì)算就是對(duì)互信息I(X;Y)求極大值的問題.對(duì)于一般信道,信道容量的計(jì)算相當(dāng)復(fù)雜.下面僅討論某些特殊類型的信道容量計(jì)算問題.第七十七頁，共九十九頁，編輯于2023年，星期五2023/5/24771、無噪無損信道

輸入和輸出符號(hào)之間有確定的一一對(duì)應(yīng)關(guān)系,即信道矩陣是單位矩陣H(X|Y)=0,H(Y|X)=0I(X;Y)=H(X)=H(Y)第七十八頁，共九十九頁，編輯于2023年，星期五2023/5/24782、有噪無損信道輸入符號(hào)通過傳輸變成若干輸出符號(hào),雖然不是一一對(duì)應(yīng)關(guān)系,但這些輸出符號(hào)仍可分成互不相交的一些集合.p(a1|bj)=1,j=1,2p(a2|bj)=1,j=3,4,5p(a3|bj)=1,j=6H(X|Y)=0,H(Y|X)≠0I(X;Y)=H(X)<H(Y)第七十九頁，共九十九頁，編輯于2023年，星期五2023/5/24793、無噪有損信道前向概率p(y|x)等于0或1,即輸出Y是輸入X的確定函數(shù);但不是一一對(duì)應(yīng),而是多一對(duì)應(yīng)關(guān)系.因而,后向概率p(x|y)不等于0或1.H(X|Y)≠0,H(Y|X)=0.I(X;Y)=H(Y)<H(X)第八十頁，共九十九頁，編輯于2023年，星期五2023/5/2480平均互信息與損失熵、噪聲熵、信源熵的關(guān)系

無噪無損有噪無損無噪有損損失熵H(X|Y)=0=0≠0噪聲熵H(Y|X)=0≠0=0平均互信息I(X;Y)=H(X)=H(Y)=H(X)<H(Y)=H(Y)<H(X)第八十一頁，共九十九頁，編輯于2023年，星期五2023/5/2481無損及無噪信道容量1、對(duì)于無損信道,其信息傳輸率R是輸入信源X輸出每個(gè)符號(hào)攜帶的信息量,即信源熵H(X),所以

式中輸入信源X有r個(gè)符號(hào),等概分布時(shí)H(X)最大.2、對(duì)于無噪信道,信道容量為

其中輸出信源Y有s個(gè)符號(hào),等概分布時(shí)H(Y)最大.而且一定能找到一種輸入分布使輸出符號(hào)Y達(dá)到等概分布.第八十二頁，共九十九頁，編輯于2023年，星期五2023/5/2482第八十三頁，共九十九頁，編輯于2023年，星期五2023/5/24833.5.2對(duì)稱離散信道對(duì)稱性:1)信道矩陣中每一行都是由{p1’,p2’,…,ps’}集的諸元素不同排列組成,2)每一列也都是由{q1’,q2’,…,qr’}集的諸元素不同排列組成.當(dāng)r=s,{pi’}集和{qi’}集相同;若r<s,{qi’}集應(yīng)是{pi’}集的子集.√×第八十四頁，共九十九頁，編輯于2023年，星期五2023/5/2484均勻信道(或強(qiáng)對(duì)稱信道)對(duì)稱離散信道的一類特例輸入和輸出符號(hào)個(gè)數(shù)相同,等于r總的錯(cuò)誤概率為p,對(duì)稱地平均分配給r-1個(gè)輸出符號(hào)信道矩陣中各列之和也等于1二元對(duì)稱信道就是r=2的均勻信道第八十五頁，共九十九頁，編輯于2023年，星期五2023/5/2485對(duì)稱離散信道的平均互信息

其中

為常數(shù),這是因?yàn)镠(Y|X=x)是固定X=x時(shí)對(duì)Y求和,與x無關(guān).由于信道和熵的對(duì)稱性,H(Y|X=x)僅與{p1’,p2’,…,ps’}取值有關(guān),與順序無關(guān).

因此可得第八十六頁，共九十九頁，編輯于2023年，星期五2023/5/2486對(duì)稱離散信道的容量即求一種輸入分布p(x)使H(Y)取最大值的問題了。現(xiàn)已知輸出Y的符號(hào)集共有s個(gè)符號(hào)，則H(Y)≤logs;H(Y)達(dá)到最大值條件:只有當(dāng)p(y)=1/s(等概分布).對(duì)稱離散信道下p(y)等概分布條件:輸入是等概分布.第八十七頁，共九十九頁，編輯于2023年，星期五2023/5/24873.5.3一般離散信道信道容量的定義:在固定信道的條件下,對(duì)所有可能的輸入概率分布p(x)求平均互信息的條件(概率和歸“1”)極大值.極值性存在條件:I(X;Y)是輸入概率分布p(x)(即r個(gè)變量{p(a1),…,p(ar)})的多元∩型凸函數(shù),所以極大值一定存在.第八十八頁，共九十九頁，編輯于2023年，星期五2023/5/24883.5.3一般離散信道求條件極值方法:拉格朗日乘子法.

引進(jìn)一個(gè)新函數(shù) 其中λ為拉格朗日乘子(待