第4章

信道編碼技術4.1離散信道模型4.2差錯控制編碼的基本概念4.3分組碼4.4卷積碼4.1離散信道模型 4.1.1離散無記憶信道 通常通信系統可以分為發信機、

物理信道或傳輸介質、

接收機三大部分,如圖4-1所示。發信機由信道編碼器和調制器組成,接收機由解調器和信道譯碼器組成,在圖4-1中,c和g之間是編碼信道,屬于離散信道；d和f之間是調制信道,屬于模擬信道。對于加性噪聲信道,噪聲和干擾會使傳輸的數據發生錯誤,因而對數據傳輸的可靠性產生影響。

圖4-1通信系統模型 對于輸入和輸出均為離散符號的離散信道,當信道中不存在干擾時,離散輸入符號X與輸出符號Y有一一對應的關系。但若信道中存在干擾,則輸入符號與輸出符號之間就不存在一一對應的關系了,而是具有一定的統計相關性。這個統計特性取決于輸入符號xi和輸出符號yj之間的轉移概率P(yj/xi)或P(xj/yi)。假設發送的符號集為X={xi}，i=1,2,…,L,有L種符號；

接收符號集為Y={yj}，j=1,2,…,M,有M種符號。這時離散無記憶信道(DMC,DiscreteMemorylessChannel)如圖4-2所示。DMC的轉移概率可以用以下矩陣表示：

圖4-2離散L輸入m輸出信道(4-1)所謂無記憶信道,是指每個輸出符號值取決于當前的輸入符號,而與其他輸入符號無關。若DMC的輸入選自X符號集的n個符號u1,u2,…,un的序列,相應的輸出選自Y符號集的n個符號v1,v2,…,vn的序列,則聯合條件概率為P(Y1=v1,Y2=v2,…,Yn=vn/X1=u1,X2=u2,…,Xn=un)=(4-2) 這個表達式正是無記憶條件的數學表述。 上述DMC的一個特例就是所謂的無記憶二進制對稱信道(BSC,BinarySymmetricChannel),其結構如圖4-3所示。對于BSC可能的符號輸入值的集合X={0,1},可能的符號輸出值的集合Y={0,1},對應的轉移概率可以表示為

這里，P(1/0)=P(0/1)=p，P(1/1)=P(0/0)=1-p。

(4-3)圖4-3二進制對稱信道 4.1.4信道容量 設離散信道模型如圖4-2所示，發送符號xi的概率為P(xi)，這里i=1，2，…，L；接收符號yj的概率為P(yj)，這里j=1，2，…，M；P(yj/xi)或P(xj/yj)表示轉移概率。在DMC信道中，輸入與輸出不再是一一對應關系，而是一種隨機對應的統計關系，這種統計關系可以用信道上的轉移概率進行描述，因此，我們可以利用信道的轉移概率來合理地描述信道受到的干擾和信道的統計特性。

信道容量定義為：

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

若要使信道容量增大，

理論上可以通過減小n0或增大S來實現。

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

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

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

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

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

即停發等候重發、

返回重發和選擇重發。圖4-5ARQ系統組成方框圖

停發等候重發系統的發送端在某一時刻向接收端發送一個碼組，接收端收到后經檢測若未發現傳輸錯誤，則發送一個認可信號(ACK)給發送端，發送端收到ACK信號后再發下一個碼組；如果接收端檢測出錯誤，則發送一個否認信號(NAK)，發送端收到NAK信號后重發前一個碼組，并再次等待ACK和NAK信號。這種方式效率不高，但工作方式簡單，在計算機數據通信中仍在使用。 在返回重發系統中，發送端無停頓地送出一個又一個碼組，不再等待ACK信號，一旦接收端發現錯誤并發回NAK信號，則發送端從下一個碼組開始重發前一段N組信號，N的大小取決于信號傳遞及處理所帶來的延遲，這種系統比停發等候重發系統有很大的改進，在許多數據傳輸系統中得到應用。 在選擇重發系統中，發送端也是連續不斷地發送碼組，接收端發現錯誤發回NAK信號。與返回重發系統不同的是，發送端不是重發前面的所有碼組，而是只重發有錯誤的那一組。顯然，這種選擇重發系統傳輸效率最高，但控制最為復雜。此外，返回重發系統和選擇重發系統都需要全雙工的鏈路，而停發等候重發系統只需要半雙工的鏈路。

由上述分析可知，ARQ的優點主要表現在： （1）只需要少量的冗余碼，

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

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

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

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

（3）按照信息碼元和監督碼元之間的約束方式不同，可以將它分為分組碼和卷積碼。在分組碼中，編碼后的碼元序列每n位分為一組，其中k位信息碼元，r個監督位，r=n-k。監督碼元僅與本碼組的信息碼元有關。卷積碼則不同，雖然編碼后序列也可以分為碼組，但監督碼元不但與本信息碼元有關，而且與前面碼組的信息碼元也有約束關系。 （4）按照信息碼元在編碼后是否保持原來的形式，可以將它分為系統碼和非系統碼。在系統碼中，編碼后的信息碼元保持原樣不變，而非系統碼中的信息碼元則發生了變化。除了個別情況，系統碼的性能大體上與非系統碼相同，同時非系統碼的譯碼較為復雜，因此，系統碼得到了廣泛的應用。

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

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

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

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

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

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

通常,在信道編碼過程中,監督位越多糾錯能力就越強,但編碼效率就越低。若碼組中信息位數為k,監督位數為r,碼長n=k+r,則編碼效率Rc可以用下式表示： Rc=k/n=(n-r)/n=1-r/n(4-30) 信道編碼的任務就是要根據不同的干擾特性,設計出編碼效率高,糾錯能力強的編碼。在實際設計過程中,需要根據具體指標要求,盡量簡化編碼實際的復雜度,節省設計費用。4.3分組碼

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

根據表4-1的對應關系,可以得到下列邏輯關系式：

S1=a6+a5+a4+a2

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

S3=a6+a4+a3+a0 在進行編碼時,設a6、a5、a4、a3為信息碼元,從表4-1中可以看到,當S3S2S1=000時,就表明碼組在傳輸過程中沒有發生錯誤,基于這一約束,利用式(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 根據上面兩個線性關系式,可以得到16個許用碼組,如表4-2所示。

表4-2許用碼組 在接收端收到碼組以后,就可以代入式(4-31)計算S1、S2和S3,如果全為0,則表明傳輸時沒有發生錯誤,否則根據表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被稱為生成矩陣,利用它可以產生整個碼組: A=M·G=［a6

a5a4

a3］G

(4-38) 由式(4-37)表示的生成矩陣形式被稱為典型生成矩陣,利用式(4-38)產生的分組碼必為系統碼,也就是信息碼元保持不變,監督碼元附加在其后。 在發送端,信息碼元M利用式(4-38)實現信道編碼,產生線性分組碼A；在傳輸過程中有可能出現誤碼,設接收到的碼組為B,則收發碼組之差為 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有關,即錯誤圖樣與校正子之間有確定的關系。ei= 在實踐中經常會遇到的線性分組碼主要有以下兩種： 1.漢明(Hamming)碼 漢明碼既有二進制的,也有非二進制的,這里僅討論二進制漢明碼的性質。二進制漢明碼可以表示為(n,k)=(2m-1,2m-1-m)(4-41) 這里m可取大于等于2的任意整數,因此,漢明碼的特點如下：碼長n=2m-1,信息位k=2m-1-m，監督位r=m,最小碼距d0=3,糾錯能力t=1。如果要產生一個系統漢明碼,那么可以將矩陣H轉換成典型形式的監督矩陣,進一步利用Q=PT的關系,得到相應的生成矩陣G。 2.哈達碼(Hadamard)碼 哈達碼矩陣Mn是一個由“0”和“1”構成的n×n維矩陣（n是偶數）,矩陣中任意兩行相比較,都存在n/2個不同的元素,矩陣中有一行是全0行,其他行都包含n/2個“0”和n/2個“1”。當n=2時,哈達碼矩陣可表示為

M2=(4-42)

進一步可以按照下述規律由Mn產生哈達碼矩陣M2n。

(4-43)

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

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

至此,可以利用M4和的行構成一個碼長n=4的二進制線性分組碼,該碼由8個碼組構成,最小碼距為d0=2。基于這種方法構成的碼稱為哈達碼。因此,哈達碼的長度n=2m,k=lb2n

=lb2m+1=m+1,d0=n/2=2m-1,這里m為正整數。

4.3.2循環碼循環碼是線性碼的一個重要子集,是目前研究得最成熟的一類碼。它有許多特殊的代數性質,這些性質有助于按所要求的糾錯能力系統地構造這類碼,且易于實現；同時循環碼的性能也較好,具有較強的檢錯和糾錯能力。

循環碼最大的特點就是循環性,所謂循環性,是指循環碼中任一許用碼組經過循環移位后,所得到的碼組仍然是許用碼組。若(an-1

an-2…a1

a0)為一循環碼組,則(an-2an-3…a0

an-1)、(an-3an-4…an-1an-2)…還是許用碼組。也就是說,不論是左移或是右移,也不論移多少位,其所得的碼組仍然是許用的循環碼組。 為了利用代數理論研究循環碼,可以將碼組用代數多項式來表示,這個多項式被稱為碼多項式,對于許用循環碼A=(an-1an-2…a1

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

(4-45)

對于二進制碼組,多項式的每個系數不是0就是1,x僅是碼元位置的標志,因此,我們這里并不關心x的取值 設上述循環許用碼組A左循環一位得到的碼組記作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) 利用代數理論知識,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)表示所得余式。由上述分析可以得到結論： 一個長為n的循環碼,它必為按模(xn+1)運算的一個余式。這個結論給出了構造許用碼的一種方法,即利用循環碼的生成多項式可以得到全部碼組。 在循環碼中,一個(n,k)碼有2k個不同的碼組,若用g(x)表示其中前(k-1)位皆為“0”的碼組,則g(x)、x·g(x)、

x2·g(x)、

…、

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

可以證明,一個(n,k)循環碼的生成多項式g(x),必須是一個常數項不為“0”的(n-k)次多項式,而且,這個g(x)還是(n,k)碼中次數為(n-k)的惟一的一個多項式。因為如果有兩個,則由于碼的封閉性,把這兩個碼相加也應該是一個碼組,且此碼組多項式的次數將小于(n-k),即出現連續“0”的個數將多于(k-1)的情況,這與(n,k)循環碼是線性碼的特性相違背,故是不可能的。為此,可以得到一個重要的結論：一旦生成多項式g(x)確定以后,整個(n,k)循環碼就被確定了。基于g(x),可以進一步寫出循環碼的生成矩陣如下：

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

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

(4-49)

根據g(x)定義可知,它是(n,k)循環碼中惟一的一個(n-k)次碼多項式,當然也就是該循環碼的許用碼組。對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)循環碼,其生成多項式應該是(xn+1)的一個(n-k)次因子,任何(n,k)循環碼的生成多項式g(x),乘上(x+1)后得到生成多項式,可以構造(n,k-1)循環碼。以(x7+1)因式分解為例：x7+1=(x+1)·(x3+x+1)·(x3+x2+1)

(4-52) 由式(4-52)可構成如表4-3所示的(7,k)循環碼。表4-3(x7+1)因式分解構成的(7,k)循環碼 由表4-3可看出不管是(7,4)循環碼還是(7,3)循環碼,均包含兩個不同的生成多項式,因此,依據不同的生成多項式將產生不同的循環碼組。 上面我們討論了循環碼的基本原理,下面就系統循環碼的產生進行分析。

根據循環碼的編碼特點,所有循環碼多項式A(x)都可以被g(x)整除。根據這一原理可以得到一個較簡單的系統循環碼編碼方法：設要產生(n,k)循環碼,m(x)表示信息多項式,則其次數必小于k,而xn-k·m(x)的次數必小于n,用xn-k·m(x)除以g(x),可得余數r(x),r(x)的次數必小于(n-k),將r(x)加到信息位后作監督位,就得到了系統循環碼,其數學描述如下： (4-53) 則系統循環碼可以表示為A(x)=xn-k·m(x)+r(x)(4-54) 上述編碼過程,在硬件實現時,可以利用除法電路來實現,這里的除法電路采用一些移位寄存器和模2加法器來構成,下面我們將以(7,3)循環碼為例來說明其具體實現過程。設該(7,3)循環碼的生成多項式為g(x)=x4+x2+x+1,則構成的系統循環碼編碼器如圖4-7所示,圖中有4個移位寄存器,一個雙刀雙擲開關。當信息位輸入時,開關位置接“1”,輸入的信息碼一方面送到除法器進行運算,一方面直接輸出；當信息位全部輸出后,開關位置接“2”,這時輸出端接到移位寄存器的輸出,除法的余項,也就是監督位依次輸出。當信息碼為110時,編碼器的工作過程如表4-4所示。圖4-7(7,3)循環碼編碼器表4-4編碼器的工作過程

對于接收端譯碼的要求通常有兩個：檢錯與糾錯。達到檢錯目的的譯碼十分簡單,可以依據式(4-54),通過判斷接收到的碼組多項式B(x)是否能被生成多項式g(x)整除來完成。當傳輸中未發生錯誤時,接收的碼組與發送的碼組相同,即A(x)=B(x),接收的碼組B(x)必能被g(x)整除；若傳輸中發生了錯誤,則A(x)≠B(x),B(x)不能被g(x)整除。因此,我們就可以根據余項是否為零來判斷碼組中有無錯碼。 需要指出的是,有錯碼的接收碼組也有可能被g(x)整除,這時的錯碼就不能檢出了。這種錯誤被稱為不可檢錯誤,不可檢錯誤的錯碼數必將超過這種編碼的檢錯能力。

在接收端為糾錯而采用的譯碼方法自然比檢錯要復雜許多,因此,對糾錯碼的研究大都集中在譯碼算法上。我們知道,校正子與錯誤圖樣之間存在某種對應關系。如同其他線性分組碼,循環碼的譯碼可以分三步進行： （1）由接收到的碼多項式B(x)計算校正子(伴隨式)多項式S(x)； （2）由校正子多項式S(x)確定錯誤圖樣E(x)； （3）將錯誤圖樣E(x)與B(x)相加,糾正錯誤。 上述第（1）步運算和檢錯譯碼類似,也就是求解B(x)整除g(x)的余式,第（3）步也很簡單。因此,糾錯碼譯碼器的復雜性主要取決于譯碼過程的第（2）步。 4.3.3BCH碼 BCH碼是循環碼中的一個重要子類,它是以三個研究和發明這種碼的人名Bose、Chaudhuri和Hocguenghem命名的。BCH碼不僅具有糾正多個隨機錯誤的能力,而且具有嚴密的代數結構,是目前研究得最為透徹的一類碼。它的生成多項式g(x)與最小碼距之間有密切的關系,人們可以根據所要求的糾錯能力t,很容易地構造出BCH碼。BCH碼的譯碼也比較容易實現,是線性分組碼中應用最為普遍的一類碼。

4.4卷積碼

4.4.1卷積碼的表述方式 卷積碼編碼器的一般形式如圖4-9所示,它包括：一個由N段組成的輸入移位寄存器,每段有k級,共Nk位寄存器；一組n個模2相加器；一個由n級組成的輸出移位寄存器。對應于每段1個比特的輸入序列,輸出n個比特。由圖可知,n個比特編碼輸出不僅與當前的k個比特信息輸入有關,而且與以前的(N-1)k個比特信息輸入有關。整個編碼過程可以看成是輸入信息序列與信道編碼器的卷積,卷積碼即由此得名。通常把N稱為約束長度(注意：約束長度的定義并無統一的標準,在有的書和文獻中把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)卷積碼編碼器當中,輸出移位寄存器用轉換開關代替,每輸入一個位信息,經編碼產生兩位輸出。假設移位寄存器的起始狀態為全0,當第一個輸入位為0時,輸出為00；若輸入比特為1,則輸出比特為11。隨著第二個位的輸入,第一位右移一位,此時輸出比特同時受當前輸入位和前一個輸入位的影響。第三位輸入時,第一、二位分別右移一位,同時輸出兩個由這三位移位寄存器存儲內容所共同決定的比特。當第四位輸入時,第一位移出移位寄存器而消失。移位過程可能產生的各種序列可以用圖4-11所示的樹狀圖來表示。樹狀圖從節點a開始畫,此時移位寄存器狀態(即存儲內容)為00。圖4-11（2，1，3）卷積碼的樹狀表示

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

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

2.網格圖

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

當然,如果將狀態圖在時間上展開,便可以得到前面講到的網格圖。

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

圖4-14（2,1,3）卷積碼的編碼過程及路徑 通過上述分析以及對具體實例的研究,我們可以得到(n,k,N)卷積碼的一些基本特性： （1）對于每組k位的輸入,利用卷積碼編碼后將得到n位的輸出； （2）樹狀圖中每個節點可引出2k條分支； （3）網格圖和狀態圖都有2k(N-1)種可能的狀態,每個狀態可以引出2k條分支,同時也有2k條分支從其他狀態或本狀態引入； （4）在任何情況下,只要卷積碼編碼器一確定,相應的樹狀圖、網格圖和狀態圖都將確定,與輸入的碼序列無關。 4.4.2二進制卷積碼的距離特性 我們知道,在分組碼中碼距(Hamming距)與糾錯能力有密切關系,生成一種分組碼時應使碼組之間的距離盡可能大。