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

第4章

信道編碼技術(shù)4.1離散信道模型4.2差錯控制編碼的基本概念4.3分組碼4.4卷積碼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ù)目煽啃援a(chǎn)生影響。

圖4-1通信系統(tǒ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=1,2,…,M,有M種符號。這時離散無記憶信道(DMC,DiscreteMemorylessChannel)如圖4-2所示。DMC的轉(zhuǎn)移概率可以用以下矩陣表示：

圖4-2離散L輸入m輸出信道(4-1)所謂無記憶信道,是指每個輸出符號值取決于當前的輸入符號,而與其他輸入符號無關(guān)。若DMC的輸入選自X符號集的n個符號u1,u2,…,un的序列,相應(yīng)的輸出選自Y符號集的n個符號v1,v2,…,vn的序列,則聯(lián)合條件概率為P(Y1=v1,Y2=v2,…,Yn=vn/X1=u1,X2=u2,…,Xn=un)=(4-2) 這個表達式正是無記憶條件的數(shù)學表述。 上述DMC的一個特例就是所謂的無記憶二進制對稱信道(BSC,BinarySymmetricChannel),其結(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)=P(0/0)=1-p。

(4-3)圖4-3二進制對稱信道 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)計特性。

信道容量定義為：

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

若要使信道容量增大，

理論上可以通過減小n0或增大S來實現(xiàn)。

那么，增大帶寬B是否可行?下面就此問題進行分析。首先將式(4-24)改寫為 當B→∞時，上式變?yōu)?4-25)(4-26) 式(4-26)中的近似利用了關(guān)系式：。

通過上述論述表明：保持S/n0一定，即使信道帶寬B→∞，信道容量也是有限的，這是因為信道帶寬B→∞時，噪聲功率B·n0也趨于無窮大。 通常，把實現(xiàn)了上述極限信息速率的通信系統(tǒng)稱為理想通信系統(tǒng)。但是香農(nóng)定理只證明了理想系統(tǒng)的“存在性”，卻沒有指出這種通信系統(tǒng)的實現(xiàn)方法。因此，理想系統(tǒng)只能作為實際系統(tǒng)的理論極限。另外，上述討論都是在信道噪聲為高斯白噪聲前提下進行的，對于其他類型的的噪聲，香農(nóng)公式需要改進。4.2差錯控制編碼的基本概念 4.2.1差錯控制方式 常用的差錯控制方式主要有三種：前向糾錯（簡稱FEC）、檢錯重發(fā)（簡稱ARQ）和混合糾錯（簡稱HEC），它們的結(jié)構(gòu)如圖4-4所示。圖中帶陰影的方框圖表示在該端檢測錯誤。

圖4-4差錯控制方式(a)前向糾錯（FEC）；(b)檢錯重發(fā)（ARQ）；(c)混合糾錯（HEC）

前向糾錯系統(tǒng)中，發(fā)送端經(jīng)信道編碼后可以發(fā)出具有糾錯能力的碼組；接收端譯碼后不僅可以發(fā)現(xiàn)錯誤碼，而且可以判斷錯誤碼的位置并予以自動糾正。因此，前向糾錯編碼需要附加較多的冗余碼元，影響數(shù)據(jù)傳輸效率，同時其編譯碼設(shè)備比較復(fù)雜。但是由于不需要反饋信道，實時性較好，因此這種技術(shù)在單工信道中普遍采用，例如無線電尋呼中采用的POGSAG編碼。

檢錯重發(fā)方式中，發(fā)送端經(jīng)信道編碼后可以發(fā)出具有檢錯能力的碼組；接收端收到后經(jīng)檢測如果發(fā)現(xiàn)傳輸中有錯誤，則通過反饋信道把這一判斷結(jié)果反饋給發(fā)送端。然后，發(fā)送端把前面發(fā)出的信息重新傳送一次，直到接收端認為已經(jīng)正確為止。典型系統(tǒng)原理方框圖如圖4-5所示。 常用的檢錯重發(fā)系統(tǒng)有三種，

即停發(fā)等候重發(fā)、

返回重發(fā)和選擇重發(fā)。圖4-5ARQ系統(tǒng)組成方框圖

停發(fā)等候重發(fā)系統(tǒng)的發(fā)送端在某一時刻向接收端發(fā)送一個碼組，接收端收到后經(jīng)檢測若未發(fā)現(xiàn)傳輸錯誤，則發(fā)送一個認可信號(ACK)給發(fā)送端，發(fā)送端收到ACK信號后再發(fā)下一個碼組；如果接收端檢測出錯誤，則發(fā)送一個否認信號(NAK)，發(fā)送端收到NAK信號后重發(fā)前一個碼組，并再次等待ACK和NAK信號。這種方式效率不高，但工作方式簡單，在計算機數(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)中得到應(yīng)用。 在選擇重發(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)只需要半雙工的鏈路。

由上述分析可知，ARQ的優(yōu)點主要表現(xiàn)在： （1）只需要少量的冗余碼，

就可以得到極低的輸出誤碼率；

（2）使用的檢錯碼基本上與信道的統(tǒng)計特性無關(guān)，有一定的自適應(yīng)能力；（3）與FEC相比，信道編譯碼器的復(fù)雜性要低得多。 同時ARQ也存在某些不足，主要表現(xiàn)在： （1）需要反向信道，故不能用于單向傳輸系統(tǒng)，并且實現(xiàn)重發(fā)控制比較復(fù)雜； （2）當信道干擾增大時，整個系統(tǒng)有可能處在重發(fā)循環(huán)當中，因而通信效率低；（3）不大適合于嚴格實時傳輸系統(tǒng)。

混合糾錯方式是前向糾錯方式和檢錯重發(fā)方式的結(jié)合。在這種系統(tǒng)中接收端不但具有糾正錯誤的能力，而且對超出糾錯能力的錯誤有檢測能力。遇到后一種情況時，系統(tǒng)可以通過反饋信道要求發(fā)送端重發(fā)一遍?；旌图m錯方式在實時性和譯碼復(fù)雜性方面是前向糾錯和檢錯重發(fā)方式的折衷。

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

（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)碼相同，同時非系統(tǒng)碼的譯碼較為復(fù)雜，因此，系統(tǒng)碼得到了廣泛的應(yīng)用。

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

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

最小碼距：在碼組集合中全體碼組之間距離的最小數(shù)值。

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

這個關(guān)系可以利用圖4-6(a)予以說明。在圖中用A和B分別表示兩個碼距為d0的碼組，若A發(fā)生e個錯誤，則A就變成以A為球心，e為半徑的球面上的碼組，為了能將這些碼組分辨出來，它們必須距離其最近的碼組B有一位的差別，

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

通常,在信道編碼過程中,監(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ù)具體指標要求,盡量簡化編碼實際的復(fù)雜度,節(jié)省設(shè)計費用。4.3分組碼

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

根據(jù)表4-1的對應(yīng)關(guān)系,可以得到下列邏輯關(guān)系式：

S1=a6+a5+a4+a2

S2=a6+a5+a3+a1(4-31)

S3=a6+a4+a3+a0 在進行編碼時,設(shè)a6、a5、a4、a3為信息碼元,從表4-1中可以看到,當S3S2S1=000時,就表明碼組在傳輸過程中沒有發(fā)生錯誤,基于這一約束,利用式(4-31),可以得到下面兩種形式的線性方程組：

a6+a5+a4+a2=0

a6+a5+a3+a1=0

a6+a4+a3+a0=0

(4-32)

a6+a5+a4=a2

a6+a5+a3=a1(4-33)

a6+a4+a3=a0 根據(jù)上面兩個線性關(guān)系式,可以得到16個許用碼組,如表4-2所示。

表4-2許用碼組 在接收端收到碼組以后,就可以代入式(4-31)計算S1、S2和S3,如果全為0,則表明傳輸時沒有發(fā)生錯誤,否則根據(jù)表4-1糾正錯誤。當然對于上述(7,4)碼而言,最小碼距d0=3,因此,它可以糾正一個錯誤或檢測兩個錯誤,如果超出這個范圍,糾錯功能就要失敗。 對于式(4-32),可以用矩陣形式表示如下：(4-34) 上式可以記作：

HAT=0T或AHT=0,其中, A=［a6

a5

a4

a3

a2

a1

a0］(4-35b) 0=［000］(4-35c)(4-35a) 或者［a2

a1

a0］=［a6

a5

a4

a3］=［a6

a5

a4

a3］Q

比較式(4-34)和式(4-36)可以看到Q=PT,如果在Q矩陣的左邊再加上一個k×k的單位矩陣,就形成了一個新矩陣G：(4-37) 這里G被稱為生成矩陣,利用它可以產(chǎn)生整個碼組: A=M·G=［a6

a5a4

a3］G

(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-1en-2…e0］(4-39) 這里 0bi=ai1bi≠ai,

ei=1表示i位有錯,ei=0表示i位無錯。基于這樣的原則,接收端利用接收到的碼組B計算校正子：S=BHT=(A+E)HT=AHT+EHT=EHT (4-40)

因此,校正子僅與E有關(guān),即錯誤圖樣與校正子之間有確定的關(guān)系。ei= 在實踐中經(jīng)常會遇到的線性分組碼主要有以下兩種： 1.漢明(Hamming)碼 漢明碼既有二進制的,也有非二進制的,這里僅討論二進制漢明碼的性質(zhì)。二進制漢明碼可以表示為(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。如果要產(chǎn)生一個系統(tǒng)漢明碼,那么可以將矩陣H轉(zhuǎn)換成典型形式的監(jiān)督矩陣,進一步利用Q=PT的關(guān)系,得到相應(yīng)的生成矩陣G。 2.哈達碼(Hadamard)碼 哈達碼矩陣Mn是一個由“0”和“1”構(gòu)成的n×n維矩陣（n是偶數(shù)）,矩陣中任意兩行相比較,都存在n/2個不同的元素,矩陣中有一行是全0行,其他行都包含n/2個“0”和n/2個“1”。當n=2時,哈達碼矩陣可表示為

M2=(4-42)

進一步可以按照下述規(guī)律由Mn產(chǎn)生哈達碼矩陣M2n。

(4-43)

式中,Mn為Mn的互補矩陣,按上述規(guī)律M4和

就可以分別表示為(4-44)

至此,可以利用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)碼是線性碼的一個重要子集,是目前研究得最成熟的一類碼。它有許多特殊的代數(shù)性質(zhì),這些性質(zhì)有助于按所要求的糾錯能力系統(tǒng)地構(gòu)造這類碼,且易于實現(xiàn)；同時循環(huán)碼的性能也較好,具有較強的檢錯和糾錯能力。

循環(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ù)多項式來表示,這個多項式被稱為碼多項式,對于許用循環(huán)碼A=(an-1an-2…a1

a0),可以將它的碼多項式表示為A(x)=an-1xn-1+an-2xn-2+…+a1x+a0

(4-45)

對于二進制碼組,多項式的每個系數(shù)不是0就是1,x僅是碼元位置的標志,因此,我們這里并不關(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+…+a0x+an-1(4-46) 同理,左移i位的碼組A（i）=(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) 利用代數(shù)理論知識,A（i）

(x)也可以用下式求得：

xi·A(x)=Q(x)·(xn+1)+A（i）(x)(4-48) 這里,Q(x)表示xi·A(x)除以(xn+1)的商,而A（i）(x)表示所得余式。由上述分析可以得到結(jié)論： 一個長為n的循環(huán)碼,它必為按模(xn+1)運算的一個余式。這個結(jié)論給出了構(gòu)造許用碼的一種方法,即利用循環(huán)碼的生成多項式可以得到全部碼組。 在循環(huán)碼中,一個(n,k)碼有2k個不同的碼組,若用g(x)表示其中前(k-1)位皆為“0”的碼組,則g(x)、x·g(x)、

x2·g(x)、

…、

xk-1·g(x)都是碼組,而且這k個碼組線性無關(guān),因此,可以利用它們構(gòu)成循環(huán)碼的生成矩陣,而g(x)被稱為生成多項式。

可以證明,一個(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)碼是線性碼的特性相違背,故是不可能的。為此,可以得到一個重要的結(jié)論：一旦生成多項式g(x)確定以后,整個(n,k)循環(huán)碼就被確定了?；趃(x),可以進一步寫出循環(huán)碼的生成矩陣如下：

顯然,上式不符合G=［Ik

Q］形式,所以此生成矩陣不是典型形式,不過,可以通過簡單的代數(shù)變換將它變成典型矩陣。

(4-49)

根據(jù)g(x)定義可知,它是(n,k)循環(huán)碼中惟一的一個(n-k)次碼多項式,當然也就是該循環(huán)碼的許用碼組。對g(x)表述的許用碼組進行k次左移,會得到同樣的碼組,將這一過程用式(4-48)描述將得到

xk·g(x)=Q(x)·(xn+1)+g(x)

(4-50) 上式左邊是一個n次多項式,因此,Q(x)=1,所以可以進一步表示為 (xn+1)=xk·g(x)+g(x)=g(x)·(xk+1)(4-51) 式(4-51)表明,生成多項式g(x)是(xn+1)的一個因式,因此,為了確定生成多項式,必須首先對(xn+1)進行因式分解,然后再用計算進行篩選,計算過程通常使用計算機來完成。

對于一個(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-3所示的(7,k)循環(huán)碼。表4-3(x7+1)因式分解構(gòu)成的(7,k)循環(huán)碼 由表4-3可看出不管是(7,4)循環(huán)碼還是(7,3)循環(huán)碼,均包含兩個不同的生成多項式,因此,依據(jù)不同的生成多項式將產(chǎn)生不同的循環(huán)碼組。 上面我們討論了循環(huán)碼的基本原理,下面就系統(tǒng)循環(huán)碼的產(chǎn)生進行分析。

根據(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-k·m(x)的次數(shù)必小于n,用xn-k·m(x)除以g(x),可得余數(shù)r(x),r(x)的次數(shù)必小于(n-k),將r(x)加到信息位后作監(jiān)督位,就得到了系統(tǒng)循環(huán)碼,其數(shù)學描述如下： (4-53) 則系統(tǒng)循環(huán)碼可以表示為A(x)=xn-k·m(x)+r(x)(4-54) 上述編碼過程,在硬件實現(xiàn)時,可以利用除法電路來實現(xiàn),這里的除法電路采用一些移位寄存器和模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)。當信息位輸入時,開關(guān)位置接“1”,輸入的信息碼一方面送到除法器進行運算,一方面直接輸出；當信息位全部輸出后,開關(guān)位置接“2”,這時輸出端接到移位寄存器的輸出,除法的余項,也就是監(jiān)督位依次輸出。當信息碼為110時,編碼器的工作過程如表4-4所示。圖4-7(7,3)循環(huán)碼編碼器表4-4編碼器的工作過程

對于接收端譯碼的要求通常有兩個：檢錯與糾錯。達到檢錯目的的譯碼十分簡單,可以依據(jù)式(4-54),通過判斷接收到的碼組多項式B(x)是否能被生成多項式g(x)整除來完成。當傳輸中未發(fā)生錯誤時,接收的碼組與發(fā)送的碼組相同,即A(x)=B(x),接收的碼組B(x)必能被g(x)整除；若傳輸中發(fā)生了錯誤,則A(x)≠B(x),B(x)不能被g(x)整除。因此,我們就可以根據(jù)余項是否為零來判斷碼組中有無錯碼。 需要指出的是,有錯碼的接收碼組也有可能被g(x)整除,這時的錯碼就不能檢出了。這種錯誤被稱為不可檢錯誤,不可檢錯誤的錯碼數(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）步也很簡單。因此,糾錯碼譯碼器的復(fù)雜性主要取決于譯碼過程的第（2）步。 4.3.3BCH碼 BCH碼是循環(huán)碼中的一個重要子類,它是以三個研究和發(fā)明這種碼的人名Bose、Chaudhuri和Hocguenghem命名的。BCH碼不僅具有糾正多個隨機錯誤的能力,而且具有嚴密的代數(shù)結(jié)構(gòu),是目前研究得最為透徹的一類碼。它的生成多項式g(x)與最小碼距之間有密切的關(guān)系,人們可以根據(jù)所要求的糾錯能力t,很容易地構(gòu)造出BCH碼。BCH碼的譯碼也比較容易實現(xiàn),是線性分組碼中應(yīng)用最為普遍的一類碼。

4.4卷積碼

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

圖4-9卷積碼編碼器的一般形式 為了介紹幾種簡單的卷積碼表述方法,我們將以圖4-10所示的(2,1,3)卷積碼為例進行分析。

圖4-10（2,1,3）卷積碼編碼器

1.樹狀圖 在(2,1,3)卷積碼編碼器當中,輸出移位寄存器用轉(zhuǎn)換開關(guān)代替,每輸入一個位信息,經(jīng)編碼產(chǎn)生兩位輸出。假設(shè)移位寄存器的起始狀態(tài)為全0,當?shù)谝粋€輸入位為0時,輸出為00；若輸入比特為1,則輸出比特為11。隨著第二個位的輸入,第一位右移一位,此時輸出比特同時受當前輸入位和前一個輸入位的影響。第三位輸入時,第一、二位分別右移一位,同時輸出兩個由這三位移位寄存器存儲內(nèi)容所共同決定的比特。當?shù)谒奈惠斎霑r,第一位移出移位寄存器而消失。移位過程可能產(chǎn)生的各種序列可以用圖4-11所示的樹狀圖來表示。樹狀圖從節(jié)點a開始畫,此時移位寄存器狀態(tài)(即存儲內(nèi)容)為00。圖4-11（2，1，3）卷積碼的樹狀表示

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

顯然,對于第j個輸入位,就有2j條分支,但是在j=N≥3時,樹狀圖的節(jié)點自上而下開始重復(fù)出現(xiàn)這4種狀態(tài)。

2.網(wǎng)格圖

從卷積碼的樹狀圖中可以看到,樹狀圖的節(jié)點自上而下會出現(xiàn)重復(fù)特性,為此,我們可以得到一種更為緊湊的圖形表示方法,即網(wǎng)格圖法,具體情況見圖4-12。在網(wǎng)格圖中,把碼樹中具有相同狀態(tài)的節(jié)點合并在一起,碼樹中的上分支（對應(yīng)輸入0）用實線表示,下分支（對應(yīng)輸入1）用虛線表示。網(wǎng)格圖中分支上標注的碼元為對應(yīng)的輸出,自上而下4行節(jié)點分別表示a、b、c、d四種狀態(tài)。一般情況下應(yīng)有2N-1種狀態(tài),從第N節(jié)開始,網(wǎng)格圖圖形開始重復(fù)而完全相同。圖4-12（2,1,3）卷積碼的網(wǎng)絡(luò)圖表示 3.狀態(tài)圖 由圖4-11可以看到,對于每一個節(jié)點當前狀態(tài)a、b、c、d,根據(jù)不同的輸入將進入不同的狀態(tài),基于這一原理,我們可以構(gòu)造出當前狀態(tài)與下一狀態(tài)之間的狀態(tài)轉(zhuǎn)換圖,也可以稱之為卷積碼的狀態(tài)圖。在圖4-13中實線表示信息位為0的路徑,虛線表示信息位為1的路徑,并在路徑上寫出相應(yīng)的輸出碼元。

當然,如果將狀態(tài)圖在時間上展開,便可以得到前面講到的網(wǎng)格圖。

圖4-13（2,1,3）卷積碼的狀態(tài)圖 假如利用圖4-10所示的卷積碼編碼器對輸入序列110111001000進行編碼,我們就可以用上述3種方法當中的任意一種來分析編碼器的輸出序列和狀態(tài)變化路徑。在這里使用卷積碼的網(wǎng)格圖表示法進行分析。 若起始狀態(tài)為a,則可以得到圖4-14所示的結(jié)論。

圖4-14（2,1,3）卷積碼的編碼過程及路徑 通過上述分析以及對具體實例的研究,我們可以得到(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.4.2二進制卷積碼的距離特性 我們知道,在分組碼中碼距(Hamming距)與糾錯能力有密切關(guān)系,生成一種分組碼時應(yīng)使碼組之間的距離盡可能大。