第4章信道編碼技術(shù)

1、第第4章章 信道編碼技術(shù)信道編碼技術(shù)第第4章章 信道編碼技術(shù)信道編碼技術(shù)4.1 離散信道模型離散信道模型4.2 差錯控制編碼的基本概念差錯控制編碼的基本概念4.3 分組碼分組碼4.4 卷積碼卷積碼第第4章章 信道編碼技術(shù)信道編碼技術(shù)4.1 離散信道模型離散信道模型4.1.1 離散無記憶信道通常通信系統(tǒng)可以分為發(fā)信機、 物理信道或傳輸介質(zhì)、 接收機三大部分,如圖4-1所示。發(fā)信機由信道編碼器和調(diào)制器組成,接收機由解調(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ā)信機物理信道接收機調(diào)制信道編碼信道數(shù)據(jù)通信信道第第4章章 信道編碼技術(shù)信道編碼技術(shù)對于輸入和輸出均為離散符號的離散信道,當(dāng)信道中不存在干擾時,離散輸入符號X與輸出符號Y有一一對應(yīng)的關(guān)系。但若信道中存在干擾,則輸入符號與輸出符號之間就不存在一一對應(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=yj，j

3、=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)。若DMC的輸入選自X符號集的n個符號u1

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

5、=P(0/0)=1-p。 ppppxyPii11)/(4-3) 第第4章章 信道編碼技術(shù)信道編碼技術(shù)圖4-3 二進制對稱信道01 p0輸入111 ppp第第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)系，而是一種隨機對應(yīng)的統(tǒng)計關(guān)系，這種統(tǒng)計關(guān)系可以用信道上的轉(zhuǎn)移概率進行描述，因此，我們可以利用信道的轉(zhuǎn)移概率來合理地描述信道受到的干擾和信道的統(tǒng)計特

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

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

8、信系統(tǒng)。 但是香農(nóng)定理只證明了理想系統(tǒng)的“存在性”，卻沒有指出這種通信系統(tǒng)的實現(xiàn)方法。 因此， 理想系統(tǒng)只能作為實際系統(tǒng)的理論極限。 另外， 上述討論都是在信道噪聲為高斯白噪聲前提下進行的， 對于其他類型的的噪聲， 香農(nóng)公式需要改進。 44. 1 )1 (1lim0elbxlbxx第第4章章 信道編碼技術(shù)信道編碼技術(shù) 4.2 差錯控制編碼的基本概念差錯控制編碼的基本概念4.2.1 差錯控制方式常用的差錯控制方式主要有三種：前向糾錯（簡稱FEC）、檢錯重發(fā)（簡稱ARQ）和混合糾錯（簡稱HEC），它們的結(jié)構(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ù)在單工信道

10、中普遍采用， 例如無線電尋呼中采用的POGSAG編碼。 第第4章章 信道編碼技術(shù)信道編碼技術(shù) 檢錯重發(fā)方式中， 發(fā)送端經(jīng)信道編碼后可以發(fā)出具有檢錯能力的碼組； 接收端收到后經(jīng)檢測如果發(fā)現(xiàn)傳輸中有錯誤， 則通過反饋信道把這一判斷結(jié)果反饋給發(fā)送端。 然后， 發(fā)送端把前面發(fā)出的信息重新傳送一次， 直到接收端認(rèn)為已經(jīng)正確為止。 典型系統(tǒng)原理方框圖如圖4-5所示。 常用的檢錯重發(fā)系統(tǒng)有三種， 即停發(fā)等候重發(fā)、 返回重發(fā)和選擇重發(fā)。第第4章章 信道編碼技術(shù)信道編碼技術(shù)圖4-5 ARQ系統(tǒng)組成方框圖編 碼 器 和緩 沖 存 儲 器信源重 發(fā) 控 制雙向信道指 令 產(chǎn) 生 器解 碼 器正 確 時 輸 出錯 誤

11、 時 刪 除輸 出 緩 沖存 儲 器收信者第第4章章 信道編碼技術(shù)信道編碼技術(shù)停發(fā)等候重發(fā)系統(tǒng)的發(fā)送端在某一時刻向接收端發(fā)送一個碼組， 接收端收到后經(jīng)檢測若未發(fā)現(xiàn)傳輸錯誤， 則發(fā)送一個認(rèn)可信號(ACK)給發(fā)送端， 發(fā)送端收到ACK信號后再發(fā)下一個碼組； 如果接收端檢測出錯誤， 則發(fā)送一個否認(rèn)信號(NAK)， 發(fā)送端收到NAK信號后重發(fā)前一個碼組， 并再次等待ACK和NAK信號。 這種方式效率不高， 但工作方式簡單， 在計算機數(shù)據(jù)通信中仍在使用。 在返回重發(fā)系統(tǒng)中， 發(fā)送端無停頓地送出一個又一個碼組， 不再等待ACK信號，一旦接收端發(fā)現(xiàn)錯誤并發(fā)回NAK信號，則發(fā)送端從下一個碼組開始重發(fā)前一段N組

12、信號， N的大小取決于信號傳遞及處理所帶來的延遲， 這種系統(tǒng)比停發(fā)等候重發(fā)系統(tǒng)有很大的改進， 在許多數(shù)據(jù)傳輸系統(tǒng)中得到應(yīng)用。 第第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)點主要表現(xiàn)在： （1）只需要少量的冗余碼， 就可以得到極低的輸出誤

13、碼率； （2）使用的檢錯碼基本上與信道的統(tǒng)計特性無關(guān)， 有一定的自適應(yīng)能力； （3）與FEC相比， 信道編譯碼器的復(fù)雜性要低得多。 同時ARQ也存在某些不足， 主要表現(xiàn)在： （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)可以通過反饋信道要求發(fā)送端重發(fā)一遍。 混和糾錯方

14、式在實時性和譯碼復(fù)雜性方面是前向糾錯和檢錯重發(fā)方式的折衷。 第第4章章 信道編碼技術(shù)信道編碼技術(shù)4.2.2 差錯控制編碼分類在差錯控制系統(tǒng)中， 信道編碼存在著多種形式， 同時信道編碼也有多種分類方法。 （1） 按照信道編碼的不同功能， 可以將它分為檢錯碼和糾錯碼。 檢錯碼僅能檢測誤碼， 例如， 在計算機串口通信中常用到的奇偶校驗碼等； 糾錯碼可以糾正誤碼， 當(dāng)然同時具有檢錯的能力， 當(dāng)發(fā)現(xiàn)不可糾正的錯誤時可以發(fā)出出錯指示。 （2） 按照信息碼元和監(jiān)督碼元之間的檢驗關(guān)系， 可以將它分為線性和非線性碼。 若信息碼元與監(jiān)督碼元之間的關(guān)系為線性關(guān)系， 即滿足一組線性方程式， 則稱為線性碼； 否則， 就

15、稱為非線性碼。 第第4章章 信道編碼技術(shù)信道編碼技術(shù)（3）按照信息碼元和監(jiān)督碼元之間的約束方式不同， 可以將它分為分組碼和卷積碼。 在分組碼中， 編碼后的碼元序列每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)碼相同， 同時非系

16、統(tǒng)碼的譯碼較為復(fù)雜， 因此，系統(tǒng)碼得到了廣泛的應(yīng)用。 第第4章章 信道編碼技術(shù)信道編碼技術(shù)（5）按照糾正錯誤的類型不同， 可以將它分為糾正隨機錯誤碼和糾正突發(fā)錯誤碼。 前者主要用于發(fā)生零星獨立錯誤的信道， 而后者用于對付以突發(fā)錯誤為主的信道。 （6） 按照信道編碼所采用的數(shù)學(xué)方法不同， 可以將它分為代數(shù)碼、 幾何碼和算術(shù)碼。 其中代數(shù)碼是目前發(fā)展最為完善的編碼， 線性碼就是代數(shù)碼的一個重要的分支。 除上述信道編碼的分類方法以外， 我們還可以將它分為二進制信道編碼和多進制信道編碼等等。 同時， 隨著數(shù)字通信系統(tǒng)的發(fā)展， 可以將信道編碼器和調(diào)制器統(tǒng)一起來綜合設(shè)計， 這就是所謂的網(wǎng)格編碼調(diào)制(TCM

17、， Trellis Coded Modulation)。 第第4章章 信道編碼技術(shù)信道編碼技術(shù)4.2.3 檢錯與糾錯的基本原理信道編碼的基本思想就是在被傳送的信息中附加一些監(jiān)督碼元， 在兩者之間建立某種校驗關(guān)系， 當(dāng)這種校驗關(guān)系因傳輸錯誤而受到破壞時， 可以被發(fā)現(xiàn)， 甚至將錯誤予以糾正， 這種檢錯與糾錯能力是用信息量的冗余度來換取的。下面我們將介紹幾個與信道編碼有關(guān)的基本概念。碼長： 碼組中碼元的數(shù)目； 碼重： 碼組中非0位的數(shù)目。對于二進制碼來講， 碼重W就是碼元中1的數(shù)目， 例如碼組10100的碼長n=5， 碼重W=2。 碼距： 兩個等長碼組之間對應(yīng)位不同的數(shù)目， 有時也稱做這兩個碼組的漢

18、明距離， 例如碼組10100與11000它們之間的碼距d=2。 第第4章章 信道編碼技術(shù)信道編碼技術(shù) 最小碼距： 在碼組集合中全體碼組之間距離的最小數(shù)值。 對于二進制碼組而言， 兩個碼組之間的模2相加， 其不同的對應(yīng)位必為1， 相同的對應(yīng)位必為0， 因此， 兩個碼組之間模2相加得到的信碼組的重量就是這兩個碼組之間的距離。 碼組之間的最小距離是衡量該碼組檢錯和糾錯能力的重要依據(jù)， 因此， 最小碼距是信道編碼的一個重要的參數(shù)。 在一般情況下， 對于分組碼的最小漢明距離d0與檢錯和糾錯能力之間滿足下列關(guān)系： （1） 當(dāng)碼組用于檢測錯誤時，如果要檢測e個錯誤， 那么d0e+1 (4-27) 第第4章章

19、 信道編碼技術(shù)信道編碼技術(shù)這個關(guān)系可以利用圖4-6(a)予以說明。 在圖中用A和B分別表示兩個碼距為d0的碼組，若A發(fā)生e個錯誤， 則A就變成以A為球心，e為半徑的球面上的碼組，為了能將這些碼組分辨出來， 它們必須距離其最近的碼組B有一位的差別， 即A和B之間最小距離為d0e+1。(2) 當(dāng)碼組用于糾正錯誤時,如果要糾正t個錯誤,那么d02t+1(4-28) 這個關(guān)系可以利用圖4-6(b)予以說明。 在圖中用A和B分別表示兩個碼距為d0的碼組,若A發(fā)生t個錯誤,則A就變成以A為球心,t為半徑的球面上的碼組； 若B發(fā)生t個錯誤,則B就變成以B為球心,t為半徑的球面上的碼組。 為了在出現(xiàn)t個錯誤之

20、后,仍能夠分辨出A和B來,那么,A和B之間距離應(yīng)大于2t,最小距離也應(yīng)當(dāng)使兩球體表面相距為1,即滿足不等式(4-28)。 第第4章章 信道編碼技術(shù)信道編碼技術(shù) （3）如果碼組用于糾t個錯,同時檢e個錯時,那么d0t+e+1(4-29) 這個關(guān)系可以利用圖4-6(c)予以說明。 在圖中用A和B分別表示兩個碼距為d0的碼組,當(dāng)碼組出現(xiàn)t個或小于t個錯誤時,系統(tǒng)按照糾錯方式工作；當(dāng)碼組出現(xiàn)大于t個而小于e個錯誤時,系統(tǒng)按照檢錯方式工作； 若A發(fā)生t個錯誤,B發(fā)生e個錯誤時,既要糾A的錯誤,又要檢B的錯誤,則A和B之間距離應(yīng)大于t+e,也就是滿足式(4-29)。 第第4章章 信道編碼技術(shù)信道編碼技術(shù)圖

21、4-6 糾（檢）錯能力的幾何解釋ABed0(a)ABtd0t1(b)ABtd0e1(c)第第4章章 信道編碼技術(shù)信道編碼技術(shù)通常,在信道編碼過程中,監(jiān)督位越多糾錯能力就越強,但編碼效率就越低。 若碼組中信息位數(shù)為k,監(jiān)督位數(shù)為r,碼長n=k+r,則編碼效率Rc可以用下式表示： Rc=k/n=(n-r)/n=1-r/n (4-30) 信道編碼的任務(wù)就是要根據(jù)不同的干擾特性,設(shè)計出編碼效率高,糾錯能力強的編碼。 在實際設(shè)計過程中,需要根據(jù)具體指標(biāo)要求,盡量簡化編碼實際的復(fù)雜度,節(jié)省設(shè)計費用。 第第4章章 信道編碼技術(shù)信道編碼技術(shù) 4.3 4.3 分組碼分組碼4.3.1 線性分組碼當(dāng)分組碼的信息碼元

22、與監(jiān)督碼元之間的關(guān)系為線性關(guān)系時,這種分組碼就被稱為線性分組碼。 線性分組碼是建立在代數(shù)群論基礎(chǔ)之上的,各許用碼的集合構(gòu)成了代數(shù)學(xué)中的群,它們的主要性質(zhì)如下： (1) 任意兩許用碼之和（對于二進制碼這個和的含義是模2和）仍為一許用碼,也就是說,線性分組碼具有封閉性； (2) 碼組間的最小碼距等于非零碼的最小碼重。 第第4章章 信道編碼技術(shù)信道編碼技術(shù) 下面通過一個例子說明線性分組碼是如何構(gòu)造的。 設(shè)分組碼(n, k)中k=4,為了能夠糾正一位錯誤,要求r3,取r=3,則n=k+r=7。 因此,可以用a6a5a4a3a2a1a0表示這7個碼元,用S1、 S2、 S3表示由三個監(jiān)督方程計算得到的校

23、正子,并假設(shè)S1、 S2、 S3三位校正子碼組與誤碼位置的關(guān)系如表4-1所示。第第4章章 信道編碼技術(shù)信道編碼技術(shù)表4-1 校正子與誤碼位置第第4章章 信道編碼技術(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在進行編碼時,設(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+a

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

25、32),可以用矩陣形式表示如下： 0001001111010101100101110123456Taaaaaaa(4-34) 第第4章章 信道編碼技術(shù)信道編碼技術(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,如果在Q矩陣的左邊再加上一個kk的單位矩陣,就形成了一個新矩陣G：

26、 1101010111111101000101010001100101110001 QIGk(4-37) 第第4章章 信道編碼技術(shù)信道編碼技術(shù)這里G被稱為生成矩陣,利用它可以產(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 e

27、0 (4-39)第第4章章 信道編碼技術(shù)信道編碼技術(shù)這里 0 bi=ai 1 biai, ei=1表示i位有錯, ei=0表示i位無錯。 基于這樣的原則,接收端利用接收到的碼組B計算校正子： S=BHT=(A+E)HT=AHT+EHT=EHT(4-40)因此,校正子僅與E有關(guān),即錯誤圖樣與校正子之間有確定的關(guān)系。 ei=第第4章章 信道編碼技術(shù)信道編碼技術(shù)在實踐中經(jīng)常會遇到的線性分組碼主要有以下兩種： 1. 漢明(Hamming)碼漢明碼既有二進制的,也有非二進制的,這里僅討論二進制漢明碼的性質(zhì)。 二進制漢明碼可以表示為 (n, k)=(2m-1, 2m-1-m) (4-41)這里m可取大于等

28、于2的任意整數(shù),因此,漢明碼的特點如下： 碼長n=2m-1,信息位k=2m-1-m，監(jiān)督位r=m,最小碼距d0=3,糾錯能力t=1。 如果要產(chǎn)生一個系統(tǒng)漢明碼, 那么可以將矩陣H轉(zhuǎn)換成典型形式的監(jiān)督矩陣,進一步利用Q=PT的關(guān)系,得到相應(yīng)的生成矩陣G。 第第4章章 信道編碼技術(shù)信道編碼技術(shù)2. 哈達碼(Hadamard)碼哈達碼矩陣Mn是一個由“0”和“1”構(gòu)成的nn維矩陣（n是偶數(shù)）,矩陣中任意兩行相比較,都存在n/2個不同的元素,矩陣中有一行是全0行,其他行都包含n/2個“0”和n/2個“1”。 當(dāng)n=2時,哈達碼矩陣可表示為 M2= (4-42) 進一步可以按照下述規(guī)律由Mn產(chǎn)生哈達碼矩

29、陣M2n。1000第第4章章 信道編碼技術(shù)信道編碼技術(shù) (4-43)式中, Mn為Mn的互補矩陣,按上述規(guī)律M4和 就可以分別表示為nnnnnMMMMM21001001101011111,0110110010100000422222MMMMMMn(4-44) 4M第第4章章 信道編碼技術(shù)信道編碼技術(shù) 至此,可以利用M4和 的行構(gòu)成一個碼長n=4的二進制線性分組碼,該碼由8個碼組構(gòu)成,最小碼距為d0=2。 基于這種方法構(gòu)成的碼稱為哈達碼。 因此,哈達碼的長度n=2m,k=lb2n =lb2m+1=m+1, d0 =n/2=2m-1,這里m為正整數(shù)。 4.3.2 循環(huán)碼 循環(huán)碼是線性碼的一個重要子

30、集,是目前研究得最成熟的一類碼。 它有許多特殊的代數(shù)性質(zhì),這些性質(zhì)有助于按所要求的糾錯能力系統(tǒng)地構(gòu)造這類碼,且易于實現(xiàn)； 同時循環(huán)碼的性能也較好,具有較強的檢錯和糾錯能力。 4M第第4章章 信道編碼技術(shù)信道編碼技術(shù)循環(huán)碼最大的特點就是循環(huán)性,所謂循環(huán)性,是指循環(huán)碼中任一許用碼組經(jīng)過循環(huán)移位后,所得到的碼組仍然是許用碼組。 若(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ù)多項

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

32、 an-i),其碼多項式為 A (i) (x)=an-i-1xn-1+an-i-2xn-2+an-i+1x+an-i (4-47)第第4章章 信道編碼技術(shù)信道編碼技術(shù) 利用代數(shù)理論知識,A（i） (x)也可以用下式求得： xiA(x)=Q(x)(xn+1)+ A（i） (x) (4-48)這里,Q(x)表示xiA(x)除以(xn+1)的商,而A（i） (x)表示所得余式。 由上述分析可以得到結(jié)論： 一個長為n的循環(huán)碼,它必為按模(xn+1)運算的一個余式。 這個結(jié)論給出了構(gòu)造許用碼的一種方法,即利用循環(huán)碼的生成多項式可以得到全部碼組。 在循環(huán)碼中,一個(n, k)碼有2k個不同的碼組,若用g(

33、x)表示其中前(k-1)位皆為“0”的碼組,則g(x)、xg(x)、 x2g(x)、 、 xk-1g(x)都是碼組,而且這k個碼組線性無關(guān),因此,可以利用它們構(gòu)成循環(huán)碼的生成矩陣,而g(x)被稱為生成多項式。 第第4章章 信道編碼技術(shù)信道編碼技術(shù)可以證明,一個(n, k)循環(huán)碼的生成多項式g(x),必須是一個常數(shù)項不為“0”的(n-k)次多項式,而且,這個g(x)還是(n, k)碼中次數(shù)為(n-k)的惟一的一個多項式。因為如果有兩個,則由于碼的封閉性,把這兩個碼相加也應(yīng)該是一個碼組,且此碼組多項式的次數(shù)將小于(n-k),即出現(xiàn)連續(xù)“0”的個數(shù)將多于(k-1)的情況,這與(n, k)循環(huán)碼是線性

34、碼的特性相違背,故是不可能的。 為此,可以得到一個重要的結(jié)論： 一旦生成多項式g(x)確定以后,整個(n, k)循環(huán)碼就被確定了。 基于g(x), 可以進一步寫出循環(huán)碼的生成矩陣如下： 第第4章章 信道編碼技術(shù)信道編碼技術(shù)顯然,上式不符合G=Ik Q形式,所以此生成矩陣不是典型形式,不過,可以通過簡單的代數(shù)變換將它變成典型矩陣。 )()()()()(21xgxgxxgxxgxxGkk(4-49)第第4章章 信道編碼技術(shù)信道編碼技術(shù)根據(jù)g(x)定義可知,它是(n, k)循環(huán)碼中惟一的一個(n-k)次碼多項式,當(dāng)然也就是該循環(huán)碼的許用碼組。 對g(x)表述的許用碼組進行k次左移,會得到同樣的碼組,

35、將這一過程用式(4-48)描述將得到xkg(x)=Q(x)(xn+1)+g(x) (4-50)上式左邊是一個n次多項式,因此,Q(x)=1,所以可以進一步表示為(xn+1)=xkg(x)+g(x)=g(x)(xk+1) (4-51)式(4-51)表明,生成多項式g(x)是(xn+1)的一個因式,因此,為了確定生成多項式,必須首先對(xn+1)進行因式分解,然后再用計算進行篩選,計算過程通常使用計算機來完成。 第第4章章 信道編碼技術(shù)信道編碼技術(shù)對于一個(n, k) 循環(huán)碼,其生成多項式應(yīng)該是(xn+1)的一個(n-k)次因子,任何(n, k)循環(huán)碼的生成多項式g(x),乘上(x+1)后得到生成

36、多項式,可以構(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-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)生進行分析。 第第4章章 信道編碼技術(shù)信道編碼技術(shù)根據(jù)循環(huán)碼的編碼特點,所有循環(huán)碼

37、多項式A(x)都可以被g(x)整除。 根據(jù)這一原理可以得到一個較簡單的系統(tǒng)循環(huán)碼編碼方法： 設(shè)要產(chǎn)生(n, k)循環(huán)碼,m(x)表示信息多項式,則其次數(shù)必小于k,而xn-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),這里的除法電路采用一些移位寄存

38、器和模2加法器來構(gòu)成,下面我們將以(7, 3)循環(huán)碼為例來說明其具體實現(xiàn) 過 程 。 設(shè) 該 ( 7 , 3 ) 循 環(huán) 碼 的 生 成 多 項 式 為g(x)=x4+x2+x+1,則構(gòu)成的系統(tǒng)循環(huán)碼編碼器如圖4-7所示,圖中有4個移位寄存器,一個雙刀雙擲開關(guān)。 當(dāng)信息位輸入時,開關(guān)位置接“1”,輸入的信息碼一方面送到除法器進行運算,一方面直接輸出； 當(dāng)信息位全部輸出后,開關(guān)位置接“2”,這時輸出端接到移位寄存器的輸出,除法的余項,也就是監(jiān)督位依次輸出。 當(dāng)信息碼為110時,編碼器的工作過程如表4-4所示。 第第4章章 信道編碼技術(shù)信道編碼技術(shù)圖4-7 (7, 3)循環(huán)碼編碼器abcd211m

39、輸入f輸出e2第第4章章 信道編碼技術(shù)信道編碼技術(shù)表4-4 編碼器的工作過程第第4章章 信道編碼技術(shù)信道編碼技術(shù)對于接收端譯碼的要求通常有兩個： 檢錯與糾錯。 達到檢錯目的的譯碼十分簡單,可以依據(jù)式(4-54),通過判斷接收到的碼組多項式B(x)是否能被生成多項式g(x)整除來完成。 當(dāng)傳輸中未發(fā)生錯誤時,接收的碼組與發(fā)送的碼組相同,即A(x)=B(x),接收的碼組B(x)必能被g(x)整除； 若傳輸中發(fā)生了錯誤,則A(x) B(x), B(x)不能被g(x)整除。 因此,我們就可以根據(jù)余項是否為零來判斷碼組中有無錯碼。 需要指出的是,有錯碼的接收碼組也有可能被g(x)整除,這時的錯碼就不能檢

40、出了。 這種錯誤被稱為不可檢錯誤,不可檢錯誤的錯碼數(shù)必將超過這種編碼的檢錯能力。 第第4章章 信道編碼技術(shù)信道編碼技術(shù)在接收端為糾錯而采用的譯碼方法自然比檢錯要復(fù)雜許多,因此,對糾錯碼的研究大都集中在譯碼算法上。 我們知道,校正子與錯誤圖樣之間存在某種對應(yīng)關(guān)系。 如同其他線性分組碼,循環(huán)碼的譯碼可以分三步進行：（1）由接收到的碼多項式B(x)計算校正子(伴隨式)多項式S(x)； （2） 由校正子多項式S(x)確定錯誤圖樣E(x)； （3） 將錯誤圖樣E(x)與B(x)相加,糾正錯誤。 上述第（1）步運算和檢錯譯碼類似,也就是求解B(x)整除g(x)的余式,第（3）步也很簡單。 因此,糾錯碼譯碼

41、器的復(fù)雜性主要取決于譯碼過程的第（2）步。 第第4章章 信道編碼技術(shù)信道編碼技術(shù)4.3.3 BCH碼BCH碼是循環(huán)碼中的一個重要子類,它是以三個研究 和 發(fā) 明 這 種 碼 的 人 名 B o s e 、 C h a u d h u r i 和Hocguenghem命名的。 BCH碼不僅具有糾正多個隨機錯誤的能力,而且具有嚴(yán)密的代數(shù)結(jié)構(gòu),是目前研究得最為透徹的一類碼。 它的生成多項式g(x)與最小碼距之間有密切的關(guān)系,人們可以根據(jù)所要求的糾錯能力t,很容易地構(gòu)造出BCH碼。 BCH碼的譯碼也比較容易實現(xiàn),是線性分組碼中應(yīng)用最為普遍的一類碼。 第第4章章 信道編碼技術(shù)信道編碼技術(shù) 4.4 卷積碼

42、卷積碼 4.4.1 卷積碼的表述方式卷積碼編碼器的一般形式如圖4-9所示,它包括：一個由N段組成的輸入移位寄存器,每段有k級,共Nk位寄存器；一組n個模2相加器；一個由n級組成的輸出移位寄存器。 對應(yīng)于每段1個比特的輸入序列,輸出n個比特。 由圖可知,n個比特編碼輸出不僅與當(dāng)前的k個比特信息輸入有關(guān),而且與以前的(N-1)k個比特信息輸入有關(guān)。 整個編碼過程可以看成是輸入信息序列與信道編碼器的卷積,卷積碼即由此得名。 通常把N稱為約束長度(注意： 約束長度的定義并無統(tǒng)一的標(biāo)準(zhǔn),在有的書和文獻中把nN或(N-1)稱為約束長度),因此,卷積碼通常可以表示為(n,k,N),它的編碼效率為Rck/n。

43、 第第4章章 信道編碼技術(shù)信道編碼技術(shù)圖4-9 卷積碼編碼器的一般形式k21輸入序列kk21k21Nk 級n213輸出序列第第4章章 信道編碼技術(shù)信道編碼技術(shù)為了介紹幾種簡單的卷積碼表述方法,我們將以圖4-10所示的(2,1,3)卷積碼為例進行分析。 第第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è)移位寄存器的起始狀態(tài)為全0,當(dāng)?shù)谝粋€輸入位為0時,

44、輸出為00； 若輸入比特為1,則輸出比特為11。 隨著第二個位的輸入,第一位右移一位,此時輸出比特同時受當(dāng)前輸入位和前一個輸入位的影響。 第三位輸入時,第一、 二位分別右移一位,同時輸出兩個由這三位移位寄存器存儲內(nèi)容所共同決定的比特。 當(dāng)?shù)谒奈惠斎霑r,第一位移出移位寄存器而消失。 移位過程可能產(chǎn)生的各種序列可以用圖4-11所示的樹狀圖來表示。 樹狀圖從節(jié)點a開始畫,此時移位寄存器狀態(tài)(即存儲內(nèi)容)為00。第第4章章 信道編碼技術(shù)信道編碼技術(shù)00aab110010cbd0111a0000acb111010cdd0101b11a0000aab110010cbd0111c00acb111010cdd

45、0101db11a圖4-11 （2，1，3）卷積碼的樹狀表示第第4章章 信道編碼技術(shù)信道編碼技術(shù)當(dāng)?shù)谝粋€輸入位m10時,輸出位x1, 1x2, 100； 當(dāng)m11時,輸出位x1, 1x2, 111； 因此從a點出發(fā)有兩條分支(樹叉)可以選擇,也就是m10時取上面一條分支,m11時取下面一條分支。 當(dāng)輸入第二位時,移位寄存器右移一位后,在上分支情況下,移位寄存器的狀態(tài)仍為00,下分支的狀態(tài)則為01,把01狀態(tài)記作b。 當(dāng)新的一位輸入時,隨著移位寄存器狀態(tài)和輸入位的不同,樹狀圖繼續(xù)分叉成4條分支,兩條向上,兩條向下。 上分支對應(yīng)于輸入0狀態(tài),下分支對應(yīng)于輸入1狀態(tài)。 如此繼續(xù)下去,即可得到圖4-1

46、1所示的二叉樹圖形。 樹狀圖中,每條樹叉上所標(biāo)注的碼元為輸出狀態(tài),每個節(jié)點上標(biāo)注的a、 b、 c、 d表示移位寄存器的狀態(tài),也就是以前輸入的信息,a狀態(tài)表示mj-2mj-100,b狀態(tài)表示mj-2mj-101,c狀態(tài)表示mj-2mj-110,d狀態(tài)表示mj-2mj-111。 顯然,對于第j個輸入位,就有2j條分支,但是在j=N3時,樹狀圖的節(jié)點自上而下開始重復(fù)出現(xiàn)這4種狀態(tài)。 第第4章章 信道編碼技術(shù)信道編碼技術(shù)2. 網(wǎng)格圖從卷積碼的樹狀圖中可以看到,樹狀圖的節(jié)點自上而下會出現(xiàn)重復(fù)特性,為此,我們可以得到一種更為緊湊的圖形表示方法,即網(wǎng)格圖法,具體情況見圖4-12。 在網(wǎng)格圖中,把碼樹中具有相

47、同狀態(tài)的節(jié)點合并在一起,碼樹中的上分支（對應(yīng)輸入0）用實線表示,下分支（對應(yīng)輸入1）用虛線表示。 網(wǎng)格圖中分支上標(biāo)注的碼元為對應(yīng)的輸出,自上而下4行節(jié)點分別表示a、 b、 c、 d四種狀態(tài)。 一般情況下應(yīng)有2N-1種狀態(tài),從第N節(jié)開始,網(wǎng)格圖圖形開始重復(fù)而完全相同。 第第4章章 信道編碼技術(shù)信道編碼技術(shù)圖4-12 （2, 1, 3）卷積碼的網(wǎng)絡(luò)圖表示0000000000111111111110狀態(tài)a00b01c10d1110101001010101010101000000101111111010第第4章章 信道編碼技術(shù)信道編碼技術(shù)3. 狀態(tài)圖由圖4-11可以看到,對于每一個節(jié)點當(dāng)前狀態(tài)a、 b

48、、 c、 d,根據(jù)不同的輸入將進入不同的狀態(tài),基于這一原理,我們可以構(gòu)造出當(dāng)前狀態(tài)與下一狀態(tài)之間的狀態(tài)轉(zhuǎn)換圖,也可以稱之為卷積碼的狀態(tài)圖。 在圖4-13中實線表示信息位為0的路徑,虛線表示信息位為1的路徑,并在路徑上寫出相應(yīng)的輸出碼元。 當(dāng)然,如果將狀態(tài)圖在時間上展開,便可以得到前面講到的網(wǎng)格圖。 第第4章章 信道編碼技術(shù)信道編碼技術(shù)圖4-13 （2,1,3）卷積碼的狀態(tài)圖adcb1000001011011101狀態(tài)a00b01c10d11第第4章章 信道編碼技術(shù)信道編碼技術(shù)假如利用圖4-10所示的卷積碼編碼器對輸入序列110111001000進行編碼,我們就可以用上述3種方法當(dāng)中的任意一種來

49、分析編碼器的輸出序列和狀態(tài)變化路徑。 在這里使用卷積碼的網(wǎng)格圖表示法進行分析。 若起始狀態(tài)為a,則可以得到圖4-14所示的結(jié)論。 第第4章章 信道編碼技術(shù)信道編碼技術(shù)圖4-14 （2,1,3）卷積碼的編碼過程及路徑a輸 出 碼狀 態(tài)輸 入 碼111b11011d010c001b011d101d010c110a111b100c110a000a0001010001100111111011第第4章章 信道編碼技術(shù)信道編碼技術(shù)通過上述分析以及對具體實例的研究,我們可以得到(n,k,N)卷積碼的一些基本特性： （1） 對于每組k位的輸入,利用卷積碼編碼后將得到n位的輸出； （2） 樹狀圖中每個節(jié)點可引出2k條分支； （3） 網(wǎng)格圖和狀態(tài)圖都有2k(N-1) 種可能的狀態(tài),每個狀態(tài)可以引出2k條分支,同時也有2k條分支從其他狀態(tài)或本狀態(tài)引入； （4） 在任何情況下,只要卷積碼編碼器一確定,相應(yīng)的樹狀圖、 網(wǎng)格圖和狀態(tài)圖都將確定,與輸入的碼序列無關(guān)。 第第4章章 信道編碼技術(shù)信道編碼技術(shù)4.4.2 二進制卷積碼的距離特性我們知道,在分組碼中碼距(Hamming距)與糾錯能力有密切關(guān)系,生成一種分組碼時應(yīng)使碼組之間的距離盡可能大。 常以最大的最小碼距作為糾錯能力的度量。 卷積碼中也同樣存在碼距的概念,通常使用的碼距有兩種： 最小碼距