第12章現(xiàn)代通信原理與技術(shù)西安電子科技大學(xué)(張輝曹麗娜編著第二版)

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

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

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

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

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

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

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

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

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

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

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

2.前向糾錯(cuò)方式(FEC)

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

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

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

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

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

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

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

(1)同時(shí)具有檢測(cè)錯(cuò)誤和糾正錯(cuò)誤的能力。

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

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

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

12.2差錯(cuò)控制編碼的基本原理

12.2.1糾錯(cuò)編碼的基本原理

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

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

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

mk-2

,…

,m0)

(12.2-1)

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

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

2.分組碼

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

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

3.許用碼組與禁用碼組

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

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

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

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

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

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

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

6.編碼增益

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

12.3常用的簡(jiǎn)單編碼

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

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

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

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

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

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

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

12.4線(xiàn)性分組碼

12.4.1線(xiàn)性分組碼原理

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

(4)最小碼距d0=3;

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

漢明碼的編碼效率為

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

12.5循環(huán)碼

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

(1)能檢測(cè)出全部單個(gè)錯(cuò)誤;

(2)能檢測(cè)出全部離散的2個(gè)錯(cuò)誤;

(3)能檢測(cè)出全部奇數(shù)個(gè)錯(cuò)誤;

(4)能檢測(cè)出全部長(zhǎng)度小于或等于n-k個(gè)突發(fā)錯(cuò)誤;

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

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

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

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

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

BCH碼

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

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

碼組長(zhǎng)度n=2m-1

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

最小碼距d0=2t+1

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

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

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

Reed－Solomon碼

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

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

碼組長(zhǎng)度n=2m-1個(gè)符號(hào),或n=m(2m-1)個(gè)比特

信息碼長(zhǎng)度k個(gè)符號(hào),或mk個(gè)比特

監(jiān)督碼長(zhǎng)度n-k=2t個(gè)符號(hào),或m(n-k)個(gè)比特

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

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

12.6卷積碼

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

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

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

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

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

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

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

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

1.狀態(tài)圖

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

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

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

2.樹(shù)圖

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

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

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

3.網(wǎng)格圖

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

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

10

00

01

01

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

1.Viterbi譯碼原理

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

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

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

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