信息論基礎(chǔ)——離散無記憶信道 信道容量
會計學(xué)1信息論基礎(chǔ)信息論基礎(chǔ)離散無記憶信道離散無記憶信道 信道容信道容量量2數(shù)據(jù)可靠傳輸和信數(shù)據(jù)可靠傳輸和信道編碼道編碼4.1 離散無記憶信道和信道離散無記憶信道和信道容量容量 4.2 信道容量的計算信道容量的計算 4.3 信道編碼理論信道編碼理論 4.4 帶反饋的信道模型帶反饋的信道模型4.5 聯(lián)合信源聯(lián)合信源-信道編碼定理信道編碼定理4.6 線性分組碼線性分組碼習(xí)題四習(xí)題四第1頁/共23頁3數(shù)據(jù)可靠傳輸和信數(shù)據(jù)可靠傳輸和信道編碼道編碼4.1 離散無記憶信道和信道容量 4.2 信道容量的計算信道容量的計算 4.3 信道編碼理論信道編碼理論 4.4 帶反饋的信道模型帶反饋的信道模型4.5 聯(lián)合信源聯(lián)合信源-信道編碼定理信道編碼定理4.6 線性分組碼線性分組碼習(xí)題四習(xí)題四第2頁/共23頁4離散無記憶信道和信道容量離散無記憶信道和信道容量 為確定信道傳輸?shù)南薅?,就要考慮信道傳遞信息的基本單元信號.信號無論采用光、聲、電還是其他形式都是一種物理過程.每個信號都需要一定的時間.在烽火臺上點燃烽火也許要花好幾分鐘,現(xiàn)代極高頻無線電通信傳遞信號所需要的時間還不到億分之一秒.盡管如此,總要有一定的時間間隔才能把信號與信號分離開來.超過時間間隔的一定限度,信號就會無法分辨:典型的例子就是一個人說話過分快,聽的人根本聽不懂他在說什么.因此,要使一個信道能夠起到傳遞信息的功能,每分鐘傳遞的信號數(shù)目就要有一定的限度.第3頁/共23頁5離散無記憶信道和信道容量離散無記憶信道和信道容量 這點是比較容易理解的.再比如,我們規(guī)定公共汽車必須一輛接一輛地開來,每輛汽車必須在車站停一分鐘,以便乘客上下.那么不管增加多少車輛,也不會越過每分鐘一輛的速率.既然如此,要想提高運輸量,途徑就是增加每輛汽車的裝載量.那么能否提高每個信號所攜帶的信息量呢?信息量的定義告訴我們,一個事件發(fā)小的概率越小,告訴我們這件事是否發(fā)生的信號帶來的信息量越大.進而增大每個信號信息量的辦法是增加不同信號的數(shù)目.第4頁/共23頁6離散無記憶信道和信道容量離散無記憶信道和信道容量 但是,對于任何給定的信道來講,可以分辨的信號數(shù)目 (這和前面所講的以時間間隔分辨信號是不同的概念)是有限的.例如對于電報來講,不同的信號只有點和劃;對于電話來講,可以分辨的音素也是有限的.即使在沒有噪聲干擾的情況下(每輛公共汽車可以載滿乘客,不必擔(dān)心中途會發(fā)少什么意外),信道在單位時間內(nèi)只能準(zhǔn)確地傳遞有限的信號,而每個信號所攜帶的信息量又是有限的,因此信道在單位時間內(nèi)傳遞的信息量也是有限的.該限度就稱為信道容量信道容量信道容量限制了通信系統(tǒng)的能力!信道容量限制了通信系統(tǒng)的能力!第5頁/共23頁7離散無記憶信道離散無記憶信道提高傳輸?shù)目煽啃?!?頁/共23頁8信道的分類:信道的分類:根據(jù)信道用戶的多少根據(jù)信道用戶的多少,可分為:(1)單用戶信道:只有一個輸入端和一個輸出端(2)多用戶信道(廣播、電視、衛(wèi)星、計算機網(wǎng))廣播、電視、衛(wèi)星、計算機網(wǎng))至少有一端有兩個以上的用戶,雙向通信離散無記憶信道離散無記憶信道第7頁/共23頁9根據(jù)符號的概率分布根據(jù)符號的概率分布根據(jù)符號的概率分布根據(jù)符號的概率分布,可分為可分為(1 1)有記憶信道)有記憶信道(2 2)無記憶信道)無記憶信道 (任一時刻輸出符號只統(tǒng)計依賴于對應(yīng)時刻輸入符號的(任一時刻輸出符號只統(tǒng)計依賴于對應(yīng)時刻輸入符號的 信道)信道)離散無記憶信道離散無記憶信道第8頁/共23頁10根據(jù)輸入輸出信號的特點,根據(jù)輸入輸出信號的特點,可分為 (1)離散信道 輸入集和輸出集都是離散集:電報信道和數(shù)據(jù)信道 (2)連續(xù)信道電視和電話信道 (3)半離散半連續(xù)信道輸入集和輸出集中一個是連續(xù)集、另一個是離散集:連續(xù)信道加上數(shù)字調(diào)制器或數(shù)字解調(diào)器 (4)波形信道以下我們只研究單用戶離散無記憶信道以下我們只研究單用戶離散無記憶信道。離散無記憶信道離散無記憶信道數(shù)字信道以數(shù)字脈沖形式(離散信號)傳輸數(shù)據(jù) 第9頁/共23頁11滿足離散無記憶信道的充要條件是其中,輸入符號集其中,輸入符號集其中,輸入符號集其中,輸入符號集 X X=x x1 1,x x2 2,x xN N 輸出符號集輸出符號集輸出符號集輸出符號集 Y Y=y=y1 1,y y2 2,y,yN N 離散無記憶信道離散無記憶信道第10頁/共23頁12信道轉(zhuǎn)移概率分布的矩陣形式:離散無記憶信道離散無記憶信道信道轉(zhuǎn)移概率信道轉(zhuǎn)移概率第11頁/共23頁13信道轉(zhuǎn)移概率分布的圖示:離散無記憶信道離散無記憶信道第12頁/共23頁14 信道的任務(wù)是以信號方式傳輸信息和存儲信信道的任務(wù)是以信號方式傳輸信息和存儲信息;因此,研究信道就是研究信道中能夠傳送或息;因此,研究信道就是研究信道中能夠傳送或存儲的最大信息量,即信息無差錯傳輸?shù)淖畲笏俅鎯Φ淖畲笮畔⒘?,即信息無差錯傳輸?shù)淖畲笏俾事?,就是信道容量問題,就是信道容量問題.因此,首先要考慮信道中平均每個符號能傳因此,首先要考慮信道中平均每個符號能傳輸?shù)男畔⒘枯數(shù)男畔⒘科骄バ畔⑵骄バ畔?區(qū)分:帶寬與信道容量區(qū)分:帶寬與信道容量 信道容量信道容量第13頁/共23頁15帶寬帶寬:信道可以不失真地傳輸信號的頻率范圍。為不同應(yīng)用而設(shè)計的信道可以不失真地傳輸信號的頻率范圍。為不同應(yīng)用而設(shè)計的傳輸媒體所支持的帶寬有所不同;在現(xiàn)代網(wǎng)絡(luò)技術(shù)中,傳輸媒體所支持的帶寬有所不同;在現(xiàn)代網(wǎng)絡(luò)技術(shù)中,“帶寬帶寬”表表示示信道的數(shù)據(jù)傳輸速率信道的數(shù)據(jù)傳輸速率.信道容量信道容量:信道在單位時間內(nèi)可以傳輸?shù)淖畲笮盘柫?,表示信道的傳信道在單位時間內(nèi)可以傳輸?shù)淖畲笮盘柫浚硎拘诺赖膫鬏斈芰?。信道容量有時也表示為單位時間內(nèi)可傳輸?shù)亩M制位的位輸能力。信道容量有時也表示為單位時間內(nèi)可傳輸?shù)亩M制位的位數(shù)(稱信道的數(shù)據(jù)傳輸速率,位速率),以位數(shù)(稱信道的數(shù)據(jù)傳輸速率,位速率),以位/秒(秒(b/sb/s)形式予以表)形式予以表示,簡記為示,簡記為bpsbps。信道容量和信道帶寬具有正比的關(guān)系:帶寬越大,容量越大。信道容量和信道帶寬具有正比的關(guān)系:帶寬越大,容量越大。局域網(wǎng)帶寬(傳輸速率):局域網(wǎng)帶寬(傳輸速率):10Mbps10Mbps、100Mbps100Mbps、1000Mbps1000Mbps;廣域網(wǎng)帶寬(傳輸速率):廣域網(wǎng)帶寬(傳輸速率):64Kbps64Kbps、2Mbps2Mbps、155Mbps155Mbps等等 信道容量信道容量第14頁/共23頁16 由于 I(X,Y)=H(X)-H(X|Y)bit/符號是輸入隨機變量X的概率分布p(x)的上凸函數(shù),因此對于一個確定信道,總存在一個信源(某種概率分布p0(x)),使得傳輸每個符號平均獲得的信息量最大,即每個固定信道都有一個最大的信息傳輸率,定義這個最大值為信道容量C.離散無記憶信道和信道容量離散無記憶信道和信道容量第15頁/共23頁17 離散無記憶信道和信道容量離散無記憶信道和信道容量第16頁/共23頁18通常,P(xi i)稱為信道的入口分布P(yi i)稱為信道的出口分布i(x;y)=logP(x,y)/P(x)P(y)為入口與出口信號的互信息密度函數(shù)p0 0(x)為最大入口分布。其中,輸入符號集其中,輸入符號集其中,輸入符號集其中,輸入符號集 X X=x x1 1,x x2 2,x xN N 輸出符號集輸出符號集輸出符號集輸出符號集 Y Y=y=y1 1,y y2 2,y,yN N 離散無記憶信道和信道容量離散無記憶信道和信道容量第17頁/共23頁19注:注:1 1)C C與輸入信源的概率分布無關(guān),它只是信道傳輸與輸入信源的概率分布無關(guān),它只是信道傳輸與輸入信源的概率分布無關(guān),它只是信道傳輸與輸入信源的概率分布無關(guān),它只是信道傳輸概概概概率的函數(shù),只與信道的統(tǒng)計特性有關(guān)率的函數(shù),只與信道的統(tǒng)計特性有關(guān)率的函數(shù),只與信道的統(tǒng)計特性有關(guān)率的函數(shù),只與信道的統(tǒng)計特性有關(guān).是完全描述信道是完全描述信道是完全描述信道是完全描述信道特性的參數(shù),是信道能夠傳輸?shù)淖畲笮畔⒘?;特性的參?shù),是信道能夠傳輸?shù)淖畲笮畔⒘?;特性的參?shù),是信道能夠傳輸?shù)淖畲笮畔⒘浚惶匦缘膮?shù),是信道能夠傳輸?shù)淖畲笮畔⒘浚? 2)從數(shù)學(xué)上來說,計算)從數(shù)學(xué)上來說,計算)從數(shù)學(xué)上來說,計算)從數(shù)學(xué)上來說,計算C C就是求就是求就是求就是求I I(X X;Y Y)的最大值;的最大值;的最大值;的最大值;但但但但是,對于一般信道計算相當(dāng)復(fù)雜是,對于一般信道計算相當(dāng)復(fù)雜是,對于一般信道計算相當(dāng)復(fù)雜是,對于一般信道計算相當(dāng)復(fù)雜.這里我們只討論幾種這里我們只討論幾種這里我們只討論幾種這里我們只討論幾種典型的無記憶信道的典型的無記憶信道的典型的無記憶信道的典型的無記憶信道的C C的計算的計算的計算的計算.離散無記憶信道和信道容量離散無記憶信道和信道容量第18頁/共23頁20 如果一個離散信道的信道轉(zhuǎn)移矩陣中的每一行都是由同一組元素的不同組合構(gòu)成的,并且每一列也是由這一組元素組成的,則稱為對稱信道;如:和2.1 2.1 二進對稱信道(二進對稱信道(BSCBSC)離散無記憶信道和信道容量離散無記憶信道和信道容量第19頁/共23頁21 X=0,1;Y=0,1;p(0/0)=p(1/1)=1-p;p(0/1)=p(1/0)=p;P=0101-pp1p1-p 0 1-p 0 p p 1 1-p 1p稱為交叉概率誤差!離散無記憶信道和信道容量離散無記憶信道和信道容量第20頁/共23頁22如果信道的輸入概率分布X=w,1-w,則 由此可得離散無記憶信道和信道容量離散無記憶信道和信道容量第21頁/共23頁23平均互信息對存在一個極大值,即當(dāng)時,有極大值,從而BSC的信道容量最大入口分布:離散無記憶信道和信道容量離散無記憶信道和信道容量第22頁/共23頁