《信道編碼技術(shù)》 (2)ppt課件

1、第第4章章 信道編碼技術(shù)信道編碼技術(shù)第第4 4章章 信道編碼技術(shù)信道編碼技術(shù)4.1 離散信道模型離散信道模型4.2 過失控制編碼的根本概念過失控制編碼的根本概念4.3 分組碼分組碼4.4 卷積碼卷積碼第第4章章 信道編碼技術(shù)信道編碼技術(shù)4.1 離散信道模型離散信道模型4.1.1 離散無記憶信道通常通訊系統(tǒng)可以分為發(fā)信機(jī)、 物理信道或傳輸介質(zhì)、 接納機(jī)三大部分,如圖4-1所示。發(fā)信機(jī)由信道編碼器和調(diào)制器組成,接納機(jī)由解調(diào)器和信道譯碼器組成,在圖4-1中,c和g之間是編碼信道,屬于離散信道； d和f之間是調(diào)制信道,屬于模擬信道。對于加性噪聲信道,噪聲和干擾會使傳輸?shù)臄?shù)據(jù)發(fā)生錯誤,因此對數(shù)據(jù)傳輸?shù)目?/p>

2、靠性產(chǎn)生影響。 第第4章章 信道編碼技術(shù)信道編碼技術(shù)圖4-1 通訊系統(tǒng)模型信道編碼b信源調(diào)制c傳輸介質(zhì)de噪聲解調(diào)f信道譯碼ga信宿發(fā)信機(jī)物理信道接收機(jī)調(diào)制信道編碼信道數(shù)據(jù)通信信道第第4章章 信道編碼技術(shù)信道編碼技術(shù)對于輸入和輸出均為離散符號的離散信道,當(dāng)信道中不存在干擾時,離散輸入符號X與輸出符號Y有一一對應(yīng)的關(guān)系。但假設(shè)信道中存在干擾,那么輸入符號與輸出符號之間就不存在一一對應(yīng)的關(guān)系了,而是具有一定的統(tǒng)計相關(guān)性。這個統(tǒng)計特性取決于輸入符號xi和輸出符號yj之間的轉(zhuǎn)移概率P(yj/xi)或P(xj/yi)。假設(shè)發(fā)送的符號集為X=xi， i=1, 2, , L,有L種符號； 接納符號集為Y=y

3、j，j =1, 2, , M,有M種符號。這時離散無記憶信道(DMC, Discrete Memoryless Channel)如圖4-2所示。DMC的轉(zhuǎn)移概率可以用以下矩陣表示： 第第4章章 信道編碼技術(shù)信道編碼技術(shù)x1x2xLy1y2yiyMXY圖4-2 離散L輸入m輸出信道第第4章章 信道編碼技術(shù)信道編碼技術(shù))/()/()/()/()/()/()/()/()/()/(21212211121111LMLLMMxyPxyPxyPxyPxyPxyPxyPxyPxyPxyP(4-1) 所謂無記憶信道,是指每個輸出符號值取決于當(dāng)前的輸入符號,而與其他輸入符號無關(guān)。假設(shè)DMC的輸入選自X符號集的n個

4、符號u1 , u2, , un的序列,相應(yīng)的輸出選自Y符號集的n個符號v1 , v2, , vn的序列,那么結(jié)合條件概率為P(Y1=v1,Y2=v2 , , Yn=vn/X1=u1,X2=u2, , Xn=un)= nkkkXYP1)/(4-2) 第第4章章 信道編碼技術(shù)信道編碼技術(shù)這個表達(dá)式正是無記憶條件的數(shù)學(xué)表述。上述DMC的一個特例就是所謂的無記憶二進(jìn)制對稱信道(BSC, Binary Symmetric Channel),其構(gòu)造如圖4-3所示。對于BSC能夠的符號輸入值的集合X=0,1,能夠的符號輸出值的集合Y=0,1,對應(yīng)的轉(zhuǎn)移概率可以表示為這里， P(1/0)=P(0/1)=p，

5、P(1/1)=P(0/0)=1-p。 ppppxyPii11)/(4-3) 第第4章章 信道編碼技術(shù)信道編碼技術(shù)圖4-3 二進(jìn)制對稱信道01p0輸 入111ppp第第4章章 信道編碼技術(shù)信道編碼技術(shù)4.1.4 信道容量設(shè)離散信道模型如圖4-2所示， 發(fā)送符號xi的概率為P(xi)， 這里i=1， 2， ，L； 接納符號yj的概率為P(yj)，這里j =1，2，M； P(yj/ xi)或P(xj/ yj)表示轉(zhuǎn)移概率。在DMC信道中，輸入與輸出不再是一一對應(yīng)關(guān)系，而是一種隨機(jī)對應(yīng)的統(tǒng)計關(guān)系，這種統(tǒng)計關(guān)系可以用信道上的轉(zhuǎn)移概率進(jìn)展描畫，因此，我們可以利用信道的轉(zhuǎn)移概率來合理地描畫信道遭到的干擾和信

6、道的統(tǒng)計特性。 第第4章章 信道編碼技術(shù)信道編碼技術(shù) 信道容量定義為： )1 (SNRlbBC(b/s)以上為著名的香農(nóng)(Shannon)定理表達(dá)式， 它闡明當(dāng)信號和作用在信道上的起伏噪聲的平均功率給定時， 在一定頻帶寬度B的信道上，實際上單位時間內(nèi)能夠傳輸信息量的極限值。 這樣我們可以看出，信道受B、 n0和S三要素的影響， 只需這三要素確定， 信道也隨之確定。第第4章章 信道編碼技術(shù)信道編碼技術(shù)從式(4-24)可以容易地看到，當(dāng)n0 =0或S=時，信道容量C=。 這是由于n0 =0意味著信道無噪聲， 而S=意味著發(fā)送功率到達(dá)無窮大， 顯然這在任何實踐系統(tǒng)中都是很難實現(xiàn)的。 不過， 這個關(guān)系

7、也通知我們： 假設(shè)要使信道容量增大， 實際上可以經(jīng)過減小n0或增大S來實現(xiàn)。 第第4章章 信道編碼技術(shù)信道編碼技術(shù)那么，增大帶寬B能否可行? 下面就此問題進(jìn)展分析。 首先將式(4-24)改寫為當(dāng)B時， 上式變?yōu)?1 (000nBSlbSnBnSC(4-25) 0000044. 1)1 (limlimnSlbenSnBSlbSnBnSCBB(4-26) 第第4章章 信道編碼技術(shù)信道編碼技術(shù)式(4-26)中的近似利用了關(guān)系式： 。 經(jīng)過上述論述闡明：堅持S/n0一定， 即使信道帶寬B，信道容量也是有限的，這是由于信道帶寬B時， 噪聲功率B n0也趨于無窮大。 通常，把實現(xiàn)了上述極限信息速率的通訊系

8、統(tǒng)稱為理想通訊系統(tǒng)。 但是香農(nóng)定理只證明了理想系統(tǒng)的“存在性，卻沒有指出這種通訊系統(tǒng)的實現(xiàn)方法。 因此， 理想系統(tǒng)只能作為實踐系統(tǒng)的實際極限。 另外， 上述討論都是在信道噪聲為高斯白噪聲前提下進(jìn)展的， 對于其他類型的的噪聲， 香農(nóng)公式需求改良。 44. 1 )1 (1lim0elbxlbxx第第4章章 信道編碼技術(shù)信道編碼技術(shù) 4.2 過失控制編碼的根本概念過失控制編碼的根本概念4.2.1 過失控制方式常用的過失控制方式主要有三種：前向糾錯簡稱FEC、檢錯重發(fā)簡稱ARQ和混合糾錯簡稱HEC，它們的構(gòu)造如圖4-4所示。圖中帶陰影的方框圖表示在該端檢測錯誤。 第第4章章 信道編碼技術(shù)信道編碼技術(shù)圖

9、4-4 過失控制方式(a) 前向糾錯FEC；(b) 檢錯重發(fā)ARQ；(c) 混合糾錯HEC 發(fā)可以糾正錯誤的碼收(a)發(fā)能夠發(fā)現(xiàn)錯誤的碼收(b)應(yīng)答信號發(fā)可以發(fā)現(xiàn)和糾正錯誤的碼收(c)應(yīng)答信號第第4章章 信道編碼技術(shù)信道編碼技術(shù)前向糾錯系統(tǒng)中， 發(fā)送端經(jīng)信道編碼后可以發(fā)出具有糾錯才干的碼組； 接納端譯碼后不僅可以發(fā)現(xiàn)錯誤碼， 而且可以判別錯誤碼的位置并予以自動糾正。 因此， 前向糾錯編碼需求附加較多的冗余碼元， 影響數(shù)據(jù)傳輸效率， 同時其編譯碼設(shè)備比較復(fù)雜。 但是由于不需求反響信道， 實時性較好， 因此這種技術(shù)在單工信道中普遍采用， 例如無線電尋呼中采用的POGSAG編碼。 第第4章章 信道編

10、碼技術(shù)信道編碼技術(shù) 檢錯重發(fā)方式中， 發(fā)送端經(jīng)信道編碼后可以發(fā)出具有檢錯才干的碼組； 接納端收到后經(jīng)檢測假設(shè)發(fā)現(xiàn)傳輸中有錯誤， 那么經(jīng)過反響信道把這一判別結(jié)果反響給發(fā)送端。 然后， 發(fā)送端把前面發(fā)出的信息重新傳送一次， 直到接納端以為曾經(jīng)正確為止。 典型系統(tǒng)原理方框圖如圖4-5所示。 常用的檢錯重發(fā)系統(tǒng)有三種， 即停發(fā)等候重發(fā)、 前往重發(fā)和選擇重發(fā)。第第4章章 信道編碼技術(shù)信道編碼技術(shù)圖4-5 ARQ系統(tǒng)組成方框圖編碼器和緩沖存儲器信源重發(fā)控制雙向信道指令產(chǎn)生器解碼器正確時輸出錯誤時刪除輸出緩沖存儲器收信者第第4章章 信道編碼技術(shù)信道編碼技術(shù)停發(fā)等候重發(fā)系統(tǒng)的發(fā)送端在某一時辰向接納端發(fā)送一個碼

11、組， 接納端收到后經(jīng)檢測假設(shè)未發(fā)現(xiàn)傳輸錯誤， 那么發(fā)送一個認(rèn)可信號(ACK)給發(fā)送端， 發(fā)送端收到ACK信號后再發(fā)下一個碼組； 假設(shè)接納端檢測出錯誤， 那么發(fā)送一個否認(rèn)信號(NAK)， 發(fā)送端收到NAK信號后重發(fā)前一個碼組， 并再次等待ACK和NAK信號。 這種方式效率不高， 但任務(wù)方式簡單， 在計算機(jī)數(shù)據(jù)通訊中仍在運用。 在前往重發(fā)系統(tǒng)中， 發(fā)送端無停頓地送出一個又一個碼組， 不再等待ACK信號，一旦接納端發(fā)現(xiàn)錯誤并發(fā)回NAK信號，那么發(fā)送端從下一個碼組開場重發(fā)前一段N組信號， N的大小取決于信號傳送及處置所帶來的延遲， 這種系統(tǒng)比停發(fā)等候重發(fā)系統(tǒng)有很大的改良， 在許多數(shù)據(jù)傳輸系統(tǒng)中得到運用

12、。 第第4章章 信道編碼技術(shù)信道編碼技術(shù)在選擇重發(fā)系統(tǒng)中，發(fā)送端也是延續(xù)不斷地發(fā)送碼組， 接納端發(fā)現(xiàn)錯誤發(fā)回NAK信號。 與前往重發(fā)系統(tǒng)不同的是，發(fā)送端不是重發(fā)前面的一切碼組， 而是只重發(fā)有錯誤的那一組。顯然，這種選擇重發(fā)系統(tǒng)傳輸效率最高，但控制最為復(fù)雜。此外，前往重發(fā)系統(tǒng)和選擇重發(fā)系統(tǒng)都需求全雙工的鏈路，而停發(fā)等候重發(fā)系統(tǒng)只需求半雙工的鏈路。 第第4章章 信道編碼技術(shù)信道編碼技術(shù)由上述分析可知， ARQ的優(yōu)點主要表如今： 1只需求少量的冗余碼， 就可以得到極低的輸出誤碼率； 2運用的檢錯碼根本上與信道的統(tǒng)計特性無關(guān)， 有一定的自順應(yīng)才干； 3與FEC相比， 信道編譯碼器的復(fù)雜性要低得多。 同

13、時ARQ也存在某些缺乏， 主要表如今： 1需求反向信道， 故不能用于單向傳輸系統(tǒng)，并且實現(xiàn)重發(fā)控制比較復(fù)雜； 2當(dāng)信道干擾增大時，整個系統(tǒng)有能夠處在重發(fā)循環(huán)當(dāng)中， 因此通訊效率低； 3不大適宜于嚴(yán)厲實時傳輸系統(tǒng)。 第第4章章 信道編碼技術(shù)信道編碼技術(shù) 混合糾錯方式是前向糾錯方式和檢錯重發(fā)方式的結(jié)合。在這種系統(tǒng)中接納端不但具有糾正錯誤的才干， 而且對超出糾錯才干的錯誤有檢測才干。 遇到后一種情況時， 系統(tǒng)可以經(jīng)過反響信道要求發(fā)送端重發(fā)一遍。 混和糾錯方式在實時性和譯碼復(fù)雜性方面是前向糾錯和檢錯重發(fā)方式的折衷。 第第4章章 信道編碼技術(shù)信道編碼技術(shù)4.2.2 過失控制編碼分類在過失控制系統(tǒng)中， 信

14、道編碼存在著多種方式， 同時信道編碼也有多種分類方法。 1 按照信道編碼的不同功能， 可以將它分為檢錯碼和糾錯碼。 檢錯碼僅能檢測誤碼， 例如， 在計算機(jī)串口通訊中常用到的奇偶校驗碼等； 糾錯碼可以糾正誤碼， 當(dāng)然同時具有檢錯的才干， 當(dāng)發(fā)現(xiàn)不可糾正的錯誤時可以發(fā)出出錯指示。 2 按照信息碼元和監(jiān)視碼元之間的檢驗關(guān)系， 可以將它分為線性和非線性碼。 假設(shè)信息碼元與監(jiān)視碼元之間的關(guān)系為線性關(guān)系， 即滿足一組線性方程式， 那么稱為線性碼； 否那么， 就稱為非線性碼。 第第4章章 信道編碼技術(shù)信道編碼技術(shù)3按照信息碼元和監(jiān)視碼元之間的約束方式不同， 可以將它分為分組碼和卷積碼。 在分組碼中， 編碼后

15、的碼元序列每n位分為一組， 其中k位信息碼元， r個監(jiān)視位，r=n-k。監(jiān)視碼元僅與本碼組的信息碼元有關(guān)。 卷積碼那么不同， 雖然編碼后序列也可以分為碼組， 但監(jiān)視碼元不但與本信息碼元有關(guān)， 而且與前面碼組的信息碼元也有約束關(guān)系。 4按照信息碼元在編碼后能否堅持原來的方式，可以將它分為系統(tǒng)碼和非系統(tǒng)碼。 在系統(tǒng)碼中， 編碼后的信息碼元堅持原樣不變，而非系統(tǒng)碼中的信息碼元那么發(fā)生了變化。 除了個別情況，系統(tǒng)碼的性能大體上與非系統(tǒng)碼一樣， 同時非系統(tǒng)碼的譯碼較為復(fù)雜， 因此，系統(tǒng)碼得到了廣泛的運用。 第第4章章 信道編碼技術(shù)信道編碼技術(shù)5按照糾正錯誤的類型不同， 可以將它分為糾正隨機(jī)錯誤碼和糾正突

16、發(fā)錯誤碼。 前者主要用于發(fā)生零星獨立錯誤的信道， 而后者用于對付以突發(fā)錯誤為主的信道。 6 按照信道編碼所采用的數(shù)學(xué)方法不同， 可以將它分為代數(shù)碼、 幾何碼和算術(shù)碼。 其中代數(shù)碼是目前開展最為完善的編碼， 線性碼就是代數(shù)碼的一個重要的分支。 除上述信道編碼的分類方法以外， 我們還可以將它分為二進(jìn)制信道編碼和多進(jìn)制信道編碼等等。 同時， 隨著數(shù)字通訊系統(tǒng)的開展， 可以將信道編碼器和調(diào)制器一致同來綜合設(shè)計， 這就是所謂的網(wǎng)格編碼調(diào)制(TCM， Trellis Coded Modulation)。 第第4章章 信道編碼技術(shù)信道編碼技術(shù)4.2.3 檢錯與糾錯的根本原理信道編碼的根本思想就是在被傳送的信

17、息中附加一些監(jiān)視碼元， 在兩者之間建立某種校驗關(guān)系， 當(dāng)這種校驗關(guān)系因傳輸錯誤而遭到破壞時， 可以被發(fā)現(xiàn)， 甚至將錯誤予以糾正， 這種檢錯與糾錯才干是用信息量的冗余度來換取的。下面我們將引見幾個與信道編碼有關(guān)的根本概念。碼長： 碼組中碼元的數(shù)目； 碼重： 碼組中非0位的數(shù)目。對于二進(jìn)制碼來講， 碼重W就是碼元中1的數(shù)目， 例如碼組10100的碼長n=5， 碼重W=2。 碼距： 兩個等長碼組之間對應(yīng)位不同的數(shù)目， 有時也稱做這兩個碼組的漢明間隔， 例如碼組10100與11000它們之間的碼距d=2。 第第4章章 信道編碼技術(shù)信道編碼技術(shù) 最小碼距： 在碼組集合中全體碼組之間間隔的最小數(shù)值。 對于

18、二進(jìn)制碼組而言， 兩個碼組之間的模2相加， 其不同的對應(yīng)位必為1， 一樣的對應(yīng)位必為0， 因此， 兩個碼組之間模2相加得到的信碼組的分量就是這兩個碼組之間的間隔。 碼組之間的最小間隔是衡量該碼組檢錯和糾錯才干的重要根據(jù)， 因此， 最小碼距是信道編碼的一個重要的參數(shù)。 在普通情況下， 對于分組碼的最小漢明間隔d0與檢錯和糾錯才干之間滿足以下關(guān)系： 1 當(dāng)碼組用于檢測錯誤時，假設(shè)要檢測e個錯誤， 那么d0e+1 (4-27) 第第4章章 信道編碼技術(shù)信道編碼技術(shù)這個關(guān)系可以利用圖4-6(a)予以闡明。 在圖中用A和B分別表示兩個碼距為d0的碼組，假設(shè)A發(fā)生e個錯誤， 那么A就變成以A為球心，e為半

19、徑的球面上的碼組，為了能將這些碼組分辨出來， 它們必需間隔其最近的碼組B有一位的差別， 即A和B之間最小間隔為d0e+1。(2) 當(dāng)碼組用于糾正錯誤時,假設(shè)要糾正t個錯誤,那么d02t+1(4-28) 這個關(guān)系可以利用圖4-6(b)予以闡明。 在圖中用A和B分別表示兩個碼距為d0的碼組,假設(shè)A發(fā)生t個錯誤,那么A就變成以A為球心,t為半徑的球面上的碼組； 假設(shè)B發(fā)生t個錯誤,那么B就變成以B為球心,t為半徑的球面上的碼組。 為了在出現(xiàn)t個錯誤之后,仍可以分辨出A和B來,那么,A和B之間間隔應(yīng)大于2t,最小間隔也該當(dāng)使兩球體外表相距為1,即滿足不等式(4-28)。 第第4章章 信道編碼技術(shù)信道編

20、碼技術(shù) 3假設(shè)碼組用于糾t個錯,同時檢e個錯時,那么d0t+e+1(4-29) 這個關(guān)系可以利用圖4-6(c)予以闡明。 在圖中用A和B分別表示兩個碼距為d0的碼組,當(dāng)碼組出現(xiàn)t個或小于t個錯誤時,系統(tǒng)按照糾錯方式任務(wù)；當(dāng)碼組出現(xiàn)大于t個而小于e個錯誤時,系統(tǒng)按照檢錯方式任務(wù)； 假設(shè)A發(fā)生t個錯誤,B發(fā)生e個錯誤時,既要糾A的錯誤,又要檢B的錯誤,那么A和B之間間隔應(yīng)大于t+e,也就是滿足式(4-29)。 第第4章章 信道編碼技術(shù)信道編碼技術(shù)圖4-6 糾檢錯才干的幾何解釋ABed0(a)ABtd0t1(b)ABtd0e1(c)第第4章章 信道編碼技術(shù)信道編碼技術(shù)通常,在信道編碼過程中,監(jiān)視位越

21、多糾錯才干就越強(qiáng),但編碼效率就越低。 假設(shè)碼組中信息位數(shù)為k,監(jiān)視位數(shù)為r,碼長n=k+r,那么編碼效率Rc可以用下式表示： Rc=k/n=(n-r)/n=1-r/n (4-30) 信道編碼的義務(wù)就是要根據(jù)不同的干擾特性,設(shè)計出編碼效率高,糾錯才干強(qiáng)的編碼。 在實踐設(shè)計過程中,需求根據(jù)詳細(xì)目的要求,盡量簡化編碼實踐的復(fù)雜度,節(jié)省設(shè)計費用。 第第4章章 信道編碼技術(shù)信道編碼技術(shù) 4.3 4.3 分組碼分組碼4.3.1 線性分組碼當(dāng)分組碼的信息碼元與監(jiān)視碼元之間的關(guān)系為線性關(guān)系時,這種分組碼就被稱為線性分組碼。 線性分組碼是建立在代數(shù)群論根底之上的,各許用碼的集合構(gòu)成了代數(shù)學(xué)中的群,它們的主要性質(zhì)

22、如下： (1) 恣意兩許用碼之和對于二進(jìn)制碼這個和的含義是模2和仍為一許用碼,也就是說,線性分組碼具有封鎖性； (2) 碼組間的最小碼距等于非零碼的最小碼重。 第第4章章 信道編碼技術(shù)信道編碼技術(shù) 下面經(jīng)過一個例子闡明線性分組碼是如何構(gòu)造的。 設(shè)分組碼(n, k)中k=4,為了可以糾正一位錯誤,要求r3,取r=3,那么n=k+r=7。 因此,可以用a6a5a4a3a2a1a0表示這7個碼元,用S1、 S2、 S3表示由三個監(jiān)視方程計算得到的校正子,并假設(shè)S1、 S2、 S3三位校正子碼組與誤碼位置的關(guān)系如表4-1所示。第第4章章 信道編碼技術(shù)信道編碼技術(shù)表4-1 校正子與誤碼位置第第4章章 信

23、道編碼技術(shù)信道編碼技術(shù)根據(jù)表4-1的對應(yīng)關(guān)系,可以得到以下邏輯關(guān)系式：S1=a6+a5+a4+a2S2=a6+a5+a3+a1 (4-31)S3=a6+a4+a3+a0在進(jìn)展編碼時,設(shè)a6、 a5、 a4、 a3為信息碼元,從表4-1中可以看到,當(dāng)S3S2S1=000時,就闡明碼組在傳輸過程中沒有發(fā)生錯誤,基于這一約束,利用式(4-31),可以得到下面兩種方式的線性方程組： a6+a5+a4+a2 =0 a6+a5+a3+a1 =0 a6+a4+a3+a0 =0 (4-32)第第4章章 信道編碼技術(shù)信道編碼技術(shù) a6+a5+a4 =a2 a6+a5+a3 =a1(4-33) a6+a4+a3

24、=a0根據(jù)上面兩個線性關(guān)系式,可以得到16個許用碼組,如表4-2所示。 第第4章章 信道編碼技術(shù)信道編碼技術(shù)表4-2 許 用 碼 組第第4章章 信道編碼技術(shù)信道編碼技術(shù) 在接納端收到碼組以后,就可以代入式(4-31)計算S1、 S2和S3,假設(shè)全為0,那么闡明傳輸時沒有發(fā)生錯誤,否那么根據(jù)表4-1糾正錯誤。 當(dāng)然對于上述(7, 4)碼而言,最小碼距d0=3,因此,它可以糾正一個錯誤或檢測兩個錯誤,假設(shè)超出這個范圍,糾錯功能就要失敗。 對于式(4-32),可以用矩陣方式表示如下： 0001001111010101100101110123456Taaaaaaa(4-34) 第第4章章 信道編碼技術(shù)

25、信道編碼技術(shù)上式可以記作： HAT=0T或AHT=0,其中, A=a6 a5 a4 a3 a2 a1 a0 (4-35b) 0=0 0 0 (4-35c)rIPH 100111101010110010111(4-35a) 第第4章章 信道編碼技術(shù)信道編碼技術(shù) 或者a2 a1 a0=a6 a5 a4 a3 =a6 a5 a4 a3Q比較式(4-34)和式(4-36)可以看到Q=PT,假設(shè)在Q矩陣的左邊再加上一個kk的單位矩陣,就構(gòu)成了一個新矩陣G： 1101010111111101000101010001100101110001 QIGk(4-37) 第第4章章 信道編碼技術(shù)信道編碼技術(shù)這里G被

26、稱為生成矩陣,利用它可以產(chǎn)生整個碼組: A=MG=a6 a5a4 a3G (4-38)由式(4-37)表示的生成矩陣方式被稱為典型生成矩陣,利用式(4-38)產(chǎn)生的分組碼必為系統(tǒng)碼,也就是信息碼元堅持不變,監(jiān)視碼元附加在其后。 在發(fā)送端,信息碼元M利用式(4-38)實現(xiàn)信道編碼,產(chǎn)生線性分組碼A； 在傳輸過程中有能夠出現(xiàn)誤碼,設(shè)接納到的碼組為B,那么收發(fā)碼組之差為 B-A=bn-1bn-2 b0-an-1 an-2 a0=E=en-1 en-2 e0 (4-39)第第4章章 信道編碼技術(shù)信道編碼技術(shù)這里 0 bi=ai 1 biai, ei=1表示i位有錯, ei=0表示i位無錯。 基于這樣的

27、原那么,接納端利用接納到的碼組B計算校正子： S=BHT=(A+E)HT=AHT+EHT=EHT (4-40)因此,校正子僅與E有關(guān),即錯誤圖樣與校正子之間有確定的關(guān)系。 ei=第第4章章 信道編碼技術(shù)信道編碼技術(shù)在實際中經(jīng)常會遇到的線性分組碼主要有以下兩種： 1. 漢明(Hamming)碼漢明碼既有二進(jìn)制的,也有非二進(jìn)制的,這里僅討論二進(jìn)制漢明碼的性質(zhì)。 二進(jìn)制漢明碼可以表示為 (n, k)=(2m-1, 2m-1-m) (4-41)這里m可取大于等于2的恣意整數(shù),因此,漢明碼的特點如下： 碼長n=2m-1,信息位k=2m-1-m，監(jiān)視位r=m,最小碼距d0=3,糾錯才干t=1。 假設(shè)要產(chǎn)生

28、一個系統(tǒng)漢明碼, 那么可以將矩陣H轉(zhuǎn)換成典型方式的監(jiān)視矩陣,進(jìn)一步利用Q=PT的關(guān)系,得到相應(yīng)的生成矩陣G。 第第4章章 信道編碼技術(shù)信道編碼技術(shù)2. 哈達(dá)碼(Hadamard)碼哈達(dá)碼矩陣Mn是一個由“0和“1構(gòu)成的nn維矩陣n是偶數(shù),矩陣中恣意兩行相比較,都存在n/2個不同的元素,矩陣中有一行是全0行,其他行都包含n/2個“0和n/2個“1。 當(dāng)n=2時,哈達(dá)碼矩陣可表示為 M2= (4-42) 進(jìn)一步可以按照下述規(guī)律由Mn產(chǎn)生哈達(dá)碼矩陣M2n。1000第第4章章 信道編碼技術(shù)信道編碼技術(shù) (4-43)式中, Mn為Mn的互補(bǔ)矩陣,按上述規(guī)律M4和 就可以分別表示為nnnnnMMMMM21

29、001001101011111,0110110010100000422222MMMMMMn(4-44) 4M第第4章章 信道編碼技術(shù)信道編碼技術(shù) 至此,可以利用M4和 的行構(gòu)成一個碼長n=4的二進(jìn)制線性分組碼,該碼由8個碼組構(gòu)成,最小碼距為d0=2。 基于這種方法構(gòu)成的碼稱為哈達(dá)碼。 因此,哈達(dá)碼的長度n=2m,k=lb2n =lb2m+1=m+1, d0 =n/2=2m-1,這里m為正整數(shù)。 4.3.2 循環(huán)碼 循環(huán)碼是線性碼的一個重要子集,是目前研討得最成熟的一類碼。 它有許多特殊的代數(shù)性質(zhì),這些性質(zhì)有助于按所要求的糾錯才干系統(tǒng)地構(gòu)造這類碼,且易于實現(xiàn)； 同時循環(huán)碼的性能也較好,具有較強(qiáng)的

30、檢錯和糾錯才干。 4M第第4章章 信道編碼技術(shù)信道編碼技術(shù)循環(huán)碼最大的特點就是循環(huán)性,所謂循環(huán)性,是指循環(huán)碼中任一許用碼組經(jīng)過循環(huán)移位后,所得到的碼組依然是許用碼組。 假設(shè)(an-1 an-2 a1 a0)為一循環(huán)碼組,那么(an-2an-3 a0 an-1)、 (an-3an-4 an-1an-2)還是許用碼組。 也就是說,不論是左移或是右移,也不論移多少位,其所得的碼組依然是許用的循環(huán)碼組。 為了利用代數(shù)實際研討循環(huán)碼,可以將碼組用代數(shù)多項式來表示,這個多項式被稱為碼多項式,對于許用循環(huán)碼A=(an-1an-2 a1 a0),可以將它的碼多項式表示為A(x)=an-1xn-1+an-2xn

31、-2+a1x+a0 (4-45) 第第4章章 信道編碼技術(shù)信道編碼技術(shù)對于二進(jìn)制碼組,多項式的每個系數(shù)不是0就是1,x僅是碼元位置的標(biāo)志,因此,我們這里并不關(guān)懷x的取值設(shè)上述循環(huán)許用碼組A左循環(huán)一位得到的碼組記作 A1= (an-2an-3 a0 an-1),其碼多項式可以表示為 A (1) (x)=an-2xn-1+an-3xn-2+a0 x+an-1 (4-46) 同理,左移i位的碼組Ai=(an-i-1 an-i-2 an-i+1 an-i),其碼多項式為 A (i) (x)=an-i-1xn-1+an-i-2xn-2+an-i+1x+an-i (4-47)第第4章章 信道編碼技術(shù)信道編

32、碼技術(shù) 利用代數(shù)實際知識,Ai (x)也可以用下式求得： xiA(x)=Q(x)(xn+1)+ Ai (x) (4-48)這里,Q(x)表示xiA(x)除以(xn+1)的商,而Ai (x)表示所得余式。 由上述分析可以得到結(jié)論： 一個長為n的循環(huán)碼,它必為按模(xn+1)運算的一個余式。 這個結(jié)論給出了構(gòu)造許用碼的一種方法,即利用循環(huán)碼的生成多項式可以得到全部碼組。 在循環(huán)碼中,一個(n, k)碼有2k個不同的碼組,假設(shè)用g(x)表示其中前(k-1)位皆為“0的碼組,那么g(x)、xg(x)、 x2g(x)、 、 xk-1g(x)都是碼組,而且這k個碼組線性無關(guān),因此,可以利用它們構(gòu)成循環(huán)碼的

33、生成矩陣,而g(x)被稱為生成多項式。 第第4章章 信道編碼技術(shù)信道編碼技術(shù)可以證明,一個(n, k)循環(huán)碼的生成多項式g(x),必需是一個常數(shù)項不為“0的(n-k)次多項式,而且,這個g(x)還是(n, k)碼中次數(shù)為(n-k)的獨一的一個多項式。由于假設(shè)有兩個,那么由于碼的封鎖性,把這兩個碼相加也應(yīng)該是一個碼組,且此碼組多項式的次數(shù)將小于(n-k),即出現(xiàn)延續(xù)“0的個數(shù)將多于(k-1)的情況,這與(n, k)循環(huán)碼是線性碼的特性相違背,故是不能夠的。 為此,可以得到一個重要的結(jié)論： 一旦生成多項式g(x)確定以后,整個(n, k)循環(huán)碼就被確定了。 基于g(x), 可以進(jìn)一步寫出循環(huán)碼的生

34、成矩陣如下： 第第4章章 信道編碼技術(shù)信道編碼技術(shù)顯然,上式不符合G=Ik Q方式,所以此生成矩陣不是典型方式,不過,可以經(jīng)過簡單的代數(shù)變換將它變成典型矩陣。 )()()()()(21xgxgxxgxxgxxGkk(4-49)第第4章章 信道編碼技術(shù)信道編碼技術(shù)根據(jù)g(x)定義可知,它是(n, k)循環(huán)碼中獨一的一個(n-k)次碼多項式,當(dāng)然也就是該循環(huán)碼的許用碼組。 對g(x)表述的許用碼組進(jìn)展k次左移,會得到同樣的碼組,將這一過程用式(4-48)描畫將得到xkg(x)=Q(x)(xn+1)+g(x) (4-50)上式左邊是一個n次多項式,因此,Q(x)=1,所以可以進(jìn)一步表示為(xn+1)

35、=xkg(x)+g(x)=g(x)(xk+1) (4-51)式(4-51)闡明,生成多項式g(x)是(xn+1)的一個因式,因此,為了確定生成多項式,必需首先對(xn+1)進(jìn)展因式分解,然后再用計算進(jìn)展挑選,計算過程通常運用計算機(jī)來完成。 第第4章章 信道編碼技術(shù)信道編碼技術(shù)對于一個(n, k) 循環(huán)碼,其生成多項式應(yīng)該是(xn+1)的一個(n-k)次因子,任何(n, k)循環(huán)碼的生成多項式g(x),乘上(x+1)后得到生成多項式,可以構(gòu)造(n, k-1)循環(huán)碼。 以(x7+1)因式分解為例： x7+1=(x+1)(x3+x+1)(x3+x2+1) (4-52) 由式(4-52)可構(gòu)成如表4-

36、3所示的(7,k)循環(huán)碼。 第第4章章 信道編碼技術(shù)信道編碼技術(shù)表4-3 (x7+1)因式分解構(gòu)成的(7,k)循環(huán)碼第第4章章 信道編碼技術(shù)信道編碼技術(shù)由表4-3可看出不論是(7, 4)循環(huán)碼還是(7, 3)循環(huán)碼,均包含兩個不同的生成多項式,因此,根據(jù)不同的生成多項式將產(chǎn)生不同的循環(huán)碼組。 上面我們討論了循環(huán)碼的根本原理,下面就系統(tǒng)循環(huán)碼的產(chǎn)生進(jìn)展分析。 第第4章章 信道編碼技術(shù)信道編碼技術(shù)根據(jù)循環(huán)碼的編碼特點,一切循環(huán)碼多項式A(x)都可以被g(x)整除。 根據(jù)這一原理可以得到一個較簡單的系統(tǒng)循環(huán)碼編碼方法： 設(shè)要產(chǎn)生(n, k)循環(huán)碼,m(x)表示信息多項式,那么其次數(shù)必小于k,而xn-

37、km(x)的次數(shù)必小于n,用xn-km(x)除以g(x),可得余數(shù)r(x),r(x)的次數(shù)必小于(n-k),將r(x)加到信息位后作監(jiān)視位,就得到了系統(tǒng)循環(huán)碼,其數(shù)學(xué)描畫如下： (4-53)那么系統(tǒng)循環(huán)碼可以表示為 A(x)=xn-km(x)+r(x) (4-54) )()()()()(xgxrxqxgxmxkn第第4章章 信道編碼技術(shù)信道編碼技術(shù)上述編碼過程,在硬件實現(xiàn)時,可以利用除法電路來實現(xiàn),這里的除法電路采用一些移位存放器和模2加法器來構(gòu)成,下面我們將以(7, 3)循環(huán)碼為例來闡明其詳細(xì)實現(xiàn) 過 程 。 設(shè) 該 ( 7 , 3 ) 循 環(huán) 碼 的 生 成 多 項 式 為g(x)=x4+

38、x2+x+1,那么構(gòu)成的系統(tǒng)循環(huán)碼編碼器如圖4-7所示,圖中有4個移位存放器,一個雙刀雙擲開關(guān)。 當(dāng)信息位輸入時,開關(guān)位置接“1,輸入的信息碼一方面送到除法器進(jìn)展運算,一方面直接輸出； 當(dāng)信息位全部輸出后,開關(guān)位置接“2,這時輸出端接到移位存放器的輸出,除法的余項,也就是監(jiān)視位依次輸出。 當(dāng)信息碼為110時,編碼器的任務(wù)過程如表4-4所示。 第第4章章 信道編碼技術(shù)信道編碼技術(shù)圖4-7 (7, 3)循環(huán)碼編碼器abcd211m輸 入f輸 出e2第第4章章 信道編碼技術(shù)信道編碼技術(shù)表4-4 編碼器的任務(wù)過程第第4章章 信道編碼技術(shù)信道編碼技術(shù)對于接納端譯碼的要求通常有兩個： 檢錯與糾錯。 到達(dá)檢

39、錯目的的譯碼非常簡單,可以根據(jù)式(4-54),經(jīng)過判別接納到的碼組多項式B(x)能否能被生成多項式g(x)整除來完成。 當(dāng)傳輸中未發(fā)生錯誤時,接納的碼組與發(fā)送的碼組一樣,即A(x)=B(x),接納的碼組B(x)必能被g(x)整除； 假設(shè)傳輸中發(fā)生了錯誤,那么A(x) B(x), B(x)不能被g(x)整除。 因此,我們就可以根據(jù)余項能否為零來判別碼組中有無錯碼。 需求指出的是,有錯碼的接納碼組也有能夠被g(x)整除,這時的錯碼就不能檢出了。 這種錯誤被稱為不可檢錯誤,不可檢錯誤的錯碼數(shù)必將超越這種編碼的檢錯才干。 第第4章章 信道編碼技術(shù)信道編碼技術(shù)在接納端為糾錯而采用的譯碼方法自然比檢錯要復(fù)

40、雜許多,因此,對糾錯碼的研討大都集中在譯碼算法上。 我們知道,校正子與錯誤圖樣之間存在某種對應(yīng)關(guān)系。 好像其他線性分組碼,循環(huán)碼的譯碼可以分三步進(jìn)展：1由接納到的碼多項式B(x)計算校正子(伴隨式)多項式S(x)； 2 由校正子多項式S(x)確定錯誤圖樣E(x)； 3 將錯誤圖樣E(x)與B(x)相加,糾正錯誤。 上述第1步運算和檢錯譯碼類似,也就是求解B(x)整除g(x)的余式,第3步也很簡單。 因此,糾錯碼譯碼器的復(fù)雜性主要取決于譯碼過程的第2步。 第第4章章 信道編碼技術(shù)信道編碼技術(shù)4.3.3 BCH碼BCH碼是循環(huán)碼中的一個重要子類,它是以三個研討 和 發(fā) 明 這 種 碼 的 人 名

41、B o s e 、 C h a u d h u r i 和Hocguenghem命名的。 BCH碼不僅具有糾正多個隨機(jī)錯誤的才干,而且具有嚴(yán)密的代數(shù)構(gòu)造,是目前研討得最為透徹的一類碼。 它的生成多項式g(x)與最小碼距之間有親密的關(guān)系,人們可以根據(jù)所要求的糾錯才干t,很容易地構(gòu)造出BCH碼。 BCH碼的譯碼也比較容易實現(xiàn),是線性分組碼中運用最為普遍的一類碼。 第第4章章 信道編碼技術(shù)信道編碼技術(shù) 4.4 卷積碼卷積碼 4.4.1 卷積碼的表述方式卷積碼編碼器的普通方式如圖4-9所示,它包括：一個由N段組成的輸入移位存放器,每段有k級,共Nk位存放器；一組n個模2相加器；一個由n級組成的輸出移位

42、存放器。 對應(yīng)于每段1個比特的輸入序列,輸出n個比特。 由圖可知,n個比特編碼輸出不僅與當(dāng)前的k個比特信息輸入有關(guān),而且與以前的(N-1)k個比特信息輸入有關(guān)。 整個編碼過程可以看成是輸入信息序列與信道編碼器的卷積,卷積碼即由此得名。 通常把N稱為約束長度(留意： 約束長度的定義并無一致的規(guī)范,在有的書和文獻(xiàn)中把nN或(N-1)稱為約束長度),因此,卷積碼通?？梢员硎緸?n,k,N),它的編碼效率為Rck/n。 第第4章章 信道編碼技術(shù)信道編碼技術(shù)圖4-9 卷積碼編碼器的普通方式k21輸入序列kk21k21Nk 級n213輸出序列第第4章章 信道編碼技術(shù)信道編碼技術(shù)為了引見幾種簡單的卷積碼表述

43、方法,我們將以圖4-10所示的(2,1,3)卷積碼為例進(jìn)展分析。 第第4章章 信道編碼技術(shù)信道編碼技術(shù)圖4-10 2,1,3卷積碼編碼器mj輸入序列m1m2mjmj1mj2輸出序列x1 , jx2 , j第第4章章 信道編碼技術(shù)信道編碼技術(shù)1. 樹狀圖在(2,1,3)卷積碼編碼器當(dāng)中,輸出移位存放器用轉(zhuǎn)換開關(guān)替代,每輸入一個位信息,經(jīng)編碼產(chǎn)生兩位輸出。 假設(shè)移位存放器的起始形狀為全0,當(dāng)?shù)谝粋€輸入位為0時,輸出為00； 假設(shè)輸入比特為1,那么輸出比特為11。 隨著第二個位的輸入,第一位右移一位,此時輸出比特同時受當(dāng)前輸入位和前一個輸入位的影響。 第三位輸入時,第一、 二位分別右移一位,同時輸出

44、兩個由這三位移位存放器存儲內(nèi)容所共同決議的比特。 當(dāng)?shù)谒奈惠斎霑r,第一位移出移位存放器而消逝。 移位過程能夠產(chǎn)生的各種序列可以用圖4-11所示的樹狀圖來表示。 樹狀圖從節(jié)點a開場畫,此時移位存放器形狀(即存儲內(nèi)容)為00。第第4章章 信道編碼技術(shù)信道編碼技術(shù)00aab110010cbd0111a0000acb111010cdd0101b11a0000aab110010cbd0111c00acb111010cdd0101db11a圖4-11 2，1，3卷積碼的樹狀表示第第4章章 信道編碼技術(shù)信道編碼技術(shù)當(dāng)?shù)谝粋€輸入位m10時,輸出位x1, 1x2, 100； 當(dāng)m11時,輸出位x1, 1x2,

45、111； 因此從a點出發(fā)有兩條分支(樹叉)可以選擇,也就是m10時取上面一條分支,m11時取下面一條分支。 當(dāng)輸入第二位時,移位存放器右移一位后,在上分支情況下,移位存放器的形狀仍為00,下分支的形狀那么為01,把01形狀記作b。 當(dāng)新的一位輸入時,隨著移位存放器形狀和輸入位的不同,樹狀圖繼續(xù)分叉成4條分支,兩條向上,兩條向下。 上分支對應(yīng)于輸入0形狀,下分支對應(yīng)于輸入1形狀。 如此繼續(xù)下去,即可得到圖4-11所示的二叉樹圖形。 樹狀圖中,每條樹叉上所標(biāo)注的碼元為輸出形狀,每個節(jié)點上標(biāo)注的a、 b、 c、 d表示移位存放器的形狀,也就是以前輸入的信息,a形狀表示mj-2mj-100,b形狀表示

46、mj-2mj-101,c形狀表示mj-2mj-110,d形狀表示mj-2mj-111。 顯然,對于第j個輸入位,就有2j條分支,但是在j=N3時,樹狀圖的節(jié)點自上而下開場反復(fù)出現(xiàn)這4種形狀。 第第4章章 信道編碼技術(shù)信道編碼技術(shù)2. 網(wǎng)格圖從卷積碼的樹狀圖中可以看到,樹狀圖的節(jié)點自上而下會出現(xiàn)反復(fù)特性,為此,我們可以得到一種更為緊湊的圖形表示方法,即網(wǎng)格圖法,詳細(xì)情況見圖4-12。 在網(wǎng)格圖中,把碼樹中具有一樣形狀的節(jié)點合并在一同,碼樹中的上分支對應(yīng)輸入0用實線表示,下分支對應(yīng)輸入1用虛線表示。 網(wǎng)格圖中分支上標(biāo)注的碼元為對應(yīng)的輸出,自上而下4行節(jié)點分別表示a、 b、 c、 d四種形狀。 普通

47、情況下應(yīng)有2N-1種形狀,從第N節(jié)開場,網(wǎng)格圖圖形開場反復(fù)而完全一樣。 第第4章章 信道編碼技術(shù)信道編碼技術(shù)圖4-12 2, 1, 3卷積碼的網(wǎng)絡(luò)圖表示0000000000111111111110狀態(tài)a00b01c10d1110101001010101010101000000101111111010第第4章章 信道編碼技術(shù)信道編碼技術(shù)3. 形狀圖由圖4-11可以看到,對于每一個節(jié)點當(dāng)前形狀a、 b、 c、 d,根據(jù)不同的輸入將進(jìn)入不同的形狀,基于這一原理,我們可以構(gòu)造出當(dāng)前形狀與下一形狀之間的形狀轉(zhuǎn)換圖,也可以稱之為卷積碼的形狀圖。 在圖4-13中實線表示信息位為0的途徑,虛線表示信息位為1的

48、途徑,并在途徑上寫出相應(yīng)的輸出碼元。 當(dāng)然,假設(shè)將形狀圖在時間上展開,便可以得到前面講到的網(wǎng)格圖。 第第4章章 信道編碼技術(shù)信道編碼技術(shù)圖4-13 2,1,3卷積碼的形狀圖adcb1000001011011101狀態(tài)a00b01c10d11第第4章章 信道編碼技術(shù)信道編碼技術(shù)假設(shè)利用圖4-10所示的卷積碼編碼器對輸入序列110111001000進(jìn)展編碼,我們就可以用上述3種方法當(dāng)中的恣意一種來分析編碼器的輸出序列和形狀變化途徑。 在這里運用卷積碼的網(wǎng)格圖表示法進(jìn)展分析。 假設(shè)起始形狀為a,那么可以得到圖4-14所示的結(jié)論。 第第4章章 信道編碼技術(shù)信道編碼技術(shù)圖4-14 2,1,3卷積碼的編碼

49、過程及途徑a輸出碼狀態(tài)輸入碼111b11011d010c001b011d101d010c110a111b100c110a000a0001010001100111111011第第4章章 信道編碼技術(shù)信道編碼技術(shù)經(jīng)過上述分析以及對詳細(xì)實例的研討,我們可以得到(n,k,N)卷積碼的一些根本特性： 1 對于每組k位的輸入,利用卷積碼編碼后將得到n位的輸出； 2 樹狀圖中每個節(jié)點可引出2k條分支； 3 網(wǎng)格圖和形狀圖都有2k(N-1) 種能夠的形狀,每個形狀可以引出2k條分支,同時也有2k條分支從其他形狀或本形狀引入； 4 在任何情況下,只需卷積碼編碼器一確定,相應(yīng)的樹狀圖、 網(wǎng)格圖和形狀圖都將確定,與輸入的碼序列無關(guān)。 第第4章章 信道編碼技術(shù)信道編碼技術(shù)4.4.2 二進(jìn)制卷積碼的間隔特性我們知道,在分組碼中碼距(Hamming距)與糾錯才干有親密關(guān)系,生成一種分組碼時應(yīng)使碼組之間的間隔盡能夠大。 常以最大的最小碼距作為糾錯才干的度量。 卷積碼中也同樣存在碼距的概念,通常運用的碼距有兩種： 最小碼距dmin和自在碼距dfr