第12章差錯控制編碼12.1概述12.2差錯控制編碼的基本原理12.3常用的簡單編碼12.4線性分組碼12.5循環(huán)碼12.6卷積碼12.1概述數(shù)據(jù)在網(wǎng)絡(luò)中傳輸時,由于信道噪聲及信道傳輸特性不理想等因素的影響,接收端所收到的數(shù)據(jù)不可避免地會發(fā)生錯誤。通常,傳輸中報文數(shù)據(jù)的部分內(nèi)容出錯的情況可能比整個報文內(nèi)容完整無缺地到達(dá)目的地的情況要多得多。因此,一個可靠的數(shù)據(jù)傳輸系統(tǒng)必須具有檢測或糾正這種錯誤的機(jī)制。通過編碼來實現(xiàn)對傳輸中出現(xiàn)的錯誤進(jìn)行檢測或糾正的方法稱為差錯控制編碼。差錯控制編碼的基本(實現(xiàn))方法是在發(fā)送端將被傳輸?shù)臄?shù)據(jù)信息(信息碼)中增加一些多余的比特(監(jiān)督碼),使原來彼此相互獨立沒有關(guān)聯(lián)的信息碼與監(jiān)督碼經(jīng)過某種變換后產(chǎn)生某種規(guī)律性或相關(guān)性。接收端按照一定的規(guī)則對信息碼與監(jiān)督碼之間的相互關(guān)系進(jìn)行校驗,一旦傳輸發(fā)生差錯,則信息碼與監(jiān)督碼的關(guān)系就受到破壞,從而接收端可以發(fā)現(xiàn)以至糾正傳輸中產(chǎn)生的錯誤。通過差錯控制編碼這一環(huán)節(jié),使系統(tǒng)具有一定的檢錯或糾錯能力,可減少接收信息中的錯誤,提高系統(tǒng)的抗干擾能力。在OSI模型中,檢測錯誤或糾正錯誤可以在數(shù)據(jù)鏈路層實現(xiàn),也可以在傳輸層實現(xiàn)。所謂檢測錯誤(簡稱檢錯),是指接收端僅對接收到的信息進(jìn)行正確或錯誤判斷,而不對錯誤進(jìn)行糾正。所謂糾正錯誤(簡稱糾錯),是指接收端不僅能對接收到的信息進(jìn)行正確或錯誤判斷,而且能對錯誤進(jìn)行糾正。由于信道噪聲及信道傳輸特性的不同,造成錯誤的統(tǒng)計特性也不同。傳輸信道中常見的錯誤有以下三種:

(1)隨機(jī)錯誤。這種錯誤是隨機(jī)出現(xiàn)的,通常不是成片地出現(xiàn)錯誤,并且各個錯誤的出現(xiàn)是統(tǒng)計獨立的。這種情況一般是由信道的加性隨機(jī)噪聲引起的。因此,一般將具有此特性的信道稱為隨機(jī)信道。

(2)突發(fā)錯誤。這種錯誤是相對集中出現(xiàn)的,即在短時間段內(nèi)有很多錯誤出現(xiàn)。這種情況如移動通信中信號在某一段時間內(nèi)發(fā)生衰落,造成一串錯誤;汽車發(fā)動時電火花干擾造成的錯誤;光盤上的一條劃痕等等。這樣的信道我們稱之為突發(fā)信道。

(3)混合錯誤。這種錯誤是指既有突發(fā)錯誤又有隨機(jī)差錯的情況。這種信道稱之為混合信道。

1.檢錯重發(fā)方式

檢錯重發(fā)又稱反饋糾錯。發(fā)送端在被傳輸?shù)臄?shù)據(jù)信息中增加一些監(jiān)督碼編成碼組,使其具有一定的檢錯能力。接收端對接收到的碼組按一定的規(guī)則進(jìn)行有無錯誤的判斷,并將判斷結(jié)果通過反饋信道送回發(fā)送端。發(fā)送端根據(jù)應(yīng)答信號內(nèi)容來決定是重新發(fā)送原來數(shù)據(jù)信息還是發(fā)送新數(shù)據(jù)信息。以此往復(fù),直至將數(shù)據(jù)信息正確接收完為止。檢錯重發(fā)方式有如下6個特點:

(1)編譯碼簡單,容易實現(xiàn);

(2)編碼效率高,只需要少量的冗余碼就能獲得極低的輸出誤碼率;

(3)所使用的檢錯碼與傳輸出錯的統(tǒng)計特性無關(guān),對各種信道的不同錯誤特性有一定的適應(yīng)能力;

(4)通信系統(tǒng)必須要有反饋信道,因而不能用于單向傳輸系統(tǒng)和一點對多點的同播系統(tǒng);(5)由于檢錯重發(fā)的隨機(jī)性,接收端送給用戶的正確數(shù)據(jù)信息也是隨機(jī)到達(dá)的,因此不適合實時數(shù)據(jù)傳輸;

(6)當(dāng)信道干擾增大時,數(shù)據(jù)傳輸中錯誤增多,這將導(dǎo)致系統(tǒng)通信效率降低。檢錯重發(fā)系統(tǒng)稱為自動要求重發(fā)ARQ(AutomaticRepeatreQuest)系統(tǒng)。圖12-1是檢錯重發(fā)差錯控制系統(tǒng)的組成框圖。檢錯重發(fā)系統(tǒng)有三種主要工作方式:發(fā)送等候(SWARQ)工作方式、連續(xù)工作方式和混合工作方式。連續(xù)工作方式又可分為退N或往返重發(fā)N方式(GBNARQ)和選擇性重發(fā)方式(SNARQ)。圖12-1檢錯重發(fā)差錯控制系統(tǒng)的組成發(fā)送等候(SWARQ)工作方式是一種簡單的檢錯重發(fā)方式,其工作過程如圖12-2所示。圖中1,2,3,…是發(fā)送的數(shù)據(jù)組;ACK是接收數(shù)據(jù)沒有錯誤的應(yīng)答信號,請求發(fā)送端發(fā)送新數(shù)據(jù)組;NAK是接收數(shù)據(jù)中出現(xiàn)錯誤的應(yīng)答信號,請求發(fā)送端重新發(fā)送前一數(shù)據(jù)組。由圖12-2可以看出,發(fā)送端每發(fā)送完一個數(shù)據(jù)組都要等待接收應(yīng)答信號。若應(yīng)答信號是ACK,則發(fā)送新數(shù)據(jù)組;若應(yīng)答信號是NAK,則重新發(fā)送前一數(shù)據(jù)組。這種檢錯重發(fā)方式簡單、易于實現(xiàn),并且誤碼率可以做得很低,適用于半雙工通信及數(shù)據(jù)網(wǎng)之間的通信。圖12-2發(fā)送等候方式工作過程

2.前向糾錯方式(FEC)

前向糾錯方式(ForwardErrorCorrection,FEC)數(shù)據(jù)通信系統(tǒng)原理如圖12-3所示,由發(fā)送數(shù)據(jù)終端、糾錯碼編碼器、數(shù)據(jù)信道、糾錯碼譯碼器、接收數(shù)據(jù)終端等部分組成。發(fā)送端在被傳輸?shù)臄?shù)據(jù)信息中增加一些監(jiān)督碼編成碼組,使其具有一定的糾錯能力。接收端對接收到的碼組按一定的規(guī)則進(jìn)行譯碼,判斷接收到的碼組有無錯誤。若無錯誤,則譯碼器直接將數(shù)據(jù)信息送給接收數(shù)據(jù)終端;若有錯誤并且錯誤在糾錯能力之內(nèi),則譯碼器對錯誤進(jìn)行糾正后再將數(shù)據(jù)信息送給接收數(shù)據(jù)終端。圖12-3前向糾錯數(shù)據(jù)通信系統(tǒng)原理前向糾錯方式有如下4個主要特點:

(1)通信系統(tǒng)不需要反饋信道,能用于單向通信系統(tǒng),因而也適用于一點對多點的同播系統(tǒng);

(2)譯碼延遲固定,適用于實時傳輸系統(tǒng);

(3)糾錯能力與所加的冗余碼多少有關(guān),為了得到較強(qiáng)的糾錯能力所需要的冗余碼較多,因而編碼效率較低;

(4)當(dāng)傳輸中產(chǎn)生的錯誤超過碼的糾錯能力時,帶有錯誤的數(shù)據(jù)信息有可能送給用戶,從而造成用戶接收到有錯的數(shù)據(jù)信息。

3.混合差錯控制方式(HEC)

混合差錯控制方式(HybridErrorCorrection,HEC)是前向糾錯與檢錯重發(fā)兩種差錯控制方式的結(jié)合。發(fā)送端進(jìn)行同時具有自動糾錯和檢錯能力的編碼,接收端收到碼組后,首先進(jìn)行錯誤情況判斷,如果出現(xiàn)的錯誤在該編碼的糾錯能力之內(nèi),則自動對錯誤進(jìn)行糾正。如果信道干擾嚴(yán)重,出現(xiàn)的錯誤超過了該編碼的糾正錯誤能力,但是在檢測錯誤能力之內(nèi),則經(jīng)過反饋信道請求發(fā)送端重新發(fā)送這組數(shù)據(jù)。如果信道干擾非常嚴(yán)重,出現(xiàn)的錯誤不僅超過了該編碼的糾正錯誤能力,而且超過了該編碼的檢測錯誤能力,對這種嚴(yán)重的錯誤,這種差錯控制方式將失去作用,譯碼器會將有錯誤的數(shù)據(jù)送給數(shù)據(jù)終端,從而產(chǎn)生接收數(shù)據(jù)出錯?；旌喜铄e控制方式的原理如圖12-4所示。發(fā)送端的差錯控制編碼應(yīng)同時具有檢測錯誤和糾正錯誤的能力。圖12-4混合差錯控制方式原理圖混合差錯控制方式有以下4個主要特點:

(1)同時具有檢測錯誤和糾正錯誤的能力。

(2)克服了檢錯重發(fā)方式數(shù)據(jù)連貫性差、通過率隨信道錯誤率的增加而迅速降低的嚴(yán)重缺點。

(3)避免了前向糾錯方式為了得到低的錯誤率,使得編碼效率低、需要很復(fù)雜的譯碼器及不能適應(yīng)信道錯誤變化的缺點。

(4)需要雙向信道。圖12-5糾錯碼的各種類型

12.2差錯控制編碼的基本原理

12.2.1糾錯編碼的基本原理

差錯控制編碼也稱糾錯編碼,其基本原理是在信息碼元序列中加入一定的監(jiān)督碼元,使編成的碼組具有一定的檢測錯誤和糾正錯誤的能力,糾錯編碼包括檢錯編碼和糾錯編碼。不同的編碼方法有不同的檢錯和糾錯能力。一般來說,付出的代價越大,檢(糾)錯的能力就越強(qiáng)。這里所說的代價,就是指增加的監(jiān)督碼元的多少。例如,若編碼序列中,平均每兩個信息碼元就有一個監(jiān)督碼元,則這種編碼的冗余度為1/3。換一種說法,這種編碼的編碼速率為2/3。下面以一個簡單的例子來闡述差錯編碼在相同的信噪比情況下為什么會獲得更小的誤碼率性能。假設(shè)我們發(fā)送一個開關(guān)的斷開和閉合兩種狀態(tài),用二進(jìn)制碼元的“0”表示開關(guān)處于“斷開”狀態(tài),用二進(jìn)制碼元的“1”表示開關(guān)處于“閉合”狀態(tài)。這時,若碼元在傳輸過程中出現(xiàn)錯誤,將“0”碼元接收為“1”碼元,或?qū)ⅰ?”碼元接收為“0”碼元,則因為接收端無法發(fā)現(xiàn)錯碼,而將收到錯誤信息。如果將開關(guān)的“斷開”和“閉合”兩種狀態(tài)信息用2個二進(jìn)制碼元表示,即進(jìn)行2個二進(jìn)制碼元編碼,共有4種編碼:“00”、“01”、“10”和“11”。選擇其中的“00”表示開關(guān)處于“斷開”狀態(tài),“11”表示開關(guān)處于“閉合”狀態(tài)。另外還有兩種編碼“01”和“10”沒有選用,稱為禁用碼組。若發(fā)送端發(fā)送的是“00”編碼,如果碼組在傳輸過程中出現(xiàn)1個錯誤,則接收到的碼組可能是“01”或“10”。由于“01”和“10”兩種編碼是禁用碼組,因此我們可以判定接收到的碼組出現(xiàn)了錯誤。同樣,若發(fā)送端發(fā)送的是“11”編碼,如果碼組在傳輸過程中出現(xiàn)1個錯誤,則接收到的碼組也可能是“01”或“10”,我們也可以判定接收到的碼組出現(xiàn)了錯誤,從而實現(xiàn)了檢測錯誤。通過這種簡單的重復(fù)編碼就可以實現(xiàn)對碼組中一個錯誤的檢測。但是這種編碼不能實現(xiàn)對兩個或兩個以上的錯碼進(jìn)行檢測,也不能糾正錯碼。如果采用更多個二進(jìn)制碼元編碼來表示開關(guān)的“斷開”和“閉合”兩種狀態(tài)則情況會如何？例如采用3個二進(jìn)制碼元編碼共有8種編碼:“000”、“001”、“010”、“011”、“100”、“101”、“110”和“111”。選擇其中的“000”表示開關(guān)處于“斷開”狀態(tài),“111”表示開關(guān)處于“閉合”狀態(tài)。另外6種編碼“001”、“010”、“011”、“100”、“101”和“110”為禁用碼組。在接收端我們用如下的譯碼方法,每收到3個比特譯碼一次,采用大數(shù)判決,即3個比特中0的個數(shù)大于1的個數(shù)則譯碼成0,反之譯碼成1。若發(fā)送端發(fā)送的是“000”編碼,如果碼組在傳輸過程中出現(xiàn)1個錯誤,則接收到的碼組可能是“001”、“010”或“100”。由于這三種編碼是禁用碼組,因此我們可以判定接收到的碼組出現(xiàn)了錯誤。更進(jìn)一步,由于接收到的碼組“001”、“010”或“100”中0的個數(shù)大于1的個數(shù),根據(jù)大數(shù)判決規(guī)則譯碼,則譯碼器譯成“000”碼輸出,糾正了傳輸中出現(xiàn)的1個錯碼。同樣,若發(fā)送端發(fā)送“111”編碼,如果碼組在傳輸過程中出現(xiàn)1個錯誤,接收端根據(jù)大數(shù)判決規(guī)則譯碼,則譯碼器譯成“111”碼輸出,也糾正了傳輸中出現(xiàn)的1個錯碼?？梢?這種糾錯編碼方法能夠糾正1個錯碼。從這個簡單例子可以看到:當(dāng)發(fā)送的信息編碼中沒有冗余碼時,接收端譯碼器不能檢測和糾正錯碼;當(dāng)在發(fā)送的信息編碼中加入1個冗余碼時,接收端譯碼器能夠檢測出1個錯碼,但是不能糾正錯碼;當(dāng)在發(fā)送的信息編碼中加入2個冗余碼時,接收端譯碼器能夠檢測出2個或1個錯碼,或糾正1個錯碼。檢測或糾正錯碼能力的增強(qiáng)是通過增加發(fā)送編碼中冗余碼而得到的。糾錯編碼的基本原理是:為了使信源信息具有檢錯和糾錯能力,應(yīng)當(dāng)按一定的規(guī)則在信息碼中增加一些冗余碼(又稱監(jiān)督碼),使這些冗余碼與被傳送信息碼之間建立一定的關(guān)系,發(fā)送端完成這個任務(wù)的過程就稱為差錯控制編碼(或糾錯編碼);在接收端,根據(jù)信息碼與監(jiān)督碼的特定關(guān)系,實現(xiàn)檢錯或糾錯,輸出原信息碼,完成這個任務(wù)的過程就稱差錯控制譯碼(或糾錯譯碼)。另外,無論檢錯和糾錯,都有一定的識別范圍。差錯控制編碼原則上是以降低信息傳輸速率來換取信息傳遞的可靠性的提高。我們研究誤碼控制編碼的目的,正是為了尋求較好的編碼方式,在盡可能少的增加冗余碼的情況下來實現(xiàn)盡可能強(qiáng)的檢錯和糾錯能力。12.2.2糾錯編碼的基本概念

1.信息碼元與監(jiān)督碼元

信息碼元又稱信息位,這是指由發(fā)送端信源發(fā)送的信息數(shù)據(jù)比特,通常以mi表示。由信息碼元組成的信息碼組為 M=(mk-1,

mk-2

,…

,m0)

(12.2-1)

其中,k為信息碼組中信息碼元的個數(shù)。在二進(jìn)制碼情況下,每個信息碼元mi的取值只有0或1兩種狀態(tài),所以總的信息碼組數(shù)共有2k個。

監(jiān)督碼元又稱監(jiān)督位,這是為了檢測或糾正錯碼而在信息碼組中加入的冗余碼。監(jiān)督碼元的個數(shù)通常以r表示。

2.分組碼

在糾錯編碼時,將r個監(jiān)督碼元附加在由k個信息碼元組成的信息碼組上,構(gòu)成一個就有糾錯功能的獨立碼組,并且監(jiān)督碼元僅與本碼組中的信息碼組有關(guān),這種按組進(jìn)行編碼的方法稱為分組碼。

分組碼通常用符號(n,k)表示,其中,n表示分組碼碼組長度;k表示信息碼元個數(shù);r=n-k,表示監(jiān)督碼元個數(shù)。在二進(jìn)制編碼中,通常分組碼都是k個信息碼元在前,r個監(jiān)督碼元附加在k個信息碼元之后,其結(jié)構(gòu)如圖12-6所示。圖12-6分組碼結(jié)構(gòu)圖通常把信息碼元個數(shù)k與碼組長度n之比稱為糾錯編碼的編碼效率或編碼速率,表示為(12.2-2)編碼效率是衡量糾錯碼性能的一個重要指標(biāo),一般情況下,監(jiān)督位越多,檢糾錯能力越強(qiáng),但相應(yīng)的編碼效率也隨之降低。

3.許用碼組與禁用碼組

在二進(jìn)制編碼中,若分組碼碼組長度為n,則總的碼組數(shù)應(yīng)為2n=2k+r個。其中被傳送的碼組有2k個,通常稱為許用碼組;其余的2n-2k個碼組不傳送,稱為禁用碼組。發(fā)送端糾錯編碼的任務(wù)正是尋求某種規(guī)則從總碼組數(shù)2n中選出2k個許用碼組,而接收端譯碼的任務(wù)則是利用相應(yīng)的規(guī)則來判斷收到的碼字是否符合許用碼組,對錯誤進(jìn)行檢測和糾正。

4.碼重、碼距與最小碼距

碼組的重量(簡稱碼重)是指碼組中非零元素的個數(shù)。對于二進(jìn)制編碼,碼重就是碼組中1的個數(shù)。例如:000碼組的重量是0,101碼組的重量是2。

碼組的距離(簡稱碼距)是指兩個碼組ci、cj之間不同比特的個數(shù),數(shù)學(xué)表示為(模q)（12.2-3）最小碼距是指在一個碼組集合中,任意兩個碼組之間距離的最小值,以字母d0表示,(模q)(12.2-4)最小碼距也稱最小漢明距離。例如:000、101與111三個碼組之間的最小碼距d0=1。

5.最小碼距d0與糾錯能力的關(guān)系

糾錯編碼理論的研究結(jié)果表明,最小碼距d0與檢、糾錯能力之間滿足下列關(guān)系:

(1)若碼組用于檢測e個錯誤時,則放大碼距:(12.2-5)(2)若碼組用于糾正t個錯誤時,則放大碼距:(12.2-6)(3)若碼組用于糾正t個錯誤,同時檢測e個錯誤時,則放大碼距:(12.2-7)圖12-7最小碼距與檢錯和糾錯能力的關(guān)系

6.編碼增益

差錯控制編碼使數(shù)據(jù)通信系統(tǒng)具有一定的糾錯能力,這種能力可以用編碼增益來衡量。在保持誤碼率不變的情況下,采用糾錯編碼所節(jié)省的信噪比Eb/n0稱為編碼增益,用分貝形式表示如下:(12.2-8)編碼增益也反映了譯碼后數(shù)據(jù)信息的誤碼率與譯碼前數(shù)據(jù)信息在信道傳輸中的誤碼率相比較時所得到的改進(jìn)量。不同的糾錯編碼具有不同的編碼增益,它和編碼方式、譯碼方式及信道誤碼率pe等因素有關(guān)。譯碼后的誤碼率pB可以近似表示為(12.2-9)

12.3常用的簡單編碼

1.奇偶監(jiān)督碼

奇偶監(jiān)督碼是一種用于檢測錯誤的簡單編碼,分為奇監(jiān)督碼和偶監(jiān)督碼兩種。編碼時只需要在信源輸出的信息碼的后面添加一位監(jiān)督碼元(又稱校驗碼元),使得碼組中“1”的個數(shù)是奇數(shù)個或偶數(shù)個。例如,若信源送出的信息碼是1001101,信息碼中有4個“1”,經(jīng)過編碼器輸出碼組為10011011,在信息碼后加了1個監(jiān)督碼“1”,使該碼組中“1”的個數(shù)為奇數(shù)個,這種編碼方法是奇監(jiān)督碼。若信息碼1001101經(jīng)過編碼器后輸出碼組為10011010,在信息碼后加了1個監(jiān)督碼“0”,使該碼組中“1”的個數(shù)為偶數(shù)個,這種編碼方法是偶監(jiān)督碼。設(shè)碼組為,則奇監(jiān)督碼滿足如下關(guān)系式:(12.3-1)偶監(jiān)督碼滿足:(12.3-2)式中,是信息位;a0是監(jiān)督位。奇偶監(jiān)督碼的譯碼方法也很簡單。若對于偶監(jiān)督碼,在接收端只需對接收到的碼組按式(12.3-2)進(jìn)行驗證。若計算結(jié)果為“0”,則認(rèn)為接收到的碼組是正確的,若計算結(jié)果為“1”,則接收到的碼組是錯誤的。奇偶監(jiān)督碼檢測錯誤的能力有限,它只能檢測出所有奇數(shù)個錯碼,不能檢測出偶數(shù)個錯碼。另外,該碼組的最小碼距d0=2,故沒有糾正錯碼的能力。由于在奇偶監(jiān)督碼中,無論信息位有多少位,監(jiān)督位只有一位,因此編碼效率很高。奇偶監(jiān)督碼組長度為n,信息位長度為n-1,所以編碼效率為(12.3-3)與一維奇偶監(jiān)督碼相比,二維奇偶監(jiān)督碼增加了列監(jiān)督碼,因此編碼效率有所降低,圖12-8所示的二維奇偶監(jiān)督碼編碼效率為(12.3-4)圖12-9二維奇偶監(jiān)督碼檢錯、糾錯原理(a)發(fā)送碼;(b)接收碼

3.循環(huán)冗余校驗(CRC)

循環(huán)冗余校驗的英文全稱為CyclicRedundancyCheck,它是一類重要的線性分組碼,編碼和解碼方法簡單,檢錯能力強(qiáng),在數(shù)據(jù)通信領(lǐng)域廣泛地用于實現(xiàn)差錯控制。

利用CRC進(jìn)行檢錯的過程可簡單描述為:在發(fā)送端根據(jù)要傳送的k位二進(jìn)制信息碼序列,以一定的規(guī)則產(chǎn)生一個校驗用的r位監(jiān)督碼(CRC碼),附在原始信息碼后邊,構(gòu)成一個新的二進(jìn)制碼序列數(shù)共k+r位,然后發(fā)送出去。在接收端,根據(jù)信息碼和CRC碼之間所遵循的規(guī)則進(jìn)行檢驗,以確定接收的數(shù)據(jù)中是否出錯。

CRC校驗采用多項式編碼方法,被處理的信息序列可以看做是一個n階的二進(jìn)制多項式,標(biāo)準(zhǔn)形式如下:(12.3-5)

(3)用xrm(x)以模2的方式加上r(x),得到二進(jìn)制多項式(模2)T(x)就是包含了CRC校驗碼的待發(fā)送數(shù)據(jù)序列。為了更清楚地了解CRC校驗碼的編碼原理,下面用一個簡單的例子來說明CRC的編碼過程。設(shè)信息碼為1100,生成多項式為1011,即m(x)=x3+x2,g(x)=x3+x+1,計算CRC的編碼過程為即r(x)=x,注意到g(x)的最高冪次r=3,得出CRC為010。由此可產(chǎn)生待發(fā)送的二進(jìn)制碼為1100000+010=1100010,其對應(yīng)的二進(jìn)制多項式為從CRC的編碼規(guī)則可以看出,CRC編碼實際上是將待發(fā)送的k位信息碼的二進(jìn)制多項式m(x)轉(zhuǎn)換成了可以被生成多項式g(x)除盡的k+r位二進(jìn)制多項式T(x)。所以解碼時可以用接收到的數(shù)據(jù)多項式去除生成多項式g(x),如果余數(shù)為零,則表示接收數(shù)據(jù)中沒有錯誤;如果余數(shù)不為零,則接收數(shù)據(jù)中肯定存在錯誤。同時,T(x)可以看做是由m(x)和CRC校驗碼的組合,所以解碼時將接收到的二進(jìn)制數(shù)據(jù)去掉尾部的r位校驗,得到的就是原始信息。多項式除法可用除法電路來實現(xiàn)。除法電路的主體由一組移位寄存器和模2加法器組成。CRC-ITU標(biāo)準(zhǔn)的CRC校驗碼生成多項式g(x)=x16+x12+x5+1,除法電路原理如圖12-10所示,它由16級移位寄存器和3個模2加法器組成(編碼器、解碼器結(jié)構(gòu)相同)。編碼、解碼前將各寄存器初始化為“1”,信息位隨著時鐘移入。當(dāng)信息位全部輸入后,從寄存器組輸出CRC結(jié)果。圖12-10CRC-ITU標(biāo)準(zhǔn)的除法電路原理表12-1列出了一些常見的CRC標(biāo)準(zhǔn)。CRC-16用于IBM的同步數(shù)據(jù)鏈路控制規(guī)程SDLC的幀校驗序列FCS;CRC-ITU用于ITU推薦的高級數(shù)據(jù)鏈路控制規(guī)程HDLC的幀校驗序列FCS等。一般情況下,r階生成多項式產(chǎn)生的CRC碼可檢測出所有的奇數(shù)位錯誤和突發(fā)長度小于等于r的突發(fā)錯誤,以及(1-2-(r-1))%的突發(fā)長度為r+1的突發(fā)錯誤和(1-2-r)%的突發(fā)長度大于r+1的突發(fā)錯誤。所以CRC生成多項式的階數(shù)越高,則誤判的概率就越小。例如對CRC-16的情況,能檢測出所有突發(fā)長度小于等于16的突發(fā)錯誤,以及99.997%的突發(fā)長度為17的突發(fā)錯誤和99.998%的突發(fā)長度大于17的突發(fā)錯誤。而CRC-32的誤判概率是CRC-16的1/105。可以看出CRC碼的檢錯能力還是很強(qiáng)的。表12-1常見的CRC標(biāo)準(zhǔn)

12.4線性分組碼

12.4.1線性分組碼原理

線性分組碼是一種定義在Galois域(記作GF(q))上的代數(shù)碼,在數(shù)據(jù)通信系統(tǒng)中,由于編碼經(jīng)常是二進(jìn)制形式,因而使用最廣泛的是二進(jìn)制域GF(2)。在二進(jìn)制編碼中,每個碼元取值是“0”或“1”兩種狀態(tài),其基本運算規(guī)則如表12-2所示。表12-2二進(jìn)制編碼基本運算規(guī)則

我們假設(shè)信源輸出是二進(jìn)制“0”或“1”序列。在線性分組碼中,二進(jìn)制信息序列被分成長度為k的信息組,共有2k個。在長度為k的信息碼后添加長度為r的監(jiān)督碼,編成長度為n=k+r的分組碼。長度為n的所有二進(jìn)制組共有2n個,線性分組碼就是以一定的規(guī)則從2n個組中選出其中2k個用做碼組,這2k個碼組構(gòu)成了一個(n,k)分組碼。我們通常稱這2k個碼組為許用碼組,而其余2n-2k個碼組為禁用碼組。如果一個(n,k)分組碼的信息碼和監(jiān)督碼之間的關(guān)系為線性的,則稱該分組碼為線性分組碼,否則稱為非線性碼。表12-3校正子與錯碼位置的對應(yīng)關(guān)系根據(jù)表12-3的規(guī)定可見,僅當(dāng)有一個錯碼且位置在a2、a4、a5或a6時,校正子S1為1,否則S1為0。這就意味著a2、a4、a5和a6四個碼元構(gòu)成偶數(shù)監(jiān)督關(guān)系,即(12.4-1)同理可得,a1、a3、a5和a6四個碼元構(gòu)成偶數(shù)監(jiān)督關(guān)系為(12.4-2)以及a0、a3、a4和a6四個碼元構(gòu)成偶數(shù)監(jiān)督關(guān)系為(12.4-3)在編碼時,a3、a4、a5和a6為信息碼,是二進(jìn)制隨機(jī)序列,a0、a1、a2為監(jiān)督碼,應(yīng)根據(jù)信息碼的取值按監(jiān)督關(guān)系式?jīng)Q定,即監(jiān)督碼應(yīng)使校正子S1、S2、S3為零,即(12.4-4)上式即是(7,4)線性分組碼的信息碼和監(jiān)督碼所滿足的監(jiān)督方程。對式(12.4-4)進(jìn)行求解可以得到監(jiān)督碼滿足下列關(guān)系:(12.4-5)圖12-11

(7,4)線性分組碼編碼器原理圖表12-4

(7,4)線性分組碼的所有碼組圖12-12

(7,4)線性分組碼譯碼器原理圖12.4.2監(jiān)督矩陣與生成矩陣

在線性碼分組碼中信息碼和監(jiān)督碼滿足一組線性方程,或者說信息碼和監(jiān)督碼之間有某種線性變換關(guān)系。下面仍以(7,4)線性分組碼為例,討論線性分組碼的一般原理。將(7,4)線性分組碼的監(jiān)督方程式(12.4-4)寫成標(biāo)準(zhǔn)的方程形式(12.4-6)式中的“+”號是指模2加,這個方程組叫做碼組的一致監(jiān)督方程或一致校驗方程。將(12.4-6)式表示成矩陣形式(12.4-7)式(12.4-7)用矩陣符號簡寫為(12.4-8)式中我們將矩陣H稱為(7,4)線性分組碼的監(jiān)督矩陣或校驗矩陣,AT和HT分別為矩陣A和監(jiān)督矩陣H的轉(zhuǎn)置。只要監(jiān)督矩陣H給定,碼組中信息碼和監(jiān)督碼之間的關(guān)系也就完全確定了。由監(jiān)督矩陣H可以看出,H矩陣是一個3行乘7列矩陣,即H矩陣的行數(shù)等于監(jiān)督碼長度r,其列數(shù)等于碼組長度n。對于本例的(7,4)線性分組碼,其監(jiān)督矩陣H可以分成兩部分(12.4-9)式中,P是3×4階矩陣,I3是3×3階單位方陣。我們將具有［PIr］形式的H矩陣稱為典型監(jiān)督矩陣。當(dāng)監(jiān)督矩陣H不是典型陣時,可以對它進(jìn)行變換,將其化為典型監(jiān)督矩陣。由典型監(jiān)督矩陣構(gòu)成的碼組稱為系統(tǒng)碼,非典型監(jiān)督矩陣構(gòu)成的碼組是非系統(tǒng)碼。系統(tǒng)碼的特點是信息位不變,監(jiān)督位直接附加于其后。(12.4-10)其中,監(jiān)督矩陣H是一個r×n階矩陣,P是一個r×k階矩陣,Ir是一個r×r階單位方陣。由代數(shù)理論可知,監(jiān)督矩陣H的各行之間是線性無關(guān)的。

同樣,將(7,4)線性分組碼的監(jiān)督碼生成方程式(12.4-5)寫成標(biāo)準(zhǔn)的方程形式(12.4-11)其矩陣表示形式為(12.4-12)或者(12.4-13)式中,Q是一個4×3階矩陣,其行數(shù)等于碼組中信息碼長度k,其列數(shù)等于監(jiān)督碼長度r。將Q矩陣與(12.4-9)式中的P矩陣相比較可以看出,Q矩陣是P矩陣的轉(zhuǎn)置,即(12.4-14)我們將矩陣的左邊加上一個階單位方陣構(gòu)成矩陣，即：(12.4-15)式中,G矩陣是一個4×7階矩陣,其行數(shù)等于碼組中信息碼長度k,其列數(shù)等于碼組長度n。顯然,由G矩陣可以生成(7,4)線性分組碼的所有碼組,因此稱G矩陣為(7,4)線性分組碼的生成矩陣。如果得到生成矩陣G也就完全確定了該碼的編碼方法。假設(shè)(7,4)線性分組碼的信息碼為a3、a4、a5和a6,則按下式可以生成對應(yīng)的碼組:(12.4-16)與監(jiān)督矩陣H類似,生成矩陣G的每一行都是一個碼組,并且各行之間也是線性無關(guān)的。如果生成矩陣G具有［IkQ］的形式,則稱G為典型生成矩陣,由典型生成矩陣生成的碼組是系統(tǒng)碼。二進(jìn)制(n,k)系統(tǒng)碼典型生成矩陣G的一般形式為(12.4-17)其中,生成矩陣G是一個k×n階矩陣,Q是一個k×r階矩陣,Ik是一個k×k階單位方陣。對式(12.4-16)進(jìn)行修改,我們可以得到產(chǎn)生碼組的一般表示形式(12.4-18)另外,由Q矩陣與P矩陣互為轉(zhuǎn)置的關(guān)系可知,只要得到了監(jiān)督矩陣H則生成矩陣G也就確定了。反之亦然。

(n,k)線性分組碼具有如下的性質(zhì):

(1)封閉性。任意兩個碼組的和還是許用的碼組。

(2)碼的最小距離等于非零碼的最小碼重。12.4.3伴隨式與錯誤圖樣

在發(fā)送端,給定信息碼由式(12.4-18)即可生成對應(yīng)的碼組,設(shè)發(fā)送端產(chǎn)生的碼組為(12.4-19)該碼組通過信道傳輸?shù)竭_(dá)接收端。設(shè)接收端收到的碼組為(12.4-20)由于信道的失真和干擾的影響,接收到的碼組R通常情況與發(fā)送的碼組A不一定相同,定義錯誤矩陣E為接收碼組與發(fā)送碼組之差,即(模2)(12.4-21)式中由ei可以看出,當(dāng)ei=0時,接收的碼元等于發(fā)送的碼元,表示接收碼組中該位碼元正確;當(dāng)ei=1時,接收的碼元不等于發(fā)送的碼元,表示接收碼組中該位碼元錯誤。因此,錯誤矩陣E反映了接收碼組的出錯情況,錯誤矩陣有時也稱為錯誤圖樣。在接收端,若能求出錯誤圖樣E就能正確恢復(fù)出發(fā)送的碼組A,即(模2)(12.4-22)例如,接收的碼組R=［1000101］,錯誤圖樣E=［0000010］,則發(fā)送的碼組A=R+E=［1000111］。根據(jù)線性分組碼的編碼原理,每個碼組應(yīng)滿足式(12.4-8),即因此,當(dāng)我們接收到R后用式(12.4-8)進(jìn)行驗證,若等于0則認(rèn)為接收到的是碼組,若不等于0,則認(rèn)為接收到的不是碼組,從而產(chǎn)生了錯碼。我們定義(12.4-23)則稱S為伴隨式或校正子。將式(12.4-22)代入式(12.4-23)可得12.4.4漢明碼

漢明碼是漢明(Hamming)于1949年提出的一種糾正一個隨機(jī)錯誤的線性分組碼,它有如下參數(shù):

(1)碼組長度n=2r-1;

(2)信息碼長度k=2r-1-r;

(3)監(jiān)督碼長度r=n-k,r是不小于3的任意正整數(shù);

(4)最小碼距d0=3;

(5)能夠糾正1個隨機(jī)錯誤或檢測2個隨機(jī)錯誤。漢明碼的監(jiān)督矩陣H具有特殊的性質(zhì),使得能以相對簡單的方法來描述該碼。對于二進(jìn)制漢明碼,其n=2r-1列包含由r=n-k個二進(jìn)制碼元組成的列矢量的所有可能的組合(全零矢量除外)。例如前面例子所討論的(7,4)線性分組碼就是碼組長度為7的漢明碼,其監(jiān)督矩陣由(001)、(010)、(100)、(011)、(101)、(110)和(111)組成。

漢明碼的編碼效率為

若碼長n很長,則編碼效率R接近1,因此漢明碼的編碼效率較高。

12.5循環(huán)碼

12.5.1循環(huán)碼的基本原理

循環(huán)碼是線性分組碼的一個重要子集,是目前研究得比較成熟的一類碼。循環(huán)碼具有許多特殊的代數(shù)性質(zhì),這些性質(zhì)有助于按照要求的糾錯能力系統(tǒng)地構(gòu)造這類碼。目前發(fā)現(xiàn)的大部分線性碼與循環(huán)碼有密切關(guān)系。循環(huán)碼還有易于實現(xiàn)的特點,很容易用帶反饋的移位寄存器實現(xiàn)其硬件。正是由于循環(huán)碼具有碼的代數(shù)結(jié)構(gòu)清晰、性能較好、編譯碼簡單和易于實現(xiàn)的特點,因此在數(shù)據(jù)通信和計算機(jī)糾錯系統(tǒng)中得到廣泛應(yīng)用。循環(huán)碼具有較強(qiáng)的檢錯和糾錯能力,它不僅可以用于糾正獨立的隨機(jī)錯誤,而且也可以用于糾正突發(fā)錯誤。表12-5

(7,3)循環(huán)碼的全部碼組

循環(huán)碼是線性分組碼,除了具有線性分組碼的性質(zhì)外還具有以下重要性質(zhì):

(1)封閉性(線性性)。任何許用碼組的線性和還是許用碼組。由此性質(zhì)可知:線性碼都包含全零碼,且最小碼距就是最小碼重(除全0碼)。

(2)循環(huán)性。任何許用的碼組循環(huán)移位后的碼組還是許用碼組。

為了便于用代數(shù)來研究循環(huán)碼,我們把長度為n的碼組用n-1次多項式表示,將碼組中各碼元當(dāng)作是一個多項式的系數(shù)。若碼組為(an-1an-2…a1a0),則相應(yīng)的多項式表示為(12.5-1)多項式A(x)稱為碼多項式。例如表12-5中的第7個碼組A=(1100101),則相應(yīng)的多項式表示為由碼多項式可以看出,對于二進(jìn)制碼組,多項式的每個系數(shù)不是0就是1,x僅是碼元位置的標(biāo)志。碼多項式的運算是采用按模運算法則,若一任意多項式M(x)被一個n次多項式N(x)除,得到商式Q(x)和一個次數(shù)小于n的余式R(x),也就是(12.5-2)可以寫為(模N(x))(12.5-3)所以取模x5+1后可得(模x5+1)(模x7+1)其對應(yīng)的碼組為A′=(1110010),它正是表12-5中第8個碼組。通過上述分析可以得到,若A(x)是(n,k)循環(huán)碼的一個碼組,則它的循環(huán)移位xA(x),x2A(x),…,以及循環(huán)移位的線性組合均是該循環(huán)碼的碼組,且這些碼多項式都是模xn+1的一個余式。(12.5-4)式中,g(x)稱為循環(huán)碼的生成多項式?？梢宰C明,生成多項式g(x)是2k個碼組集合中唯一的一個次數(shù)為n-k次多項式。當(dāng)給出k個信息碼(an-1an-2…an-k),則可以根據(jù)公式(12.5-5)求出碼多項式A(x)。例如,對于上例的(7,3)循環(huán)碼,由表12-5可以看出,前面k-1=2位都是0的碼組是(0010111),該碼組對應(yīng)的生成多項式g(x)=x4+x2+x+1,則生成矩陣G的多項式表示為相應(yīng)的生成矩陣G為可以看出該生成矩陣G不是典型生成矩陣,將生成矩陣中的第3行加到第1行可得典型生成矩陣為當(dāng)信息碼為(110)時,編出的系統(tǒng)碼碼組為通過以上對循環(huán)碼的討論可以看出,尋找循環(huán)碼的生成多項式是循環(huán)碼編碼的關(guān)鍵。研究表明循環(huán)碼生成多項式有如下重要性質(zhì):循環(huán)碼生成多項g(x)是xn+1的一個n-k=r次因式。該性質(zhì)為我們提供了一種尋找循環(huán)碼生成多項式的方法。例如對于(7,3)循環(huán)碼,其生成多項式g(x)應(yīng)是x7+1的7-3=4次因式。對x7+1進(jìn)行因式分解有12.5.3循環(huán)碼的編碼和譯碼方法

1.循環(huán)碼的編碼

由式(12.5-5)可以看出,用信息碼多項式m(x)乘以生成多項式g(x)就得到一個碼多項式。但是用這種相乘的方法產(chǎn)生的循環(huán)碼不是系統(tǒng)碼。為了得到系統(tǒng)循環(huán)碼的編碼方法,我們可以采用除法方法。編碼過程可分為三個步驟:

(1)設(shè)m(x)為信息碼多項式,用xn-k乘信息碼多項式m(x),則xn-km(x)的次數(shù)小于n;

(2)用g(x)除xn-km(x),即(12.5-6)其中,r(x)是余式,其次數(shù)小于n-k;編出碼組的碼多項式為對應(yīng)的碼組為它是表12-5所示(7,3)循環(huán)碼中的第6個碼組。上述循環(huán)碼的編碼過程可以用由移位寄存器和模2加法器組成的g(x)除法電路實現(xiàn)。對于生成多項式g(x)=x4+x2+x+1的(7,3)循環(huán)碼的編碼器如圖12-13所示。圖中有一個四級移位寄存器,分別用D1、D2、D3和D4表示。另外還有一個雙刀雙擲開關(guān)S。編碼器工作過程如下:

第1步開關(guān)S向下,輸入的k位信息碼m0,m1,…,mk-1一方面送入除法器進(jìn)行運算,同時直接輸出。一旦k位信息碼全部送入除法器,在n-k=4級移位寄存器中的數(shù)據(jù)就是除法余項(它就是信息碼的監(jiān)督碼)。第2步開關(guān)S向上,斷開反饋輸入,同時移位寄存器連接到輸出。

第3步將移位寄存器中保存的余項(監(jiān)督碼)依次輸出,當(dāng)移位n-k=4次后移位寄存器中的余項全部送完。這n-k=4個監(jiān)督碼與k=3個信息碼一起構(gòu)成一個完整的碼組。

用這種方式編出的碼組,前面是原來的k個信息碼,后面是n-k個監(jiān)督碼,因此它是系統(tǒng)碼。如信息碼為(110)時,圖12-13所示編碼器的工作過程如表12-6所示。圖12-13

(7,3)循環(huán)碼編碼器表12-6編碼器的工作過程

2.循環(huán)碼的譯碼

對于接收端譯碼的要求通常有兩個:檢錯與糾錯。實現(xiàn)檢錯目的的譯碼相對比較簡單。在線性分組碼譯碼中,關(guān)鍵是計算伴隨式,若伴隨式為零,則接收的是一個碼組,且譯碼器認(rèn)為就是所發(fā)送的碼組(也可能是不可檢錯誤)。若伴隨式不為零,則接收的不是一個碼組,從而檢測出有錯誤存在。對循環(huán)碼而言,計算伴隨式是非常容易的。設(shè)A(x)是發(fā)送的碼多項式,R(x)是接收的碼多項式,用生成多項式g(x)除R(x)可得(12.5-7)(12.5-8)式中,S(x)是g(x)除R(x)的余式,也就是伴隨式,它是一個冪次小于或等于n-k-1次的多項式。由此我們可知,循環(huán)碼的檢錯電路核心是一個用g(x)除R(x)的除法電路(伴隨式計算電路)。若余式(伴隨式)為0,則說明接收沒有錯誤或產(chǎn)生了一個不可檢測的錯誤;若余式不為0,則說明接收有錯誤。循環(huán)碼檢錯譯碼器原理如圖12-14所示,其核心是除法電路和緩沖移位寄存器,并且除法電路與發(fā)送端編碼器中的除法電路相同。若除法器中R(x)/g(x)的余式為0,則認(rèn)為接收碼組R(x)無錯,這時就將暫存于緩沖移位寄存器中的接收碼組送出到解調(diào)器輸出端;若R(x)/g(x)的余式不為0,則認(rèn)為接收碼組R(x)中有錯,但不知道錯在哪一位。這時可以將緩沖移位寄存器中的接收碼組刪除,并向發(fā)送端發(fā)出一重發(fā)指令,要求重發(fā)一次該碼組。圖12-14循環(huán)碼檢錯譯碼器原理循環(huán)碼的檢錯能力很強(qiáng),其檢錯能力為:

(1)能檢測出全部單個錯誤;

(2)能檢測出全部離散的2個錯誤;

(3)能檢測出全部奇數(shù)個錯誤;

(4)能檢測出全部長度小于或等于n-k個突發(fā)錯誤;

(5)能以1-(1/2)r-1的概率檢測出長度為r+1的突發(fā)錯以及能以1-(1/2)r的概率檢測出多于r+1的突發(fā)錯。接收端糾錯譯碼方法要比檢錯譯碼復(fù)雜得多。因此,對糾錯碼的研究大都集中在譯碼算法上。我們知道,伴隨式與錯誤圖樣之間存在著某種對應(yīng)關(guān)系。與線性分組碼譯碼相同,循環(huán)碼糾錯譯碼可以分三步進(jìn)行:

第1步由接收到的碼多項式R(x)計算伴隨式多項式S(x);

第2步由伴隨式多項式S(x)確定錯誤圖樣E(x);

第3步將錯誤圖樣E(x)與接收到的碼多項式R(x)相加,糾正錯誤。

上述第1步運算和檢錯譯碼類似,也就是求解生成多項式g(x)除R(x)的余式,第3步也很簡單。因此,糾錯碼譯碼器的復(fù)雜性主要取決于譯碼過程的第2步?；阱e誤圖樣識別的譯碼器稱為梅吉特(Meggitt)譯碼器,其原理圖如圖12-15所示。錯誤圖樣識別器是一個具有n-k個輸入端的邏輯電路,原則上可以采用查表的方法,根據(jù)伴隨式找到錯誤圖樣,利用循環(huán)碼的上述特性可以簡化識別電路。梅吉特譯碼器工作原理如下:圖中k級緩沖移位寄存器用于存儲系統(tǒng)循環(huán)碼的信息碼元,模2加電路用于糾正錯誤。當(dāng)伴隨式為0時,模2加來自錯誤圖樣識別電路的輸入端為0,輸出緩沖移位寄存器的內(nèi)容;當(dāng)伴隨式不為0時,模2加來自錯誤圖樣識別電路的輸入端在第i位輸出為1,它可以使緩沖移位寄存器輸出取補(bǔ),即糾正錯誤。梅吉特譯碼器特別適合于糾正2個以下的隨機(jī)獨立錯誤。圖12-15梅吉特譯碼器原理圖循環(huán)碼的譯碼方法除了梅吉特譯碼外,還有捕錯譯碼、大數(shù)邏輯譯碼等方法。捕錯譯碼是梅吉特譯碼的一種變形,也可以用較簡單的組合邏輯電路實現(xiàn),它特別適合于糾正突發(fā)錯誤、單個隨機(jī)錯誤和兩個錯誤的碼字。大數(shù)邏輯譯碼也稱為門限譯碼,只能用于有一定結(jié)構(gòu)的為數(shù)不多的大數(shù)邏輯可譯碼。但這種譯碼算法和硬件比較簡單,因此在實際中有較廣泛的應(yīng)用。12.5.4

BCH碼

BCH碼是以三個研究和發(fā)明這種碼的人名Bose－Chaudhuri－Hocguenghem命名的,它是一類糾正多個隨機(jī)錯誤的循環(huán)碼。BCH碼有嚴(yán)密的代數(shù)理論,是目前研究最透徹的一類碼。

BCH碼分為本原BCH碼和非本原BCH碼兩類。本原BCH碼的生成多項式g(x)中含有最高次數(shù)為m的本原多項式,并且碼長為n=2m-1。非本原BCH碼的生成多項式g(x)中不含這種本原多項式,并且碼長n是2m-1的一個因子,即碼長n一定能除得盡2m-1。對于二進(jìn)制BCH碼的碼長n與監(jiān)督位、最小碼距d0、糾錯個數(shù)t之間的關(guān)系如下:

碼組長度n=2m-1

監(jiān)督碼長度n-k≤mt

最小碼距d0=2t+1

式中,m是大于等于3的任意正整數(shù)。例如,漢明碼是糾正單個隨機(jī)錯誤的線性分組碼,它的碼長n=2r-1,信息碼長k=2r-1-r。具有循環(huán)性質(zhì)的漢明碼就是糾正單個隨機(jī)錯誤的本原BCH碼,如以生成多項式g1(x)=x3+x2+1或g2(x)=x3+x+1生成的(7,4)循環(huán)碼就是本原BCH碼。為了便于設(shè)計出滿足要求的BCH碼,表12-7列出了n≤63的本原BCH碼的碼組長度n、信息碼長度k、糾錯個數(shù)t和生成多項式g(x)的系數(shù)。系數(shù)以八進(jìn)制形式給出,最左邊的數(shù)字對應(yīng)生成多項式的最高次項系數(shù)。例如,(15,5)碼的生成多項式的系數(shù)是八進(jìn)制2467,用二進(jìn)制形式表示是10100110111,其對應(yīng)的生成多項式g(x)=x10+x8+x5+x4+x2+x+1。表12-7碼長7≤n≤127的本原BCH碼生成多項式系數(shù)(八進(jìn) 制形式)

表12-8部分非本原BCH碼生成多項式系數(shù)(八進(jìn)制形式)

表中,(23,12)碼是一個特殊的非本原BCH碼,稱為戈雷碼,它的最小碼距為7,能糾正3個錯誤,其生成多項式為g(x)=x11+x9+x7+x6+x5+x+1。戈雷碼也是目前為止發(fā)現(xiàn)的唯一能糾正多個錯誤的完備碼。12.5.5

Reed－Solomon碼

除了二進(jìn)制BCH碼之外,還有多進(jìn)制BCH碼,只需對二進(jìn)制BCH碼稍加修改就能推廣到多進(jìn)制BCH碼。ReedSolomon碼(里德－索洛蒙碼)是一類具有很強(qiáng)糾錯能力的多進(jìn)制BCH碼,它首先由里德和索洛蒙提出,所以簡稱RS碼。

定義在伽羅華域GF(2m)上的(n,k)RS碼中,輸入信息碼分成k·m比特一組,每組包括k個符號,每個符號由m個比特組成,而不是前面所述的二進(jìn)制BCH碼由一個比特組成。一個能夠糾正t個符號錯誤的RS碼有如下參數(shù):

碼組長度n=2m-1個符號,或n=m(2m-1)個比特

信息碼長度k個符號,或mk個比特

監(jiān)督碼長度n-k=2t個符號,或m(n-k)個比特

最小碼距d0=2t+1個符號,或m(2t+1)個比特可以看出,RS碼的最小碼距比監(jiān)督碼數(shù)目多1個符號。令α是伽羅華域GF(2m)中的本原元素,則碼長n=2m-1,糾正t個錯誤符號的本原RS碼的的生成多項式為(12.5-9)表12-9以x4+x+1為模生成的GF(24)中的元素

例如,構(gòu)造一個能糾3個錯誤符號,碼長n=15,m=4的RS碼,由RS碼的參數(shù)可知,該碼的最小碼距為7,監(jiān)督碼長為6個符號。因此該碼為(15,9)RS碼,其生成多項式為該(15,9)RS碼的每個符號由4個二進(jìn)制碼構(gòu)成,所以從二進(jìn)制角度看,這是一個(60,36)碼。

12.6卷積碼

12.6.1生成距陣G(卷積碼的解析分析)

在(n,k)分組碼中,一個碼組中的n個碼元完全由該碼組中的k個信息碼所決定。這個碼組中的監(jiān)督碼僅與監(jiān)督本碼組中的k個信息碼有關(guān),而與其他各組碼元無關(guān)。分組碼譯碼時,也僅從本碼組中的碼元內(nèi)提取有關(guān)譯碼信息,而與其他各組無關(guān)。而卷積碼則不然,卷積碼用符號(n,k,m)表示,編碼器一般原理如圖12-16所示。它由移位寄存器、模2加法器和多路選擇開關(guān)三種部件組成。圖中共有N段移位寄存器,每段均為k級,第一段k級存儲當(dāng)前輸入的k個輸入信息碼,其余N-1段存儲以前的k(N-1)個信息碼。在一段規(guī)定時間內(nèi),有k個輸入信息碼從左向右移入第一段k級移位寄存器,并且移位寄存器其他各級暫存的內(nèi)容向右移k位。在此時間內(nèi),多路選擇開關(guān)旋轉(zhuǎn)一周,共輸出n個碼元。

圖12-16卷積碼編碼器一般原理圖可以看出,(n,k,m)卷積碼編碼器在任何一段規(guī)定時間內(nèi)產(chǎn)生的n個碼元,不僅取決于這段時間輸入的k個信息碼,而且與前面m=N-1段的輸入信息碼有關(guān)。這時,監(jiān)督碼要監(jiān)督總共N=m+1段時間內(nèi)的信息。

在卷積碼譯碼過程中,譯碼器不僅從該時刻收到的碼組中提取譯碼信息,而且還要利用以前或以后各時刻收到的碼組提取譯碼信息。在(n,k,m)卷積碼中,n是每次編碼器的輸出,k是每次移入編碼器的輸入信息(k<n),m是編碼存儲,它表示輸入信息組在編碼器中需存儲的單位時間。N=m+1稱為編碼約束度,它表示編碼過程中互相約束的碼段個數(shù)。NA=Nn稱為編碼約束長度,它表示編碼過程中互相約束的碼元個數(shù)。由此可知,m或N、NA是表示卷積碼編碼器復(fù)雜性的重要參數(shù)。對于(n,1,m)卷積碼,則編碼器結(jié)構(gòu)將大大簡化。我們用一個具體的例子來說明卷積碼的編碼原理。二進(jìn)制(2,1,3)卷積碼的編碼器原理如圖12-17所示。可以看出,卷積碼編碼器由m=3級存儲,n=2個模2加法器和進(jìn)行并串變換的多路選擇器組成,每次輸入一個信息碼元,編碼器輸出兩個碼元。由于模2加是線性運算,因而編碼器是線性前饋移位寄存器,所有卷積碼編碼器都可以用這種結(jié)構(gòu)實現(xiàn)。圖12-17

(2,1,3)卷積碼的編碼器原理設(shè)信息序列為(12.6-1)每次進(jìn)入編碼器一個碼元。編碼器兩個輸出序列分別為(12.6-2)(12.6-3)因為編碼器是線性系統(tǒng),所以輸出序列C1和C2分別是輸入序列M和編碼器的兩個單位沖激響應(yīng)的卷積。單位沖激響應(yīng)可以通過令輸入序列M=(1000…)并觀察兩個并行輸出序列得到,分別表示為(12.6-4)(12.6-5)單位沖激響應(yīng)g1和g2稱為卷積碼的子生成序列。用多項式形式表示為(12.6-6)(12.6-7)其中,g1(x)和g2(x)稱為卷積碼的子生成多項式。編碼器兩個輸出分別是輸入序列與各支路生成序列的卷積,即(12.6-8)(12.6-9)式中,“*”表示離散卷積,所有運算都是模2運算。將兩個并行輸出進(jìn)行并串變換,合并為串行序列輸出,此碼字由下式給出:(12.6-10)其中,碼字C就是所需要的卷積碼。例如,對于圖12-17所示的(2,1,3)卷積碼編碼器,其子生成序列分別為令輸入信息序列為M=(10111),則編碼器的兩個并行輸出分別為

并串變換后輸出的卷積碼為將子生成序列g(shù)1和g2進(jìn)行交織排列,得到的新序列g(shù)為(12.6-11)式中,將序列g(shù)重新排列成矩陣的形式:(12.6-12)矩陣G稱為卷積碼的生成矩陣?？梢钥闯?當(dāng)輸入信息序列M無限長時,生成矩陣G是一個半無限矩陣,它的每行都與前面一行相等,只是向右移了n=2位。若輸入信息序列M的長度為L,則生成矩陣G有L行2(m+L)列。

與線性分組碼相同,由生成矩陣可以產(chǎn)生對應(yīng)的碼字。若輸入信息序列為M,則卷積碼編碼方程的矩陣表示形式為

其中所有運算都是模2運算。若輸入信息序列M的長度為L,則生成的碼字C的長度為2(m+L)。(12.6-13)例如,對于圖12-17所示的(2,1,3)卷積碼編碼器,其子生成序列分別為令輸入信息序列為M=(10111),則編碼器的生成矩陣為根據(jù)式(12.6-13),編碼器輸出碼字為可以看出,這和我們前面用離散卷積的計算結(jié)果一致。12.6.2卷積碼的結(jié)構(gòu)特點

1.狀態(tài)圖

狀態(tài)圖是一張表明編碼器的可能狀態(tài)及其狀態(tài)間可能存在的轉(zhuǎn)移關(guān)系的圖。由于卷積碼編碼器的輸出是由輸入和編碼器的當(dāng)前狀態(tài)所決定的,因此可以用狀態(tài)圖來描述編碼過程。我們以(2,1,2)卷積碼為例,分析該碼的狀態(tài)圖。(2,1,2)卷積碼編碼器原理如圖12-18所示,該碼編碼存儲m=2,k=1,編碼器由兩級移位寄存器組成。編碼器移位寄存器中任一時刻的存儲內(nèi)容稱為編碼器的一個狀態(tài),以si表示。在該例中,編碼器由兩級移位寄存器組成,因此存的內(nèi)容有4種可能狀態(tài):00、01、10和11,分別用s0=00、s1=10、s2=01和s3=11表示。隨著信息序列不斷送入,編碼器就不斷地從一個狀態(tài)轉(zhuǎn)移到另一個狀態(tài),并輸出相應(yīng)的碼序列。這種表征編碼器工作狀態(tài)變化的流程圖就稱為編碼器的狀態(tài)圖,(2,1,2)卷積碼編碼器狀態(tài)圖如圖12-19所示。編碼器中虛線表示輸入1時的狀態(tài)轉(zhuǎn)移,實線表示輸入0時的狀態(tài)轉(zhuǎn)移?？梢钥闯?若編碼器初始狀態(tài)處于s0,當(dāng)輸入1信息碼元時,編碼器從s0狀態(tài)轉(zhuǎn)移到s1狀態(tài),并編碼輸出11;當(dāng)輸入0信息碼元時,則編碼器仍停留在s0狀態(tài),編碼輸出00,如此等等。隨著信息碼元不斷輸入,編碼器狀態(tài)也不斷隨著轉(zhuǎn)移,并編碼輸出碼序列。圖12-18

(2,1,2)卷積碼編碼器原理圖12-19

(2,1,2)卷積碼編碼器狀態(tài)圖

2.樹圖

樹圖以帶有分支的樹的形式標(biāo)示出編碼器的結(jié)構(gòu),卷積碼的樹圖可以很形象的表示出卷積碼的編譯碼過程,因此在卷積碼概率譯碼中經(jīng)常用到這種方法。

若卷積碼編碼器輸入信息序列是半無限長序列,則卷積碼樹圖也是半無限樹圖。仍以圖12-19所示的(2,1,2)卷積碼編碼器為例,其半無限碼樹圖如圖12-20所示。圖12-20

(2,1,2)卷積碼的碼樹圖

3.網(wǎng)格圖

根據(jù)碼樹圖中的重復(fù)性,我們可以得到卷積碼的一種更為緊湊的圖形表示形式,即網(wǎng)格圖(Trellis)。對于圖12-19所示的(2,1,2)卷積碼編碼器,其網(wǎng)格圖如圖12-21所示。網(wǎng)格圖由節(jié)點和分支組成,每個節(jié)點上標(biāo)注的s0、s1、s2和s3為移位寄存器的狀態(tài),其中,s0=00,s1=10,s2=01,s3=11,每個分支上所標(biāo)注的碼元為輸出。一般情況下網(wǎng)格圖有nm種狀態(tài),從第m+1極開始網(wǎng)格圖開始重復(fù),若輸入信息序列是半無限長序列,則卷積碼網(wǎng)格圖也是半無限的。在圖12-21所示的網(wǎng)格圖中,每一狀態(tài)有兩個輸入和兩個輸出分支。在某一節(jié)點si,若輸入編碼器信息碼mi=1,則離開該狀態(tài)為下面分支(用虛線表示);若輸入編碼器信息碼mi=0,則離開該狀態(tài)為上面分支(用實線表示);每一分支上的n=2個數(shù)字表示該時刻編碼器的輸出。因而網(wǎng)格圖中的每一條路徑都對應(yīng)于編碼器的輸出序列。圖12-21

(2,1,2)卷積碼的網(wǎng)格圖仍然假設(shè)輸入(2,1,2)編碼器的信息序列M=(101100),編碼器沿網(wǎng)格圖所走的一條路徑在圖12-21所示的網(wǎng)格圖中用粗線表示,該路徑所對應(yīng)的輸出碼序列C=(11

10

00

01

01

11),這與狀態(tài)圖法和碼樹圖法得到的結(jié)果完全相同。12.6.3卷積碼的Viterbi譯碼

1.Viterbi譯碼原理

Viterbi譯碼算法是一種基于最大似然譯碼原理的概率譯碼算法,在加性白高斯噪聲(AWGN)信道中具有最佳性能。當(dāng)碼的約束度較大時,譯碼算法運算量大,難以實現(xiàn),因此Viterbi譯碼算法主要作為碼的約束度較小情況下的譯碼方法。下面我們考慮卷積碼通過離散無記憶信道(DMC)的情況。(12.6-14)(12.6-15)最大似然譯碼也可以看成是在網(wǎng)格圖上尋找具有最大路徑度量值的過程。對于二進(jìn)制對稱信道(BSC),計算和尋找具有最大度量的路徑等價于尋找與接收序列R有最小漢明距離的路徑,即尋找(12.6-16)以上是最大似然譯碼原理,但是在實現(xiàn)時由于運算量太大,因此很難實現(xiàn)。例如對于(2,1,2)卷積碼,當(dāng)L=100時,在網(wǎng)格圖上共有2kL=2100>1030條路徑。即使對于只有100bit/s這種很低的信息傳輸速率,譯碼器在1秒鐘內(nèi)也要計算、比較1030個似然函數(shù)(或漢明距離),這是根本無法實現(xiàn)的。更何況通常情況下L值是成千上萬,因此必須尋找運算量小的最大似然譯碼算法。Viterbi譯碼算法成功地解決了尋找最大路徑度量時計算量隨長度L指數(shù)增長這一問題。它并不是在網(wǎng)格圖上一次比較所有可能的2kL條路徑,而是采用迭代的方法,接收一段,計算、比較一段,選擇一段最可能的碼段,從而達(dá)到整個碼序列是一個具有最大似然函數(shù)(或最小漢明距離)的序列。Viterbi譯碼算法可以分為以下幾個步驟:

(1)從某一時間單位j開始,計算出進(jìn)入每一狀態(tài)的所有路徑的路徑度量值,然后進(jìn)行比較,保存具有最大路徑度量的路徑及其路徑度量值,而刪除其他路徑。被保存下來的路徑被稱為留存(或幸存)路徑。

(2)j加1,把此時刻進(jìn)入每一狀態(tài)的所有分支度量和同這些分支相連的前一時刻的留存路徑的度量相加,得到并保存此時刻進(jìn)入每一狀態(tài)的留存路徑及其路徑度量值,刪除其他路徑。因此,留存路徑延長了一個分支。

(3)若j<L+m,則重復(fù)以上各步,否則停止。從各狀態(tài)的留存路徑中選取具有最大路徑度量的留存路徑上的信息碼元作為譯碼輸出序列C,這一路徑就是要尋找的具有最大似然函數(shù)的路徑,因而Viterbi譯碼方法是一種最佳的譯碼方法。在Viterbi譯碼算法中,對于(n,k,m)卷積碼,每一步迭代需計算、比較2(m+1)k條可能路徑的路徑度量,其中,k和m是與卷積碼編碼器結(jié)構(gòu)有關(guān)的參數(shù),通常k和m都比較小。L步迭代