信道編碼定理

信道編碼定理錯(cuò)誤概率譯碼準(zhǔn)則信道編碼定理1噪聲信道的編碼問(wèn)題在二進(jìn)制數(shù)字通信系統(tǒng)中，編碼器的編碼過(guò)程分為兩步：信源編碼：把信源的消息數(shù)據(jù)序列編成二進(jìn)制數(shù)字構(gòu)成的碼序列；信道編碼：把二進(jìn)制數(shù)據(jù)序列編成具有糾檢錯(cuò)能力的二進(jìn)制序列。由于信源編碼在構(gòu)造上并未考慮抗干擾，如果把信源編碼器的輸出直接接入信道，由于信道中存在噪聲干擾，將引起誤碼，降低通信可靠性。因此提出了以提高通信可靠性為主要目的的信道編碼，它是對(duì)信源編碼器輸出的最佳碼再進(jìn)行一次編碼，以提高其抗干擾能力的一種編碼形式。2信道編譯碼的理論基礎(chǔ)信道的特征是由信道傳遞概率p(Y|X)來(lái)描述的。由p(Y|X)可以算出信道容量C，只要在信道中實(shí)際傳送的信息率R’<C，在接收端就能夠無(wú)差錯(cuò)地譯出發(fā)端所輸送的信息。信道輸入符號(hào)序列X代表M種信源符號(hào)，信源符號(hào)也可以是已經(jīng)經(jīng)過(guò)信源編碼的M種碼字，使從信道輸出符號(hào)序列Y能正確地譯出這M種碼字，問(wèn)題就在于如何用X組成這M種碼字，才能達(dá)到無(wú)差錯(cuò)地傳送，這就要編碼。這種編碼實(shí)質(zhì)上是希望信源與信道特性相匹配，所以稱為信道編碼。

3信道編譯碼的基本思想信道編碼的編碼對(duì)象是信源編碼器輸出的數(shù)字序列M，又稱為信息序列。通常是由二元符號(hào)0，1構(gòu)成的序列，而且符號(hào)0和1是獨(dú)立等概的。信道編碼，就是按一定的規(guī)則給數(shù)字序列M增加一些多余的碼元，使不具有規(guī)律性的信息序列M變換為具有某種規(guī)律性的數(shù)字序列C，又稱為碼序列。碼序列中信息序列的諸碼元與多余碼元之間是相關(guān)的。在接收端，信道譯碼器利用這種預(yù)知的編碼規(guī)則來(lái)譯碼，或者檢錯(cuò)(檢驗(yàn)接收到的數(shù)字序列R中是否有錯(cuò))，或者糾錯(cuò)(糾正其中的差錯(cuò))。信道編碼的基本思想是就是根據(jù)相關(guān)性來(lái)檢測(cè)和糾正傳輸過(guò)程中產(chǎn)生的差錯(cuò)。4通信的可靠性問(wèn)題通信的可靠性問(wèn)題，即消息通過(guò)信道傳輸時(shí)如何選擇編碼方案以減少差錯(cuò)。首先，通信的可靠性顯然與信道的統(tǒng)計(jì)特性有關(guān)，因?yàn)殡s噪干擾是造成錯(cuò)誤的主要因素。其次，編碼方法和譯碼方法也將影響信息傳輸?shù)目煽啃?。在有噪信道中傳輸信息是?huì)發(fā)生錯(cuò)誤的，錯(cuò)誤概率和信道統(tǒng)計(jì)特性、編譯碼過(guò)程以及譯碼規(guī)則有關(guān)。5編碼信道的概念信道編碼研究的對(duì)象是編碼信道，如上圖所示，它是由信道編碼器、信道譯碼器和實(shí)際信道一起形成的一個(gè)新的信道。編碼信道是研究信道糾錯(cuò)編碼和譯碼的一種模型。它可以是：無(wú)線通信中的如發(fā)射機(jī)、天線、自由空間、接收機(jī)等全體；有線通信中的如調(diào)制解調(diào)器、電纜等全體；互聯(lián)網(wǎng)的多個(gè)路由器、節(jié)點(diǎn)、電纜、低層協(xié)議等全體；計(jì)算機(jī)的存儲(chǔ)器如磁盤等的全體；……。接收向量

Y碼字X編碼信道信源編碼信源譯碼消息m消息m’6錯(cuò)誤概率和譯碼規(guī)則考慮一個(gè)二元對(duì)稱信道，單符號(hào)錯(cuò)誤傳遞概率是pb=0.9，其輸入符號(hào)為等概率分布。如果規(guī)定在信道輸出端接收到符號(hào)0時(shí)，譯碼器把它譯成0；接收到1時(shí)譯成1，那么譯碼錯(cuò)誤概率為0.9。反之，如果規(guī)定在接收到符號(hào)0時(shí)譯成1；接收到1時(shí)譯成0，則譯碼錯(cuò)誤概率為0.1?？梢?jiàn)，錯(cuò)誤概率既與信道統(tǒng)計(jì)特性有關(guān)，也與譯碼規(guī)則有關(guān)。00111-pb1-pbpbpb二元對(duì)稱信道7無(wú)記憶二進(jìn)制對(duì)稱信道（BSC）假定數(shù)字通信系統(tǒng)的編碼信道是無(wú)記憶二進(jìn)制對(duì)稱信道：二進(jìn)制信道是指碼字和接收向量均由二元序列表示的信道，即c=(c0,c1,…,cn-1)ci{0,1}、

r=(r0,r1,…,rn-1)ri{0,1}。二進(jìn)制信道可用轉(zhuǎn)移概率p(r/c)描述輸入輸出關(guān)系；滿足以下公式的二進(jìn)制信道稱為無(wú)記憶二進(jìn)制信道：

p(r/c)=p(ri

/ci

)i=0…n-1滿足以下對(duì)稱特性的無(wú)記憶二進(jìn)制信道稱為無(wú)記憶二進(jìn)制對(duì)稱信道，簡(jiǎn)稱BSC：p(0/1)=

p(1/0)=pb接收向量rri{0,1}

碼字cci{0,1}二進(jìn)制信道p(r/c)信源編碼信源譯碼消息m消息m’8BSC的信道模型只要噪聲是白噪聲，大多數(shù)二進(jìn)制傳輸信道的模型可等效為一個(gè)BSC，其信道模型如下圖所示。+cer二進(jìn)制無(wú)記憶00111-pb1-pbpbpbBSC轉(zhuǎn)移概率BSC編碼信道9可將BSC的輸入輸出關(guān)系等效為代數(shù)關(guān)系：r=c+emod2e=(e0,e1,…,en-1)差錯(cuò)圖案：隨機(jī)序列(ei)隨機(jī)錯(cuò)誤：ei

=1,i位突發(fā)錯(cuò)誤：第i至第j位之間有很多錯(cuò)誤。BSC的輸入輸出關(guān)系描述+cer10譯碼規(guī)則譯碼規(guī)則的定義11譯碼規(guī)則-例設(shè)有一離散無(wú)記憶信道，其信道矩陣為則以下A和B是兩個(gè)不同的譯碼規(guī)則：由于n=3，m=3，m個(gè)輸出符號(hào)中的每一個(gè)都可以譯成n個(gè)輸入符號(hào)中的任何一個(gè)，故按此信道矩陣總共可設(shè)計(jì)出33=27種譯碼規(guī)則。在所有的譯碼規(guī)則中，不是每一種譯碼規(guī)則都是合理的，因此要討論選擇譯碼規(guī)則的準(zhǔn)則，這些準(zhǔn)則總的原則是使譯碼平均錯(cuò)誤概率最小。

121、譯碼平均錯(cuò)誤概率若譯碼規(guī)則為，則信道輸出端接收到符號(hào)yj時(shí)，一定譯成xi。如果發(fā)送端發(fā)的就是xi，這就是正確譯碼，因此條件正確概率為反之，如果發(fā)送端發(fā)的是，則是錯(cuò)誤譯碼，因此條件錯(cuò)誤概率為

經(jīng)過(guò)譯碼后，平均到一個(gè)符號(hào)所產(chǎn)生的錯(cuò)誤的大小，也就是譯碼平均錯(cuò)誤概率為

13譯碼平均錯(cuò)誤概率的其它表達(dá)式譯碼平均錯(cuò)誤概率還可以寫(xiě)成若用條件概率表示，則可以寫(xiě)成平均正確概率則可以寫(xiě)成

14等概率分布時(shí)的譯碼平均錯(cuò)誤概率若輸入為等概率分布，則上式意味著，在輸入為等概率分布的條件下，譯碼錯(cuò)誤概率可用信道矩陣中元素的求和來(lái)求。這種求和是除去信道矩陣中每列中對(duì)應(yīng)于的那一項(xiàng)后，求矩陣中其余元素之和。

152、譯碼規(guī)則選擇譯碼規(guī)則總的原則應(yīng)是使譯碼平均錯(cuò)誤概率pE最小。

譯碼平均錯(cuò)誤概率

為非負(fù)項(xiàng)之和，欲使譯碼平均錯(cuò)誤概率最小，那么應(yīng)使每一項(xiàng)為最小。由于p(yj)

與譯碼規(guī)則無(wú)關(guān)，故欲使譯碼平均錯(cuò)誤概率最小，即為使最小，或者使為最大，于是引出最大后驗(yàn)概率準(zhǔn)則。

16最大后驗(yàn)概率譯碼準(zhǔn)則-定義17最大后驗(yàn)概率準(zhǔn)則-例題18最大后驗(yàn)概率準(zhǔn)則-例題（續(xù)）19后驗(yàn)概率與最大似然-譯碼準(zhǔn)則從最大后驗(yàn)概率譯碼規(guī)則可以很容易推出極大似然譯碼規(guī)則。20最大似然譯碼準(zhǔn)則-定義

當(dāng)信道輸入符號(hào)為等概分布時(shí)，應(yīng)用極大似然譯碼準(zhǔn)則是很方便的，即將yj譯成信道矩陣中第j列最大的那個(gè)元素。式中的條件概率即為信道矩陣中的元素。21最大似然譯碼準(zhǔn)則-例題當(dāng)輸入為等概率分布時(shí)，譯碼規(guī)則A就是依據(jù)最大似然譯碼準(zhǔn)則而得的。22最大似然譯碼準(zhǔn)則-例題（續(xù)）輸入為等概率分布時(shí)，兩種譯碼規(guī)則所對(duì)應(yīng)的平均錯(cuò)誤概率分別為

在輸入為等概率分布時(shí)，最大似然譯碼準(zhǔn)則是最優(yōu)的。23費(fèi)諾不等式譯碼時(shí)發(fā)生錯(cuò)誤是由信道中噪聲引起，因此平均錯(cuò)誤概率與信道疑義度H(X|Y)有關(guān)，其關(guān)系由費(fèi)諾不等式表示。引理6.1.1譯碼平均錯(cuò)誤概率與信道疑義度H(X|Y)間滿足以下關(guān)系這個(gè)不等式稱為費(fèi)諾不等式。

24費(fèi)諾不等式的物理意義雖然PE與譯碼規(guī)則有關(guān)，但不管采用什么譯碼規(guī)則費(fèi)諾不等式均成立。費(fèi)諾不等式表示，當(dāng)作了一次譯碼判決后所保留的關(guān)于信元的不確定性可以分成兩部分：H(PE)和PE

log(n-1)。第二部分是當(dāng)判決是錯(cuò)誤的，其錯(cuò)誤概率為PE

時(shí)，到底是n-1個(gè)輸入符號(hào)中哪一個(gè)引起錯(cuò)誤的最大不確定性，它是(n-1)個(gè)符號(hào)不確定性的最大值log(n-1)與PE

的乘積。

第一部分是接收到Y(jié)后，判決是否發(fā)生錯(cuò)誤的不確定性H(PE)，其中H(PE

)是譯碼平均錯(cuò)誤概率PE

的熵，表示產(chǎn)生錯(cuò)誤概率PE

的不確定性。25費(fèi)諾不等式的幾何含義信道疑義度是信源熵H(X)超過(guò)平均互信息I(X;Y)的部分。若以H(X|Y)為縱坐標(biāo)，PE為橫坐標(biāo)，則函數(shù)H(PE)+PE

log(n-1)隨PE變化的曲線如圖所示。由圖可知，當(dāng)信源、信道給定時(shí)，信道疑義度H(X|Y)就給定了譯碼平均錯(cuò)誤概率PE的下限。

26錯(cuò)誤概率與編碼方法

前面討論了平均錯(cuò)誤概率與譯碼規(guī)則的關(guān)系。選擇最佳譯碼規(guī)則只能使錯(cuò)誤概率有限地減小，無(wú)法使其任意地小。要想進(jìn)一步減小錯(cuò)誤概率，必須優(yōu)選信道編碼方法?，F(xiàn)在討論不同的編碼方法對(duì)譯碼平均錯(cuò)誤概率和信息傳輸率的影響。

27錯(cuò)誤概率與編碼方法1簡(jiǎn)單重復(fù)編碼2消息符號(hào)個(gè)數(shù)3（5,2）線性碼4漢明距離281簡(jiǎn)單重復(fù)編碼與錯(cuò)誤概率

本節(jié)舉例說(shuō)明在采用簡(jiǎn)單重復(fù)編碼時(shí)重復(fù)次數(shù)對(duì)譯碼平均錯(cuò)誤概率和信息傳輸率的影響。設(shè)有二元對(duì)稱信道如圖其信道矩陣為未編碼時(shí)：選擇最佳譯碼規(guī)則為

在輸入為等概率分布時(shí)，譯碼平均錯(cuò)誤概率為29簡(jiǎn)單重復(fù)編碼舉例（續(xù)1）采用簡(jiǎn)單重復(fù)編碼，規(guī)定信源符號(hào)為0（或1）時(shí)重復(fù)發(fā)送三個(gè)0（或1）。輸入符號(hào)和輸出符號(hào)的關(guān)系如圖：

30簡(jiǎn)單重復(fù)編碼舉例（續(xù)2）31簡(jiǎn)單重復(fù)編碼舉例（續(xù)3）在簡(jiǎn)單重復(fù)編碼時(shí)，采用“擇多譯碼”的譯碼規(guī)則等效于最大似然譯碼準(zhǔn)則。擇多譯碼是根據(jù)接收序列中“0”和“1”的個(gè)數(shù)，如果是“0”多，則譯碼器就判決為“0”，如果是“1”多，就判決為“1”。采用簡(jiǎn)單重復(fù)編碼方法，如果增大重復(fù)次數(shù)n，則會(huì)降低譯碼平均錯(cuò)誤概率，但信息傳輸率也要減小。信息傳輸率表示平均每個(gè)碼符號(hào)所攜帶的信息量，其中M為消息符號(hào)個(gè)數(shù)。32簡(jiǎn)單重復(fù)編碼舉例（續(xù)4）重復(fù)次數(shù)對(duì)信息傳輸率和錯(cuò)誤概率的影響如下能否找到一種編碼方法，使平均錯(cuò)誤概率充分小，而信息傳輸率R’又可以保持在一定水平上，這就是香農(nóng)第二定理所要回答的問(wèn)題。

332消息符號(hào)個(gè)數(shù)M本節(jié)討論消息符號(hào)個(gè)數(shù)M對(duì)錯(cuò)誤概率和信息傳輸率的影響。在一個(gè)二元信道的n次無(wú)記憶擴(kuò)展信道中，輸入端共有2n個(gè)符號(hào)序列可能作為消息符號(hào)，現(xiàn)僅選其中M個(gè)作為消息符號(hào)傳遞。

34消息符號(hào)個(gè)數(shù)M的影響（續(xù)1）設(shè)n=3，那么可供選擇的消息符號(hào)數(shù)共有8個(gè)，發(fā)送端只選擇其中M個(gè)作為輸入消息符號(hào)傳遞，而接收端會(huì)接收到所有8個(gè)輸出符號(hào)，然后從中譯出M個(gè)消息符號(hào)。

以下假設(shè)輸入為等概率分布p(x)=1/M，信道錯(cuò)誤傳遞概率p=0.01，采用簡(jiǎn)單重復(fù)編碼和最大似然譯碼準(zhǔn)則。當(dāng)n=3，M=2時(shí)，有：

35消息符號(hào)個(gè)數(shù)M的影響（續(xù)2）當(dāng)n=3，M=4時(shí)，有比特/碼符號(hào)

M=4有不同的選取方法，代表不同的編碼方法，其平均錯(cuò)誤概率是不同的。

36結(jié)論：輸入信息符號(hào)個(gè)數(shù)M增大時(shí)，平均錯(cuò)誤概率顯然是增大了，但信息傳輸率也增大了。反之，亦然。

輸入信息符號(hào)個(gè)數(shù)M不變時(shí)，即信息傳輸率不變時(shí)，不同的編碼方法，其平均錯(cuò)誤概率是不同的。

37錯(cuò)誤概率與編碼方法1簡(jiǎn)單重復(fù)編碼2消息符號(hào)個(gè)數(shù)3（5,2）線性碼4漢明距離383（5，2）線性碼從以上討論看出：增大簡(jiǎn)單重復(fù)編碼次數(shù)n，雖然使平均錯(cuò)誤概率pE下降，但信息傳輸率R’也降低了。增大輸入消息符號(hào)個(gè)數(shù)M，盡管可使信息傳輸率R’增大，但又增大了平均錯(cuò)誤概率pE。當(dāng)采用好的編碼方法時(shí)，可以使平均錯(cuò)誤概率pE和信息傳輸率R’兩個(gè)指標(biāo)得到較好的折衷。39（5，2）線性碼的編碼設(shè)M=4，n=5則輸入符號(hào)有M=4種，由的4個(gè)不同取值決定。采用以下編碼方法將輸入符號(hào)編碼成為5位碼：40（5,2）線性碼的編碼（續(xù)）由上述編碼方法得到一種(5,2)線性碼，如圖所示:41（5,2）線性碼的譯碼效果采用最大似然譯碼準(zhǔn)則，當(dāng)p=0.01時(shí)正確譯碼概率為平均錯(cuò)誤譯碼概率為信息傳輸率為前述n=3，M=4的一種簡(jiǎn)單重復(fù)編碼平均錯(cuò)誤譯碼概率為信息傳輸率為42結(jié)論與n=3，M=4的簡(jiǎn)單重復(fù)編碼比較，（5,2）線性碼的信息傳輸率R’略有降低，但平均錯(cuò)誤概率卻好得多。說(shuō)明好的編碼方法可以在錯(cuò)誤概率和信息傳輸率兩個(gè)性能上達(dá)到最佳折衷。43離散信道編碼定理信道編碼定理是一個(gè)理想編碼的存在性定理。信道容量是一個(gè)臨界值，信息傳輸率不超過(guò)這個(gè)值，信道就可幾乎無(wú)失真地把信息傳過(guò)去，否則就會(huì)產(chǎn)生失真。44糾錯(cuò)碼分類

檢糾錯(cuò)碼的種類繁多，其分類也有多種方式，主要依據(jù)使用的信道、糾錯(cuò)類型和碼的數(shù)學(xué)結(jié)構(gòu)分類。以下首先簡(jiǎn)要介紹干擾類型和對(duì)應(yīng)的信道類型、檢糾錯(cuò)工作方式，再介紹檢糾錯(cuò)碼的不同分類方法。45干擾類型信道中的干擾一般分為兩種形式：隨機(jī)噪聲，它主要來(lái)源于設(shè)備的熱噪聲和散彈噪聲以及傳播媒介的熱噪聲，它是通信系統(tǒng)中的主要噪聲；脈沖干擾，它的特點(diǎn)是突發(fā)出現(xiàn)，主要來(lái)源于雷電、通電開(kāi)關(guān)、負(fù)荷突變或設(shè)備故障等。46檢糾錯(cuò)的工作方式

反饋重傳糾錯(cuò)當(dāng)發(fā)現(xiàn)有錯(cuò)時(shí)，通過(guò)反饋系統(tǒng)向發(fā)出端發(fā)出詢問(wèn)信號(hào)要求重新發(fā)送。發(fā)送端收到信號(hào)后，重發(fā)已發(fā)生錯(cuò)誤的那部分信息，直至接收端認(rèn)為無(wú)錯(cuò)誤為止。前向糾錯(cuò)當(dāng)在傳輸中出現(xiàn)差錯(cuò)，且錯(cuò)誤個(gè)數(shù)在碼的糾錯(cuò)能力范圍內(nèi)時(shí)，系統(tǒng)的接收端根據(jù)編碼規(guī)則進(jìn)行解碼，并自動(dòng)糾正錯(cuò)誤。這種糾錯(cuò)方式不需要反饋，故稱其為前向糾錯(cuò)?；旌霞m錯(cuò)當(dāng)錯(cuò)誤在碼的糾錯(cuò)能力之內(nèi)時(shí)，采用自動(dòng)糾錯(cuò)。當(dāng)超出碼的糾錯(cuò)能力，且能發(fā)現(xiàn)錯(cuò)誤，則發(fā)出詢問(wèn)信號(hào)，反饋到發(fā)送端要求重發(fā)。47線性碼和非線性碼根據(jù)碼的數(shù)學(xué)結(jié)構(gòu)，可以有不同的分類。按校驗(yàn)元與信息元的關(guān)系，可分為線性碼和非線性碼。線性碼的校檢位是若干信息位的線性組合，而非線性碼的校檢位與信息位不滿足線性關(guān)系。線性碼的編譯碼都優(yōu)于相同糾錯(cuò)能力的非線性碼。48分組碼和卷積碼按對(duì)信息序列處理方式分類，可分為分組碼和卷積碼分組碼:對(duì)于某組碼字，其信息序列劃分為一組k位碼元，將其編成n（n>k）位的碼字。重點(diǎn)討論線性分組碼。根據(jù)分組碼的結(jié)構(gòu)，又可分為循環(huán)碼和非循環(huán)碼。卷積碼:是將整個(gè)信息序列編成一個(gè)碼序列，碼與碼之間相互影響，不能分開(kāi)。卷積碼又稱為樹(shù)碼或鏈碼。494漢明距離

定義：設(shè)為兩個(gè)n長(zhǎng)的二元碼字，則碼字X和Y之間的漢明距離為其中，代表模二和運(yùn)算。上式的含義是，兩個(gè)碼字之間的漢明距離就是它們?cè)谙嗤簧喜煌a符號(hào)的數(shù)目的總和。

舉例：設(shè)X=(101111)，Y=(111100)，則D(X,Y)=350漢明距離滿足的性質(zhì)1、非負(fù)性D(X,Y)≥0當(dāng)且僅當(dāng)X=Y式等號(hào)成立。2、對(duì)稱性D(X,Y)=D(Y,X)3、三角不等式D(X,Z)+D(Y,Z)≥D(X,Y)51最小碼距Dmin定義：在二元碼C中，任意兩個(gè)碼字的漢明距離的最小值，稱為碼C的最小碼距，即舉例：設(shè)有n=3的兩組碼對(duì)于碼C1有對(duì)于碼C2有52最小碼距對(duì)錯(cuò)誤概率的影響顯然，最小碼距Dmin越大，則平均錯(cuò)誤概率pE越小。碼本中最小碼距Dmin越大，受干擾后，越不容易把一個(gè)碼字錯(cuò)譯成另一個(gè)碼字，因而平均錯(cuò)誤概率pE小。如果碼本中最小碼距Dmin小，受干擾后很容易把一個(gè)碼字錯(cuò)譯成另一個(gè)碼字，因而平均錯(cuò)誤概率pE大。因此，在選擇編碼規(guī)則時(shí)，應(yīng)使碼字之間的距離Dmin越大越好，這樣的準(zhǔn)則即為最小