第五章離散信道及其編碼定理

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

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

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

{X

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

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

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

式中假設(shè)輸入信源X的符號(hào)共有n個(gè)，所以等概率分布時(shí)信源熵最大。38對(duì)于無(wú)噪信道，其信道容量為

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

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

實(shí)現(xiàn)準(zhǔn)對(duì)稱DMC信道容量的最佳輸入分布為等概分布YS：子陣中每一列都是第一列置換對(duì)每個(gè)j相同對(duì)每個(gè)k相同值與k無(wú)關(guān)46對(duì)稱DMC容量的計(jì)算結(jié)論

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

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

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

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

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

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