信息論與編碼離散信道

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

對任意N值和任意x、y的取值，上式成立。第12頁，共99頁，2023年，2月20日，星期三2023/4/312(3)有干擾有記憶信道。這是更一般的情況,既有干擾(噪聲)又有記憶.實際信道往往是這種類型.例如碼字干擾就是由于信道濾波使頻率特性不理想造成的.有記憶信道:輸出符號不但與對應時刻的輸入符號有關(guān),還與以前時刻輸入及輸出符號有關(guān),其信道條件概率p(y|x)不再滿足式(3.2)。第13頁，共99頁，2023年，2月20日，星期三2023/4/313(3)有干擾有記憶信道。處理這類有記憶信道時最直觀的方法是把記憶較強的N個符號當作一個矢量符號來處理,而各矢量符號之間認為是無記憶的,轉(zhuǎn)化成無記憶信道的問題.另一種方法是把p(y|x)看成馬爾可夫鏈的形式,把信道的輸入和輸出序列看成為信道的狀態(tài).那么,信道的統(tǒng)計特性可用p(ynsn|xnsn-1)來描述.第14頁，共99頁，2023年，2月20日，星期三2023/4/314單符號離散無記憶信道單符號離散信道的條件概率(也稱傳遞概率或轉(zhuǎn)移概率)為p(y|x)=p(y=bj|x=ai)=p(bj|ai)i=1,2,…,rj=1,2,…,s信道干擾使輸入x在傳輸中發(fā)生錯誤,可用傳遞概率p(bj|ai)來描述干擾影響的大小.信道的干擾(噪聲)使當信道輸入為x=ai,輸出y是哪一個符號無法確定.但信道輸出一定是b1,b2,…,bs中的一個.即有

第15頁，共99頁，2023年，2月20日，星期三2023/4/315單符號離散無記憶信道因此,單符號離散信道可以用e[X,p(y|x),Y]三者加以描述.也可用圖來描述,如圖3.2所示。第16頁，共99頁，2023年，2月20日，星期三2023/4/316[例3.1]二元對稱信道，簡記為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且滿足其可用傳遞矩陣來表示,如第17頁，共99頁，2023年，2月20日，星期三2023/4/317[例3.2]二元刪除信道，簡記為BEC(BinaryEliminateChannel)。其傳遞概率如圖3.4所示,傳遞矩陣為并滿足式(3.4).第18頁，共99頁，2023年，2月20日，星期三2023/4/318這種信道實際是存在的.假如一個實際信道,輸入0和1用兩個正、負方波信號表示,如圖3.5(a)所示.信道輸出送入譯碼器的將是受干擾后的方波信號R(t),如圖3.5(b)所示.第19頁，共99頁，2023年，2月20日，星期三2023/4/319用積分器I=∫R(t)dt來判別發(fā)送信號.如果I是正的,且大于某一電平,判別為“0”;若I是負的,且小于某一電平,判別是“1”;而若I的絕對值很小,不能作出判斷,就認為是特殊符號“2”;信道干擾不是很嚴重的話,1→0和0→1的可能性要比0→2和1→2的可能性小得多,所以假設p(y=1|x=0)=p(y=0|x=1)=0是較合理的.第20頁，共99頁，2023年，2月20日，星期三2023/4/320一般離散單符號信道的傳遞概率可用矩陣形式表示,即為了表述方便,令p(bj|ai)=pij,即第21頁，共99頁，2023年，2月20日，星期三2023/4/321且滿足該矩陣完全描述了信道的統(tǒng)計特性,有些概率是信道干擾引起的錯誤概率,其他是信道正確傳輸?shù)?所以該矩陣又稱為信道矩陣.第22頁，共99頁，2023年，2月20日，星期三2023/4/322下面推導一般離散信道的一些概率關(guān)系。(1)輸入符號概率已知,p(x=ai)=p(ai),i=1,2,…,r,且輸入和輸出符號聯(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):已知信道輸出端接收到符號為bj但發(fā)送的輸入符號為ai的概率.先驗概率p(ai):收到輸出符號以前,輸入符號的概率;后驗概率p(ai|bj):收到輸出符號以后,輸入符號的概率.第23頁，共99頁，2023年，2月20日，星期三2023/4/323(2)根據(jù)聯(lián)合概率可得輸出符號的概率

也可寫成矩陣形式，即第24頁，共99頁，2023年，2月20日，星期三2023/4/324(3)根據(jù)貝葉斯定律可得后驗概率

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

接收到輸出為bj后關(guān)于輸入X的信息測度(不確定性).第28頁，共99頁，2023年，2月20日，星期三2023/4/3283.2.1信道疑義度三、信道疑義度后驗熵是隨輸出y變化的隨機量,對輸出Y求期望,得條件熵為

這個條件熵稱為信道疑義度.表示輸出端收到輸出Y的全部符號后,對于輸入X尚存在的平均不確定性(疑義).第29頁，共99頁，2023年，2月20日，星期三2023/4/3293.2.1信道疑義度三、信道疑義度對X尚存的不確定性是信道干擾(噪聲)引起.如果是一一對應信道,收到輸出Y后,對X的不確定性完全消除,則H(X|Y)=0。由于H(X|Y)<H(X),這說明收到變量Y的所有符號,總能消除一些關(guān)于輸入端X的不確定性，從而獲得了一些信息。第30頁，共99頁，2023年，2月20日，星期三2023/4/3303.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后平均每個符號獲得的關(guān)于X的信息量。:從定義可進一步理解熵只是平均不確定性的描述,而熵差(不確定性的消除)才等于接收端所獲得信息量.因此,信息量不應該與不確定性混為一談.第31頁，共99頁，2023年，2月20日，星期三2023/4/3313.2.2平均互信息平均互信息I(X;Y)是緒論中提到的互信息I(x;y)在兩個概率空間X和Y中求統(tǒng)計平均的結(jié)果.因此給出互信息I(x;y)的表達式以示區(qū)別.即第32頁，共99頁，2023年，2月20日，星期三2023/4/3323.2.2平均互信息互信息I(x;y)可取正值,也可取負值.如果互信息I(x;y)取負值,說明由于噪聲的存在,收到消息y后,反而使收信者對消息x是否出現(xiàn)的猜測難度增加了.獲得的信息量為負值。但在下一節(jié)，將證明平均互信息I(X;Y)永遠不會取負值。第33頁，共99頁，2023年，2月20日，星期三2023/4/3333.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)第34頁，共99頁，2023年，2月20日，星期三2023/4/3343.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)第35頁，共99頁，2023年，2月20日，星期三2023/4/3353.2.3平均互信息與各類熵的關(guān)系H(X|Y)是信道疑義度,表示信源X通過有噪信道傳輸后引起的信息量損失,故也稱為損失熵.H(Y|X)表示已知輸入X,對輸出Y尚存在的不確定性(疑義),這是由信道中噪聲引起的,故稱噪聲熵,或散布度,反映了信道中噪聲源的不確定性.圖中可看出I(X;Y)與I(Y;X)的交互性.可見,“互信息”的命名是恰當?shù)?H(X|Y)=H(X)-I(X;Y)H(Y|X)=H(Y)-I(X;Y)第36頁，共99頁，2023年，2月20日，星期三2023/4/3363.2.3條件平均互信息一、推廣到三個概率空間互信息I(x;y)是求兩個概率空間中事件之間的互信息.可將這概念推廣到三個概率空間中求事件之間的互信息.設三個離散概率空間X,Y,Z;x∈X,y∈Y,z∈Z,且有概率關(guān)系式:第37頁，共99頁，2023年，2月20日，星期三2023/4/3373.2.3條件平均互信息一、推廣到三個概率空間 這三個概率空間可看作為兩個串接系統(tǒng)1和系統(tǒng)2的輸入和輸出空間,如圖3.6(a)所示.也可考慮為如圖3.6(b),(c)所示,將X作為系統(tǒng)1的輸入空間,而Y和Z作為系統(tǒng)1的輸出空間,其中Y,Z可為并行輸出或按時間前后的串行輸出。第38頁，共99頁，2023年，2月20日，星期三2023/4/338二、條件互信息在已知z的條件下,接收到y(tǒng)獲得關(guān)于事件x的條件互信息

與互信息的區(qū)別:其先驗概率和后驗概率都是在某一特定條件下的取值.第39頁，共99頁，2023年，2月20日，星期三2023/4/339三、平均條件互信息將條件互信息I(x;y|z)在概率空間XYZ中求統(tǒng)計平均,得平均條件互信息:第40頁，共99頁，2023年，2月20日，星期三2023/4/340四、互信息從互信息的定義得出,當已知y,z后,總共獲得關(guān)于x的互信息

這個關(guān)系式表明:yz聯(lián)合給出關(guān)于x的互信息量等于y給出關(guān)于x的互信息量與y已知條件下z給出關(guān)于x的互信息量之和.第41頁，共99頁，2023年，2月20日，星期三2023/4/341五、平均互信息將互信息I(x;yz)在概率空間XYZ中求統(tǒng)計平均,得平均互信息:第42頁，共99頁，2023年，2月20日，星期三2023/4/342六、關(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)系式十分有用。第43頁，共99頁，2023年，2月20日，星期三2023/4/343[例3.3]四個等概率分布的消息M1,M2,M3和M4被送入一個二元無記憶對稱信道(BSC)進行傳送.通過編碼使M1=00,M2=01,M3=10和M4=11.而BSC信道如右圖所示.試問,輸入是M1和輸出符號是0的互信息是多少?如果知道第二個符號也是0,這是帶來多少附加信息量?第44頁，共99頁，2023年，2月20日，星期三2023/4/344解:(1)根據(jù)題意知p(M1)=p(M2)=p(M3)=p(M4)=1/4,而p(0|M1)=p(0|0)=1-p.所以,輸入M1和第一個輸出符號0的聯(lián)合概率為根據(jù)信源的概率分布，輸出第一個符號為0的概率為根據(jù)互信息的定義，可得第45頁，共99頁，2023年，2月20日，星期三2023/4/345(2)若輸出符號為00，可得根據(jù)信道是無記憶的，有同理，可得由式(3.25)可知,當已知第一個符號為0,第二個也是0帶來關(guān)于M1的附加信息第46頁，共99頁，2023年，2月20日，星期三2023/4/346第三章離散信道3.1信道的數(shù)學模型及分類3.2信道疑義度及平均互信息3.3平均互信息的特性3.4離散無記憶的擴展信道3.5信道容量及其迭代算法3.6信源與信道的匹配第47頁，共99頁，2023年，2月20日，星期三2023/4/3473.3平均互信息的特性(1)平均互信息的非負性.即I(X;Y)≥0.當X和Y統(tǒng)計獨立時,等式成立.證明:根據(jù)平均互信息的定義,因為logx是嚴格∩型凸函數(shù),直接應用詹森不等式得第48頁，共99頁，2023年，2月20日，星期三2023/4/3483.3平均互信息的特性(1)平均互信息的非負性.即I(X;Y)≥0.這個性質(zhì)說明:1)平均互信息量不會是負值.從平均的角度來看,信道傳輸總能消除一些不確定性,接收到一定的信息.2)在統(tǒng)計獨立信道(信道輸入和輸出是統(tǒng)計獨立)中,接收不到任何信息.因為傳輸?shù)男畔⑷繐p失在信道中,以致沒有任何信息傳輸?shù)浇K端,但也不會失去已知的信息.第49頁，共99頁，2023年，2月20日，星期三2023/4/349(2)平均互信息的極值性.即0≤I(X;Y)≤H(X)因為信道疑義度H(X|Y)總大于零,所以平均互信息I(X;Y)總是小于熵H(X).只有當信道中傳輸信息無損失時,即H(X|Y)=0,接收到Y(jié)后獲得關(guān)于X的信息量才等于符號集X中平均每符號所含有的信息量.一般情況下,平均互信息I(X;Y)必在零和H(X)之間.第50頁，共99頁，2023年，2月20日，星期三2023/4/350(3)平均互信息的交互性(對稱性).即I(X;Y)=I(Y;X)這個性質(zhì)說明:1)當X和Y統(tǒng)計獨立時(即H(X|Y)=H(X)),就不可能從一個隨機變量獲得關(guān)于另一個隨機變量的信息,所以I(X;Y)=I(Y;X)=0;2)當信道輸入X和輸出Y一一對應時,即H(X|Y)=0,從一個變量就可以充分獲得關(guān)于另一個變量的信息,即I(X;Y)=I(Y;X)=H(X)=H(Y).第51頁，共99頁，2023年，2月20日，星期三2023/4/351(4)平均互信息的凸函數(shù)性.平均互信息I(X;Y)只是信源輸入X的概率分布p(x)和信道傳遞概率p(y|x)的函數(shù),因此對于不同信源和不同信道得到的平均互信息是不同的.第52頁，共99頁，2023年，2月20日，星期三2023/4/352定理3.1I(X;Y)是信源輸入概率分布p(x)的∩型凸函數(shù).定理3.2I(X;Y)是信道傳遞概率p(y|x)的∪型凸函數(shù).定理3.1意味著,當固定某信道時,一定存在有一種信源(某一種概率分布p(x)),使輸出端獲得的平均信息量為最大(因為∩型凸函數(shù)存在極大值).定理3.2說明:當信源(概率空間)固定后,存在一種最差的信道,此信道的干擾(噪聲)最大,而輸出端獲得的信息量最小.第53頁，共99頁，2023年，2月20日，星期三2023/4/353[證明3.1]根據(jù)∩型凸函數(shù)的定義來證明.首先固定信道,即信道的轉(zhuǎn)移概率p(y|x)是固定的.那么平均互信息I(X;Y)將只是p(x)的函數(shù),簡寫成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),

相應的平均互信息為I[p(x)].第54頁，共99頁，2023年，2月20日，星期三2023/4/354因為f=logx是∩型凸函數(shù),根據(jù)詹森不等式可得第55頁，共99頁，2023年，2月20日，星期三2023/4/355因為0<θ<1,可得即I(X;Y)是輸入信源的概率分布p(x)的∩型凸函數(shù).第56頁，共99頁，2023年，2月20日，星期三2023/4/356[例3.4](續(xù)例3.1)設二元對稱信道的輸入概率空間和信道特性如圖3.3所示.計算得平均互信息

其中,H(p)是[0,1]區(qū)域上的熵函數(shù).第57頁，共99頁，2023年，2月20日，星期三2023/4/357根據(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ù).第58頁，共99頁，2023年，2月20日，星期三2023/4/358當信道固定即固定p時,可得I(X

;Y)是w的∩型凸函數(shù),其曲線如圖3.9.從圖中可知,當二元對稱信道的信道矩陣固定后,若輸入變量X的概率分布不同,在接收端平均每個符號獲得的信息量就不同.只有當輸入變量X是等概率分布,在信道接收端平均每個符號才獲得最大的信息量.第59頁，共99頁，2023年，2月20日，星期三2023/4/359當固定信源的概率分布w時,即得I(X

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

;Y)=H(X)-H(X|Y)=1-0.27=0.73比特/符號第63頁，共99頁，2023年，2月20日，星期三2023/4/363第三章離散信道3.1信道的數(shù)學模型及分類3.2信道疑義度及平均互信息3.3平均互信息的特性3.4離散無記憶的擴展信道3.5信道容量及其迭代算法3.6信源與信道的匹配第64頁，共99頁，2023年，2月20日，星期三2023/4/364離散無記憶的N次擴展信道1、信道模型第65頁，共99頁，2023年，2月20日，星期三2023/4/365離散無記憶的N次擴展信道2、轉(zhuǎn)移概率矩陣第66頁，共99頁，2023年，2月20日，星期三2023/4/366[例3.5]求例3.1中二元無記憶信道的二次擴展信道輸入符號集A2=[00,01,10,11],輸出符號集B2=[00,01,10,11];轉(zhuǎn)移概率為轉(zhuǎn)移概率矩陣為第67頁，共99頁，2023年，2月20日，星期三2023/4/367N次擴展信道的平均互信息N次擴展信道的平均互信息為定理3.3

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

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

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

等式成立條件:信道也無記憶.第68頁，共99頁，2023年，2月20日，星期三2023/4/368定理3.3證明？？？？第69頁，共99頁，2023年，2月20日，星期三2023/4/369定理3.3說明:信源的有記憶性降低了信源的熵H(XN);[∵I(X;Y)=H(XN)-H(XN|YN)]有記憶信源:信源先后發(fā)出的符號是互相依賴的定理3.4說明:信道的有記憶性降低了條件熵H(XN|YN);有記憶信道:輸出符號不但與對應時刻的輸入符號有關(guān),還與以前時刻輸入及輸出符號有關(guān)第70頁，共99頁，2023年，2月20日，星期三2023/4/370無記憶的N次擴展信道的平均互信息若信源和信道都是無記憶的,即定理3.3和3.4同時成立,那么等式成立,即

若同時滿足:1)Xi取自同一概率空間(相同符號集及概率分布);2)相同的信道(信道轉(zhuǎn)移概率矩陣)則有:第71頁，共99頁，2023年，2月20日，星期三2023/4/371無記憶的N次擴展信道的平均互信息對于無擾一一對應(無噪)信道(H(X|Y)=0),接收到的平均互信息就是輸入信源的熵,定理3.3同時說明

第72頁，共99頁，2023年，2月20日，星期三2023/4/372第三章離散信道3.1信道的數(shù)學模型及分類3.2信道疑義度及平均互信息3.3平均互信息的特性3.4離散無記憶的擴展信道3.5信道容量及特殊信道的容量計算3.6信源與信道的匹配第73頁，共99頁，2023年，2月20日，星期三2023/4/373信道的信息傳輸率R信道研究的目的:討論信道中平均每個符號所能傳送的信息量,即信道的信息傳輸率R.信道的信息傳輸率R就是平均互信息,這是因為平均互信息I(X;Y)就是接收到符號Y后平均每個符號獲得的關(guān)于X的信息量.因此R=I(X;Y)=H(X)-H(X|Y)比特/符號第74頁，共99頁，2023年，2月20日，星期三2023/4/374信道容量C定義:最大的信息傳輸率,即

其相應的輸入概率分布稱為最佳輸入分布.這是因為在信道固定時,I(X;Y)是輸入變量X的概率分布p(x)的∩型凸函數(shù)(見定理3.1).可知:信道容量C與信源概率分布無關(guān),它只是信道傳輸概率的函數(shù),只與信道統(tǒng)計特性有關(guān).所以,信道容量是完全描述信道特性的參量,是信道能夠傳輸?shù)淖畲笮畔⒘?第75頁，共99頁，2023年，2月20日，星期三2023/4/375單位時間內(nèi)的R和C有時關(guān)心的是信道在單位時間內(nèi)平均傳輸?shù)男畔⒘?信息傳輸速率Rt:信道每秒鐘傳輸?shù)男畔⒘?若平均傳輸一個符號需要t秒),即同理,可得單位時間內(nèi)平均傳輸?shù)淖畲笮畔⒘康?6頁，共99頁，2023年，2月20日，星期三2023/4/3763.5.1離散無噪信道從數(shù)學上說,信道容量計算就是對互信息I(X;Y)求極大值的問題.對于一般信道,信道容量的計算相當復雜.下面僅討論某些特殊類型的信道容量計算問題.第77頁，共99頁，2023年，2月20日，星期三2023/4/3771、無噪無損信道

輸入和輸出符號之間有確定的一一對應關(guān)系,即信道矩陣是單位矩陣H(X|Y)=0,H(Y|X)=0I(X;Y)=H(X)=H(Y)第78頁，共99頁，2023年，2月20日，星期三2023/4/3782、有噪無損信道輸入符號通過傳輸變成若干輸出符號,雖然不是一一對應關(guān)系,但這些輸出符號仍可分成互不相交的一些集合.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)第79頁，共99頁，2023年，2月20日，星期三2023/4/3793、無噪有損信道前向概率p(y|x)等于0或1,即輸出Y是輸入X的確定函數(shù);但不是一一對應,而是多一對應關(guān)系.因而,后向概率p(x|y)不等于0或1.H(X|Y)≠0,H(Y|X)=0.I(X;Y)=H(Y)<H(X)第80頁，共99頁，2023年，2月20日，星期三2023/4/380平均互信息與損失熵、噪聲熵、信源熵的關(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)第81頁，共99頁，2023年，2月20日，星期三2023/4/381無損及無噪信道容量1、對于無損信道,其信息傳輸率R是輸入信源X輸出每個符號攜帶的信息量,即信源熵H(X),所以

式中輸入信源X有r個符號,等概分布時H(X)最大.2、對于無噪信道,信道容量為

其中輸出信源Y有s個符號,等概分布時H(Y)最大.而且一定能找到一種輸入分布使輸出符號Y達到等概分布.第82頁，共99頁，2023年，2月20日，星期三2023/4/382第83頁，共99頁，2023年，2月20日，星期三2023/4/3833.5.2對稱離散信道對稱性:1)信道矩陣中每一行都是由{p1’,p2’,…,ps’}集的諸元素不同排列組成,2)每一列也都是由{q1’,q2’,…,qr’}集的諸元素不同排列組成.當r=s,{pi’}集和{qi’}集相同;若r<s,{qi’}集應是{pi’}集的子集.√×第84頁，共99頁，2023年，2月20日，星期三2023/4/384均勻信道(或強對稱信道)對稱離散信道的一類特例輸入和輸出符號個數(shù)相同,等于r總的錯誤概率為p,對稱地平均分配給r-1個輸出符號信道矩陣中各列之和也等于1二元對稱信道就是r=2的均勻信道第85頁，共99頁，2023年，2月20日，星期三2023/4/385對稱離散信道的平均互信息

其中

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

因此可得第86頁，共99頁，2023年，2月20日，星期三2023/4/386對稱離散信道的容量即求一種輸入分布p(x)使H(Y)取最大值的問題了。現(xiàn)已知輸出Y的符號集共有s個符號，則H(Y)≤logs;H(Y)達到最大值條件:只有當p(y)=1/s(等概分布).對稱離散信道下p(y)等概分布條件:輸入是等概分布.第87頁，共99頁，2023年，2月20日，星期三2023/4/3873.5.3一般離散信道信道容量的定義:在固定信道的條件下,對所有可能的輸入概率分布p(x)求平均互信息的條件(概率和歸“1”)極大值.極值性存在條件:I(X;Y)是輸入概率分布p(x)(即r個變量{p(a1),…,p(ar)})的多元∩型凸函數(shù),所以極大值一定存在.第88頁，共99頁，2023年，2月20日，星期三2023/4/3883.5.3一般離散信道求條件極值方法:拉格朗日乘子法.

引進一個新函數(shù) 其中λ為拉格朗日乘子(