10.1概述

10.2檢錯碼

10.3線性分組碼

10.4卷積碼

10.5復合編碼

10.6m序列

思考題

習題第10章信道編碼原理10.1概述10.1.1信源編碼與信道編碼數字通信中，根據不同的目的，可將編碼分為信源編碼和信道編碼兩大類。為了提高數字信號的有效性而采取的編碼稱為信源編碼，又稱有效編碼；為了提高數字通信的可靠性而采取的編碼稱為信道編碼(或者可靠編碼)，又稱抗干擾編碼，這是本章要討論的內容。數字通信要求傳輸過程中所造成的碼元差錯足夠低。引起傳輸差錯的根本原因是信道內存在噪聲以及信道傳輸特性不理想所造成的碼間串擾。通常，由于信道線性畸變所造成的碼間串擾可以通過均衡的辦法來消除,因此，常常只把信道中的噪聲作為造成傳輸差錯的根本原因。為了提高數字通信系統的抗噪聲性能，可以采取增大發射功率、降低接收設備本身的噪聲、選擇好的調制制度和解調方式、加強天線的方向性等措施。但是,這些措施只能將差錯減小到一定程度,要進一步提高通信的可靠性，就需要采用信道編碼技術，對可能或者已經出現的差錯進行控制。

信道編碼是使不帶規律性或者規律性不強的原始數字信號變換為帶上規律性或者加強了規律性的數字信號，信道譯碼器則利用這些規律性來鑒別是否發生了錯誤，進而糾正錯誤。信道編碼分為糾錯編碼和正交編碼兩大類。糾錯碼的規律性體現在各碼組的碼元之間，而正交碼的規律性體現在各碼組之間的正交性。這兩類碼有密切的聯系，有些正交碼就是糾錯碼。

原始數字信號是分組傳輸的，例如每k個二進制碼元為一組，稱為信息組，經信道編碼后轉換為每n個碼元一組的碼字(碼組)，n>k。可見，信道編碼是采用增加數碼，利用“多余”碼來提高抗干擾能力的，亦即以降低信息傳輸速率為代價來減少錯誤，或者說是通過采用削弱有效性來增強可靠性。10.1.2糾錯碼的分類

(1)根據糾錯碼各碼組的碼元與信息元之間的函數關系，糾錯碼可分為線性碼和非線性碼。如果函數關系是線性的，則稱為線性碼，否則稱為非線性碼。

(2)根據上述關系涉及的范圍，糾錯碼可分為分組碼和卷積碼。分組碼的各碼元僅與本組的信息元有關，卷積碼中的碼元不僅與本組的信息元有關，而且還與前面若干組的信息元有關，卷積碼又稱連環碼。線性分組碼中，把具有循環移位特性的碼稱為循環碼，否則稱非循環碼。

(3)根據糾錯碼組中信息元是否隱蔽，糾錯碼可分為系統碼和非系統碼。如果信息元能從碼組中截然分離出來(通常K個信息元與原始數字信號一致，且位于碼組的前K位)，則稱為系統碼或組織碼，否則稱為非系統碼或非組織碼。

(4)根據碼的用途,糾錯碼可分為檢錯碼和糾錯碼。前者以檢測(發現)錯誤為目的，后者以糾正錯誤為目的。糾錯碼一定能檢錯，檢錯碼不一定能糾錯。平常所說的糾錯碼是兩者的統稱。

(5)根據糾(檢)錯碼的類型區分，糾錯碼可分為糾(檢)隨機錯碼、糾(檢)突發錯碼及既能糾(檢)隨機錯又能糾(檢)突發錯的碼。

(6)根據碼元取值的進制，糾錯碼可分為二進制碼和多進制碼。本章主要介紹二進制糾錯碼。10.1.3差錯控制的工作方式差錯控制的基本工作方式有4種，如圖10.1所示。圖中有斜線的方框圖表示在該端檢出錯誤。圖10.1差錯控制的基本工作方式前向糾錯(FEC，ForwardErrorCorrection)：又稱自動糾錯，發端發送糾錯碼，收端譯碼器自動發現并糾正錯誤。其特點是能單向連續傳輸，實時性好，但是譯碼電路比較復雜。檢錯重發(ARQ,AutoRepeat-reQuest):又稱反饋重發、自動重傳請求或者判決反饋，發端發出檢錯碼，通過正向信道送到收端，收端譯碼器判決碼組中有無錯誤出現，再把判決信號通過反饋信道送回發端，發端根據判決信號將收端認為有錯的消息重發到收端，直到正確接收為止。其特點是需要反饋信道，但是譯碼設備簡單，對突發錯誤特別有效。信息反饋(IF，InformationFeedback)：又稱反饋檢驗，收端把收到的消息原封不動地通過反饋信道送回發端，發端把反饋回來的信息與原發送信息進行比較，從而發現錯誤，并把二者不一致的部分重發到收端。其特點是沒有糾(檢)錯編碼，電路較簡單，但是需要反饋信道并且傳輸速率較低。

混合糾錯(HEC，HybridErrorCorrection)：是FEC與ARQ的混合，發端發出便于檢錯和糾錯的碼，通過正向信道送到收端，收端對錯誤能糾正的就自動糾正，糾正不了時自動發出判決信號并送回發端，發端把收端認為有錯并且無法糾正的消息重發到收端，以達到正確傳輸。這種方式具有FEC與ARQ的特點，能充分發揮碼的糾錯和檢錯性能，在較差的信道中仍然可以收到好的效果，缺點是需要反饋信道以及復雜的譯碼設備。

以上4種工作方式在數字通信系統中都得到了廣泛的應用。例如,在高速防空系統中常采用前向糾錯方式，在國際間的數字通信系統中往往采用檢錯重發的方式或者信息反饋的方式，而在復雜的短波信道與散射信道中則常采用混合糾錯的方式。10.1.4糾錯碼的基本概念

1．碼長、碼重和碼距碼組(碼字或碼矢)中碼元的數目稱為碼組的長度，簡稱碼長。碼組中非0位的數目稱為碼組的重量，簡稱碼重。對于二進制碼而言，碼重W就是碼組中1的數目，例如碼組11010，碼長n=5，碼重W=3。兩個等長碼組之間對應位不同的數目稱為這兩個碼組的漢明距離，簡稱碼距,例如碼組11000與10011的距離d=3。而碼組集合中全體碼組之間距離的最小數值d0稱為碼的最小距離。由于兩個碼組模二相加，其不同的對應位必為1，而相同的對應位必為0，因此兩個碼組模二相加得到的新碼組的重量就是這兩個碼組之間的距離。碼的最小距離是衡量該碼糾錯能力的依據，是重要的參數。

2．為什么糾錯碼能夠檢錯或者糾錯現在以二進制碼組為例說明糾錯碼檢錯和糾錯的基本原理。分組碼對數字序列是分段處理的，設每一段由k個碼元組成，稱做長度為k的信息組，又稱k重。由于每個碼元有0或1兩個值，因此共有2k個不同的k重。每段長k的信息組，以一定的規則增加r個稱為監督元的多余度碼元，來監督這k個信息元，這樣就組成長為n=k+r的碼組，又稱n重，共得到2k個不同的n重。這2k個n重分別代表2k個不同的信息組，稱為許用碼組。長n的數字序列共有2n種可能的組合，其中2n-2k個n重未被選用，稱為禁用碼組。上述2k

個不同的長n的許用碼組的集合稱為分組碼。分組碼能夠檢錯或者糾錯的原因是每個n重中有多余度碼元，或者說2n個n重中有禁用碼組。舉例說明如下：

設發送端發送A和B兩個消息，分別用一位碼元(k=1)表示，1代表A，0代表B。如果這兩個信息組在傳輸中產生了錯誤，0錯成了1或者1錯成了0，則接收端不能發現這種錯誤，更談不上糾正錯誤,此時收到的消息就不可靠。如果每個一位長的信息組中添加上一個監督元(r=1)，其規則是與信息元重復，則這樣編出的兩個長為n=2的碼組是11(代表A)和00(代表B)。11、00是許用碼組，這兩個碼字組成一個(2，1)分組碼，其特點是各碼字的碼元是重復的，因此又稱為重復碼。01、10是禁用碼組。設發送11經信道傳輸錯了一位，變成01或10，收端譯碼器根據重復碼的規則，能發現有一位錯誤，但是不能指明錯在哪一位，亦即不能作出發送的消息是A(“11”)還是B(“00”)的判決。如果信道干擾嚴重，使發送碼字的兩位都產生錯誤，從而使11錯成了00，則收端譯碼器根據重復碼的規則檢驗，不認為有錯，并且判決為消息B，造成了錯判。這種碼距為2的(2，1)重復碼能發現1個碼元的錯誤，不能發現2個碼元的錯誤(以下簡稱1個錯誤、2個錯誤、……)，也不能糾正錯誤。如果仍然按照重復碼的規則，再加一個監督元，則得到(3，1)重復碼，它的兩個碼字為111和000，碼距為3；其余6個碼組(001，010，100，110，101，011)為禁用碼組。設發送111(代表消息A)，譯碼器收到的3重為110，根據重復碼的規則，發現有錯，并且當采用最大似然法譯碼時，把與發送碼字最相似的碼組認為是發送碼組。110與111只有一位不同，而與000有兩位不同，因此判決為111。事實上，一般情況下錯1位的可能性比錯2位的可能性大得多，從統計的觀點看，這樣判決是正確的。因此，這種(3，1)碼能糾正一個錯誤，但不能糾正兩個錯誤，因為如果發送111，收到100，根據譯碼規則將譯為000，這就判錯了。類似于前面的分析，如果用這種碼來檢錯，則可以發現兩個錯誤，但是不能發現3個錯誤。如果按照重復碼的規則編成(4，1)碼，則長度為4的碼組共有16個，其中1111和0000為許用碼組，分別代表消息A和B，其余14個碼組為禁用碼組。類似的方法可以證明，這種碼距為4的(4，1)碼能夠糾正一個錯誤，同時發現兩個錯誤，如果僅作檢錯用，則可以發現3個錯誤。上述例子表明，糾錯碼的抗干擾能力完全取決于許用碼組之間的距離。碼的最小距離d0越大，說明碼字間的最小差別越大，抗干擾能力就越強，即受較強的干擾時仍然可以不造成許用碼組之間的混淆。糾錯碼的糾錯效果與信道誤碼率有密切的關系：信道誤碼率越低，糾錯效果越顯著，反之不顯著，信道誤碼率很大時甚至會出現“越糾越錯”的現象。

香農編碼定理告訴我們，只要信息傳輸速率不大于信道容量，在理論上存在一種方法，使得通過信道傳輸的數碼的差錯概率為任意小。香農編碼定理沒有給出具體的編碼方法，但是它指明了研究的方向。

3．分組碼的糾(檢)錯能力與最小碼距的關系任一(n，k)分組碼，如果要在碼字內：

(1)檢測e個隨機錯誤，則要求碼的最小距離d0≥e+1

(10.1)

(2)糾正t個隨機錯誤，則要求碼的最小距離

d0≥2t+1

(10.2)

(3)糾正t個同時檢測e(>t)個隨機錯誤，則要求碼的最小距離

d0≥t+e+1

(10.3)

下面利用幾何圖形進行簡要證明。設A1、A2是分組碼中相距d0的兩個碼字，分別位于A1及A2兩點。由圖10.2(a)可見，如果A1發生e個錯誤，則位置將移動e，至以A1為圓心、e為半徑的圓上某點，考慮造成使A1、A2兩碼組最難分辨的情況是移至

點。如果譯碼器不將錯判成A2，則必須使

與A2之間的距離d(，A2)≥1，因此檢測e個錯誤的條件是d0≥e+1。圖10.2糾(檢)錯能力的幾何解釋由圖10.2(b)可見，如果A1發生t個錯誤，則位置移至，d(A1，

)=t。如果譯碼器能把

正確判成A1，則必須要求d(A1，)<d(A2，)，即d(A2，)≥t+1。因此糾正t個錯誤的條件是d0≥2t+1。由圖10.2(c)可見，如果A1發生t個錯誤的同時A2發生e(>t)個錯誤，則位置分別移至及

，為了保證糾正t個同時檢測e個錯誤，必須要求d(，)≥1，即d0≥t+e+1。這里說的“同時”是指在譯碼過程中,如果錯誤個數小于等于t，則能糾正；如果錯誤個數大于t

且小于等于e(e>t)，則能檢測這些錯誤，但是不能糾正，或者說能檢測t+e個錯誤，其中t個錯誤可以糾正。

4．對糾錯編碼的基本要求以上討論說明，碼的最小距離d0越大，碼的糾(檢)錯的能力越強。但是，隨著多余碼元的增多，信息傳輸速率降低越多。通常用R=k/n來表示碼字中信息元所占的比例，稱為編碼效率，簡稱碼率。它是衡量碼性能的又一個重要參數。碼率越高，傳信率就越高，但是此時糾錯能力要降低，R=1時就沒有糾錯能力了。可見，碼率與糾錯能力之間是有矛盾的。對糾錯編碼的基本要求是：糾錯和檢錯能力盡量強；編碼效率盡量高；碼長盡量短；編碼規律盡量簡單。實際應用中應根據具體指標要求，保證有一定的糾檢錯誤的能力和編碼效率，要易于實現，節省費用。10.2檢錯碼10.2.1奇偶監督碼

1．意義及特點奇偶監督碼是奇監督碼和偶監督碼的統稱，是一種最基本的檢錯碼。在n-1個信息元后面附加一個監督元，使得長度為n的碼字中1的個數保持為奇數或者偶數的碼稱為奇偶監督碼。或者說,奇偶監督碼是r=1、W為奇數或偶數的系統分組碼。常用的奇偶監督碼的碼重W為偶數。設碼字A=［an-1，an-2，…，a1，a0］滿足an-1+an-2+…+a1+a0=0

(10.4)式中:a0為監督元；“+”為模二加(以后也這樣表示，請讀者注意)。由于這種碼的每一個碼字均按同一規則構成，因此又稱為一致監督碼。式(10.4)稱為一致監督方程或監督方程。

利用式(10.4)，由信息元即可求出監督元。另外，如果發生單個或者奇數個錯誤，就會破壞這個關系式，因此，通過該式能檢測碼字中是否發生了奇數個錯誤。以碼長n=5為例，列出全部偶監督碼字如表10.1所示。從表中可以看出，該碼的最小碼距為2，這是能檢測單個錯誤所要求的最小d0值。人們常把注意力集中在檢(糾)單個錯誤上，這是因為碼字中發生單個錯誤的概率比發生兩個、多個錯誤的概率要大得多。設碼字中各碼元的錯誤互相獨立，誤碼率為10-4，則n=5的碼字只錯一位的概率為

錯兩位的概率為

錯3、4、5位的概率分別為10-11、5×10-16、10-20。由此可見，要檢(糾)錯誤，首先要解決單個錯誤，這樣才抓住了主要矛盾。一般情況下用上述偶監督碼來檢出奇數個錯誤，檢錯效果是令人滿意的。奇偶監督碼不能發現偶數個錯誤。奇偶監督碼的編碼效率很高，R=(n-1)/n，隨著n的增大而趨近于1。

2．編碼電路和檢錯電路奇偶監督碼的編碼可以用數字軟件實現，也可以用編碼電路(硬件)實現。圖10.3是碼長為5的偶監督碼編碼器。4位長的信息組，串行送入4級移位寄存器(輸入定時緩沖器)，一旦存滿，立即輸送給輸出定時緩沖器前4級，同時經模2運算得到監督元，存入輸出緩沖器末級。編碼完成后即可輸出碼字。圖10.3偶監督碼編碼器接收端的檢錯電路如圖10.4所示。當一個接收碼組B完全進入5級移存器內時，開關S立即接通，從而取得檢錯信號M=b4+b3+b2+b1+b0。如果接收碼組B無錯，B=A，則M=0；如果接收碼組B有奇數個錯誤，則M=1。圖10.4偶監督碼的檢錯電路行列監督碼又稱為水平垂直一致監督碼、二維奇偶監督碼或者矩陣碼。它同時對水平(行)方向的碼元和垂直(列)方向的碼元實施奇偶監督。一般L×m個信息元，附加L+m+1個監督元，由L+1行、m+1列組成一個(Lm+L+m+1，Lm)行列監督碼的碼字。圖10.5是(66，50)行列監督碼的一個碼字(L=5，m=10)，它的各行和各列對1的數目都實行偶數監督。可以逐行傳輸，也可以逐列傳輸。譯碼時分別檢查各行、各列的監督關系，判斷是否有錯。圖10.5行列監督碼這種碼具有較強的檢測隨機錯誤的能力，能發現所有1、2、3及其它奇數個錯誤，也能發現大部分偶數個錯誤，但是分布在矩形的四個頂點這類偶數個錯誤則例外。這種碼適于檢測突發錯誤。逐行傳輸時，能檢測長度b≤m+1的突發錯誤；逐列傳輸時，能檢測長度b≤L+1的突發錯誤。這種碼還可以糾正單個錯誤以及僅在一行中的奇數個錯誤，因為這些錯誤的位置是可以由行、列監督而確定的。10.2.3恒比碼恒比碼又稱為等重碼或者定1碼，這種碼的碼字中1和0的位數保持恒定的比例。由于每個碼字的長度是相同的，因此，如果1、0恒比，則碼字必等重。如果碼長為n，碼重為W，則此碼的碼字個數為，禁用碼字數為。該碼的檢錯能力較強，除對換差錯(1和0成對地出錯)不能發現外，其他各種錯誤均能發現。目前我國電傳通信中普遍采用3∶2碼，該碼共有個許用碼字，用來傳送10個阿拉伯數字，如表10.2所示。這種碼又稱為5中取3數字保護碼。因為每個漢字是以4位十進制數來代表的，所以提高十進制數字傳輸的可靠性，就等于提高漢字傳輸的可靠性。實踐證明，采用這種碼后，我國漢字電報的差錯率大為降低。

目前國際上通用的ARQ電報通信系統中，采用3∶4碼,即7中取3碼，這種碼共有個許用碼字，93個禁用碼字。35個許用碼字用來代表不同的字母和符號。實踐證明，應用這種碼后，使國際電報通信的誤碼率保持在10-6以下。10.3線性分組碼10.3.1基本概念可以用線性方程組表述碼的規律性的分組碼稱為線性分組碼。奇偶監督碼是一種線性分組碼，因為它滿足線性方程式(10.4)。現在以(7，3)分組碼為例來說明線性分組碼的意義及特點。設該碼的碼字為A=［a6，a5，a4，a3，a2，a1，a0］，其中前3位是信息元，后4位是監督元，可以用下列線性方程組來表述這種線性分組碼，產生4個監督元：顯然,上述方程中各方程是線性無關的。對上式進行運算，可以得到(7，3)線性分組碼的8個碼字，如表10.3所示。我們可以把(n，k)線性分組碼的每一個碼字看成是一個n維線性空間中的一個矢量。長度為n的碼組共有2n個，組成一個n維線性空間，(n，k)線性分組碼共有2k個碼字(k<n)，構成了一個k維的線性子空間。因此，(n，k)線性分組碼是n維線性空間的一個k維子空間，這是線性分組碼的另一個定義。由于該線性子空間在模二加法運算中構成阿貝爾群，因此線性分組碼又稱為群碼。某種集合稱為群，此集合中的元素(在此為任一碼組)對于某種運算(在此為模二加法)必須滿足下列4個條件：

(1)封閉性(自閉律)。集合中的任意兩個元素經此運算后得到的仍為該集合中的元素。例如A1+A2=A3，A6+A7=A1等(A1、A2、…分別是表10.3中序號為1、2、…的碼字)。

(2)有零元(乘法運算為單位元)。如上例中A0即是零元，

A0+Ai=Ai

i=0，1,…，7

(3)有負元(乘法運算為逆元)。線性分組碼中任一碼組即是它自身的負元,

Ai+Ai=A0

i=0，1，…，7

(4)結合律成立。例如，(A2+A3)+A4=A2+(A3+A4)。如果除滿足上述4個條件外，又滿足交換律，則稱為交換群或者阿貝爾群。由于線性分組碼是滿足交換律的，如A1+A2=A2+A1等，因此，線性分組碼對于模二加法運算構成交換群。

(n，k)線性分組碼的封閉性表明，碼組集合中的任意兩個碼組模二相加所得的碼組，一定在該碼組集中。又由于兩個碼組模二和所得的碼組的重量等于這兩個碼組的距離，因此(n，k)線性分組碼中兩個碼組之間的距離一定等于該分組碼中某一非全0碼組的重量。所以，線性分組碼的最小距離必等于碼中非全0碼字的最小重量。設A0為全0碼矢，則有d0=Wmin(Ai)Ai∈(n，k)，i≠0

(10.6)

上述重要特點告訴我們，如何去查找一個線性分組碼的最小距離，進而明確該碼的糾(檢)錯能力。除此之外，線性分組碼還有以下特點：

(1)d(A1，A2)≤W(A1)+W(A2)；

(2)d(A1，A2)+d(A2，A3)≥d(A1，A3)；

(3)碼字的重量或者全部為偶數，或者奇數重量的碼字數等于偶數重量的碼字數。10.3.2漢明碼漢明碼是一種高碼率的糾單個錯誤的線性分組碼，其特點是d0=3，碼長n與監督元個數r滿足關系式n=2r-1。現以r=3、n=7的(7，4)漢明碼為例來說明(n，k)線性分組碼編碼和譯碼的理論依據。

1．監督矩陣H和生成矩陣G

設(7，4)漢明碼的碼字A=［a6，a5，a4，a3，a2，a1，a0］，它有3個監督元，可以建立3個互相獨立的監督關系式

(10.7)寫成矩陣形式為

簡記為H·AT=OT

或者

A·HT=O

(10.9)

其中AT是A的轉置，OT是O=[000]的轉置，HT是H的轉置。

(10.10)稱為(7，4)漢明碼的監督矩陣。(n，k)線性分組碼的監督矩陣H由r行n列組成，這r行是線性無關的。系統碼的監督矩陣可寫成如下形式：

H=[PIr]

(10.11)稱為典型監督矩陣，Ir為r×r的單位矩陣，P是r×k的矩陣。對式(10.10)，有

如果信息元已知，則通過P矩陣可以求得監督元。將式(10.7)變換成

(10.12)

即滿足

或者

(10.13)只要將PT矩陣擴展一下，在其左邊加上4×4的單位矩陣，即可由已知的信息元求得碼組A，即

(10.14)其中。設信息組M=［a6，a5，a4，a3］，則式(10.14)可以寫成

A=M·G

(10.15)G稱為生成矩陣。由生成矩陣及信息組就可以產生出全部碼字。G由k行n列組成，每一行是一個碼字，k行線性無關。系統碼的生成矩陣可以寫成：

G=［IkPT］(10.16)

稱為典型生成矩陣。利用式(10.14)產生的全部(7，4)碼的碼字如表10.4所示。

2．伴隨式(校正子)

設發送碼組A=［an-1，an-2，…，a1，a0］，接收碼組B=［bn-1，bn-2，…，b1，b0］，錯誤圖樣(誤差矢量)為E=［en-1，en-2，…，e1，e0］

E=B-A=B+A

E矩陣中哪位出現1，就表示接收碼組B中相應的碼元錯了。接收端利用監督矩陣來檢測接收碼組B中的錯誤。令S=BHT，稱為伴隨式或者校正子，則

S=BHT=(A+E)HT=AHT+EHT=EHT

(10.17)

由于E為1×n矩陣，HT為n×r矩陣，因此S為1×r矩陣，即r列的行矩陣

S=［Sr-1，Sr-2，…，S1，S0］(10.18)

由式(10.17)可知，S與E之間有確定的線性變換關系，即S能代表B中錯誤的情況，B無錯則S=0，B有錯則S≠0(非全0矩陣)。S有2r種不同的形式，可以代表2r-1種錯誤圖樣。為了用伴隨式指明單個錯誤的位置以便糾正，要求

2r-1≥n

(10.19)

對于(7，4)漢明碼，n=7，r=3，n=2r-1，即對式(10.19)取等號。這就表明用來糾正單個錯誤時，漢明碼所用的監督碼元位數最少。與碼長相同的其他糾單個錯誤的碼比較，其碼率最高。上述(7，4)漢明碼的伴隨式S與錯誤圖樣E的對應關系可以由式(10.17)求得，如表10.5所示。在接收端的譯碼器中有專門的伴隨式計算電路，可實現檢錯和糾錯。10.3.3循環碼循環碼是一類重要的線性分組碼，它的構造便于運用代數理論來研究。其編譯碼電路比較簡單，因此應用十分廣泛。

1．循環碼的意義及特點如果線性分組碼的任一碼組循環移位所得的碼組仍在該碼組集合中，則此線性分組碼稱為循環碼。很明顯，(n，1)重復碼是一個循環碼。表10.6中的(7，3)碼及表10.7中的(6，3)碼也都是循環碼，其循環特性分別如圖10.6及圖10.7所示。循環圈上的數字為碼字的序號。由圖可見，同一循環圈上的各碼組重量是相等的。全0、全1碼組分別自成循環圈。循環碼的循環圈數目≥2。圖10.6(7，3)循環碼的循環圈圖10.7(6，3)循環碼的循環圈

人們常用代數多項式來表示循環碼的碼字，稱為碼多項式。(n，k)循環碼的碼多項式按降冪順序排列為

A(x)=an-1xn-1+an-2xn-2+…+a1x+a0

(10.20)

碼組中各位碼元的數值是其碼多項式中相應各項的系數值(0或1)。例如,表10.6中第4號碼字可以用多項式A4(x)=x6+x3+x2+x表示。

2．生成多項式及生成矩陣循環碼中次數最低的多項式(全0碼字除外)稱為生成多項式g(x)。可以證明，g(x)是常數項為1的r=n-k次多項式，是xn+1的一個因式。循環碼的碼多項式都是g(x)的倍式。用多項式來表示生成矩陣的各行，則生成矩陣可以寫成

(10.21)其中

g(x)=xr+gr-1xr-1+…+g1x+1

(10.22)例如表10.6中(7，3)循環碼，n=7，k=3，r=4，其生成多項式及生成矩陣分別為

即生成矩陣中的3行都是表10.6中的碼字，并且是線性無關的。表10.6中的所有碼字用多項式表示時，均是g(x)的倍式。g(x)可由x7+1分解因式(系數按模二運算)得到x7+1=(x4+x3+x2+1)

(x3+x2+1)。設信息組M=［mk-1，mk-2，…，m1，m0］，則(n，k)循環碼的所有碼字由下式生成：A(x)=MG(x)=(mk-1xk-1+mk-2xk-2+…+m1x+m0)·g(x)

=m(x)·g(x)(10.23)其中m(x)為信息組多項式，其最高次數為k-1。由上式可見，知道m(x)及g(x)就可以生成全部碼字。但是，由式(10.23)直接產生的碼字并非系統碼。由于(n，k)循環碼的所有碼多項式都是g(x)的倍式，最高次數為n-1，因此系統循環碼的碼多項式可以表示為A(x)=xn-k·m(x)+［xn-k·m(x)］′

(10.24)其中，前一部分代表信息組；后一部分用［］′表示，是xn-k·m(x)被g(x)除得的余式，代表監督組。

3．監督多項式及監督矩陣由于(n，k)循環碼中的g(x)是xn+1的因式，因此可以令

(10.25)由于g(x)是常數項為1的r次多項式，因此h(x)必是常數項為1的k次多項式。h(x)稱為監督多項式。與式(10.21)所表示的G(x)相對應，監督矩陣可以表示為(10.26)其中h*(x)=xk+h1xk-1+h2xk-2+…+hk-1x+1(10.27)是h(x)的逆多項式。例如表10.6中的(7，3)循環碼：g(x)=x4+x3+x2+1則h*(x)=x3+x+1于是即

4．編碼電路根據式(10.24)，利用多項式除法電路求xn-km(x)除以g(x)的余式，即可產生(n，k)系統循環碼。當g(x)=x4+x3+x2+1時，(7，3)循環碼的編碼器如圖10.8所示。D0D1D2D3是4級移存器，反饋線的連接與g(x)的非0系數相對應。首先，4級移存器清零，3位信息元輸入時，門1斷開，門2接通，直接輸出信息元。第3次移位脈沖來時,將除法電路運算所得的余數存入4級移存器中。第4~7次移位時，門2斷開，門1接通，輸出監督元(即余數)。當一個碼字輸出完畢后,就將移存器清零，等待下一組信息數字送入后重新編碼。設輸入的信息組為110，圖10.8中各器件及端點狀態變化情況如表10.8所示。該編碼器編出的全部碼字如表10.6所示。圖10.8(7，3)循環碼編碼器

5．譯碼電路設接收碼組、錯誤圖樣及伴隨式的多項式分別為

B(x)=bn-1xn-1+bn-2xn-2+…+b1x+b0

E(x)=en-1xn-1+en-2xn-2+…+e1x+e0

S(x)=Sr-1xr-1+Sr-2xr-2+…+S1x+S0

可以證明

S(x)=B·HT(x)=［B(x)］′=［E(x)］′(10.28)即B(x)或E(x)除以g(x)所得的余式就是S(x)。用于檢錯時，根據S(x)是否為零來判決接收碼組B是否有錯，S(x)=0時,表明B無錯，S(x)≠0時,表明B有錯。用于糾錯時，需要根據不同的非零S(x)來指明不同的錯誤位置，從而糾正錯誤。伴隨式S(x)的計算由g(x)除法電路來實現。利用式(10.28)可以求得(7，3)循環碼單個錯誤的錯型多項式E(x)與伴隨式S(x)的對應關系，如表10.9所示。針對接收碼組中單個錯誤出現在首位的錯誤圖樣及相應的伴隨式來設計組合邏輯電路，以實現糾錯。由于循環碼的伴隨式也具有循環移位特性，因此利用移存器的循環移位就可以糾正任何一位上的單個錯誤。為了在g(x)除法電路的移存器中存放如表10.9所示的與E(x)對應的伴隨式，接收碼組必須從除法電路的第一級移存器輸入。上述(7,3)循環碼的譯碼電路如圖10.9所示。接收到的B(x)(高次項在前，低次項在后)一方面送入7級緩沖移位寄存器，一方面送入g(x)除法電路計算伴隨式。第7次移位時，7個碼元一組的碼組全部送入緩存器，B(x)中首位b6輸出，同時g(x)除法電路也得到了伴隨式S(x)(共4項，由低次到高次分別存于D0、D1、D2、D3中)，如果首位b6有錯，則D0D1D2D3的狀態必為0111。經與門輸出1(糾錯信號)，即可糾正b6的錯誤，該糾錯信號同時也送到S(x)計算電路去清零，如圖中虛線所示。此糾錯譯碼過程如表10.10所示。其他位上錯誤的糾正過程讀者可自行畫出。圖10.9(7，3)循環碼譯碼器之一為使譯碼連續不斷地進行，在譯碼器中需要采用兩套g(x)除法電路。采用像編碼器中的變形除法電路進行譯碼也是可以的，但是邏輯控制電路有所不同，如圖10.10所示，其譯碼過程供讀者自己研究。圖10.10(7，3)循環碼譯碼器之二10.3.4BCH碼

BCH碼是循環碼的一個子集，它是以三個發明者的名字Bose、Chaudhuri和Hocquenghem命名的，一般用于糾正t個錯誤。BCH碼的設計因具有良好的通用性并且有高效的譯碼算法而受到高度重視。對于任意碼長m≥2，糾錯數目為t的編碼，都存在滿足下列參數的BCH碼：n=2m-1，n-k≤mt，dmin=2t+1。由于m和t可以自由選擇，因此在碼長和碼率的設計上有很大的選擇余地。BCH碼已經過了詳細的推導，并且有了碼長為7~255的BCH碼生成多項式的系數表，有興趣的讀者可以查閱相關文獻。10.3.5里德-索洛蒙碼里德-索洛蒙(R-S，Reed-Solomon)碼是BCH碼的子集，因此也屬于循環碼。它是一種非二進制碼，即碼字c=(c1，c2,…，cn)中的任意元素ci是一個q進制數，q=2k，這時每個q進制字符包含k比特信息。在(N，K)R-S碼中，長度為K的q進制碼元將映射為長度為N的q進制碼元，然后在信道上傳送，如圖10.11所示。圖10.11R-S碼編碼器

R-S碼是按照下列條件定義的BCH碼：N=q-1=2k-1(k=2，3，…)，dmin=N-K+1，碼率Rc=K/N。R-S碼能夠糾正t=(dmin-1)/2個碼元錯誤。里德-索洛蒙碼具有優越的距離特性，特別適于與q進制調制聯合使用。R-S碼還能夠有效地糾正突發錯誤，因為突發錯誤在R-S碼中表現為少量幾個碼元錯誤，因而易于糾正。在二進制編碼中，同樣的突發錯誤會導致許多比特的錯誤，因而不容易糾正。

R-S碼還可以與二進制編碼進行連接，以獲得更強的糾錯能力。與R-S碼連接的二進制編碼可以是分組碼或者卷積碼。

圖10.12m=4的(28，16)交錯碼10.3.6交錯碼交錯碼又稱交織碼，是一種能糾正突發錯誤的碼。它是利用糾隨機錯誤的碼，以交錯的方法來構造碼本的。把糾隨機錯誤的(n，k)線性分組碼的m個碼字，排成m行的一個碼陣，該碼陣稱為交錯碼陣。一個交錯碼陣就是交錯碼的一個碼字。交錯碼陣中的每一行稱為交錯碼的子碼或行碼，行數m稱為交錯度。圖10.12所示的是(28，16)交錯碼的一個碼字，其行碼是能糾單個隨機錯誤的(7，4)線性分組碼，交錯度m=4。傳輸時按列的次序進行，因此送往信道的交錯碼的一個碼字為a61

a62

a63

a64

a51

a52…a01

a02

a03

a04。

圖10.12m=4的(28，16)交錯碼在傳輸過程中如果發生長度b≤4的單個突發錯誤，那么無論從哪一位開始，至多只影響圖10.12碼陣中每一行的一個碼元。接收端把收到的交錯碼的碼字再排成如圖10.12所示的碼陣，然后逐行分別譯碼，由于每一行碼能糾正一個錯誤，因此4行譯完后，就可把b≤4的突發錯誤糾正過來。如果要糾正較長的突發錯誤，則可以把碼陣中的行數增加，即增大交錯度(交織度)。一般，一個(n，k)碼能糾正t個隨機錯誤，按照上述方法交錯，交錯度為m時即可得到一個(nm，km)交錯碼,該交錯碼能糾正長度b≤mt的單個突發錯誤。可以證明，如果(n，k)是一個循環碼，它的生成多項式為g(x)，那么(nm，km)交錯碼也是一個循環碼，其生成多項式為g(xm)，且碼率與其行碼相同。10.4卷積碼卷積碼的規律性與分組碼有明顯的區別。(n，k)線性分組碼的規律性完全局限在各碼組之內,每個碼組的n個碼元完全由本組的k個信息元確定。或者說，各碼組中的監督元只對本組的信息元起監督作用。卷積碼則不同，每個(n，k)碼段(也稱子碼，通常較短)內的n個碼元不僅與該碼段內的信息元有關，而且與前面m段內的信息元有關。或者說，各碼段內的監督元不僅對本碼段而且對前面m段內的信息元起監督作用。卷積碼序列的每一碼段與前后有關碼段互相關聯，一環扣一環，因此又稱為連環碼。這種碼能用卷積運算的線性方程組描述。分組碼各碼組彼此獨立地進行編碼和譯碼。卷積碼則不然，無論編碼還是譯碼，各子碼都不能獨立地進行。卷積碼子碼間的約束關系如圖10.13所示。圖中A1，A2,…表示卷積碼序列中的各個子碼，均是(n，k)線性分組碼，各子碼之間的約束范圍如圖中虛線方框所示。通常稱m為編碼存儲，它反映了輸入信息元在編碼器中需要存儲的時間長短；稱N=m+1為編碼約束度，它是相互約束的碼段個數；稱nN為編碼約束長度，它是相互約束的碼元個數。卷積碼常用子碼長度、子碼中的信息元個數及編碼存儲三個參數表示，記為(n，k，m)，或用約束度及子碼符號表示，記為N(n，k)，也可用約束長度內的分組碼形式表示，記為(nN，kN)。如果卷積碼的各子碼是系統碼，則稱該卷積碼為系統卷積碼，否則為非系統卷積碼。很明顯，假如m=0，N=1，那么卷積碼就是(n，k)分組碼了。圖10.13卷積碼子碼間的約束關系圖10.14是一個(3，1，2)系統卷積碼的編碼器。由三級移位寄存器、兩個模二加法器及開關電路組成。編碼前，各級移存器清零，信息元按a1a2

a3…aj-2

aj-1

aj…的順序輸入編碼器。每輸入一個信息元aj，開關S依次接到aj、aj1、aj2各端點一次，編出一個子碼ajaj1aj2(n=3，k=1)，其中兩個監督元由下式確定：

(10.29)編碼器編出的任一子碼均與前面兩段信息元有關，因此編碼存儲m=2，編碼約束度N=m+1=3，約束長度Nn=9。圖10.14(3，1，2)卷積碼編碼器及輸入輸出關系10.5復合編碼分組碼和卷積碼的性能都與其距離特性有關。為了設計一個達到給定碼率并且具有較好距離特性的分組碼或者卷積碼，只有增加碼字的分組長度n或者卷積碼的約束長度，這將導致譯碼器復雜度增加。為了在增加碼字的有效分組長度或約束長度的同時，限制設備復雜度的增加，人們提出了許多方案，其中大多數方法都是通過合成簡單編碼而得到復雜編碼，合成碼的譯碼方法也是基于前面討論的簡單編碼。如果采用復雜的最佳譯碼算法，則通常也能獲得滿意的效果。下面簡單討論三種使用較為廣泛的復合編碼，即乘積碼、鏈接碼和Turbo碼。10.5.1乘積碼乘積碼也稱陣列碼，由以矩陣形式列出的兩個線性分組碼構成，如圖10.15所示。這兩個線性分組碼的參數分別是(n1，k1，dmin1)和(n2，k2，dmin2)，合成碼是參數為(n1n2，k1k2，dmin1

dmin2)的線性分組碼，它的最小距離是其組成碼的最小距離的乘積，即dmin=dmin1dmin2。如果采用復雜的最佳譯碼，則糾錯能力為

(10.30)圖10.15乘積碼的結構示意圖其中［.］表示向下取整。也可以用組成碼的特性來譯碼，譯碼思路如下:先根據行上的碼字猜測每一比特的值，再根據對應列上的碼字進一步修改猜測的結果。這一過程可以用迭代的方法反復進行，在每一步的迭代中逐漸提高猜測的準確度，稱這種譯碼方式為迭代譯碼。10.5.2鏈接碼鏈接碼包括一個內部碼和一個外部碼，兩者的連接方式如圖10.16所示。內部碼是二進制分組碼或者卷積碼，而典型的外部碼是R-S碼。設內部碼是(n，k)碼，可以把內部編碼器、數字調制器、波形信道、數字解調器和內部譯碼器合并起來看成一個數字信道，信道的輸入、輸出都是長度為k的二進制分組，或者說是q進制字符集中的一個元素。隨后,對這個q進制輸入、q進制輸出的信道運用R-S碼(外部碼)，以達到更高的糾錯性能。如果內部碼和外部碼的碼率分別是rc和Rc，則鏈接碼的碼率為

Rcc=Rcrc

(10.31)圖10.16鏈接碼結構示意圖10.5.3Turbo碼

Turob碼是一類特殊的鏈接碼，在兩個并聯或者串聯的編碼器之間存在一個數字交織器，使得Turbo碼具有很大的碼字長度和優越的性能，特別是在低SNR的情況下。采用Turbo碼可以在低SNR的情況下獲得接近0.7dB的香農極限。

Turbo碼編碼器的結構如圖10.17所示，兩個成員碼由長度為N的數字交織器分隔開。成員碼通常是碼率為1/2的遞歸系統卷積碼(RSCC，RecursiveSystematicConvolutionalCodes)，并且兩個成員碼通常是相同的。遞歸卷積碼與常見的非遞歸卷積碼的區別在于遞歸卷積碼移位寄存器中存在反饋，因此以無限脈沖響應(IIR，InfiniteImpulseResponse)的濾波器形式實現。圖10.17Turbo碼的編碼原理框圖圖10.17所示的編碼器中，在N比特信息進入第1編碼器的同時，通過交織器將此N比特信息傳送到第2編碼器。因為編碼器采用系統碼，所以每個編碼器的輸出在N個消息比特后加上了N個監督比特，最終的比特輸出是3N比特，即N比特信息和兩個編碼器的2N監督比特。因此總的碼率為R=N/(3N)=1/3。

Turbo碼中的數字交織器的長度通常都很大，采用偽隨機交織器可以獲得很好的性能。由于Turbo碼是由兩個成員碼構成的，因此可以采用迭代算法進行譯碼。所有服從比特的似然特性的譯碼都可以使用迭代算法實現，例如最大后驗概率譯碼及其各種變形等。還有一種復雜度較低的方法是軟輸出維特比算法(SOVA，SoftOutpotViterbiAlgorithm)，在這類譯碼中，第1級譯碼器計算出每一比特的似然度并送入第2級譯碼器，第2個譯碼器計算似然度后將結果進行修正并返回給第1級譯碼器。重復這一過程，直到似然度顯示的正確譯碼概率很高為止，則在這一點上得到最終判決。迭代過程如圖10.18所示，圖中ys、y1p、y2p分別表示對應于信息比特、系統比特編碼器1的監督比特、編碼器2的監督比特的接收數據，L12和L21表示在兩個譯碼器之間傳遞的信息。圖10.18Turbo碼迭代譯碼原理10.6m

序列

m序列是由線性反饋移位寄存器產生的周期最長的碼序列。m表示最長周期的意思。m序列是一種正交碼，它具有隨機特性，是目前廣泛應用的一種偽隨機或偽噪聲(PN)碼。10.6.1正交碼及偽隨機碼的概念如果n個長度均為P的碼組X1，X2，…，Xn所組成的集合中任意兩個不同碼組的互相關系數均為零，即

ρ(Xi，Xj)=0i≠j

(10.32)則稱這種碼組集合為正交碼。如果ρ(Xi，Xj)<0，i≠j，則稱為超正交碼。有時把兩者統稱為正交碼。對于(+1，-1)二元序列，互相關系數為(10.33)式中,Xik、Xjk分別表示碼組Xi、Xj的第k個碼元值。互相關系數也可以表示為

(10.34)式中,A為Xi、Xj中對應碼元相同的個數，D為Xi、Yj中對應碼元不同的個數。顯然,A+D=P。對于(0,1)二元序列，其互相關系數用式(10.34)計算，或者規定0、1分別對應+1、-1，再用式(10.33)計算。可以預先確定并且可以重復實現的序列稱為確定序列；具有隨機特性，貌似隨機序列的確定序列稱為偽隨機序列或偽噪聲(PN)碼。偽噪聲碼是很實用的正交碼。由于正交碼各碼組之間的相關性很弱，受到干擾后不容易互相混淆，因而具有較強的抗干擾能力。10.6.2線性反饋移位寄存器圖10.19是線性反饋移位寄存器的原理框圖，它由n級移位寄存器、時鐘脈沖產生器(省略未畫)及一些模二加法器經適當連接而成。圖中，ai(i=0，1，…，n-1)表示某一級移存器的狀態;Ci表示反饋線的連接狀態(相當于反饋系數)，Ci=1表示此線接通，參與反饋，Ci=0表示此線斷開，不參與反饋。C0=Cn=1。圖10.19線性反饋移位寄存器

(1)遞推關系式(反饋邏輯函數)。移位寄存器各級的初始狀態及反饋連接狀態如圖10.19所示，反饋到第1級的信號為一般，如果n級移存器的狀態為al-1，al-2，…，al-n，則反饋到第1級的信號為

(10.35)根據遞推關系式(10.35)，可以從移位寄存器的初始狀態(l=n時)a0，a1，…，an-1直接推導出an，an+1，…，從而得到整個輸出序列{ak}。

(2)序列多項式(母函數)。輸出序列{ak}=a0，a1，a2，…用多項式表示時，可寫成

(10.36)稱為序列多項式。

(3)特征多項式(特征方程)。把反饋系數C0,C1,…,Cn寫成多項式形式，即

(10.37)稱為線性反饋移存器的特征多項式。由于C0=Cn=1，因此特征多項式必包含xn+1項。特征多項式的次數n就是移位寄存器的級數。Ci的取值(0或1)確定了反饋線的連接狀態。

(4)線性反饋移位寄存器的相繼狀態具有周期性，周期P≤2n-1。n級線性反饋移位寄存器能產生m序列(P=2n-1)的充要條件是：移存器的特征多項式f(x)為本原多項式。f(x)為n次本原多項式，必須滿足三個條件：第一，f(x)為既約(不可再分解的)多項式；第二，f(x)能整除xP+1，P=2n-1；第三，f(x)不能整除xq+1，q<P。10.6.3m序列產生器要構成m序列產生器，關鍵是確定其特征多項式。現以4級移位寄存器構成周期為P=24-1=15的m序列產生器為例來說明。先將x15+1分解因式，使各因式為既約多項式，再從中尋找次數為4的本原多項式,即x15+1=(x+1)(x2+x+1)(x4+x+1)(x4+x3+1)(x4+x3+x2+x+1)其中4次既約多項式有3個，但是x4+x3+x2+x+1能整除x5+1，因此它不是本原多項式，而x4+x+1或x4+x3+1不能整除xq+1(q<15)，因此它們均是本原多項式。取f(x)=1+x+x4，構成的m序列產生器如圖10.20所示。設4級移位寄存器的初始狀態為1000，其相繼狀態如圖所示。由圖可見，輸出序列{ak}的周期長度為15。值得注意的是，移位寄存器的初始狀態不能為全0，否則輸出序列就是全0了。為此，m序列產生器中通常有所謂的全0排除電路，這樣才能確保m序列產生器正常工作。圖10.20m序列的產生10.6.4m序列的性質

(1)均衡特性(平衡性)。m序列每一周期中1的個數比0的個數多1。P=2n-1為奇數，1的個數為(P+1)/2=2n-1(偶數)，0的個數為(P-1)/2=2n-1-1(奇數)。P足夠大時，在每一周期中1與0出現的次數基本相同(均衡)。上例中P=15，1為8個，0為7個。

(2)游程特性(游程分布的隨機性)。游程是序列中連續出現同種元素的統稱。一個游程中元素的個數稱為游程長度。m序列每個周期中的游程總數為2n-1(偶數)，“1”游程與“0”游程的數目各占一半。其中:長度為n的“1”游程1個；長度為n-1的“0”游程1個；長度為n-2的游程21=2個;長度為n-3的游程22=4個。一般，長度為k的游程個數為2n-k-1個，1≤k≤n-1。在k的取值范圍內，游程長度每減短1，則其游程數目加倍。長度為1的游程個數為2n-2，是游程總數的一半。上例中一個周期內的碼元為000111101011001，可見長度為1的“1”游程、“0”游程各為2個，長為2的“1”游程、“0”游程各為1個，長為3的“0”游程1個，