1第5章離散信道及信道編碼定理5.1信道分類5.2離散無記憶信道5.3信道編碼和譯碼5.4信道編碼定理5.5信道編碼定理的應用5.6信道的組合2通信系統(tǒng)的模型細分信源信源編碼器糾錯編碼器調制器信道干擾源解調器糾錯譯碼器信源譯碼器信宿等效離散信道等效離散信源等效信宿信道編碼器信道譯碼器3通信系統(tǒng)模型信道編碼：從消息到信道波形或矢量的映射

信道編碼的作用：在資源、可靠性和傳信量之間選擇一個好的工作點（有時還要考慮延時）4什么是信道？信道——信號所通過的通道。信息是抽象的，信道則是具體的。比如：二人對話，二人間的空氣就是信道；打電話，電話線就是信道；看電視，聽收音機，收、發(fā)間的空間就是信道。5信道的作用

在通信系統(tǒng)中信道主要用于傳輸。研究信道的目的在通信系統(tǒng)中研究信道，主要是為了描述、度量、分析不同類型信道，計算其容量，即極限傳輸能力，并分析其特性。6信道概述轉移概率P(y|x)描述發(fā)送變量和接收變量之間的關系。75.1信道分類離散信道：輸入輸出均為離散事件集連續(xù)信道：輸入輸出空間均為連續(xù)事件集半連續(xù)信道：輸入和輸出一個是離散的，一個是連續(xù)的時間離散的連續(xù)信道：信道輸入和輸出是連續(xù)的時間序列波形信道：輸入和輸出都是時間的實函數(shù)x(t),y(t)根據(jù)輸入輸出空間的連續(xù)性劃分8信道分類兩端信道：兩用戶多端信道：多用戶平穩(wěn)(恒參)信道：參數(shù)不隨時間變化非平穩(wěn)(隨參)信道：參數(shù)隨時間變化無記憶信道和有記憶信道對稱信道和非對稱信道根據(jù)輸入輸出集合的個數(shù)、對稱性劃分9一般信道的數(shù)學模型①信道的輸入輸出關系②一般信道的數(shù)學模型10①信道的輸入輸出關系信號在信道中傳輸會引入噪聲或干擾，它使信號通過信道后產(chǎn)生錯誤和失真；信道的輸入和輸出之間一般不是確定的函數(shù)關系，而是統(tǒng)計依賴關系；知道了信道的輸入信號、輸出信號以及它們之間的依賴關系，信道的全部特性就確定了。11②一般信道的數(shù)學模型數(shù)學模型的數(shù)學符號表示

{X

P(Y/X)Y}輸入和輸出信號總可以分解成隨機序列來研究。隨機序列中每個隨機變量的取值可以是可數(shù)的離散值，也可以是不可數(shù)的連續(xù)值。12第5章離散信道及信道編碼定理5.1信道分類5.2離散無記憶信道5.3信道編碼和譯碼5.4信道編碼定理5.5信道編碼定理的應用5.6信道的組合135.2離散無記憶信道離散無記憶信道定義(DMC)DMC的信道容量對稱DMC的信道容量計算一般DMC的信道容量計算14離散無記憶信道定義Def.設(1)信道的輸入輸出空間X={0,1,…,K-1},Y={0,1,…,J-1}.(2)信道的輸入輸出序列為x=(x1,x2,…,xN),y=(y1,y2,…,yN)時間序列(3)信道的條件或轉移概率為P(y|x)=P(y1,y2,…,yN|x1,x2,…,xN)。15離散無記憶信道定義則稱該信道為離散無記憶信道。（DMC）則稱該信道為離散無記憶平穩(wěn)信道。

16離散無記憶信道定義“離散”的含義是時間離散，事件離散。即：信道的輸入、輸出時刻是離散的，且輸入隨機變量和輸出隨機變量都是離散型的隨機變量。“無記憶”的含義是信道響應沒有時間延遲，當時的輸出只依賴于當時的輸入。“平穩(wěn)”的含義是信道在不同時刻的響應特性是相同的。17離散無記憶信道定義“離散無記憶平穩(wěn)信道”是最簡單的信道，信道在某一時刻u的響應特性P(yn=j|xn=k)；就能很簡單地計算出信道在任意時間段的響應特性。18二元對稱信道,BSC設p=0.1給定一離散無記憶平穩(wěn)信道1-p1-ppp110019有關DMC的容量定理一、有關DMC的容量定理（所說的DMC都是離散無記憶平穩(wěn)信道）設DMC在某個時刻輸入隨機變量為X，輸出隨機變量為Y。信道響應特性為轉移概率矩陣[p(y|x)，x∈{0,1,…,K-1}，y∈{0,1,…,J-1}]，它是一個K×J階矩陣（其中p(y|x)=P(Y=y|X=x)）。X的概率分布為{x,q(x),x∈{0,1,…,K-1}}。Y的概率分布為{y,w(y),y∈{0,1,…,J-1}}。我們有以下的結論：20有關DMC的容量定理（1）轉移概率矩陣的每一行都是一個概率向量。21有關DMC的容量定理（2）對任意y∈{0,1,…,J-1}，由全概率公式有。22有關DMC的容量定理（3）I(X;Y)是概率向量{q(x),x∈{0,1,…,K-1}}和轉移概率矩陣[p(y|x)，x∈{0,1,…,K-1}，y∈{0,1,…,J-1}]的函數(shù)23平均互信息量的凸性互信息是輸入分布函數(shù)（輸入概率密度）和條件概率分布（條件概率密度）的函數(shù)。24平均互信息量的凸性Th.平均互信息量I(X;Y)是輸入信源概率分布pX(x)的上凸函數(shù)。物理含義.當信道給定時，即條件概率p(y/x)給定下，I(X;Y)為輸入概率分布的凸函數(shù)就保證了使傳送信息量I(X;Y)為最大的最佳輸入分布的存在。（信道容量的討論）25有關DMC的容量定理（4）設轉移概率矩陣[p(y|x)，x∈{0,1,…,K-1}，y∈{0,1,…,J-1}]確定，希望選擇概率向量{q(x),x∈{0,1,…,K-1}}使I(X;Y)達到最大。定義離散無記憶信道的信道容量定義為如下的C。達到信道容量的輸入概率分布{x,q(x),x∈{0,1,…,K-1}}稱為最佳輸入分布。其中26定理5.2.1定理令Q(x)是DMC的N長輸入字母序列的聯(lián)合分布，XN和YN分別表示長為N的輸入輸出序列集合，Xn,Yn表示第n個輸入和輸出，有定理說明對于DMC，N長序列的信息傳輸問題可以歸結為單符號的信息傳輸問題27定理5.2.2Q={Q0,Q1,…,QK-1}達到信道容量的充要條件

給定輸入分布，若某個輸入k與所有輸出的平均互信息量最大，就可以加大Qk來增加I(X;Y).不斷調整輸入可以使I(k;Y)任意接近。28定理5.2.2解釋給定一個DMC信道的響應特性，也就是說給定一個信道的轉移概率矩陣[p(y|x)，x∈{0,1,…,K-1}，y∈{0,1,…,J-1}]，達到信道容量時所對應的最佳輸入分布是滿足定理5.2.2條件的概率向量{q(x),x∈{0,1,…,K-1}}。其信道容量是每個使得q(k)>0的k所對應的半平均互信息量I(X=k;Y)。29特殊信道的信道容量①具有一一對應關系的無噪信道②具有擴展性能的無損信道③具有歸并性能的無噪信道④準對稱信道⑤對稱信道30①具有一一對應關系的無噪信道31X和Y有確定的對應關系：已知X后Y沒有不確定性，噪聲熵H(Y/X)=0；收到Y后，X也不存在不確定性，損失熵H(X/Y)=0;故有I(X;Y)=H(X)=H(Y)。接收到符號Y后，平均獲得的信息量就是信源發(fā)出每個符號所含有的平均信息量，信道中無信息損失，而且噪聲熵也等于零，輸出端Y的不確定性沒有增加。嚴格地講，這種輸入輸出有確定的一一對應關系的信道，應稱為無噪無損信道。當信源呈等概率分布時，具有一一對應確定關系的無噪信道達到信道容量32②具有擴展性能的無損信道n<m，輸入X的符號集個數(shù)小于輸出Y的符號集個數(shù)。33每列中只有一個非零元素：已知Y后，X不再有任何不確定度，損失熵H(X/Y)=0，I(X;Y)=H(X)-H(X/Y)=H(X)。接收到符號Y后，對發(fā)送的符號X是完全確定的，損失熵為零，但噪聲熵H(Y/X)不為零。這類信道被稱為有噪無損信道。信道容量為與一一對應信道不同的是，此時輸入端符號熵小于輸出端符號熵，H(X)<H(Y)。34③具有歸并性能的無噪信道n>m，輸入X的符號集個數(shù)大于輸出Y的符號集個數(shù)。35每行僅有一個非零元素，但每列的非零元素個數(shù)大于1：已知某一個xi后，對應的yj完全確定，信道噪聲熵H(Y/X)=0。但是收到某一個yj后，對應的xi不完全確定，信道損失熵H(X/Y)≠0。在這類信道中，接受到符號Y后不能完全消除對X的不確定性，信息有損失。但輸出端Y的平均不確定性因噪聲熵等于零而沒有增加，所以這類信道稱為無噪有損信道也稱確定信道。36每行僅有一個非零元素，但每列的非零元素個數(shù)大于1：信道容量為這種信道輸入端符號熵大于輸出端符號熵，H(X)>H(Y)。注意：在求信道容量時，調整的始終是輸入端的概率分布p(xi)，盡管信道容量式子中平均互信息I(X;Y)等于輸出端符號熵H(Y)，但是在求極大值時調整的仍然是輸入端的概率分布p(xi)，而不能用輸出端的概率分布p(yj)來代替。37綜合上述三種情況，若嚴格區(qū)分的話，凡損失熵等于零的信道稱為無損信道；凡噪聲熵等于零的信道稱為無噪信道，而一一對應的無噪信道則為無噪無損信道。對于無損信道，其信息傳輸率R就是輸入信源X輸出每個符號攜帶的信息量(信源熵H(X))，因此其信道容量為

式中假設輸入信源X的符號共有n個，所以等概率分布時信源熵最大。38對于無噪信道，其信道容量為

式中假設輸出信源Y的符號共有m個，等概率分布時H(Y)最大,而且一定能找到一種輸入分布使得輸出符號Y達到等概率分布。可見這些信道的信道容量C只決定于信道的輸入符號數(shù)n，或輸出符號數(shù)m，與信源無關。39對稱DMC容量的計算定義

設DMC的轉移概率矩陣為若P的任一行是第一行的置換，則稱信道關于輸入為對稱的。若P的任一列是第一列的置換，則稱信道關于輸出為對稱的。40對稱DMC容量的計算若P所有行矢量都是第一行的置換，稱為關于輸入對稱。由于{p(y|x)，y=0~J-1}與{p(y|k)，y=0~J-1}互為置換41對稱DMC容量的計算P的所有列都是第一列的一種置換，關于輸出是對稱的當輸入事件等概，Qk=1/K此時{p(y|x)，x=0~K-1}與{p(0|x)，x=0~K-1}互為置換。42對稱DMC的容量計算輸出集Y可劃為若干個子集,每個子集對應的信道轉移概率矩陣P中列所組成的子陣具有下列性質每一行都是第一行的置換每一列都是第一列的置換該信道稱為準對稱信道準對稱信道關于輸入對稱。Y的劃分只有一個時，關于輸入輸出均對稱稱為對稱信道43對稱DMC的容量計算幾個簡單的結論：（1）準對稱信道一定是關于輸入為對稱的。（2）對稱信道關于輸入和輸出都對稱。（3）對稱DMC當輸入分布等概時，輸出分布等概。（4）準對稱DMC當輸入分布等概時，輸出分布局部等概。（準對稱DMC當輸入分布等概時，若j和l屬于轉移概率矩陣的同一個列子集，則wj=wl。）（5）對稱信道未必有J=K。44對稱DMC的容量計算準對稱信道對稱信道45準對稱DMC容量的計算定理

實現(xiàn)準對稱DMC信道容量的最佳輸入分布為等概分布YS：子陣中每一列都是第一列置換對每個j相同對每個k相同值與k無關46對稱DMC容量的計算結論

實現(xiàn)對稱DMC信道容量的輸入分布為等概分布關于輸入對稱的47K元對稱信道容量計算例：K元對稱信道容量計算K=2,C=1-H(p)48準對稱信道容量計算例：二元對稱刪除信道（準對稱信道）C=1-q（二元純刪除信道）49一般DMC的容量計算一般DMC的信道容量與最佳輸入分布的計算

若DMC的轉移概率矩陣P是可逆方陣（此時K=J，非奇異）。則可以先假設最佳輸入分布{q(x),x∈{0,1,…,K-1}}中每個概率q(x)都滿足q(x)>0。在這個假設下，求出信道容量C；然后求出最佳輸入分布對應的“最佳輸出分布”{w(y),y∈{0,1,…,K-1}}；然后求出最佳輸入分布{q(x),x∈{0,1,…,K-1}}。50一般DMC的容量計算此時，51一般DMC的容量計算這是K個未知量{β0,β1,…,βK-1}={C+logw(0),C+logw(1),…,C+logw(K-1)}的線性方程組，系數(shù)矩陣是可逆方陣，因此唯一解出{β0,β1,…,βK-1}52一般DMC的容量計算另一個等式：

w(0)+w(1)+…+w(K-1)=1。于是βi=C+logw(i)53一般離散信道容量計算步驟54一般DMC的容量計算例子例設DMC的輸入事件為{0,1}，輸出事件為{0,1}，轉移概率矩陣為求信道容量和最佳輸入分布。先假設最佳輸入分布{q(0),q(1)}滿足q(0)>0，q(1)>0。因此55一般DMC的容量計算例子因此56第5章離散信道及信道編碼定理5.1信道分類5.2離散無記憶信道5.3信道編碼和譯碼5.4信道編碼定理5.5信道編碼定理的應用57信道編碼最簡單的檢錯和糾錯單個的字無法檢錯：捫→？詞匯能夠檢錯：我捫的→我捫的詞匯能夠糾錯：我捫的→我們的，我等的，我輩的，我班的，…原因分析：“捫→？”可以有幾百個答案，但“我捫的→？”的答案卻很少。結論：課文以及詞匯的概率分布的稀疏性可以用來檢錯和糾錯。58信道編碼K信息比特N編碼比特編碼器(n0,k0)卷積碼(Convolutionalcodes)：m個分組相關，約束長度為K=(m+1)k0編碼速率(N,K)分組碼(Blockcodes)：分組之間獨立編碼速率卷積編碼示意59譯碼準則信息序列個數(shù)：可能的N長二元序列個數(shù)：編碼：K長信息序列到N長二元序列空間的映射K長二元序列空間N長二元序列空間60譯碼準則接收矢量：碼字：信道譯碼編碼61譯碼準則譯碼錯誤概率（誤組率）對特定接收序列y的譯碼錯誤概率誤比特率Biterrorrate第k位出錯的概率62譯碼準則最小錯誤概率準則使最小最大后驗概率準則最大后驗概率準則計算后驗概率是困難的，通常針對具體信道（轉移概率已知），采用最大似然準則63離散序列譯碼根據(jù)貝葉斯公式若要求等價于64離散序列譯碼若消息序列先驗概率相等得最大似然準則最大后驗準則65離散序列譯碼譯碼是由YN到UL的映射，將YN劃分為M個不相交子集x1x2xMYNY1Y2YM是Ym的補集若消息m的先驗概率為Q(m),則平均譯碼錯誤概率為66離散序列譯碼最大后驗概率譯碼最大似然譯碼所有消息等概q元對稱信道最小漢明距離譯碼漢明距離：兩個碼字U、V之間對應碼元位上符號取值不同的個數(shù)，稱為碼字U、V之間的漢明距離。例如：兩個碼字U=0011101,V=0100111，它們之間第2、3、4和6位不同。因此，碼字U和V的距離為4。67離散序列譯碼對兩種譯碼準則的評述最大后驗概率準則具有很好的直觀合理性。收到y(tǒng)的條件下，最可能發(fā)送的是哪個碼字，就認為發(fā)送的是哪個碼字”。最大似然概率準則（最小距離準則）所具有的直觀合理性弱一些。發(fā)送哪個碼字的條件下，最可能收到y(tǒng)，就認為發(fā)送的是哪個碼字。68離散序列譯碼對兩種譯碼準則的評述最大似然概率準則（最小距離準則）的實現(xiàn)比最大后驗概率準則的實現(xiàn)更簡單：

前者只需要看哪個碼字與y的Hamming距離最小；后者需要知道各碼字的概率分布，然后用貝葉斯公式計算并比較后驗概率。69離散序列譯碼例

兩個消息等概，x1=0000，x2=1111，通過二元對稱信道，轉移概率p譯碼規(guī)則如下：當(Y1Y2Y3Y4)中1的個數(shù)為0或1時，(Y1Y2Y3Y4)→(0000)→0；當(Y1Y2Y3Y4)中1的個數(shù)為3或4時，(Y1Y2Y3Y4)→(1111)→1；當(Y1Y2Y3Y4)中1的個數(shù)為2時，(0011)、(1100)、(1001)→(0000)→0，(0101)、(1010)、(0110)→(1111)→1。譯碼規(guī)則顯然是最小距離準則。70離散序列譯碼譯碼規(guī)則是最小距離準則。何時檢測到信道傳輸錯誤？當(Y1Y2Y3Y4)不是一個碼字時，檢測到信道傳輸錯誤。換句話說，(Y1Y2Y3Y4)與原發(fā)碼字(U1U2U3U4)的Hamming距離≥1且≤3時，檢測到信道傳輸錯誤。因此，信道傳輸有錯誤但能檢測出錯誤的概率為71離散序列譯碼何時正確譯碼（正確接收）？當(Y1Y2Y3Y4)與原發(fā)碼字(U1U2U3U4)的Hamming距離≤1時，正確譯碼；當(Y1Y2Y3Y4)與原發(fā)碼字(U1U2U3U4)的Hamming距離=2時，一半能正確譯碼，另一半不能正確譯碼；當(Y1Y2Y3Y4)與原發(fā)碼字(U1U2U3U4)的Hamming距離≥3時，不能正確譯碼。正確譯碼（正確接收）的概率為72第5章離散信道及信道編碼定理5.1信道分類5.2離散無記憶信道5.3信道編碼和譯碼5.4信道編碼定理5.5信道編碼定理的應用73信道編碼定理DMCP(y|x)令編碼速率為R，則各碼字的標號集為[1,2NR]。編碼函數(shù)譯碼函數(shù)74信道編碼定理發(fā)送消息

平均誤組率發(fā)送m的誤組率對給定離散無記憶信道和任意e>0，若有一種編碼速率為R的碼，在N足夠大時，能使pe<e，就稱R是可達的。75信道編碼定理（Shannon第二定理）定理(Shannon信道編碼定理)，給定容量為C的離散無記憶信道{X，p(x|y)，Y}，若編碼速率R<C，則R是可達的。存在性定理，從理論上證明，平均錯誤譯碼概率趨于0、信道信息傳輸速率R無限接近于信道容量C的抗干擾信道編碼是存在的。76第5章離散信道及信道編碼定理5.