第4章信道編碼4.1信道編碼的基礎(chǔ)

4.2線性分組碼

4.3循環(huán)碼

4.4卷積碼

4.5交織碼

4.6網(wǎng)格編碼調(diào)制

4.7Turbo碼

習(xí)題

4.1信道編碼的基礎(chǔ)

4.1.1信道編碼的基本概念在數(shù)字通信中，根據(jù)不同的目的，編碼可分為信源編碼和信道編碼。信源編碼是為了提高數(shù)字通信系統(tǒng)的有效性，即通過(guò)各種數(shù)據(jù)壓縮方法盡可能地去除信號(hào)中的冗余信息，最大限度地降低傳輸速率和減少傳輸頻帶。信道編碼則不同，它是為了提高數(shù)字通信系統(tǒng)的可靠性而采取的措施。

數(shù)字信號(hào)在傳輸過(guò)程中，由于噪聲干擾和信道特性不理想等都會(huì)產(chǎn)生誤碼。為了提高數(shù)字通信系統(tǒng)的性能，可采取諸如合理設(shè)計(jì)基帶信號(hào)，選擇合適的調(diào)制解調(diào)方式，采用時(shí)域均衡和頻域均衡，加大發(fā)射功率，采取分集接收等各種抗噪聲干擾措施，以盡量減小噪聲干擾的影響。若采取上述措施仍難以滿(mǎn)足要求，則可以采用信道編碼技術(shù)。信道編碼又稱(chēng)差錯(cuò)控制編碼或糾錯(cuò)編碼，它的基本思想是：按照某種確定的編碼規(guī)則在待發(fā)送的信息碼元序列中加入一些多余的碼元(監(jiān)督碼元或校驗(yàn)碼元)，在接收端利用該規(guī)則進(jìn)行解碼，以便發(fā)現(xiàn)錯(cuò)誤、糾正錯(cuò)誤，從而提高信息碼元傳輸?shù)目煽啃浴?/p>

1.信道分類(lèi)

按照噪聲或干擾引起傳輸差錯(cuò)的變化規(guī)律，可以將信道分為以下三類(lèi)：

(1)隨機(jī)差錯(cuò)信道，恒參高斯白噪聲信道是典型的隨機(jī)信道。在隨機(jī)信道中，錯(cuò)碼是隨機(jī)出現(xiàn)的，且各個(gè)錯(cuò)碼的出現(xiàn)是統(tǒng)計(jì)獨(dú)立的。

(2)突發(fā)差錯(cuò)信道，具有脈沖干擾的信道是典型的突發(fā)信道。在突發(fā)信道中，錯(cuò)碼是相對(duì)集中、成串、成群出現(xiàn)的，即在短時(shí)間內(nèi)出現(xiàn)大量錯(cuò)碼。

(3)混合差錯(cuò)信道，短波信道和對(duì)流層散射信道是典型的混合信道。在混合信道中，錯(cuò)碼既有隨機(jī)的又有突發(fā)的。

2.差錯(cuò)控制方式

常用的差錯(cuò)控制方式主要有以下三種，

如圖

4-1所示。

(1)檢錯(cuò)重發(fā)(ARQ)。在發(fā)送信息碼元序列中加入一些能夠發(fā)現(xiàn)錯(cuò)誤的碼元，接收端能夠利用這些檢錯(cuò)碼元發(fā)現(xiàn)接收碼元序列中的錯(cuò)碼，但不能確定錯(cuò)碼的準(zhǔn)確位置。此時(shí)，接收端通過(guò)反向信道通知發(fā)送端重發(fā)，直到接收端確認(rèn)收到正確信息碼元序列為止。檢錯(cuò)重發(fā)方式的特點(diǎn)是需要使用反向信道，譯碼設(shè)備簡(jiǎn)單，適合于突發(fā)錯(cuò)誤或信道干擾嚴(yán)重的情況。但實(shí)時(shí)性較差，

主要應(yīng)用于計(jì)算機(jī)數(shù)據(jù)通信等。

圖4-1差錯(cuò)控制方式(a)ARQ;(b)FEC;(c)HEC圖4-1差錯(cuò)控制方式(a)ARQ;(b)FEC;(c)HEC

(2)前向糾錯(cuò)(FEC)。發(fā)送端發(fā)送能夠糾錯(cuò)的信息碼元序列，接收端不僅能發(fā)現(xiàn)錯(cuò)碼，而且能確定錯(cuò)碼的準(zhǔn)確位置，并自動(dòng)糾正錯(cuò)碼。前向糾錯(cuò)方式的特點(diǎn)是無(wú)需反向信道，延時(shí)小，實(shí)時(shí)性好，但譯碼設(shè)備比較復(fù)雜。隨著編碼理論和大規(guī)模集成電路的發(fā)展，性能優(yōu)良的實(shí)用編譯碼方法不斷涌現(xiàn)，

FEC方式得到了越來(lái)越廣泛的應(yīng)用。

(3)混合糾錯(cuò)(HEC)。它是FEC方式和ARQ方式的結(jié)合，即發(fā)送端發(fā)送具有檢錯(cuò)和糾錯(cuò)能力的信息碼元序列，接收端檢查錯(cuò)碼情況，如果錯(cuò)碼在其糾錯(cuò)能力范圍內(nèi)，則自動(dòng)糾錯(cuò)；如果錯(cuò)碼超過(guò)了其糾錯(cuò)能力，但能檢測(cè)出來(lái)，則通過(guò)反向信道請(qǐng)求發(fā)送端重發(fā)。由于HEC方式具有FEC和ARQ的優(yōu)點(diǎn)，

可實(shí)現(xiàn)較低的誤碼率，

因而得到了廣泛的應(yīng)用。

3.信道編碼分類(lèi)

1)線性碼與非線性碼根據(jù)信息碼元與監(jiān)督碼元之間的函數(shù)關(guān)系，信道編碼可分為線性碼和非線性碼。如果信息碼元與監(jiān)督碼元之間的函數(shù)關(guān)系是線性的，即滿(mǎn)足一組線性方程式，則稱(chēng)為線性碼;否則，

稱(chēng)為非線性碼。

2)分組碼與卷積碼根據(jù)信息碼元與監(jiān)督碼元之間的約束方式，信道編碼可分為分組碼和卷積碼。在分組碼中，監(jiān)督碼元只與本碼組的信息碼元有關(guān)；在卷積碼中，監(jiān)督碼元不僅與本碼組的信息碼元有關(guān)，而且還與前面幾個(gè)碼組的信息碼元有關(guān)。

3)檢錯(cuò)碼與糾錯(cuò)碼根據(jù)碼的用途，信道編碼可分為檢錯(cuò)碼和糾錯(cuò)碼。檢錯(cuò)碼以檢錯(cuò)為目的，不一定能糾錯(cuò)；糾錯(cuò)碼以糾錯(cuò)為目的，一定能檢錯(cuò)。

4)系統(tǒng)碼與非系統(tǒng)碼根據(jù)信息碼元在編碼前后是否保持原來(lái)的形式不變，信道編碼可以分為系統(tǒng)碼和非系統(tǒng)碼。若編碼前后信息碼元保持原樣不變，

則稱(chēng)為系統(tǒng)碼；反之，則稱(chēng)為非系統(tǒng)碼。

4.1.2信道編碼的基本原理

1.分組碼的結(jié)構(gòu)下面以分組碼為例來(lái)說(shuō)明糾錯(cuò)編碼的基本原理。分組碼一般可用符號(hào)(n,k)表示，如圖4-2所示。其中n為碼組長(zhǎng)度(簡(jiǎn)稱(chēng)碼長(zhǎng))，即編碼后的碼元序列每n位為一組；k是信息碼元數(shù)目;r=n－k是碼組中的監(jiān)督碼元數(shù)目。簡(jiǎn)而言之，分組碼是對(duì)每段k位長(zhǎng)的信息碼元以規(guī)定的編碼規(guī)則增加r個(gè)監(jiān)督碼元，組成碼長(zhǎng)為n的碼字。在二進(jìn)制情況下，共有2k個(gè)不同的信息碼組，相應(yīng)地可得到2k個(gè)不同的碼字，稱(chēng)為許用碼組，其余2n－2k個(gè)碼字未被選用，稱(chēng)為禁用碼組。圖

4-2分組碼的結(jié)構(gòu)

2.碼重與最小碼距

在分組碼中，將碼組內(nèi)“1”的個(gè)數(shù)稱(chēng)為碼組的漢明重量，簡(jiǎn)稱(chēng)為碼重。例如碼組0011011的碼重為4。兩個(gè)等長(zhǎng)碼組之間對(duì)應(yīng)位取值不同的位數(shù)稱(chēng)為這兩個(gè)碼組的漢明(Hamming)距離，簡(jiǎn)稱(chēng)為碼距。例如碼組0011011與1110010之間的距離d=5。碼組集中任意兩個(gè)碼組之間距離的最小值稱(chēng)為最小距離，用d0表示。最小碼距是一個(gè)重要的參數(shù)，它是衡量碼檢錯(cuò)、糾錯(cuò)能力的依據(jù)。

3.檢錯(cuò)和糾錯(cuò)能力

我們以重復(fù)碼為例來(lái)說(shuō)明糾錯(cuò)編碼的檢錯(cuò)與糾錯(cuò)能力。若分組碼中監(jiān)督碼元是信息碼元的簡(jiǎn)單重復(fù)，則稱(chēng)該分組碼為重復(fù)碼。重復(fù)碼是一種簡(jiǎn)單實(shí)用的檢錯(cuò)碼，并具有一定的糾錯(cuò)能力。例如(3,1)重復(fù)碼，假定000和111是兩個(gè)許用碼組，其余為禁用碼組，顯然最小碼距d0=3，接收端譯碼時(shí)，若出現(xiàn)禁用碼組001、010、011、100、101、110，則可檢出兩個(gè)錯(cuò)誤，

或可糾正一個(gè)錯(cuò)誤。

顯然，一個(gè)分組碼的檢錯(cuò)和糾錯(cuò)能力取決于最小碼距d0的值，分組碼的檢錯(cuò)和糾錯(cuò)能力與最小碼距d0之間有如下關(guān)系：

(1)為了能檢測(cè)e個(gè)錯(cuò)碼，要求最小碼距d0≥e+1。

(2)為了能糾正t個(gè)錯(cuò)碼，要求最小碼距d0≥2t+1。

(3)為了能糾正t個(gè)錯(cuò)碼，同時(shí)檢測(cè)e(e＞t)個(gè)錯(cuò)碼，要求最小碼距d0≥t+e+1。4.1.3糾錯(cuò)編碼的信道模型

1.隨機(jī)差錯(cuò)編碼信道模型隨機(jī)差錯(cuò)編碼信道的差錯(cuò)是由高斯白噪聲(AWGN)引起的。通常隨機(jī)差錯(cuò)編碼信道可分為二進(jìn)制對(duì)稱(chēng)信道、離散無(wú)記憶信道和帶限波形信道。

1)二進(jìn)制對(duì)稱(chēng)信道(BSC)

二進(jìn)制對(duì)稱(chēng)信道模型如圖4-3所示。它有一個(gè)對(duì)稱(chēng)二進(jìn)制輸入值集合X=｛0,1｝和二進(jìn)制輸出值集合Y=｛0,1｝，以及一組表示輸入、輸出關(guān)系的條件概率(轉(zhuǎn)移概率)，若噪聲導(dǎo)致差錯(cuò)統(tǒng)計(jì)獨(dú)立且條件概率對(duì)稱(chēng)，

即

P(Y=0/X=1)=P(Y=1/X=0)=P

P(Y=1/X=1)=P(Y=0/X=0)=1－P

(4.1-1)

BSC是無(wú)記憶的，它的輸出僅與對(duì)應(yīng)時(shí)刻的輸入有關(guān)，而與前后輸入無(wú)關(guān)。BSC是研究二進(jìn)制編碼解碼最簡(jiǎn)單、最常用的模型。

圖4-3二進(jìn)制對(duì)稱(chēng)信道（BSC）

2)離散無(wú)記憶信道(DMC)離散無(wú)記憶信道(DMC)模型如圖4-4所示。假設(shè)信道的離散輸入是q元符號(hào)，即輸入符號(hào)集由q個(gè)元素X=｛x0，x1，…，xq-1｝構(gòu)成；信道的離散輸出是Q元符號(hào)，即信道輸出符號(hào)集由Q個(gè)元素Y=｛y0，y1，…，yQ-1｝構(gòu)成,且信道是無(wú)記憶的，則信道模型的輸入—輸出特性可以用一組共qQ個(gè)條件概率來(lái)描述，即(4.1-2)式中，i=0,1,…，q-1；j=0，1，…，Q-1。

圖4-4離散無(wú)記憶信道(DMC)條件概率決定了DMC的特征，可以寫(xiě)成矩陣形式P=［Pij］，其中Pij=P(yj/xi)，P稱(chēng)為信道轉(zhuǎn)移概率矩陣，

即

(4.1-3)在信道輸入為xi的條件下，由于噪聲干擾的存在，信道輸出不是一個(gè)固定值，而是概率各異的一組值，這種信道稱(chēng)為有擾離散信道。顯然輸入xi時(shí)，各可能輸出值yj的概率之和必定為1，即i=0,1,…,q-1如果信道轉(zhuǎn)移概率矩陣的每一行中只包含一個(gè)“1”，其余元素均為“0”，說(shuō)明信道無(wú)干擾，

這種信道稱(chēng)為無(wú)擾信道。

3)離散輸入、連續(xù)輸出信道假設(shè)信道輸入符號(hào)選自一個(gè)有限的、離散的輸入符號(hào)集X=｛x0，x1，…，xq-1｝，而信道輸出未經(jīng)量化，這時(shí)的譯碼器輸出可以是實(shí)軸上的任意值，即Y=｛－∞,＋∞｝。定義這樣的信道模型稱(chēng)為離散時(shí)間無(wú)記憶信道，它的特性由離散輸入X、連續(xù)輸出Y以及一組概率密度函數(shù)P(Y/X=xi),i=0，1,…，q-1來(lái)決定。這類(lèi)信道中最重要的一種是加性高斯白噪聲(AWGN)信道，對(duì)它而言有Y=X+G式中，G是一個(gè)零均值、方差為σ2的高斯隨機(jī)變量，

即

（4.1-5）

2.突發(fā)差錯(cuò)編碼信道模型

上述三種信道模型都是針對(duì)隨機(jī)差錯(cuò)信道的。對(duì)于突發(fā)差錯(cuò)信道，有大量的信道模型可供研究。其中，最常用的有記憶突發(fā)差錯(cuò)信道模型是雙狀態(tài)一階馬爾可夫鏈模型，也稱(chēng)為吉爾伯特模型，如圖4-5所示。吉爾伯特模型有兩種狀態(tài)：G(Good)狀態(tài)和B(bad)。

圖

4-5吉爾伯特模型

在某一時(shí)刻，信道處于兩種狀態(tài)之一。當(dāng)信道處于B狀態(tài)時(shí)，信道以很大的概率Pbe發(fā)生錯(cuò)碼；當(dāng)信道處于G狀態(tài)時(shí)，不產(chǎn)生錯(cuò)誤(或與Pbe相比可忽略不計(jì))。顯然，信道處于B狀態(tài)意味著有突發(fā)差錯(cuò)出現(xiàn)。信道在B和G兩種狀態(tài)之間移動(dòng)時(shí)，在碼元周期內(nèi)，信道從G狀態(tài)向B狀態(tài)轉(zhuǎn)移的概率為Pgb，保持在G狀態(tài)的概率為1－Pgb。同理，信道從B狀態(tài)向G狀態(tài)轉(zhuǎn)移概率為Pgb

，保持在B狀態(tài)的概率為1－Pbg

。因此，吉爾伯特模型的參數(shù)是：B狀態(tài)時(shí)的誤碼率Pbe

，狀態(tài)轉(zhuǎn)移概率Pgb和Pbg

。可以證明，吉爾伯特模型代表的編碼信道的平均誤碼率為（4.1-6）

4.1.4信道編碼定理

香農(nóng)有擾離散信道的信道編碼定理指出：每個(gè)信道都有一定的信道容量C，對(duì)于給定的傳信率(碼率)Rb(Rb＜C)及碼長(zhǎng)n，總存在一種編譯碼方法，使得差錯(cuò)概率(4.1-7)式中，E(Rb)為可靠性函數(shù)，也稱(chēng)為誤差指數(shù)，它與C的關(guān)系如圖4-6所示。信道編碼定理表明了錯(cuò)誤概率與碼長(zhǎng)n、信道容量C、信息傳輸速率Rb之間的轉(zhuǎn)換關(guān)系。這是糾錯(cuò)編碼的理論基礎(chǔ)。圖

4-6誤差指數(shù)曲線

4.1.5差錯(cuò)控制的原理

1.原理一由信道編碼定理的公式可知，降低差錯(cuò)概率應(yīng)增大碼長(zhǎng)n或增大可靠性函數(shù)E(Rb)，而要增大E(Rb)就要加大信道容量C或減小碼率Rb。從圖4-6可以看出：

(1)對(duì)于相同的碼率Rb

，信道容量C大者其可靠性函數(shù)E(Rb)也大。

(2)對(duì)于相同的信道容量C，碼率Rb減小時(shí)可靠性函數(shù)E(Rb)增大。由此，我們可采取如下措施來(lái)降低差錯(cuò)概率。

1)增大信道容量C

增大信道容量C是提高通信可靠性的基本原理之一。根據(jù)信道容量公式 ，信道容量C與帶寬W、信號(hào)平均功率S和噪聲平均功率N有關(guān)，S/N為信號(hào)噪聲功率比(簡(jiǎn)稱(chēng)信噪比)。為此，我們可以：

(1)擴(kuò)展頻帶。例如有線通信從明線(150kHz)、雙絞線(100MHz)、同軸電纜(1GHz)到光纖(25THz)，無(wú)線通信從中波、短波、超短波到微波、毫米波。

(2)加大功率。例如提高發(fā)射功率、增大天線增益；采用分集接收、點(diǎn)波束等技術(shù)。

(3)降低噪聲。例如采用低噪聲器件、濾波、屏蔽、接地、低溫運(yùn)行等。

2)減小碼率Rb

未編碼時(shí)，一個(gè)二進(jìn)制碼元可攜帶1比特信息(傳信率為1比特/符號(hào))；編碼后，n個(gè)二進(jìn)制碼元攜帶k比特信息(傳信率為k/n比特/符號(hào))。定義Rb=k/n為二進(jìn)制分組碼的碼率(或效率)。對(duì)于q進(jìn)制(n,k)分組碼(k個(gè)q元符號(hào)編成n個(gè)q元符號(hào))，其碼率Rb=(klbq)/n。由此可知降低碼率的方法有：

(1)q,n不變而減小k，這意味著降低信息源速率，每秒少傳一些信息。

(2)q,k不變而增大n，這意味著提高符號(hào)速率(波特率)，占用更大帶寬。

(3)n,k不變而減小q，這意味著減小信道的輸入、輸出符號(hào)集，在發(fā)射信號(hào)功率固定時(shí)增大信號(hào)間的區(qū)分度，從而提高可靠性。在一定的通信容量C下減小Rb，等效于拉大C和Rb之差，因此這是用增大信道容量的冗余度來(lái)?yè)Q取可靠性。從20世紀(jì)50年代到70年代，主要的糾錯(cuò)編碼方法都是以這種冗余度為基礎(chǔ)的。

3)增加碼長(zhǎng)n

如果保持碼率Rb不變，增加碼長(zhǎng)n的同時(shí)應(yīng)增大信息位k，以保持k/n之比不變。在C和Rb固定的情況下增大n，并沒(méi)有增加信道容量的冗余度，它是利用了隨機(jī)編碼的特點(diǎn)：隨著n增大，矢量空間Xn呈指數(shù)量級(jí)增大，從統(tǒng)計(jì)角度而言，碼字間距離也將增大，從而提高了可靠性。另外，碼長(zhǎng)n越大，其實(shí)際差錯(cuò)概率就越符合統(tǒng)計(jì)規(guī)律。增大碼長(zhǎng)n所帶來(lái)的好處同樣需要付出某種代價(jià)才能換得，代價(jià)就是碼長(zhǎng)越長(zhǎng)，編/解碼算法就越復(fù)雜，編/解碼器就越昂貴。香農(nóng)早在1948年就已指出增大n的途徑，但在20世紀(jì)70年代前由于器件水平不允許編/解碼器做得太復(fù)雜，因此，當(dāng)時(shí)實(shí)用的糾錯(cuò)編碼主要還是靠犧牲功率和頻帶利用率來(lái)?yè)Q取可靠性的。進(jìn)入20世紀(jì)80年代后，隨著超大規(guī)模集成電路(VLSI)的發(fā)展，編/解碼器可以做得越來(lái)越復(fù)雜，很多編/解碼算法可在數(shù)字信號(hào)處理專(zhuān)用芯片DSP上實(shí)現(xiàn)，因此碼長(zhǎng)允許設(shè)計(jì)得很長(zhǎng)。目前，通過(guò)增大碼長(zhǎng)來(lái)提高可靠性已成為糾錯(cuò)編碼的主要途徑之一，它實(shí)際上是以編/解碼設(shè)備的復(fù)雜度來(lái)?yè)Q取可靠性的。從這個(gè)意義上說(shuō)，設(shè)備的復(fù)雜性是妨礙數(shù)字通信系統(tǒng)性能提高的真正限制因素。

2.原理二

1)利用冗余度冗余度就是在信息比特流中插入冗余比特，這些冗余比特與信息比特之間存在著特定的相關(guān)性。這樣，在傳輸過(guò)程中即使個(gè)別信息比特出錯(cuò)，也可以利用其相關(guān)性從其他未出錯(cuò)的冗余比特中推測(cè)出出錯(cuò)比特的原形，保證了信息比特傳輸?shù)目煽啃浴＠?，如果?比特表示四種意義，則無(wú)論如何也不能發(fā)現(xiàn)差錯(cuò)，因?yàn)槿粲幸恍畔?1誤成00，則根本無(wú)法判斷這是傳輸過(guò)程中由01誤成00，還是原本發(fā)送的就是00。但如果用3比特來(lái)表示四種意義，則就有可能發(fā)現(xiàn)差錯(cuò)，因?yàn)?比特的八種組合能表示八種意義，用它代表四種意義尚剩四種冗余組合，如果傳輸差錯(cuò)使收到的3比特組合落入四種冗余組合，就可判定一定有錯(cuò)碼發(fā)生。至于加多少冗余比特、加什么樣的相關(guān)性最好，這正是糾錯(cuò)編碼技術(shù)要解決的問(wèn)題，但必須有冗余，這是糾錯(cuò)編碼的基本原理。

為了傳輸這些冗余比特，必然要?jiǎng)佑萌哂嗟馁Y源。這些資源可以是：

(1)時(shí)間。例如一個(gè)比特重發(fā)幾次，或一段消息重發(fā)幾次，或根據(jù)收端的反饋重發(fā)受損信息比特組等。

(2)頻帶。插入冗余比特后傳輸效率下降，若要保持有用信息的傳輸速率不變，最直接的方法就是增大符號(hào)傳送速率(波特率)，結(jié)果是占用更大的帶寬。例如二進(jìn)制碼(1比特/符號(hào))編成(8，4)分組碼后，

其符號(hào)速率增大一倍，占用帶寬也增大一倍。

(3)功率。采用多進(jìn)制符號(hào)，例如用一個(gè)八進(jìn)制ASK符號(hào)代替一個(gè)四進(jìn)制ASK符號(hào)來(lái)傳送2比特信息，可騰出位置另傳1比特冗余信息。但為了維持信號(hào)集各點(diǎn)之間的距離不變，八進(jìn)制符號(hào)的平均功率比四進(jìn)制時(shí)要大，這就是動(dòng)用冗余的功率資源來(lái)傳輸冗余比特。

(4)設(shè)備復(fù)雜性。增大碼長(zhǎng)n，例如采用網(wǎng)格編碼調(diào)制(TCM)，該方法是在功率、帶寬受限信道中實(shí)施糾錯(cuò)編碼的有效方法之一，其代價(jià)是算法復(fù)雜度增大，需動(dòng)用計(jì)算（設(shè)備）資源。

2)噪聲均化噪聲均化的基本思想是讓差錯(cuò)隨機(jī)化，設(shè)法將危害較大的、較為集中的噪聲干擾(稱(chēng)為突發(fā)差錯(cuò))分散開(kāi)，變?yōu)榉稚⒌脑肼暩蓴_(稱(chēng)為隨機(jī)差錯(cuò))，從而使不可恢復(fù)的信息損傷達(dá)到最小。噪聲均化將差錯(cuò)均勻分?jǐn)偨o各碼組，從而提高了總體差錯(cuò)控制能力。噪聲均化的方法主要有以下三種。

(1)增加碼長(zhǎng)。例如某BSC信道差錯(cuò)概率Pe=0.01，假如編碼后的糾錯(cuò)能力是10%，即在長(zhǎng)度為n的碼字中，只要差錯(cuò)碼元個(gè)數(shù)少于等于n的10%，就可以通過(guò)譯碼加以糾正。若碼長(zhǎng)n=10，則碼字中有多于一個(gè)碼元出錯(cuò)時(shí)就會(huì)產(chǎn)生譯碼差錯(cuò)，差錯(cuò)概率為

如果保持碼率Rb不變，將碼長(zhǎng)n增大到40，則當(dāng)碼字中多于四個(gè)碼元出錯(cuò)時(shí)就會(huì)產(chǎn)生譯碼差錯(cuò)，

差錯(cuò)概率為

從本例可以看到，只要將碼長(zhǎng)n由10增長(zhǎng)到40，譯碼差錯(cuò)概率就可以降低兩個(gè)數(shù)量級(jí)。這是因?yàn)椋捍a長(zhǎng)越長(zhǎng)，每個(gè)碼字中錯(cuò)碼的比例就越接近統(tǒng)計(jì)平均值，即噪聲均攤到了各個(gè)碼字上。

(2)卷積。在分組碼中，是將信息碼元序列分割成k位一組，每組再加入r位監(jiān)督碼元后編成n位碼字，即碼元之間的相關(guān)性?xún)H限于在各個(gè)碼字內(nèi)，碼字之間是彼此無(wú)關(guān)的(統(tǒng)計(jì)獨(dú)立的)。卷積碼則不然，它在一定約束長(zhǎng)度內(nèi)的若干碼字之間加進(jìn)了相關(guān)性，譯碼時(shí)不是根據(jù)單個(gè)碼字，而是一串碼字來(lái)進(jìn)行判決。卷積碼是將噪聲分?jǐn)偟酱a字序列而非一個(gè)碼字上，從而達(dá)到噪聲均化的目的。

(3)交織(也稱(chēng)為交錯(cuò))。交織是對(duì)付突發(fā)差錯(cuò)最有效的措施之一。突發(fā)噪聲干擾使碼流產(chǎn)生集中成串的、不可糾正的差錯(cuò)。交織碼的基本思想是：對(duì)編碼器輸出的碼流與信道上的符號(hào)流做順序上的變換，將碼流轉(zhuǎn)換為隨機(jī)的、可糾正的差錯(cuò)，即均化突發(fā)信道造成的符號(hào)流中的突發(fā)差錯(cuò)。

4.1.6糾錯(cuò)編碼系統(tǒng)的性能指標(biāo)

1.編碼效率糾錯(cuò)編碼是以降低有效性為代價(jià)來(lái)提高數(shù)字通信系統(tǒng)的可靠性的。對(duì)于分組碼(n,k)來(lái)說(shuō)，定義編碼效率（4.1-8）

式中，n為碼長(zhǎng);k為信息碼元的個(gè)數(shù)。

2.糾錯(cuò)編碼的誤碼性能

對(duì)于二進(jìn)制對(duì)稱(chēng)信道(BSC)，假設(shè)在隨機(jī)差錯(cuò)信道中，發(fā)送“0”時(shí)的差錯(cuò)概率與發(fā)送“1”時(shí)的差錯(cuò)率均為Pe，且Pe<<1?？梢宰C明，在碼長(zhǎng)為n的碼組中恰好發(fā)生i個(gè)錯(cuò)誤的概率為（4.1-9）

則不加糾錯(cuò)時(shí)的誤碼組率為

（4.1-10）

如果使用可以糾正t位隨機(jī)誤碼的糾錯(cuò)碼，則譯碼后的誤碼組率降低

（4.1-11）

系統(tǒng)誤比特率與具體所采用的編譯碼算法有關(guān)。

一般來(lái)說(shuō)，

可近似地有

（4.1-12）

例如，碼長(zhǎng)n=7，Pe=10-3，此時(shí)有

P7(1)≈7Pe=7×1-3，P7(2)≈21P2e=2.1×10-5，P7(3)≈35P3e=3.5×10-8由此可見(jiàn)，在信道誤碼率較低的情況下，采用糾錯(cuò)編碼，即使只能糾正1～2個(gè)錯(cuò)碼，也能使系統(tǒng)誤碼率下降幾個(gè)數(shù)量級(jí)。

對(duì)于高斯白噪聲信道(AWGN)，由第3章可知，在數(shù)字調(diào)制系統(tǒng)中，誤比特率Pb與Eb/n0

和調(diào)制方式有關(guān)。例如相干解調(diào)2PSK無(wú)糾錯(cuò)時(shí)的誤比特率為（4.1-13）

式中，Eb為單位比特能量;n0為噪聲功率譜密度。

如果在2PSK調(diào)制前先進(jìn)行(n,k)分組碼糾錯(cuò)編碼，則由于加入監(jiān)督碼元，在相同碼率情況下，信道中需要傳輸?shù)姆?hào)速率增加了k/n倍。因此，誤比特率變?yōu)椋?.1-14）

這里，Ec為單位符號(hào)能量，它與Eb有如下關(guān)系

（4.1-15）

利用式(4.1-12)、(4.1-13)和(4.1-14)可以求出編譯碼后誤比特率Pb與Eb/n0的關(guān)系。

3.編碼增益在給定誤比特率(例如10-5)的條件下，采用糾錯(cuò)編碼所節(jié)省的信噪比Eb/n0稱(chēng)為編碼增益，通常用分貝表示（4.1-16）

式中，(Eb/n0)u為未編碼時(shí)所需的信噪比(dB)；(Eb/n0)c為編碼后所需的信噪比(dB)。顯然，編碼增益越大越好。4.1.7常用的檢錯(cuò)碼

1.奇偶監(jiān)督碼奇偶監(jiān)督碼又稱(chēng)奇偶校驗(yàn)碼，是一種簡(jiǎn)單的檢錯(cuò)碼，在計(jì)算機(jī)數(shù)據(jù)通信中應(yīng)用廣泛。奇偶監(jiān)督碼的基本思想是在n-1位信息碼元的后面附加上一位監(jiān)督碼元，構(gòu)成(n,n-1)的分組碼，監(jiān)督碼元的作用是使得碼長(zhǎng)為n的碼組中“1”的個(gè)數(shù)是奇數(shù)或偶數(shù)。碼組中“1”的個(gè)數(shù)是奇數(shù)的編碼稱(chēng)為奇監(jiān)督碼，碼組中“1”的個(gè)數(shù)是偶數(shù)的編碼稱(chēng)為偶監(jiān)督碼。奇偶監(jiān)督碼的編碼規(guī)則是：首先將要發(fā)送的二進(jìn)制信息碼元進(jìn)行分組，然后對(duì)所有信息碼元和監(jiān)督碼元進(jìn)行模2加，選擇正確的監(jiān)督碼元，以保證模2加的結(jié)果為0(偶監(jiān)督碼)或1(奇監(jiān)督碼)。假設(shè)由n個(gè)碼元構(gòu)成的碼字為(an-1，an-2，…，a0)，其中前n－1位是信息碼元，第n位a0是監(jiān)督碼元，對(duì)偶監(jiān)督碼有（4.1-17）

a0可以由下式確定

（4.1-18）

接收端譯碼時(shí)，按式(4.1-17)將碼組中的碼元進(jìn)行模2加，若結(jié)果為“0”，則判定為無(wú)錯(cuò)碼；若結(jié)果為“1”，則判定該碼組經(jīng)傳輸后有奇數(shù)個(gè)錯(cuò)碼。對(duì)奇監(jiān)督碼有

（4.1-19）

a0可以由下式確定

（4.1-20）

奇偶監(jiān)督碼最小碼距為2，無(wú)論是奇監(jiān)督碼還是偶監(jiān)督碼，都只能檢測(cè)出單個(gè)或奇數(shù)個(gè)錯(cuò)碼，而不能檢測(cè)出偶數(shù)個(gè)錯(cuò)碼。奇偶監(jiān)督碼的編碼效率為R=(n－1)/n。例如，在ASCII碼中，通常采用7位二進(jìn)制碼元來(lái)表示128種字符。傳輸時(shí)再加上一個(gè)奇偶監(jiān)督位8位碼組，接收端根據(jù)是否滿(mǎn)足式(4.1-17)或式(4.1-19)來(lái)判定傳輸過(guò)程中是否發(fā)生錯(cuò)誤。

2.行列監(jiān)督碼

行列監(jiān)督碼是二維奇偶監(jiān)督碼，又稱(chēng)為矩陣碼或方陣碼。為了改進(jìn)奇偶監(jiān)督碼不能發(fā)現(xiàn)偶數(shù)個(gè)錯(cuò)誤的情況，行列監(jiān)督碼不僅對(duì)水平(行)方向的碼元，而且對(duì)垂直(列)方向的碼元實(shí)施了奇偶監(jiān)督，如圖4-7(a)所示。具體編碼方法是：將要發(fā)送的若干信息碼元排列成一個(gè)方陣，方陣中的每一行為一個(gè)碼組，在行的最后一位加上一個(gè)監(jiān)督碼元ai0(i=1,2，…，m)，進(jìn)行奇偶監(jiān)督；同理，在每列的最后一位也加上一個(gè)監(jiān)督碼元ci-1(i=1,2，…，n)，形成行列監(jiān)督碼。圖4-7(b)是(66,50)行列監(jiān)督的一個(gè)碼字。圖4-7奇偶監(jiān)督碼(a)編碼方法；

(b)(66,50)行列監(jiān)督碼

行列監(jiān)督碼不僅具有較強(qiáng)的檢錯(cuò)能力，還可用來(lái)糾正一些錯(cuò)碼。例如，當(dāng)碼組僅在一行中出現(xiàn)奇數(shù)個(gè)錯(cuò)誤時(shí)，可以確定錯(cuò)碼的位置并加以糾正。行列監(jiān)督碼適合于檢測(cè)突發(fā)錯(cuò)誤。由于突發(fā)錯(cuò)誤常常集中成串出現(xiàn)，隨后較長(zhǎng)一段時(shí)間無(wú)差錯(cuò)，因此在一行中出現(xiàn)多個(gè)奇數(shù)或偶數(shù)錯(cuò)碼的機(jī)會(huì)較多，而行列監(jiān)督碼有可能檢測(cè)偶數(shù)個(gè)錯(cuò)誤。盡管每行中的偶數(shù)個(gè)錯(cuò)誤不能由本行的監(jiān)督碼元檢出，但按列的方向可能由本列的監(jiān)督碼元檢測(cè)出來(lái)。由于行列監(jiān)督碼只是對(duì)構(gòu)成矩形四角的錯(cuò)碼無(wú)法檢測(cè)，故其檢錯(cuò)能力較強(qiáng)。

3.恒比碼

恒比碼又稱(chēng)為等比碼或等重碼。在恒比碼中，每個(gè)碼組中“1”的數(shù)目與“0”的數(shù)目保持恒定比例，即每個(gè)碼組都含有相同數(shù)目的“1”和“0”。接收端譯碼時(shí)，只要檢測(cè)碼組中“1”或“0”的數(shù)目是否與規(guī)定的數(shù)目相同，就可以判定有無(wú)錯(cuò)碼。例如，目前我國(guó)電傳通信中普遍采用五位數(shù)字保護(hù)電碼(3∶2碼)，即5中取3的恒比碼，每個(gè)碼組的長(zhǎng)度為5，其中有三個(gè)“1”。準(zhǔn)用碼組的數(shù)目為C35=10，正好表示10個(gè)阿位伯?dāng)?shù)字(0～9)，如表4-1所示。每個(gè)漢字可以用四位十進(jìn)制數(shù)來(lái)表示。表

4-1

5中取3的恒比碼

恒比碼的最小碼距為2，能發(fā)現(xiàn)所有奇數(shù)個(gè)錯(cuò)誤，但不能發(fā)現(xiàn)所有偶數(shù)個(gè)錯(cuò)誤。實(shí)踐證明，采用這種恒比碼能有效降低漢字電報(bào)的差錯(cuò)率。目前國(guó)際上通用的ARQ電報(bào)通信系統(tǒng)采用3∶4碼。即7中取3的恒比碼，每個(gè)碼組長(zhǎng)度為7，其中有三個(gè)“1”，準(zhǔn)用碼組數(shù)為C37=35，35個(gè)碼組分別表示26個(gè)字母和其他符號(hào)。恒比碼的主要優(yōu)點(diǎn)是簡(jiǎn)單、實(shí)用，適合傳送電報(bào)或其他鍵盤(pán)設(shè)備產(chǎn)生的字母字符，但不適合傳送二進(jìn)制隨機(jī)數(shù)字序列。4.2線

性

分

組

碼

4.2.1線性分組碼的基本概念線性分組碼中的分組是指編、譯碼過(guò)程是按分組進(jìn)行的，一般是按每k個(gè)信息碼元一組進(jìn)行編譯碼；而線性則是指分組碼中監(jiān)督碼元按線性方程生成的，即r=n-k個(gè)監(jiān)督碼元是由k個(gè)信息碼元的線性變換產(chǎn)生。例如在(7，4)線性分組碼中，信息碼元每四位一組進(jìn)行編碼，即輸入信息碼元長(zhǎng)度k=4；編碼器輸出碼組長(zhǎng)度n=7，監(jiān)督碼元長(zhǎng)度r=n-k=7-4=3；編碼效率R=k/n=4/7。從空間的角度看，(n,k)線性分組碼中的每一個(gè)碼字都可以看成n維線性空間中的一個(gè)矢量。長(zhǎng)度為n的碼字共有2n個(gè)矢量，構(gòu)成一個(gè)n維線性空間。(n,k)線性分組碼中有2k個(gè)準(zhǔn)用碼字(k＜n)，構(gòu)成了一個(gè)k維線性子空間，即(n,k)線性分組碼是n維線性空間中的一個(gè)k維線性子空間。糾錯(cuò)編碼的任務(wù)就是在n維線性空間的2n種可能組合中選擇2k個(gè)構(gòu)成一個(gè)k維線性子空間。由于該線性子空間在模2加法運(yùn)算中構(gòu)成阿貝爾群，因此線性分組碼又稱(chēng)為群碼。4.2.2線性分組碼編碼方程與生成矩陣G

下面以(7，3)二進(jìn)制線性分組碼為例來(lái)說(shuō)明。假設(shè)輸入信息碼組為m=(m0m1m2)，編碼器輸出碼組為C=(c0c1c2c3c4c5c6)，已知輸入碼與輸出碼的關(guān)系式是c0=m0,c1=m1,c2=m2,c3=m0+m2,c4=m0+m1+m2，c5=m0+m1,c6=m1+m2。因此，

可將上述關(guān)系式列成如下編碼線性方程：

（4.2-1）

可見(jiàn)，輸出碼組中前三位是信息碼元的簡(jiǎn)單重復(fù)，后四位是監(jiān)督碼元，它由前三個(gè)信息碼元的線性組合構(gòu)造。寫(xiě)成對(duì)應(yīng)的矩陣形式為

(4.2-2)式中，G稱(chēng)為生成矩陣，由G和信息組就可以產(chǎn)生全部碼字。G為k×n階矩陣，各行也是線性無(wú)關(guān)的。生成矩陣也可分為兩部分，即G=［Ik

Q］

…(4.2-3)式中，Q為k×r階矩陣；Ik為k階單位矩陣；G稱(chēng)為典型生成矩陣，

非典型生成矩陣經(jīng)過(guò)行列運(yùn)算可以轉(zhuǎn)化為典型生成矩陣。

在本例中，七位二進(jìn)制數(shù)有27=128種組合，而三位信息碼組只有23=8種組合，一一對(duì)應(yīng)到八個(gè)碼字。在以上編碼過(guò)程中，核心的因素是生成矩陣G，它決定了編碼規(guī)則，也決定了碼字集合。該生成矩陣G可以看成是由三個(gè)行矢量組成的，所有碼字是這三個(gè)行矢量的線性組合：

C=m0(1001110)+m1(0100110)+m2(0011101)

分別令信息組m=(m0m1m2)為(000)，(001)，…，(111)，不難算出各信息組對(duì)應(yīng)的碼字，

如表

4-2所示。

表

4-2信息碼組與碼字對(duì)應(yīng)表

4.2.3線性分組碼的監(jiān)督方程與監(jiān)督矩陣H

若將式(4.2-1)編碼方程中后四位監(jiān)督方程改寫(xiě)，

可得

（4.2-4）

將上述線性方程寫(xiě)成如下矩陣形式

即

或

(4.2-5)其中，CT是碼空間C的轉(zhuǎn)置，OT是O=［0000］的轉(zhuǎn)置，HT是H的轉(zhuǎn)置。

（4.2-6）

H稱(chēng)為監(jiān)督矩陣。一旦給定H，信息碼元和監(jiān)督碼元之間的關(guān)系也就確定了。H為r×n

階矩陣，H矩陣每行之間是彼此線性無(wú)關(guān)的。P為r×k(4×3)階矩陣，Ir為r×r（4×4）階單位矩陣。寫(xiě)成H=［PIr］形式的矩陣稱(chēng)為典型監(jiān)督矩陣。由式(4.2-3)和式(4.2-6)可以看出…（4.2-7）

其中PT是P的轉(zhuǎn)置。

根據(jù)以上推導(dǎo)可以看出，監(jiān)督矩陣H與生成矩陣G之間存在一一對(duì)應(yīng)的關(guān)系，

即

（4.2-8）（4.2-9）

只要生成矩陣G確定了，監(jiān)督矩陣H也就確定了；反之亦然。顯然，線性分組碼可以由生成矩陣G或監(jiān)督矩陣H完全確定。編碼時(shí)通常采用生成矩陣G，譯碼時(shí)通常采用監(jiān)督矩陣H。

HCT=OT，說(shuō)明H矩陣與碼字的轉(zhuǎn)置乘積必為零，可以用來(lái)作為判定接收碼字C是否出錯(cuò)的依據(jù)。

4.2.4校正子(伴隨式)S與譯碼假設(shè)發(fā)送碼組C=(c6c5c4c3c2c1c0)，在傳輸過(guò)程中可能發(fā)生誤碼，接收碼組B=(b6b5b4b3b2b1b0)，則發(fā)送碼組與接收碼組之差定義為錯(cuò)誤圖樣E，也稱(chēng)為誤差矢量，即E=B－C=B+C，其中E=(e6e5e4e3e2e1e0)，且i=0,1,…,6（4.2-10）

當(dāng)ei=0時(shí)，表示該位接收碼元正確；當(dāng)ei=1時(shí)，表示該位接收碼元有錯(cuò)。令S=BHT，稱(chēng)為伴隨式或校正子。當(dāng)接收端譯碼時(shí)，用監(jiān)督矩陣H進(jìn)行校驗(yàn)，計(jì)算校正子S，即由于CHT=0，因此校正子S只與錯(cuò)誤圖樣E有關(guān)，與發(fā)送碼字C無(wú)關(guān)。由此可見(jiàn)，校正子S與錯(cuò)誤圖樣之間有確定的線性變換關(guān)系。接收端譯碼器的任務(wù)就是從校正子S確定錯(cuò)誤圖樣E，然后從接收到的碼字中減去錯(cuò)誤圖樣。圖4-8給出了譯碼過(guò)程框圖。（4.2-11)圖

4-8譯碼過(guò)程框圖

如果接收碼無(wú)誤，必有B=C，E=0及EHT=0，S=0；如果信道產(chǎn)生差錯(cuò)而使E≠0，必有BHT=EHT≠0，S≠0。從物理意義看，校正子S并不反映發(fā)送的碼字是什么，而只反映了信道對(duì)碼字造成怎樣的干擾。在接收端，我們并不知道發(fā)送碼C究竟是什么，但知道HT和接收碼B，從而算出S。譯碼最重要的任務(wù)是從校正子S中找出C的估值C。具體方法是：先算出S，再由S算出E，最后令C=B+E而求出C，即^^^（4.2-12）

問(wèn)題的關(guān)鍵是從S中找出E，只要E正確，譯出的碼就是正確的。下面以(5，2)線性分組碼來(lái)說(shuō)明如何構(gòu)造該碼的標(biāo)準(zhǔn)陣列譯碼表和譯碼。假設(shè)(5，2)線性分組碼的生成矩陣為

其中,n=5,k=2,r=3。由信息組m=(00),(01),(10),(11)，由式(4.2-2)可求得四個(gè)準(zhǔn)用碼字為C0=(00000),C1=(10111),C2=(01101),C3=(11010)。由式(4.2-8)可求得監(jiān)督矩陣（4.2-13）

由S=EHT可得

（4.2-14）由BHT確定S后，對(duì)應(yīng)的E可以有2k(22=4)個(gè)解，究竟取哪一個(gè)作為差錯(cuò)圖樣E的解?最簡(jiǎn)單明了的處理方法是概率譯碼，即對(duì)所有2k個(gè)解的重量(差錯(cuò)圖樣E中1的個(gè)數(shù))進(jìn)行比較，選擇重量最小的作為E的估值。由于E=B+C，E重量最小，就是B和C的漢明距離最小。顯然，在進(jìn)行概率譯碼時(shí)，每接收一個(gè)碼字就要解一次線性方程，非常復(fù)雜麻煩。但如果n－k不太大，我們可以預(yù)先把不同校正子S情況下的所有方程組都預(yù)先解出來(lái)，將各種情況下的最大概率譯碼輸出列成一個(gè)標(biāo)準(zhǔn)陣列譯碼表。這樣，在實(shí)際譯碼時(shí)就不必解方程，只要查譯碼表就可以了。

校正子S有2n-k=23=8種組合；而錯(cuò)誤圖樣有25=32種，其中：①代表無(wú)差錯(cuò)的全零錯(cuò)誤圖樣有C05=1種；②代表一個(gè)差錯(cuò)的錯(cuò)誤圖樣有C15=5種；③代表兩個(gè)差錯(cuò)的錯(cuò)誤圖樣C25=10種。顯然，要把八個(gè)校正子對(duì)應(yīng)到八個(gè)重量最小的錯(cuò)誤圖樣，無(wú)疑應(yīng)先選擇：①全零錯(cuò)誤圖樣；②五種一個(gè)差錯(cuò)的錯(cuò)誤圖樣；③剩下的兩個(gè)校正子不得不在10種兩個(gè)差錯(cuò)的錯(cuò)誤圖樣中選擇兩個(gè)。具體方法是：

(1)先將全零錯(cuò)誤圖樣E=(00000)代入式(4.2-14)，可求得對(duì)應(yīng)的S=(000)。

(2)再將五種一個(gè)差錯(cuò)的錯(cuò)誤圖樣E=(10000),(01000),(00100),(00010),(00001)代入式(4.2-14)，可求得對(duì)應(yīng)的S=(111),(101),(100),(010),(001)。

(3)剩下的兩個(gè)校正子是(011)和(110)，每個(gè)有2２種解，對(duì)應(yīng)22個(gè)錯(cuò)誤圖樣。對(duì)于校正子(011)的22個(gè)解(錯(cuò)誤圖樣E)為(00011)，(10100)，(01110)，(11001)，其中(00011)和(10100)具有最小重量，可選擇其中之一作為錯(cuò)誤圖樣，例如選擇(00011)。同理，校正子(110)所對(duì)應(yīng)的重量最小的錯(cuò)誤圖樣之一是(00110)，

如表4-3所示。

表4-3(5，

2)線性分組碼譯碼表

若接收碼B=(10101)，可采用以下三種方法之一進(jìn)行譯碼：

(1)直接搜索譯碼表，查表得(10101)所在列的碼字為C1=(10111)。

(2)先求校正子S=BHT=(10101)HT=(010)，再由010搜索譯碼表的第五行可找到(10101)，可得所在列的碼字C1=(10111)。

(3)先求校正子S=BHT=(010)，可查到對(duì)應(yīng)的錯(cuò)誤圖樣E=(00010)，再計(jì)算C=B+E=(10101)+(00010)=(10111)。

4.2.5完備碼與漢明碼

1.完備碼對(duì)于(n,k)線性分組碼，它有2k個(gè)碼字，2r個(gè)校正子，若該碼要糾正小于等于t個(gè)隨機(jī)錯(cuò)誤，則必須滿(mǎn)足

滿(mǎn)足上式條件的線性分組碼稱(chēng)為漢明碼。式(4.2-15)指出了n、r與t之間的關(guān)系。若式(4.2-15)的等式成立，則該線性分組碼稱(chēng)為完備碼。顯然，漢明碼是一種完備碼。能滿(mǎn)足 的完備碼并不多見(jiàn)，已發(fā)現(xiàn)的二進(jìn)制完備碼有t=1的漢明碼，t=3的(23，12)高萊(Golay)碼。

2.漢明碼漢明碼是一種常用的線性分組碼，也是糾錯(cuò)能力t=1的完備碼，1950年由Hamming提出。漢明碼的主要特點(diǎn)有：

(1)給定監(jiān)督碼元數(shù)r，就能確定漢明碼的碼長(zhǎng)為n=2r－1，信息碼元數(shù)為k=2r－r－1。當(dāng)r=3，4，5，6，…時(shí)，分別有(7，4)，(15，11)，(31，26)，(63，5)，…漢明碼。

(2)最小碼距d0=3，可以糾正一位錯(cuò)碼，

常用于FEC系統(tǒng)。

(3)編碼效率為 。可以看出，當(dāng)r(或n)很大時(shí)，R趨于1，顯然，漢明碼是一種高效碼。

若在漢明碼中再加上一位對(duì)所有碼元都進(jìn)行校驗(yàn)的監(jiān)督位，則監(jiān)督位由r擴(kuò)展至r+1，信息碼元數(shù)不變，碼長(zhǎng)由2r－1增到2r，通常把這種(2r，2r－r－1)碼稱(chēng)為擴(kuò)展?jié)h明碼。擴(kuò)展?jié)h明碼的最小碼距d0=4，能在糾正1位錯(cuò)誤的同時(shí)檢測(cè)2位錯(cuò)誤。在某些情況下，還可以將原漢明碼的碼長(zhǎng)n及信息碼元數(shù)k同時(shí)縮短s位，即可得到(n－s,k－s)縮短漢明碼。擴(kuò)展?jié)h明碼和縮短漢明碼都是從漢明碼變形得到的，統(tǒng)稱(chēng)為變形的漢明碼。上述對(duì)漢明碼進(jìn)行擴(kuò)展和縮短的變形方法可以推廣應(yīng)用到所有其他線性分組碼中，以構(gòu)造任意碼長(zhǎng)的線性分組碼。

3.高萊碼高萊碼是二進(jìn)制(23,12)線性分組碼，最小碼距d0=7，糾錯(cuò)能力t=3，由于223-12=2048=1+C123+C223+C323，故也是完備碼。在(23,12)碼上添加一位監(jiān)督位即得二進(jìn)制線性(24,12)高萊碼，最小碼距d0=8。4.3循

環(huán)

碼

4.3.1循環(huán)碼的概念循環(huán)碼是1957年由普蘭奇(Prange)提出的。它是線性分組碼中最重要的一個(gè)子類(lèi)。目前，實(shí)用差錯(cuò)控制編碼中所使用的線性分組碼幾乎都是循環(huán)碼或循環(huán)碼的子類(lèi)。循環(huán)碼除了具有(n,k)線性分組碼的一般性質(zhì)外，還具有循環(huán)性，即若將其任意一個(gè)碼字(cn-1,cn-2,…,c1,c0)的碼元向右或向左循環(huán)移一位，所得的(c0,cn-1,cn-2,…,c1)或(cn-2,…,c1,c0,cn-1)仍然是碼字，表4-4是一種(7，3)循環(huán)碼的全部碼字和碼多項(xiàng)式。表

4-4（7，

3）循環(huán)碼

循環(huán)碼的結(jié)構(gòu)完全建立在有限域的基礎(chǔ)上，可以用代數(shù)的方法來(lái)描述。為了便于計(jì)算，通常用碼多項(xiàng)式來(lái)表示碼字。對(duì)于(n,k)循環(huán)碼的碼字(cn-1,cn-2,…,c1,c0)，其碼多項(xiàng)式為C(x)=(cn-1xn-1+cn-2xn-2+…+c1x+c0)。例如碼字(1101001)對(duì)應(yīng)的碼多項(xiàng)式為C(x)=x6+x5+x3+1，其中x只是碼元位置的標(biāo)記，我們并不關(guān)心它的取值。4.3.2循環(huán)碼的碼多項(xiàng)式在整數(shù)運(yùn)算中，有模n運(yùn)算。例如，在模2運(yùn)算中

1+1=2≡0(模2)，

1+2=3≡1(模2)，

２×３=6≡0(模2)對(duì)于整數(shù)m進(jìn)行模n運(yùn)算,有

（4.3-1）

式中，Q為整數(shù)，p＜n。這說(shuō)明：在模n運(yùn)算下，一個(gè)整數(shù)m等于它被n除得的余數(shù)。例如，在模3運(yùn)算中，7/3=2+1/3≡1(模3)。對(duì)碼多項(xiàng)式也可以按模運(yùn)算。若任意一個(gè)多項(xiàng)式F(x)被一個(gè)n次多項(xiàng)式N(x)除，得到商式Q(x)和一個(gè)次數(shù)小于n的余式R(x)，即F(x)=N(x)Q(x)+R(x)(4.3-2)則在按模N(x)運(yùn)算下，有

(模N(x))此時(shí)，碼多項(xiàng)式系數(shù)仍按模2運(yùn)算，系數(shù)只取0和1。例如F(x)=x4+x2+1被N(x)=x3+1除，得到余式R(x)=x2+x+1，即x4+x2+1≡x2+x+1（模(x3+1))。x

在(n,k)循環(huán)碼中，若C(x)是一個(gè)長(zhǎng)度為n的碼字，則xiC(x)在按模(xn+1)運(yùn)算下，也是該循環(huán)碼中的一個(gè)碼字。即若xiC(x)=Q(x)(xn+1)+C′(x)≡C′(x)(模(xn+1))（4.3-3）

則C′(x)也是該循環(huán)碼中的一個(gè)碼組。其中，i為碼字左移的位數(shù)，Q(x)為xiC(x)除以xn+1的商式，C′(x)為xiC(x)被xn+1除得的余式。例如碼字(1101001)，

若將此碼字左移兩位，

由式(4.3-3)可得到

x2(x6+x5+x3+1)=(x+1)(x7+1)+x5+x2+x+1即Q(x)=x+1；C(x)=x5+x2+x+1，對(duì)應(yīng)的碼字為(0100111)，與直接對(duì)碼字進(jìn)行循環(huán)左移兩位的結(jié)果相同。4.3.3循環(huán)碼的生成多項(xiàng)式和生成矩陣

1.循環(huán)碼的生成多項(xiàng)式如果一種碼的所有碼多項(xiàng)式都是多項(xiàng)式g(x)的倍式，則稱(chēng)g(x)為該碼的生成多項(xiàng)式。循環(huán)碼的碼多項(xiàng)式都是最低次碼多項(xiàng)式g(x)的倍式。例如表4-3所示的(7，3)循環(huán)碼中，生成多項(xiàng)式g(x)=x4+x3+x2+1。顯然，循環(huán)碼中次數(shù)最低的多項(xiàng)式(除全0碼字外)就是生成多項(xiàng)式g(x)?？梢宰C明，g(x)是常數(shù)項(xiàng)為1的r次多項(xiàng)式，是xn+1的一個(gè)因子。一旦確定了g(x)，則整個(gè)(n,k)循環(huán)碼就被確定了。問(wèn)題是如何確定任意一個(gè)(n,k)循環(huán)碼的生成多項(xiàng)式g(x)，例如，(x7+1)可以分解為：x7+1=(x+1)(x3+x2+1)(x3+x+1)。為了求出(7，3)循環(huán)碼的生成多項(xiàng)式g(x)，需要從中找到一個(gè)r=n－k=7－3=4次的因子。不難看出，這樣的因子有兩個(gè)：①(x+1)(x3+x2+1)=x4+x2+x+1；②(x+1)(x3+x+1)=x4+x3+x2+1。這兩個(gè)因子都可以作為生成多項(xiàng)式。

注意選用不同的生成多項(xiàng)式，所產(chǎn)生的循環(huán)碼的碼字不同。

(n,k)循環(huán)碼的生成多項(xiàng)式滿(mǎn)足下面三條性質(zhì)：(1)g(x)是一個(gè)（n－k）次多項(xiàng)式。(2)g(x)的常數(shù)項(xiàng)不為0。(3)g(x)是xn+1的一個(gè)因子。2.循環(huán)碼的生成矩陣循環(huán)碼的生成矩陣G常用多項(xiàng)式的形式來(lái)表示，即

（4.3-4）

例如表4-3所示的(7，3)循環(huán)碼，n=7,k=3,r=4，其生成多項(xiàng)式g(x)=x4+x3+x2+1，代入式(4.3-4)可得

即

顯然，G不是典型形式的生成矩陣，但經(jīng)過(guò)簡(jiǎn)單的變換就很容易化為典型形式的生成矩陣，

即

4.3.4循環(huán)碼的監(jiān)督多項(xiàng)式和監(jiān)督矩陣

1.循環(huán)碼的監(jiān)督多項(xiàng)式

由于g(x)能除盡xn+1，因此有

（4.3-5）

其中，g(x)是常數(shù)項(xiàng)為1的r次生成多項(xiàng)式；h(x)是常數(shù)項(xiàng)為1的k次多項(xiàng)式，稱(chēng)為監(jiān)督多項(xiàng)式。令h(x)=xk+hk-1xk-1+…+h1x+1，h(x)的逆多項(xiàng)式h*(x)=xk+h1xk-1+h2xk-2+…+hk-1x+1。例如(7，3)循環(huán)碼中，g(x)=x4+x3+x2+1，則（4.3-6）

（4.3-7）

2.循環(huán)碼的監(jiān)督矩陣

由監(jiān)督多項(xiàng)式很容易得到循環(huán)碼的監(jiān)督矩陣，

即

（4.3-8）

例如由式(4.3-7)可得(7，

3)循環(huán)碼的監(jiān)督矩陣為

（4.3-9）

即

（4.3-10）

【例4-1】

已知（7，4）循環(huán)碼的全部碼組為0000000，0100111，1000101，1100010，0001011，0101100，1001110，1101001，0010110，0110001，1010011，1110100，0011101，0111010，1011000，1111111。試求該循環(huán)碼的生成多項(xiàng)式、生成矩陣和監(jiān)督矩陣。

解（1）求生成多項(xiàng)式g(x)。已知n=7，k=4，r=n－k=7－4=3x7+1=(x+1)(x3+x+1)(x3+x2+1)因?yàn)樯啥囗?xiàng)式g(x)必須滿(mǎn)足：是一個(gè)n－k=3次多項(xiàng)式，其常數(shù)項(xiàng)不為0，是x7+1的一個(gè)因子，顯然滿(mǎn)足上述條件的因子有兩個(gè):x3+x+1和x3+x2+1。由于本題給出了循環(huán)碼的全部碼字，因此符合本題條件的生成多項(xiàng)式g(x)只有一個(gè)，假定g(x)=x3+x+1。（2）

求生成矩陣G。

生成矩陣為

將第三行與第四行的和加到第一行，得到;再將第四行加到第二行，

得到典型生成矩陣

經(jīng)檢驗(yàn)，由g(x)=x3+x+1得到的生成矩陣G能產(chǎn)生本題所給定的全部生成碼字。而g(x)=x3+x2+1所生成的循環(huán)碼與本題所給的碼組不符。（3）求監(jiān)督矩陣。4.3.5循環(huán)碼的編碼方法

循環(huán)碼編碼時(shí)，首先要根據(jù)給定的(n,k)值來(lái)選定生成多項(xiàng)式g(x)，即從(xn+1)的因式中選定一個(gè)r=n－k次多項(xiàng)式作為g(x)。根據(jù)循環(huán)碼中的所有碼多項(xiàng)式都可被g(x)整除這條原則，就可以對(duì)給定的信息碼元進(jìn)行編碼。假設(shè)編碼前的信息碼多項(xiàng)式為m(x)，其次數(shù)小于k。用xr乘以m(x)，得到xrm(x)的次數(shù)小于n。用g(x)除以xrm(x)，得到余式R(x),R(x)次數(shù)必小于g(x)的次數(shù)，即小于(n－k)。將此余數(shù)R(x)加在信息碼元之后作為監(jiān)督位，即將R(x)與xrm(x)相加，得到的多項(xiàng)式必為碼多項(xiàng)式。因?yàn)樗啬鼙籫(x)整除，且高的次數(shù)不大于(k-1)。因此，循環(huán)碼的碼多項(xiàng)式為(4.3-11)循環(huán)碼的編碼方法可歸納如下：

(1)用xr乘以m(x)。該運(yùn)算的作用是在信息碼元后附加上r個(gè)“0”。例如在(7，3)碼中信息碼組為(110)，它可以寫(xiě)成m(x)=x2+x；由于r=n－k=7－3=4，所以xrm(x)=x4(x2+x)=x6+x5，它表示碼組1100000，即信息碼元后附加四個(gè)“0”。

(2)用g(x)除以xrm(x)，得到商Q(x)和余式R(x)，即（4.3-12）

若選定g(x)=x4+x2+x+1，則有

（4.3-13）

即Q(x)=x2+x+1，R(x)=x2+1。

上式等效于

（4.3-14）

(3)編碼器輸出的碼字為

C(x)=xrm(x)+R(x)=1100000+101=110010(4.3-15)4.3.6循環(huán)碼的譯碼方法

1.循環(huán)碼的檢錯(cuò)由于任一碼多項(xiàng)式C(x)都應(yīng)能被生成多項(xiàng)式g(x)整除，因此在接收端可以將接收碼組B(x)用生成多項(xiàng)式去除，即。當(dāng)傳輸過(guò)程中沒(méi)有發(fā)生差錯(cuò)時(shí)，接收碼組與發(fā)送碼組相同(C(x)=B(x))，即接收碼組B(x)必定能被g(x)整除，即R(x)=0。當(dāng)傳輸過(guò)程中發(fā)生差錯(cuò)時(shí)，C(x)≠B(x)，B(x)除以g(x)時(shí)必定除不盡而有余項(xiàng)，即R(x)≠0。因此，可以用余項(xiàng)R(x)是否為零來(lái)判定碼組中是否有差錯(cuò)。應(yīng)當(dāng)注意，當(dāng)接收碼組中的錯(cuò)誤數(shù)量超出編碼的檢錯(cuò)能力時(shí)，有錯(cuò)誤的接收碼組也可能被g(x)整除。此時(shí)，差錯(cuò)就無(wú)法檢出。這種錯(cuò)誤稱(chēng)為不可檢錯(cuò)碼。

【例4-2】已知（15，7）循環(huán)碼的生成多項(xiàng)式為g(x)=x8+x7+x6+x4+1，試問(wèn)接收碼組B(x)=x１４+x5+x+1是否有誤。

解因?yàn)樗越邮沾aB(x)=x14+x5+x+1有誤。

2.循環(huán)碼的糾錯(cuò)在糾錯(cuò)時(shí)，譯碼方法比檢錯(cuò)時(shí)復(fù)雜。為了能糾錯(cuò)，要求每個(gè)可糾正的錯(cuò)誤圖樣必須與一個(gè)特定的余式有一一對(duì)應(yīng)關(guān)系。只有這樣才可能按此余式惟一地決定錯(cuò)誤圖樣，從而糾正錯(cuò)誤。循環(huán)碼的糾錯(cuò)譯碼方法如下：

(1)用生成多項(xiàng)式g(x)除以接收碼組B(x)，得到余式R(x)。

(2)按照余式R(x)，用查表方法或計(jì)算校正子得出錯(cuò)誤圖樣E(x)，就可以確定錯(cuò)碼的位置。

(3)從B(x)中減去E(x)，便得到已經(jīng)糾正錯(cuò)碼的原發(fā)送碼組C(x)。常用的循環(huán)碼譯碼方法主要有梅吉特譯碼、捕錯(cuò)譯碼和大數(shù)邏輯譯碼等。4.3.7縮短循環(huán)碼

一般來(lái)說(shuō)，xn+1的因式數(shù)目不多，它們所能組合出來(lái)的因式次數(shù)也是有限的,并非任何(n,k)的取值都能產(chǎn)生循環(huán)碼。為了滿(mǎn)足實(shí)際中對(duì)n、k的多種要求和限制，循環(huán)碼常采用縮短碼的形式，即縮短循環(huán)碼。縮短循環(huán)碼的基本思想是：從(n,k)循環(huán)碼的2k個(gè)碼字中挑選出前i(0＜i＜k)個(gè)信息碼元為0值的碼字(即有2k-i個(gè)這樣的碼字)，刪去前i位后作為(n-i,k-i)縮短循環(huán)碼的碼字。由于縮短循環(huán)碼的碼集是(n,k)循環(huán)碼的子集，因此其碼多項(xiàng)式也一定能被生成多項(xiàng)式g(x)整除。由于在縮短循環(huán)碼的過(guò)程中，并沒(méi)有刪除“1”碼，因此縮短循環(huán)碼的最小碼距d0不變，即(n-i,k-i)縮短循環(huán)碼的檢糾錯(cuò)能力與原(n,k)循環(huán)碼的相同，只是編碼效率降低了。4.3.8BCH碼

BCH碼是一種非常重要的循環(huán)碼，它在編碼理論研究和實(shí)際應(yīng)用上占有重要地位。BCH碼的重要性體現(xiàn)在：①它有嚴(yán)密的代數(shù)結(jié)構(gòu)，是目前研究得最透徹的一類(lèi)碼；②它的生成多項(xiàng)式g(x)與最小碼距d0之間有密切的關(guān)系，人們能根據(jù)所要求的糾錯(cuò)能力(對(duì)d0的要求)，很容易地構(gòu)造出BCH碼；③BCH編/譯碼比較簡(jiǎn)單，易于實(shí)現(xiàn)，是線性分組中應(yīng)用最為普遍的一類(lèi)碼。首先引入本原多項(xiàng)式的概念。如果一個(gè)n次多項(xiàng)式F(x)滿(mǎn)足以下條件：

(1)F(x)是既約多項(xiàng)式(即不能分解因式的多項(xiàng)式)。

(2)F(x)可整除(xp+1)，p=2n－1。

(3)F(x)除不盡(xq+1)，q＜p。則稱(chēng)F(x)是一個(gè)最高次數(shù)為n的本原多項(xiàng)式。例如當(dāng)n=3時(shí)，x2n-1+1=x7+1，此時(shí)最高次為3的本原多項(xiàng)式為x3+x2+1和x3+x+1，它們都能整除x7+1，但不能整除x6+1，x5+1等。

BCH碼可分為本原BCH碼和非本原BCH碼。本原BCH碼是指在生成多項(xiàng)式g(x)中，含有最高次數(shù)為m的一個(gè)本原多項(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。

BCH碼的碼長(zhǎng)n、監(jiān)督位r和糾錯(cuò)能力t之間的關(guān)系如下：對(duì)于任意整數(shù)m和t≤m/2，一定存在一個(gè)二進(jìn)制BCH碼，其碼長(zhǎng)n=2m－1，監(jiān)督位數(shù)r=n－k≤mt，并能糾正所有不大于t的隨機(jī)錯(cuò)誤。為了便于應(yīng)用，表4-5給出了碼長(zhǎng)n≤63的本原BCH碼，表4-6給出了碼長(zhǎng)n≤73的非本原BCH碼。其中g(shù)(x)欄下的數(shù)字是八進(jìn)制數(shù)，用于表示生成多項(xiàng)式g(x)中的各項(xiàng)系數(shù)值。例如表4-5中，由于八進(jìn)制數(shù)“23”對(duì)應(yīng)的二進(jìn)制碼為“010011”，故生成多項(xiàng)式g(x)=x4+x+1。表

4-5

n≤63的本原BCH碼

表4-6部分非本原BCH碼

在實(shí)際應(yīng)用中，如果要求BCH碼的碼長(zhǎng)不是2m-1或它的因子，則可采用前面介紹的縮短碼的方法來(lái)構(gòu)造縮短BCH碼。

4.3.9Fire碼

Fire(法爾)碼是一種糾正單位個(gè)突發(fā)錯(cuò)誤的循環(huán)碼，其特點(diǎn)是可以根據(jù)不同的要求方便地設(shè)計(jì)所需的碼，譯碼簡(jiǎn)單，廣泛應(yīng)用于計(jì)算機(jī)磁盤(pán)系統(tǒng)中。令p(x)是一個(gè)m次的既約多項(xiàng)式，且l與m互素，

則Fire碼的生成多項(xiàng)式為

g(x)=p(x)·(xl+1)(4.3-16)該碼的碼長(zhǎng)為

n=LCM(l,e)(4.3-17)式中，LCM表示取最小公倍數(shù)；e=2m－1。該碼的監(jiān)督位數(shù)為r=n－k=l+m(4.3-18)例如p(x)=x4+x+1，令l=7，

Fire碼的生成多項(xiàng)式為

g(x)=(x

4+x+1)·(x7+1)=x11+x8+x7+x4+x+1碼長(zhǎng)n=LCM(7,24－1)=LCM(7，15)=105監(jiān)督位數(shù)r=7+4=11信息位數(shù)k=105－11=94,即(105，94)Fire碼4.3.10RS碼

RS碼是里德-索洛蒙(Reed-Solomon)碼的簡(jiǎn)稱(chēng)。它是一種多進(jìn)制BCH碼，具有很強(qiáng)的糾錯(cuò)能力，特別適合在衰落信道中糾正突發(fā)錯(cuò)誤。

在(n,k)RS碼中輸入信號(hào)分成k·m比特一組，每組包括k個(gè)符號(hào)，每個(gè)符號(hào)由m比特組成。一個(gè)能糾正t個(gè)符號(hào)錯(cuò)誤的RS碼，其主要參數(shù)如下：

(1)碼長(zhǎng)，n=2m－1符號(hào)或n=m(2m－1)個(gè)比特。

(2)信息段，k個(gè)符號(hào)或mk個(gè)比特。

(3)監(jiān)督段，r=n－k=2t個(gè)符號(hào)或m·2t個(gè)比特。

(4)最小碼距，d0=2t+1個(gè)符號(hào)或m(2t+1)個(gè)比特。對(duì)于一個(gè)長(zhǎng)度為n=2m－1符號(hào)的RS碼，每個(gè)符號(hào)都可以看成是有限域GF(2m)中的一個(gè)元素。對(duì)于最小碼距為d0符號(hào)的RS碼，其生成多項(xiàng)式為其中，αi是GF(2m)域元素，i=1,2,…，d0－1。

（4.3-19）

例如，構(gòu)造一個(gè)能糾正三個(gè)錯(cuò)誤符號(hào)，碼長(zhǎng)為15，m=4的RS碼，最小碼距為d0=2t+1=2×3+1=7個(gè)符號(hào)，監(jiān)督段有r=2t=2×3=6個(gè)符號(hào)，信息段有k=n－r=15－6=9個(gè)符號(hào)，即(15，9)RS碼。從二進(jìn)制的角度，這是一個(gè)(60，36)碼。由式(4.3-19)知，其生成多項(xiàng)式為g(x)=(x+α)(x+α2)(x+α3)(x+α4)(x+α5)(x+α6)

=x6+α10x5+α14x4+α4x3+α6x2+α9x+α6

RS碼的編碼過(guò)程與BCH碼的大體一樣，同樣可以用帶反饋的移位寄存器來(lái)實(shí)現(xiàn)。不同之處有：①移位寄存器為m級(jí)并聯(lián)工作；②每個(gè)反饋連接必須乘以生成多項(xiàng)式g(x)中相應(yīng)的系數(shù)。

RS的譯碼過(guò)程也與BCH碼的大體相同。不同的是：需要在找到錯(cuò)誤位置后，求出錯(cuò)誤值，這是因?yàn)镽S譯碼有2m－1種可能的取值。

4.3.11循環(huán)冗余校驗(yàn)碼

循環(huán)冗余校驗(yàn)碼(CRC)是一種檢錯(cuò)能力很強(qiáng)的(n,k)循環(huán)碼，廣泛應(yīng)用于幀校驗(yàn)。CRC碼的結(jié)構(gòu)如圖4-9所示。整個(gè)n位幀(或分組、信元等)就是一個(gè)碼組(C(x))，由k位信息(m(x))和n－k

個(gè)校驗(yàn)位(R(x))組成。在發(fā)送端，C(x)=xn-km(x)，其中，R(x)是xn-km(x)除以g(x)的余式。在接收端，若接收碼組中無(wú)錯(cuò)誤，應(yīng)有接收碼組B(x)等于發(fā)送碼組C(x)，即B(x)=C(x)=xn-km(x)+R(x)=Q(x)g(x)，接收碼組B(x)能被g(x)整除；若接收碼組中有錯(cuò)碼，則B(x)必定不能被g(x)整除。例如假定CRC碼的生成多項(xiàng)式g(x)=x4+x+1，n－k=4；信息碼組m=(110001)，信息碼多項(xiàng)式m(x)=x5+x4+1,k=6；因此n=4+6=10。xn-km(x)=x4(x5+x4+1)=x9+x8+x4，將xn-km(x)除以g(x)，可得余式R(x)=x3+x2，并可求得發(fā)送碼多項(xiàng)式C(x)=xn-km(x)+R(x)=x9+x8+x4+x3+x2，對(duì)應(yīng)的發(fā)送碼組為(1100011100)。

CRC碼在數(shù)據(jù)通信中得到了廣泛應(yīng)用，國(guó)際上常用的CRC碼如表4-7所示。其中，CRC-ITU-T用于HDLC、SDLC、X.25、7號(hào)信令、ISDN等，CRC-16用于北美二進(jìn)制同步系統(tǒng)，CRC-32用于以太網(wǎng)、ATMAAL5等。圖4-9循環(huán)冗余校驗(yàn)碼（CRC）結(jié)構(gòu)表4-7國(guó)際上常用的CRC碼

4.4卷

積

碼

4.4.1卷積碼的概念卷積碼是P.Elias于1955年提出的一種非分組碼。在分組碼中，為了達(dá)到一定的檢糾錯(cuò)能力和編碼效率(R=k/n)，碼組的長(zhǎng)度通常都比較大。編譯碼時(shí)必須把整個(gè)碼組存儲(chǔ)起來(lái)，因此處理產(chǎn)生的延時(shí)隨碼長(zhǎng)n的增大而線性增加。在(n,k)線性分組碼中，本組r=n－k個(gè)監(jiān)督碼元僅與本組k個(gè)信息有關(guān)，而各碼組之間是彼此無(wú)關(guān)的，沒(méi)有利用碼組之間的相關(guān)性。卷積碼的信息碼元數(shù)k和碼長(zhǎng)n通常較小，故處理延時(shí)小，特別適合以串行形式傳輸信息的數(shù)字通信。同時(shí)卷積碼在任何一個(gè)碼組中的監(jiān)督碼元都不僅與本組的k個(gè)信息碼元有關(guān)，而且與前面N－1段的信息碼元有關(guān)，相關(guān)的碼元數(shù)為Nn個(gè)。隨著N的增加，卷積碼的糾錯(cuò)能力隨之增強(qiáng)，誤碼率呈指數(shù)下降。一般來(lái)說(shuō)，在編碼器復(fù)雜性相同的情況下，卷積碼的性能優(yōu)于分組碼，因而，卷積碼在數(shù)字通信中得到了廣泛的應(yīng)用。需要指出的是，目前卷積碼尚未