第6章信道編碼本章內容：有擾離散信道的編碼定理糾錯編譯碼的基本原理與分析方法線性分組碼卷積碼1第六講信道編碼

PartI--有噪信道編碼信道編碼的意義譯碼規(guī)則信源編碼提高數字信號有效性將信源的模擬信號轉變?yōu)閿底中盘?降低數碼率,壓縮傳輸頻帶(數據壓縮)信道編碼提高數字通信可靠性

數字信號在信道的傳輸過程中,由于實際信道的傳輸特性不理想以及存在加性噪聲,在接收端往往會產生誤碼。3編碼有噪信道編碼定理（香農第二定理）離散、無記憶、平穩(wěn)信道，信道容量為C，只要待傳送的信息率R<C，就一定能找到一種信道編碼方法，使得碼長N足夠大時，平均差錯率Pe任意接近于零。香農第二定理是存在性定理，它指出在R<C時，肯定存在一種好的信道編碼方法，使Pe逼近零。但并沒有給出編碼的具體方法。

有噪信道編碼逆定理離散、無記憶、平穩(wěn)信道，信道容量為C，如果信息率R>C，則肯定找不到一種信道編碼方法，使得碼長N足夠大時，平均差錯率任意接近于零。1、香農信息論對信道編碼的指導意義信道編碼定理：每一個信道具有確定的信道容量C，對于任何小于C的信息傳輸率R，總存在一個碼長為n，碼率等于R的分組碼，若采用最大似然譯碼，則其譯碼錯誤概率PE滿足

PEAe-nE(R)

其中：A是常數，E（R)為誤差函數錯誤概率PE越小，傳輸可靠性越高。增大碼長n也可提高傳輸可靠性有噪信道編碼定理（香農第二定理）

如一個離散無記憶信道，信道容量為C。當信息傳輸率R≤C時，只要碼長足夠長，總可以在輸入符號集中找到M個碼字組成的一組碼和相應的譯碼準則，使信道輸出端的平均錯誤譯碼概率達到任意小。有噪信道編碼逆定理

如一個離散無記憶信道，信道容量為C。當信息傳輸率R>C時，則無論碼長n多長，總找不到一種編碼使信道輸出端的平均錯誤譯碼概率達到任意小。信道編碼的理論依據：當取信道容量C以下的信息傳輸率時，以指數趨進于0；當取分界點以下的信息傳輸率時，以指數趨進于1；因此在任何信道中，信道容量都是可達的、最大的可靠信息傳輸率。存在定理，它沒有給出一個具體可構造的編碼方法，但有助于指導各種通信系統(tǒng)的設計，有助于評價各種系統(tǒng)及編碼的效率。差錯符號、差錯比特差錯符號：由符號發(fā)生差錯引起，也叫信號差錯，信號差錯概率用誤碼元率表示；差錯比特：由信息比特發(fā)生差錯引起，也叫信息差錯，信息差錯概率用誤比特率表示；對于二進制傳輸系統(tǒng)，符號差錯等效于比特差錯；對于多進制系統(tǒng)，一個符號差錯到底對應多少比特差錯卻難以確定。因為一個符號由多個比特組成。10誤碼率/差錯率根據不同的應用場合對差錯率有不同的要求:在電報傳送時,允許的比特差錯率約為:10－4～10－5；計算機數據傳輸,一般要求比特差錯率小于:10－8～10－9；在遙控指令和武器系統(tǒng)的指令系統(tǒng)中,要求有更小的誤比特率或碼組差錯率11通常，降低誤碼率可采取兩方面的措施：一是降低信道本身引起的誤碼率。二是采用差錯控制、糾錯編碼技術。差錯圖樣（errorpattern）為了定量地描述信號的差錯，定義收、發(fā)碼之“差”為： 差錯圖樣E＝發(fā)碼C－收碼R

（模M）例：8進制(M=8)碼元， 若發(fā)碼 C=（0,2,5,4,7,5,2） 收碼變?yōu)?R=（0,1,5,4,7,5,4） 差錯圖樣 E=C－R=（0,1,0,0,0,0,6）（模8）12差錯圖樣（errorpattern）二進制碼：E=CR或

C=RE

，差錯圖樣中的“１”既是符號差錯也是比特差錯，差錯的個數叫漢明距離。13設發(fā)送的碼字C1111111111

接收的碼字R1001001111

差錯的圖樣E0110110000差錯圖樣中的“1”既是符號差錯也是比特差錯,差錯的個數叫漢明距離。0:傳輸中無錯1:傳輸中有錯

差錯類型隨機差錯：差錯是相互獨立的,不相關，以相等的概率獨立發(fā)生于各碼字、各碼元、各比特存在這種差錯的信道是無記憶信道或隨機信道----(較多恒參信道)突發(fā)差錯：指成串出現的錯誤,錯誤間有相關性,一個差錯往往要影響到后面一串字----(隨參信道)差錯碼元開頭、以差錯碼元結尾，之間并不是每個碼元都錯，而是碼元差錯概率超過了某個額定值E:001001000000

10011100000

14突發(fā)長度=4突發(fā)長度=6糾錯碼分類15從功能角度講,差錯碼分為檢錯碼和糾錯碼檢錯碼：用于發(fā)現差錯糾錯碼：能自動糾正差錯糾錯碼與檢錯碼在理論上沒有本質區(qū)別,只是應用場合不同,而側重的性能參數也不同。糾錯碼分類對信息序列的處理方法：分組碼、卷積碼碼元與原始信息位的關系：線性碼、非線性碼差錯類型：糾隨機差錯碼、糾突發(fā)差錯碼、介于中間的糾隨機/突發(fā)差錯碼。構碼理論：代數碼、幾何碼、算術碼、組合碼等16檢錯與糾錯舉例0:晴,1:雨若1→0,0→1。收端無法發(fā)現錯誤1700晴1001110011雨能發(fā)現一個錯誤禁用碼組插入1位監(jiān)督碼后具有檢出1位錯碼的能力,但不能予以糾正。檢錯與糾錯舉例18000晴010001111000111雨晴在只有1位錯碼的情況下,可以判決哪位是錯碼并予以糾正,可以檢出2位或2位以下的錯碼，但糾錯能力有限，比如111000。100011101110雨擇多譯碼糾錯編碼的基本思路糾錯能力的獲取歸結為兩條：一條是利用冗余度，另一條是噪聲均化（隨機化、概率化）19冗余度就是在信息流中插入冗余比特。例：3bit表示4種意義。1、增加碼長N例：設某BSC信道誤碼率Pe=0.01，假如編碼后的糾錯能力是10%。先設碼長N=10，碼字中多于1位誤碼時就會產生譯碼差錯，差錯概率為：糾錯編碼的基本思路2、噪聲均化就是讓差錯隨機化，就是設法將危害較大的、較為集中的噪聲干擾分攤開來。卷積：卷積碼在一定約束長度內的若干碼字之間加進了相關性，譯碼時不是根據單個碼字，而是一串碼字，這樣就可以將噪聲分攤到碼字序列而不是一個碼字上。交錯：交錯是對付突發(fā)差錯的有效措施。如果保持碼率不變，將碼長增加到N=40，那么當碼字中多于4位誤碼時，會產生譯碼差錯，差錯的概率為信道編碼（糾錯編碼）在被傳輸信息中附加一些冗余碼,即監(jiān)督碼元,利用附加碼元與信息碼元間的約束關系加以校驗,以檢測和糾正錯誤。信源編碼減少了冗余度冗余度是隨機的、無規(guī)律的信道（糾錯）編碼增加了冗余度冗余度是特定的、有規(guī)律的,故可利用其在接收端進行檢錯和糾錯。21傳輸冗余比特必然要占用更多的資源。時間：比如一個比特重復發(fā)幾次,或一段消息重復發(fā)幾遍,或根據收端的反饋重發(fā)受損信息組。頻帶：插入冗余比特后傳輸效率下降,若要保持有用信息的速率不變,方法之一是增大符號傳遞速率(波特率),結果就占用了更大的帶寬。功率：采用多進制符號,用8進制ASK符號代替4進制ASK符號來傳送2比特信息,可騰出位置另傳1冗余比特。8進制ASK符號的平均功率肯定比4進制時要大,這就是動用冗余的功率資源來傳輸冗余比特。設備復雜度：加大碼長,采用網格編碼調制,是在功率、帶寬受限信道中實施糾錯編碼的有效方法,代價是算法復雜度的提高,需動用設備資源。22差錯控制系統(tǒng)分類前向糾錯（FEC）：發(fā)端信息經糾錯編碼后傳送，收端通過糾錯譯碼自動糾正傳遞過程中的差錯反饋重發(fā)（ARQ）：收端通過檢測接收碼是否符合編碼規(guī)律來判斷，如判定碼組有錯，則通過反向信道通知發(fā)端重發(fā)該碼混合糾錯（HEC）：前向糾錯和反饋重發(fā)的結合，發(fā)端發(fā)送的碼兼有檢錯和糾錯兩種能力231.前向糾錯方式前向糾錯方式：FEC(ForwardError-Correction)。利用糾錯碼自動糾正收端檢出的錯誤。

FEC方式的優(yōu)點是：無需反饋信道，傳信率恒定，譯碼延時恒定，有利于實時處理和同步。

FEC方式的缺點是：如果糾大量的錯誤，必須插入較多的監(jiān)督碼元，編碼效率低，需增加相應的信道容量，或使用高效碼，對于高可靠性通信，選擇適用的糾錯碼及其譯碼算法往往比較困難。自動請求重傳系統(tǒng)有三種：停發(fā)等侯重發(fā)返回重發(fā)選擇重發(fā)停發(fā)等候重發(fā)

停發(fā)等候重發(fā)方式在兩個碼組之間有停頓時間（T1），使傳輸效率受到影響，但由于工作原理簡單，在計算機數據通信中仍得到應用過程演示即停等候重發(fā)系統(tǒng)中：1發(fā)送端1接收端TW發(fā)送端在TW時間內送出一個碼組給接收端接收端進行檢驗即停等候重發(fā)系統(tǒng)中：1發(fā)送端1接收端TWACKT1接收端未發(fā)現錯誤，則發(fā)回一個認可信號（ACK）給發(fā)送端兩碼組之間有停頓時間T1即停等候重發(fā)系統(tǒng)中：1發(fā)送端1接收端TW發(fā)送端收到信號ACK后再發(fā)出下一個碼組ACKT12233即停等候重發(fā)系統(tǒng)中：1發(fā)送端1接收端TWACKT1223如果接收端檢測出錯誤，則發(fā)回一個否認信號NAK發(fā)現錯誤3NAK發(fā)送端收到信號后重發(fā)前一個碼組即停等候重發(fā)系統(tǒng)中：1發(fā)送端1接收端TWACKT12233發(fā)現錯誤NAK3返回返回重發(fā)

返回重發(fā)系統(tǒng)比停發(fā)等候重發(fā)系統(tǒng)有很大改進，在許多數據傳輸系統(tǒng)中得到應用過程演示1發(fā)送端接收端發(fā)送端無停頓地送出一個又一個碼組給接收端不再等候ACK信號123411發(fā)送端接收端234發(fā)現錯誤一旦接收端發(fā)現錯誤便發(fā)回NAK信號34253NAK6TW11發(fā)送端接收端2234發(fā)現錯誤34NAK34562TW發(fā)送端重發(fā)下一個碼組時先重發(fā)前N段碼組11接收端2234發(fā)現錯誤34NAK34562TW2345645623789101145678從碼組2開始重發(fā)發(fā)送端返回11發(fā)送端接收端2234發(fā)現錯誤34NAK34562TW2345645623789101145678從碼組2開始重發(fā)N=5選擇重發(fā)

選擇重發(fā)系統(tǒng)傳輸效率最高，但另一方面價格也最貴，應為它要求較為復雜的控制,在發(fā)送、接收端都要求數據緩存器。

此外，重發(fā)系統(tǒng)和返回重發(fā)系統(tǒng)都需要全雙工的鏈路，而停發(fā)等後系統(tǒng)只要求半雙工的鏈路。過程演示1發(fā)送端接收端發(fā)送端無停頓的送出一個又一個碼組給接收端不再等候ACK信號123411發(fā)送端接收端234發(fā)現錯誤一旦接收端發(fā)現錯誤便發(fā)回NAK信號。這幾步和返回重發(fā)是一樣的。34253NAK6TW11發(fā)送端接收端234發(fā)現錯誤34253NAK6TW發(fā)送端重發(fā)有錯誤的一組。（而返回重發(fā)要重發(fā)前面所有的碼組）4211接收端2234發(fā)現錯誤34NAK34562TW27891045627111213141589101112只重發(fā)碼組2發(fā)送端返回43混合糾錯(HEC)：是FEC與ARQ方式的結合。發(fā)端發(fā)送同時具有自動糾錯和檢測能力的碼組,收端收到碼組后,檢查差錯情況,如果差錯在碼的糾錯能力以內,則自動進行糾正。如果信道干擾很嚴重,錯誤很多,超過了碼的糾錯能力,但能檢測出來,則經反饋信道請求發(fā)端重發(fā)這組數據。信息反饋(IRQ)：收端把收到的數據,原封不動地通過反饋信道送回到發(fā)端,發(fā)端比較發(fā)的數據與反饋來的數據,從而發(fā)現錯誤,并且把錯誤的消息再次傳送,直到發(fā)端沒有發(fā)現錯誤為止。有噪信道編碼的譯碼準則實際的信道傳輸過程中，差錯的發(fā)生往往不可避免；錯誤概率和信道統(tǒng)計特性等相關；選擇合適的譯碼規(guī)則能降低差錯。

[例]錯誤概率與譯碼規(guī)則有關01XY01二元對稱信道錯誤概率不僅與信道的統(tǒng)計特征有關，而且也與譯碼規(guī)則有關。信道編碼以及譯碼將信道用圖5-1所示的模型表示。信道編碼器信道信道譯碼器uxy信道模型

信源輸出序列u，經信道編碼器編成碼字x=f(u)并輸入信道，由于干擾，信道輸出y，信道譯碼器對y估值得

=F(y)

。

譯碼器的任務是從受損的信息序列中盡可能正確地恢復出原信息。兩種常用譯碼規(guī)則信道總不可避免會攙雜噪聲，所以信息在信道傳輸過程中，差錯是不可避免的。選擇合適的譯碼規(guī)則可以彌補信道的不足。1．最大后驗概率譯碼準則發(fā)送碼矢xk，其發(fā)送概率為q(xk)，通過信道轉移概率為p(y︱xk)的信道傳輸，接收到矢量y，信道譯碼器輸出

通信過程可用圖5－5所示框圖表示。信源信道編碼器信道信道譯碼器信宿干擾{xk}{y}圖5－5通信過程框圖

當估值≠xk時，就產生了誤碼，用（x︱y）表示后驗概率，則收到y(tǒng)估錯的概率為

（5-2）

通信總希望錯誤概率最小，由式(5-2)可看出錯誤概率pe

(xk)最小等同于后驗概率（xk︱y）最大，這就是最大后驗概率譯碼準則。

根據概率關系式

（5-3）

根據式（5-3）后驗概率（x︱y）最的就意味著p（x

y）全概率最大，因此最大后驗概率譯碼準則也稱為最大聯合概率譯碼準則?！纠?.5】信源分布，信道轉移概率矩陣,信道輸出符號Y={y1,y2,y3}，按最大后驗概率準則譯碼。(1)根據p(xy)=p(y︱x)q(x)算出全概率，用矩陣表示

(2)根據，算出[（y）]=[0.380.340.28]

(3)再由算出后驗概率，用矩陣表示

(4)按最大后驗概率準則譯碼，在后驗概率矩陣中，每列選一最大值（矩陣中帶下劃線的值），譯為

(5)若按最大聯合概率譯碼準則譯碼，在全概率矩陣[p(xy)]中每列選一最大值（矩陣中帶下劃線的值），也可譯出

最大后驗概率譯碼準則存在問題：

不易實現,對于信道，可以獲知統(tǒng)計特性P（y/x）,但難以獲得信源分布p（x），因此無法求得全概率p（xy）；

而獲得后驗概率（收發(fā)）也很困難。

在實際應用中，一般按最大信道轉移概率來確定估值，即在收到矢量y后，在所有的xm(m=1,2,…,M)中,選一個轉移概率p(y︱xm)最大的xm值，作為對y的估值=xk，這一譯碼規(guī)則稱為極大似然譯碼規(guī)則。2．極大似然譯碼準則---退而求其次已知接收序列的條件下使先驗概率最大的譯碼算法實際應用中，能夠獲知信道的統(tǒng)計特性p(y/x)，所以可根據信道轉移概率來確定碼字估值。3．平均錯誤概率

（5-4）

【例5.6】計算[例5.5]的平均錯誤概率，若信源等概分布，對其譯碼，并求平均錯誤概率。

()?=-=Mjkj1)(1yxyfw（1）求平均錯誤概率pe根據式（6-4）得=0.01+0.12+0.07+0.12+0.1+0.02=0.44(2)當信源等概分布，按最大似然函數譯碼準則譯碼，[例5.5]已給出信道轉移概率矩陣在矩陣的每列中選一最大值(矩陣中帶下劃線的值)，譯碼為平均錯誤概率最優(yōu)譯碼與最大似然譯碼譯碼器的任務是從受損的信息序列中盡可能正確地恢復出原信息。譯碼算法的已知條件是：實際接收到的碼字序列{r},r=(r1,r2,…,rN)發(fā)端所采用的編碼算法和該算法產生的碼集XN，滿足信道模型及信道參數。55最優(yōu)譯碼：最大后驗概率譯碼準則最佳譯碼，也叫最大后驗概率譯碼(MAP:Maximumaposteriori)已知r的條件下找出可能性最大的發(fā)碼作為譯碼估值,通過經驗與歸納推測發(fā)碼的方法56

消息組mi

碼字ci

接收碼r

估值

消息編碼器信道譯碼消息還原最大后驗概率譯碼準則等同于最小傳輸錯誤概率準則57

消息組mi

碼字ci

接收碼r

估值

消息編碼器信道譯碼消息還原存在問題：

不易實現,對于信道，可以獲知統(tǒng)計特性P（y/x）,但難以獲得信源分布p（x），因此無法求得全概率p（xy）；

而獲得后驗概率（收發(fā)）也很困難。

已收到碼為條件的條件概率全概率、聯合概率，也等同于最大聯合概率譯碼準則次最優(yōu)：最大似然譯碼準則最大似然譯碼(MLD:MaximumLikelihoodDecoding)已知r的條件下使先驗概率最大的譯碼算法實際應用中，能夠獲知信道的統(tǒng)計特性p(y/x)，但很難獲得信源分布P(x),無法求得全概率p(xy)所以根據信道轉移概率來確定碼字估值。58最優(yōu)譯碼與最大似然譯碼的關系如果構成碼集的2K個碼字以相同概率發(fā)送，滿足P(ci)=1/2K

，i=1,2,…,2K

P(r)對于任何r都有相同的值，滿足P(r)=1/2K

則P(ci/r)最大等效于P(r/ci)的最大，在此前提下最佳譯碼等效于最大似然譯碼。59最優(yōu)譯碼與最大似然譯碼對于無記憶信道，

[例]：BSC信道的最大似然譯碼可以簡化為最小漢明距離譯碼。漢明距離譯碼是一種硬判決譯碼。由于BSC信道是對稱的，只要發(fā)送的碼字獨立、等概率，漢明距離譯碼也就是最佳譯碼。

60[例]已知信道矩陣并設p(x1)=1/2,p(x2)=p(x3)=1/4,分別用最小錯誤概率準則和最大似然譯碼準則確定相應的譯碼規(guī)則，并計算平均錯誤概率。解：由于輸入符號不是等概率分布，所以對于最小錯誤概率準則必須根據聯合概率的大小來選擇。p(x1y1)=1/4,p(x2y1)=1/24,p(x3y1)=1/12p(x1y2)=1/6,p(x2y2)=1/8,p(x3y2)=1/24p(x1y3)=1/12,p(x2y3)=1/12,p(x3y3)=1/8故譯碼規(guī)則是F(y1)=x1,F(y2)=x1,F(y3)=x3對于最大似然譯碼準則，可以直接從信道矩陣的傳遞概率來選擇，譯碼規(guī)則是F(y1)=x1,F(y2)=x2,F(y3)=x3平均錯誤概率為pE=1/24+1/12+1/6+1/24+1/12+1/12=12/24p’E=1/24+1/12+1/8+1/24+1/12+1/12=11/24<pE64選擇最佳譯碼規(guī)則只能使錯誤概率pE有限地減小，無法使其任意的小。要想進一步減小錯誤概率，必須優(yōu)選信道編碼方法。[例]已知信道轉移矩陣如下，試確定譯碼規(guī)則。解只知轉移概率，無法找出最佳譯碼規(guī)則，只能采用最大似然譯碼規(guī)則。將轉移概率矩陣各列最大的值標出，重寫轉移矩陣如下：

按轉移概率最大原則確定最大似然譯碼規(guī)則如下：

盡管一般情況下并不知道這樣譯碼的差錯率。但可以證明，當信道輸入等概時，最大似然譯碼規(guī)則也是最佳的。糾錯碼的數學基礎：

矢量空間與碼空間基本的糾錯碼為（n,k）分組碼（塊碼）每塊為k個符號由n個碼元組成碼字碼字可視為n重矢量（n個矢量元素）67矢量空間與碼空間F表示碼元所在的數域(對于二進制碼，F代表二元域{0,1})設n重有序元素的集合V={Vi

},若滿足條件：V中矢量元素在矢量加運算下構成加群；V中矢量元素與數域F元素的標乘封閉在V中；分配律、結合律成立，則稱集合V是數域F上的n維矢量空間，或稱n維線性空間，n維矢量又稱n重(n-tuples)。68矢量空間中矢量的關系

對于域F上的若干矢量線性組合：

線性相關：

其中任一矢量可表示為其它矢量的線性組合線性無關或線性獨立：一組矢量中的任意一個都不可能用其它矢量的線性組合來代替.69矢量空間與基底一組線性無關的矢量，其線性組合的集合就構成了一個矢量空間V，這組矢量就是這個矢量空間的基底。n維矢量空間應包含n個基底基底不是唯一的，例：線性無關的兩個矢量（1,0）和（0,1）以及（-1,0）和（0,-1）可張成同一個兩維空間。70二元域GF(2)上三重矢量空間以（100）為基底可張成一維三重子空間V1，含21=2個元素，即以(010)(001)為基底可張成二維三重子空間V2，含22=4個元素，即以(100)(010)(001)為基底可張成三維三重空間V,含23=8個元素，V1和V2都是V的子空間。71概念重數構成矢量的有序元素的個數維數構成矢量空間的基底的個數72矢量空間每個矢量空間或子空間中必然包含零矢量兩個矢量正交：V1V2＝0兩個矢量空間正交：某矢量空間中的任意元素與另一矢量空間中的任意元素正交正交的兩個子空間V1、V2互為對偶空間

(DualSpace)，其中一個空間是另一個空間的零空間（nullspace，也稱零化空間）。73碼空間

74

消息k長 (n,k)碼字n長

qk

種分組編碼器qn種

k維k重矢量n維n重矢量

通常qn>>qk，分組編碼的任務是要在n維n重矢量空間的qn種可能組合中選擇其中的qk個構成一個碼空間，其元素就是許用碼的碼集。分組編碼的任務選擇一個ｋ維n重子空間作為碼空間。確定由k維k重信息空間到ｋ維n重碼空間的映射方法。碼空間的不同選擇方法，以及信息組與碼組的不同映射算法，就構成了不同的分組碼。75隨機編碼編碼的分析設計途徑：1.數學解析途徑，即將代數、幾何、數論等理論運用到編解碼，如分組碼，卷積碼。2.運用概率統(tǒng)計方法在特定信道條件下對編碼信號的性能作出統(tǒng)計分析，求出差錯概率的上下限邊界，其中最優(yōu)碼所能達到的差錯概率上界稱作隨機碼界。用這種方法不能得知最優(yōu)碼是如何具體編出來的，卻能得知最優(yōu)碼可以好到什么程度，并進而推導出有擾離散信道的編碼定理，對指導編碼技術具有特別重要的理論價值。76隨機編碼對于一個(N,K)分組編碼器對K個q進制組成的消息組m=(m0,m1,…,mk-1)編碼；生成N個q進制符號組成的碼字c=(c0,c1,…cN-1)；在(N,K)分組編碼器中隨機選定的碼集有qNM種一個消息組的編碼有qN種選擇（N個碼元，q進制）qK個消息組共有種選擇令M=qK，可得上式77隨機編碼在(N,K)分組編碼器中隨機選定的碼集有