第6章信道編碼1 2012

1第6章信道編碼6.1信道編碼的概念

6.2信道編碼定理

6.3線性分組碼2第6章信道編碼

信道編碼是以信息在信道上的正確傳輸為目標(biāo)的編碼，可分為兩個層次上的問題：如何正確接收載有信息的信號 －－線路編碼如何避免少量差錯信號對信息內(nèi)容的影響 －－糾錯編碼36.1信道編碼的概念進(jìn)行信道編碼是為了提高信號傳輸?shù)目煽啃?，改善通信系統(tǒng)的傳輸質(zhì)量，研究信道編碼的目標(biāo)是尋找具體構(gòu)造編碼的理論與方法。從原理上看，構(gòu)造信道碼的基本思路是根據(jù)一定的規(guī)律在待發(fā)送的信息碼元中人為地加入一定的多余碼元(稱為監(jiān)督碼)，以引入最小的多余度為代價來換取最好的抗干擾性能。

46.1.1信道編碼的分類

對不同的信道需要設(shè)計不同類型的信道編碼方案，按照信道特性進(jìn)行劃分，信道編碼可分為：以糾獨(dú)立隨機(jī)差錯為主的信道編碼、以糾突發(fā)差錯為主的信道編碼和糾混合差錯的信道編碼。從功能上看，信道編碼可分為檢錯(可以發(fā)現(xiàn)錯誤)碼與糾錯(不僅能發(fā)現(xiàn)而且能自動糾正)碼兩類，糾錯碼一定能檢錯，檢錯碼不一定能糾錯，平常所說的糾錯碼是兩者的統(tǒng)稱。

56.1.1信道編碼的分類根據(jù)信息碼元與監(jiān)督碼元之間的關(guān)系，糾錯碼分為線性碼和非線性碼。

線性碼——信息碼元與監(jiān)督碼元之間呈線性關(guān)系，它們的關(guān)系可用一組線性代數(shù)方程聯(lián)系起來。非線性碼——信息碼元與監(jiān)督校元之間不存在線性關(guān)系。

66.1.1信道編碼的分類按照對信息碼元處理的方法的不同，糾錯碼分為分組碼和卷積碼。

分組碼----把信息序列以每k個碼元分組，然后把每組k個信息元按一定規(guī)律產(chǎn)生r個多余的監(jiān)督碼元，輸出序列每組長為n=k+r，則每一碼字的r個校驗元只與本碼字的k個信息位有關(guān)，與別的碼字的信息位無關(guān)，通常記分組碼為(n,k)。

76.1.1信道編碼的分類其中分組碼又可分循環(huán)碼和非循環(huán)碼：對循環(huán)碼而言，其碼書的特點(diǎn)是，若將其全部碼字分成若干組，則每組中任一碼字中碼元循環(huán)移位后仍是這組的碼字；對非循環(huán)碼來說，任一碼字中的碼元循環(huán)移位后不一定再是該碼書中的碼字。86.1.1信道編碼的分類

卷積碼----把信息序列以每k0(通常較小)個碼元分段，編碼器輸出該段的監(jiān)督碼元r=n-k0

不但與本段的k0個信息元有關(guān)，而且還與其前面L段的信息碼元有關(guān)，故記卷積碼為(n,k0,L)。按照每個碼元的取值來分，可有二元碼和多元碼。由于目前的傳輸或存儲系統(tǒng)大都采用二進(jìn)制的數(shù)字系統(tǒng)，所以一般提到的糾錯碼都是指二元碼。

96.1.1信道編碼的分類106.1.2與糾錯編碼有關(guān)的基本概念

在通信系統(tǒng)的接收端，若接收到的消息序列R和發(fā)送的碼符號序列C不一樣，例如R=(11000)，而C=(10001)，R與C中有兩位不同，即出現(xiàn)兩個錯誤，這種錯誤是由信道中的噪聲干擾所引起的。116.1.2與糾錯編碼有關(guān)的基本概念1.碼長、碼重和碼距碼字中碼元的個數(shù)稱為碼字的長度，簡稱碼長，用n表示。碼字中非“0”碼元的個數(shù)稱為碼字的漢明重量(簡稱碼重，記作W)。對二進(jìn)制碼來說，碼重W就是碼字中所含碼元“1”的數(shù)目，例如碼字“110000”，其碼長n=6，碼重W=2。兩個等長碼字之間對應(yīng)碼元不相同的數(shù)目稱為這兩個碼組的漢明距離(簡稱碼距)。例如碼字“110000”與“100001”，它們的漢明距離D=2。

126.1.2與糾錯編碼有關(guān)的基本概念在某一碼集C中，任意兩個碼字之間漢明距離的最小值稱為該碼的最小距離dmin，即：例如：碼組C={0111100，1011011，1101001}的最小碼距dmin=3。從避免碼字受干擾而出錯的角度出發(fā)，總是希望碼字間有盡可能大的距離，因為最小碼距代表著一個碼組中最不利的情況。

136.1.2與糾錯編碼有關(guān)的基本概念2.錯誤圖樣為了定量地描述信號的差錯，定義收、發(fā)碼之“差”為差錯圖樣。差錯圖樣E＝發(fā)碼C-

收碼R

（模M）。例：8進(jìn)制(M=8)碼元，若發(fā)碼 ：C=（0,2,5,4,7,5,2）收碼變?yōu)椋篟=（0,1,5,4,7,5,4）差錯圖樣 E=C-R=（0,1,0,0,0,0,6）（模8）二進(jìn)制碼：E=CR或

C=RE。

146.1.3錯誤的種類1、隨機(jī)錯誤：由隨機(jī)干擾引起。(前后位置無關(guān)，時間無關(guān)，差錯以等概率發(fā)生)特點(diǎn)：因為干擾是隨機(jī)的，所以各碼元是否發(fā)生錯誤是相互獨(dú)立的，不會成片出錯。2、突發(fā)錯誤：由突發(fā)干擾引起（前后相關(guān)，成堆出現(xiàn)）。特點(diǎn)：因為突發(fā)干擾是突然出現(xiàn)的，且能持續(xù)一段時間，同時相對功率較大，所以錯誤往往成片出現(xiàn)。常見錯誤有兩種：隨機(jī)錯誤和突發(fā)錯誤

（在一個突發(fā)錯誤持續(xù)長度內(nèi)，開頭和末尾的碼元總是錯的，中間一些碼元不一定都錯，但錯的碼元數(shù)較多）如閃電和開關(guān)瞬態(tài)往往引起突發(fā)錯誤。156.1.2與糾錯編碼有關(guān)的基本概念3.重復(fù)碼和奇偶校驗碼

1)重復(fù)碼構(gòu)成重復(fù)碼的方法是當(dāng)發(fā)送某個信源符號ai時，不是只發(fā)一個，而是連續(xù)重發(fā)多個，連續(xù)重發(fā)的個數(shù)越多，重復(fù)碼的抗干擾能力就越強(qiáng)，當(dāng)然效率也越低。

166.1.2與糾錯編碼有關(guān)的基本概念不重復(fù)時為(1，1)重復(fù)碼，如圖所示：重復(fù)一次時為(2，1)重復(fù)碼，如圖所示：

176.1.2與糾錯編碼有關(guān)的基本概念重復(fù)二次時為(3，1)重復(fù)碼，如圖所示：

186.1.2與糾錯編碼有關(guān)的基本概念

2)奇偶檢驗碼奇偶校驗是一種最基本的校驗方法。構(gòu)成奇偶檢驗碼的方法是在每k個二進(jìn)制信息位后加上一個奇(偶)監(jiān)督位(或稱校驗位)，使碼長n=k+r，同時使碼中“1”的個數(shù)恒為奇數(shù)(或偶數(shù))，如圖所示。在奇偶校驗碼中，監(jiān)督位r=1，它是一種碼重W為奇數(shù)(或偶數(shù))的系統(tǒng)分組碼。

196.1.2與糾錯編碼有關(guān)的基本概念206.1.2與糾錯編碼有關(guān)的基本概念

奇校驗----如果信息碼元中“1”值的個數(shù)為奇數(shù)個，則校驗碼元值為“0”；如果信息碼元中“1”值的個數(shù)為偶數(shù)個，則校驗碼元值為“1”。即所有信息碼元與校驗碼元的模二和等于“1”。偶校驗----如果信息碼元中“1”值的個數(shù)為偶數(shù)個，則校驗碼元值為“0”；如果信息碼元中“1”值的個數(shù)為奇數(shù)個，則校驗碼元值為“1”。即所有信息碼元與校驗碼元的模二和等于“0”。

216.1.3檢錯與糾錯原理

要糾正傳輸差錯，首先必須檢測出錯誤。而要檢測出錯誤，常用的方法是將發(fā)送端要傳送的信息序列(常為二進(jìn)制序列)中截取出長度相等的碼元進(jìn)行分組，每組長度為k，組成k位碼元信息序列M，并根據(jù)某種編碼算法以一定的規(guī)則在每個信息組的后面產(chǎn)生r個冗余碼元，由冗余碼元和信息碼元一起形成“n位編碼序列”，即信號碼字C，n位的碼字比信息碼長(有n=k+r個碼元)，因而糾錯編碼是冗余編碼。226.1.3檢錯與糾錯原理譯碼就是利用校驗關(guān)系進(jìn)行檢錯、糾錯的，在接收端收到的位碼字中，信息碼元與冗余碼元之間也應(yīng)符合上述編碼規(guī)則，并根據(jù)這一規(guī)則進(jìn)行檢驗，從而確定是否有錯誤。這就是差錯控制的基本思想。

236.1.3檢錯與糾錯原理分組碼一般用符號(n,k)表示，其中k是每組二進(jìn)制信息碼元的數(shù)目，n是編碼組的長度(簡稱碼長)，即編碼組的總位數(shù)，n-k=r為每碼組中的校驗碼元(或稱監(jiān)督位)數(shù)目。通常，將分組碼規(guī)定為具有如圖所示的結(jié)構(gòu)。圖中前面k位為信息位，后面附加r個校驗位。

24奇偶校驗方法。增加偶(或奇)校驗位使得對消息序列而言校驗方程成立，當(dāng)校驗位數(shù)增加時，可以檢測到差錯圖樣的種類數(shù)也增加，但同時碼率減小。n重復(fù)碼方法。重復(fù)消息位使之可以檢測出任意小于n個差錯的錯誤圖樣。等重碼方法。設(shè)計碼字中的非“0”符號個數(shù)(若是二進(jìn)制碼則為“1”的個數(shù))恒為常數(shù)，使碼集C由全體重量恒等的n長矢量組成。6.1.3檢錯與糾錯原理256.1.3檢錯與糾錯原理表所示為一種用于表示數(shù)字“0”到“9”的五中取三等重碼(所有碼字的碼重都等于“3”)的例子。

123456789001011110011011011010001111010111100011101001101101266.1.4檢錯與糾錯方式和能力

1.檢錯與糾錯方式自動請求重發(fā)方式----用于檢錯的糾錯碼在譯碼器輸出端給出當(dāng)前碼字傳輸是否可能出錯的指示，當(dāng)有錯時按某種協(xié)議通過一個反向信道請求發(fā)送端重傳已發(fā)送的全部或部分碼字，這種糾錯碼的應(yīng)用方式稱為自動請求重發(fā)方式(ARQ，Automatic-Repeat-reQuest)。27前向糾錯方式----用于糾錯的糾錯碼在譯碼器輸出端總要輸出一個碼字或是否出錯的標(biāo)志，這種糾錯碼的應(yīng)用方式稱為前向糾錯方式(FEC，F(xiàn)orward-errorcontrol)。另外用于檢錯與糾錯的方式還有混合糾錯(HEC，HybridErrorCorrection)。如圖所示為上述幾種檢錯與糾錯方式示意圖，圖中有斜線的方框表示在該端檢出錯誤。6.1.4檢錯與糾錯方式和能力286.1.4檢錯與糾錯方式和能力29ARQ方式：發(fā)送端用編碼器對發(fā)送數(shù)據(jù)進(jìn)行差錯編碼，通過正向信道送到接收端，而接收端經(jīng)譯碼器處理后只是檢測有無差錯，不作自動糾正。如檢測到差錯，則利用反向信道反饋信號，請求發(fā)送端重發(fā)有錯的數(shù)據(jù)單元，直到接收端檢測不到差錯為止。

6.1.4檢錯與糾錯方式和能力30FEC方式：發(fā)送端用編碼器對發(fā)送數(shù)據(jù)進(jìn)行差錯編碼，在接收端用譯碼器對接收到的數(shù)據(jù)進(jìn)行譯碼后檢測有無差錯，通過按預(yù)定規(guī)則的運(yùn)算，如檢測到差錯，則確定差錯的具體位置和性質(zhì)，自動加以糾正，故稱為“前向糾錯”。6.1.4檢錯與糾錯方式和能力31HEC方式：是檢錯重發(fā)和前向糾錯兩種方式的混合。發(fā)送端用編碼器對發(fā)送數(shù)據(jù)進(jìn)行便于檢錯和糾錯的編碼，通過正向信道送到接收端，接收端對少量的接收差錯進(jìn)行自動前向糾正，而對超出糾正能力的差錯則通過反饋重發(fā)方式加以糾正，所以是一種糾檢結(jié)合的混合方式。6.1.4檢錯與糾錯方式和能力32

2.檢錯與糾錯能力一個糾錯碼的每個碼字都可以形成一個漢明球，因此要能夠糾正所有不多于t位的差錯，糾錯碼的所有漢明球均應(yīng)不相交，判定糾錯碼的檢、糾錯能力可根據(jù)任意兩個漢明球不相交的要求，由碼的最小距離dmin來決定。

6.1.4檢錯與糾錯方式和能力33定理1若糾錯碼的最小距離為dmin，那么如下三個結(jié)論的任何一個結(jié)論獨(dú)立成立：①若要發(fā)現(xiàn)e個獨(dú)立差錯，則要求最小碼距

②若要糾正t個獨(dú)立差錯，則要求最小碼距

③若要求發(fā)現(xiàn)e個同時又糾正t個獨(dú)立差錯，則6.1.4檢錯與糾錯方式和能力34

6.1.4檢錯與糾錯方式和能力35定理說明，碼的最小距離dmin越大，碼的糾(檢)錯誤的能力越強(qiáng)。但是，隨著多余碼元的增多，信息傳輸速率會降低得越多。通常用=k/n來表示碼字中信息碼元所占的比例，稱為編碼效率，它是衡量碼性能的又一個重要參數(shù)。碼率越高，信息傳輸率就越高，但此時糾錯能力要降低，若=1時就沒有糾錯能力了。可見，碼率與糾錯能力之間是有矛盾。6.1.4檢錯與糾錯方式和能力366.1.5矢量空間與碼空間F表示碼元所在的數(shù)域，對于二進(jìn)制碼，F(xiàn)代表二元域{0,1}。設(shè)n重有序元素的集合V={Vi

},若滿足條件：V中矢量元素在矢量加運(yùn)算下構(gòu)成加群；V中矢量元素與數(shù)域F元素的標(biāo)乘封閉在V中；分配律、結(jié)合律成立，則稱集合V是數(shù)域F上的n維矢量空間，或稱n維線性空間，n維矢量又稱n重(n-tuples)。376.1.5矢量空間與碼空間對于域F上的若干矢量

線性組合：

線性相關(guān)：其中任一矢量可表示為其它矢量的線性組合

線性無關(guān)或線性獨(dú)立：一組矢量中的任意一個都不可能用其它矢量的線性組合來代替。386.1.5矢量空間與碼空間一組線性無關(guān)的矢量，線性組合的集合就構(gòu)成了一個矢量空間V，這組矢量就是這個矢量空間的基底。n維矢量空間應(yīng)包含n個基底基底不是唯一的，例：線性無關(guān)的兩個矢量（1,0）和（0,1）以及（-1,0）和（0,-1）可張成同一個兩維空間。396.1.5矢量空間與碼空間以（100）為基底可張成一維三重子空間V1，含21=2個元素，即以(010)(001)為基底可張成二維三重子空間V2，含22=4個元素，即以(100)(010)(001)為基底可張成三維三重空間V,含23=8個元素，V1和V2都是V的子空間。406.1.5矢量空間與碼空間每個矢量空間或子空間中必然包含零矢量兩個矢量正交：V1V2＝0兩個矢量空間正交：某矢量空間中的任意元素與另一矢量空間中的任意元素正交正交的兩個子空間V1、V2互為對偶空間(DualSpace)，其中一個空間是另一個空間的零空間（nullspace，也稱零化空間）。416.1.5矢量空間與碼空間碼空間通常qn>>qk，分組編碼的任務(wù)是要在n維n重矢量空間的qn種可能組合中選擇其中的qk個構(gòu)成一個碼空間，其元素就是許用碼的碼集。

消息k長 (n,k)碼字n長

qk

種分組編碼器qn種

k維k重矢量n維n重矢量426.1.5矢量空間與碼空間分組編碼的任務(wù)：

①選擇一個ｋ維n重子空間作為碼空間。

②確定由k維k重信息空間到ｋ維n重碼空間的映射方法。碼空間的不同選擇方法，以及信息組與碼組的不同映射算法，就構(gòu)成了不同的分組碼。436.1.6隨機(jī)編碼運(yùn)用概率統(tǒng)計方法在特定信道條件下對編碼信號的性能作出統(tǒng)計分析，求出差錯概率的上下限邊界，其中最優(yōu)碼所能達(dá)到的差錯概率上界稱作隨機(jī)碼界。用這種方法不能得知最優(yōu)碼是如何具體編出來的，卻能得知最優(yōu)碼可以好到什么程度，并進(jìn)而推導(dǎo)出有擾離散信道的編碼定理，對指導(dǎo)編碼技術(shù)具有特別重要的理論價值。446.1.6隨機(jī)編碼在(N,K)分組編碼器中隨機(jī)選定的碼集有qNM種，第m個碼集(記作{c}m)被隨機(jī)選中的概率是：設(shè)與這種選擇相對應(yīng)的條件差錯概率是Pe({c}m)，那么全部碼集的平均差錯概率是：456.1.6隨機(jī)編碼必定存在某些碼集某些碼集若，就必然存在一批碼集即差錯概率趨于零的好碼一定存在466.1.6隨機(jī)編碼碼集點(diǎn)數(shù)M=qK占N維矢量空間總點(diǎn)數(shù)qN的比例是F=qK/qN

=q-(N-K)

。當(dāng)K和N的差值拉大即冗余的空間點(diǎn)數(shù)增加時，平均而言碼字的分布將變得稀疏，碼字間的平均距離將變大，平均差錯概率將變小。當(dāng)F0即(N-K)時，能否讓平均差錯概率？Gallager在1965年推導(dǎo)了的上邊界，并證明這個上邊界是按指數(shù)規(guī)律收斂的。47

E(R)為可靠性函數(shù)，也叫誤差指數(shù)。碼率：R=(lbM)

/N

，

M是可能的信息組合數(shù)，M=qK，N是每碼字的碼元數(shù)，R表示每碼元攜帶的信息量，單位是每符號比特（bit/symbol）。R在[0,R0]區(qū)間時E(R)~R曲線是斜率為-1（-45）的直線，E(R)反比于R；而當(dāng)R=C時E(R)=0即可靠性為零。

6.1.7信道編碼定理486.1.7信道編碼定理49

正定理：只要傳信率R小于信道容量C，總存在一種信道碼（及解碼器），可以以所要求的任意小的差錯概率實現(xiàn)可靠的通信。逆定理：信道容量C是可靠通信系統(tǒng)傳信率R的上邊界，如果R>C，就不可能有任何一種編碼能使差錯概率任意小。6.1.7信道編碼定理506.2糾錯編譯碼的基本原理與分析

R不變，信道容量大者其可靠性函數(shù)E(R)也大；C不變，碼率減小時其可靠性函數(shù)E(R)增大E(R) R0R1<R2C1

<C2

增大E(R)的途徑516.2.1糾錯編碼的基本思路對于同樣的碼率，信道容量大者其可靠性函數(shù)E(R)也大；對于同樣的信道容量，碼率減小時其可靠性函數(shù)E(R)增大?？刹扇∫韵麓胧p小差錯概率。(1)增大信道容量C增大E(R)的途徑①擴(kuò)展帶寬。②加大功率。③降低噪聲。52(2)減小碼率R①q，N不變而減小K，這意味著降低信息源速率，每秒少傳一些信息。②q，K不變而增大N，這意味著提高符號速率（波特率），占用更大帶寬。③N，K不變而減小q，這意味著減小信道的輸入、輸出符號集，在發(fā)送功率固定時提高信號間的區(qū)分度，從而提高可靠性。6.2.1糾錯編碼的基本思路53(3)增加碼長N隨著N增大，矢量空間以指數(shù)量級增大，從統(tǒng)計角度而言碼字間距離也將加大，從而可靠性提高。另外，碼長N越大，其實際差錯概率就越能符合統(tǒng)計規(guī)律。6.2.1糾錯編碼的基本思路54糾錯能力的獲取

(1)利用冗余度冗余度：在信息流中插入冗余比特，這些冗余比特與信息比特之間存著特定的相關(guān)性。冗余的資源：時間，頻帶，功率，設(shè)備復(fù)雜度。

6.2.1糾錯編碼的基本思路556.2.1糾錯編碼的基本思路

(2)噪聲均化噪聲均化：讓差錯隨機(jī)化，以便更符合編碼定理的條件從而得到符合編碼定理的結(jié)果?；舅枷耄涸O(shè)法將危害較大的、較為集中的噪聲干擾分?jǐn)傞_來，使不可恢復(fù)的信息損傷最小。①增加碼長N②卷積③交錯（或稱交織）

566.2.2最優(yōu)譯碼與最大似然譯碼譯碼器的任務(wù)是從受損的信息序列中盡可能正確地恢復(fù)出原信息。譯碼算法的已知條件是：①實際接收到的碼字序列{r},r=(rn,rn-1,…,r1)②發(fā)端所采用的編碼算法和該算法產(chǎn)生的碼集Xn,滿足③信道模型及信道參數(shù)。576.2.2最優(yōu)譯碼與最大似然譯碼586.2.2最優(yōu)譯碼與最大似然譯碼1.最佳譯碼(最大后驗概率譯碼)在已知r的條件下找出可能性最大的發(fā)碼作為譯碼估值，即令596.2.2最優(yōu)譯碼與最大似然譯碼2.最大似然譯碼在已知r的條件下使先驗概率最大的譯碼算法

也叫似然函數(shù)。利用貝葉斯公司可以建立先驗概率和后驗概率之間的關(guān)系：606.2.2最優(yōu)譯碼與最大似然譯碼如果①構(gòu)成碼集的個碼字以相同概率發(fā)送，滿足。②對于任何r都有相同的值，滿足。則最大等效于的最大，在此前提下最佳譯碼等效于最大似然譯碼。616.2.2最優(yōu)譯碼與最大似然譯碼對于無記憶信道，

例：BSC信道的最大似然譯碼可以簡化為最小漢明距離譯碼。漢明距離譯碼是一種硬判決譯碼。由于BSC信道是對稱的，只要發(fā)送的碼字獨(dú)立、等概，漢明距離譯碼也就是最佳譯碼。626.3線性分組碼m=(mk-1,…,m1,m0)c=(cn-1,…,c1,c0)碼字c消息m(n,k)分組編碼器

碼集C能否構(gòu)成n維n重矢量空間的一個k維n重子空間？如何尋找最佳的碼空間？qk個信息元組以什么算法一一對應(yīng)映射到碼空間。

碼率－－編碼效率：Rc

=k/n

636.3線性分組碼為了敘述方便，以下認(rèn)為碼失、碼字、碼組是同義詞，對n重矢量、1n矩陣、行矢量等的數(shù)學(xué)表達(dá)式也不作嚴(yán)格區(qū)別。646.3線性分組碼設(shè)有等概出現(xiàn)的M組待傳信源消息，每組有k位，即。今加上r個多余位，使每組消息變成n=k+r位。而n位長的二進(jìn)制序列共有2n個，但由于信息組只有2k個，故有2n-2k個n位序列不是碼字。設(shè)碼字的形式為：656.3.1生成矩陣和校驗矩陣

線性分組碼碼空間C是由k個線性無關(guān)的基底張成的k維n重子空間，碼空間的所有元素（即碼字）都可以寫成k個基底的線性組合，即這種線性組合特性正是線性分組碼名稱的來歷。顯然，研究線性分組碼的關(guān)鍵是研究基底、子空間和映射規(guī)則，如圖所示

666.3.1生成矩陣和校驗矩陣Hn-k維n重對偶空間Dk維k重信息組空間mk維n重碼空間cGn維n重空間Vn676.3.1生成矩陣和校驗矩陣用gi表示第i個基底并寫成矩陣再將k個基底排列成k行n列的G矩陣686.3.1生成矩陣和校驗矩陣碼空間的所有元素（即碼字）都可以寫成k個基底的線性組合。由于k個基底即G的k個行矢量線性無關(guān)，矩陣G的秩一定等于k。當(dāng)信息元確定后，碼字僅由G矩陣決定，因此我們稱這k×n矩陣G為該(n,k)線性分組碼的生成矩陣。696.3.1生成矩陣和校驗矩陣1.生成矩陣G(k×n)的特點(diǎn)想要保證(n,k)線性分組碼能夠構(gòu)成k維n重子空間，G

的k個行矢量gk-1,…,g1,g0必須是線性無關(guān)的，只有這樣才符合作為基底的條件。由于基底不是唯一的，所以G也就不是唯一的。不同的基底有可能生成同一碼集，但因編碼涉及碼集和映射兩個因素，碼集一樣而映射方法不同也不能說是同樣的碼。706.3.1生成矩陣和校驗矩陣2.系統(tǒng)形式的生成矩陣

(n,k)碼的任何生成矩陣都可以通過行運(yùn)算（以及列置換）簡化成“系統(tǒng)形式”。

Ik是k×k單位矩陣，P是k×(n-k)矩陣。

716.3.1生成矩陣和校驗矩陣3.生成的碼字C

前k位由單位矩陣Ik決定，等于把信息組m原封不動搬到碼字的前k位；其余的n-k位叫冗余位或一致校驗位，是前k個信息位的線性組合。這樣生成的（n,k）碼叫做系統(tǒng)碼。若生成矩陣G不具備系統(tǒng)形式，則生成的碼叫做非系統(tǒng)碼。系統(tǒng)化不改變碼集，只是改變了映射規(guī)則。726.3.1生成矩陣和校驗矩陣4.系統(tǒng)碼若通過行運(yùn)算和列置換能將兩個生成矩陣G互等，則稱這兩個G等效。非系統(tǒng)碼的G可通過運(yùn)算轉(zhuǎn)變?yōu)橄到y(tǒng)碼的G。等效的兩個G生成的兩個(n,k)線性碼也是等效的。因此，每個(n,k)線性碼都可以和一個系統(tǒng)的(n,k)線性碼等效。736.3.1生成矩陣和校驗矩陣5.空間構(gòu)成n維n重空間有相互正交的n個基底，選擇k個基底構(gòu)成碼空間C，選擇另外的(n-k)個基底構(gòu)成空間H，C和H是對偶的CHT＝0,GHT=0。746.3.1生成矩陣和校驗矩陣6.校驗矩陣將H空間的n-k個基底排列起來可構(gòu)成一個(n-k)×n矩陣，稱為校驗矩陣H。用來校驗接收到的碼字是否是正確的；G是(n,k)碼的生成矩陣，H是它的校驗矩陣；H是(n,n-k)對偶碼的生成矩陣，它的每一行是一個基底。G則是它的校驗矩陣。756.3.1生成矩陣和校驗矩陣以(7,3)線性分組碼為例。信息位k=3，則校驗元個數(shù)為r=n-k，設(shè)碼字為：,其中為信息元；為校驗元。每個碼元取值為“0”或“1”。設(shè)某(7,3)線性分組碼各碼字的校驗元與信息元之間的關(guān)系由下述方程決定：766.3.1生成矩陣和校驗矩陣

稱此方程為該（7,3）線性分組碼的校驗方程，由于該碼系的所有碼字都按同一規(guī)則確定與校驗，故又稱為一致校驗方程。776.3.1生成矩陣和校驗矩陣如：信息組為101，即代入一致校驗方程得：所以由信息組101編出的可送給信道傳輸?shù)摹⒕哂幸欢m錯能力的碼字為：1010011。同理可求出與其他7個信息組相對應(yīng)的碼字見下表：信息組對應(yīng)碼字對應(yīng)碼字信息組00000101001111111010110001110100100111001110100000001110100110100110100111001110786.3.1生成矩陣和校驗矩陣為了運(yùn)算方便，可將一致校驗方程組寫成矩陣形式：796.3.1生成矩陣和校驗矩陣設(shè)則：或：（4×3）單位子陣806.3.1生成矩陣和校驗矩陣線性分組碼的一致生成矩陣與一致校驗矩陣之間有著非常密切的關(guān)系，這種關(guān)系非常重要。下面說明它們的關(guān)系：由于生成矩陣G的每一行都是一個碼字，而或者816.3.1生成矩陣和校驗矩陣更進(jìn)一步：結(jié)論：(n,k)線性分組碼的一致生成矩陣G與一致校驗矩陣H之間可方便地相互轉(zhuǎn)換?；蛘?26.3.1生成矩陣和校驗矩陣?yán)?.1(6,3)線性分組碼，其生成矩陣是836.3.1生成矩陣和校驗矩陣求：(1)計算碼集，列出信息組與碼字的映射關(guān)系。(2)將該碼系統(tǒng)化處理后，計算系統(tǒng)碼碼集并列出映射關(guān)系。(3)計算系統(tǒng)碼的校驗矩陣H。若收碼r=[100110],檢驗它是否碼字？(4)根據(jù)系統(tǒng)碼生成矩陣畫出編碼器電原理圖。846.3.1生成矩陣和校驗矩陣解(1)由得

令得信息碼字系統(tǒng)碼字000000000000000001 011101 001011010 110001 010110011 101100 011101100 111010 100111101 100111 101100110 001011 110001111010110 111010856.3.1生成矩陣和校驗矩陣(2)對G作行運(yùn)算，得系統(tǒng)化后的生成矩陣Gs

866.3.1生成矩陣和校驗矩陣(3)876.3.1生成矩陣和校驗矩陣(4)m0m1m2c0c1c2輸入輸出886.3.2線性分組碼的糾錯能力

N重碼矢可與N維矢量空間XN中的一個點(diǎn)對應(yīng)，全體碼字所對應(yīng)的點(diǎn)構(gòu)成矢量空間里的一個子集。發(fā)碼一定在這個子集里，傳輸無誤時的收碼也一定位于該子集。當(dāng)出現(xiàn)差錯時，接收的N重矢量有兩種可能：一種是對應(yīng)到子集外空間某一點(diǎn)；另一種對應(yīng)到該子集，卻對應(yīng)到該子集的另一點(diǎn)上。

896.3.2線性分組碼的糾錯能力定理6.1任何最小距離dmin的線性分組碼，其檢錯能力為（dmin-1）,糾錯能力t為定理6.2線性分組碼的最小距離等于碼集中非零碼字的最小重量

dmin=min{w(Ci

)} CiC

及Ci

0906.3.2線性分組碼的糾錯能力

定理6.3(n,k)線性分組碼最小距離等于dmin的充要條件是：校驗矩陣H中有（dmin-1)列線性無關(guān)。

定理6.4(n,k)線性分組碼的最小距離必定小于等于(n-k+1)916.3.2線性分組碼的糾錯能力例：(7，4)線性碼

926.3.2線性分組碼的糾錯能力各列都不相同，任意2列之和不等于0，2列線性無關(guān)；任意2列之和一定等于矩陣中某一列，任意3列線性相關(guān)。所以該碼的最小距離為3，小于n-k+1=4。

(n,k)線性碼最小距離dmin的上邊界是n-k+1。如果我們設(shè)計的(n,k)線性碼的dmin達(dá)到了n-k+1，就是達(dá)到了設(shè)計性能的極點(diǎn)。因此，dmin=n-k+1的碼稱為極大最小距離碼

(MDC–MaximizedminimumDistanceCode)。936.3.3伴隨式與標(biāo)準(zhǔn)陣列譯碼

定義差錯圖案E

二進(jìn)制碼中模2加與模2減是等同的，因此有E=R+C

及R=C+E

1.伴隨式S的定義因為CHT=0(碼字和校驗矩陣的正交性)所以RHT=(C+E)HT=CHT+EHT=EHT946.3.3伴隨式與標(biāo)準(zhǔn)陣列譯碼

1、如果收碼無誤：必有R=C即E=0，則EHT=0RHT=0。

2、如果收碼有誤：即E

0，則RHT

=EHT0。在HT固定的前提下，RHT僅僅與差錯圖案E有關(guān)，而與發(fā)送碼C無關(guān)。定義伴隨式S

S=(sn-k-1,…,s1,s0)=RHT=EHT

956.3.3伴隨式與標(biāo)準(zhǔn)陣列譯碼

2.伴隨式S的意義從物理意義上看，伴隨式S并不反映發(fā)送的碼字是什么，而只是反映信道對碼字造成怎樣的干擾。

差錯圖案E是n重矢量，共有2n個可能的組合，而伴隨式S是(n-k)重矢量，只有2n-k個可能的組合，因此不同的差錯圖案可能有相同的伴隨式。

接收端收到R后，因為已知HT，可求出S=RHT

；如果能知道對應(yīng)的E，則通過C=R+E而求得C。966.3.3伴隨式與標(biāo)準(zhǔn)陣列譯碼

3.差錯圖案E的求解可以通過解線性方程求解E：

976.3.3伴隨式與標(biāo)準(zhǔn)陣列譯碼得到線性方程組：

sn-k-1=en-1h(n-k-1)(n-1)+…+e1h(n-k-1)1+e0h(n-k-1)0

s1=en-1h1(n-1)+…+e1h11+e0h10

s0=en-1h0(n-1)+…+e1h01+e0h00986.3.3伴隨式與標(biāo)準(zhǔn)陣列譯碼上述方程組中有n個未知數(shù)en-1,…e1,e0

，卻只有n-k個方程，可知方程組有多解。在有理數(shù)或?qū)崝?shù)域中，少一個方程就可能導(dǎo)致無限多個解，而在二元域中，少一個方程導(dǎo)致兩個解，少兩個方程四個解，以此類推，少n-(n-k)=k個方程導(dǎo)致每個未知數(shù)有2k個解。到底取哪一個作為附加在收碼R上的差錯圖案E的估值呢？

996.3.3伴隨式與標(biāo)準(zhǔn)陣列譯碼概率譯碼：把所有2k個解的重量(差錯圖案E中1的個數(shù))作比較，選擇其中最輕者作為E的估值。該方法概念上很簡單但計算效率不高。依據(jù)：若BSC信道的差錯概率是p，則長度n的碼中錯誤概率：1006.3.3伴隨式與標(biāo)準(zhǔn)陣列譯碼0個錯1個錯2個錯…n個錯

(1-p)n

p(1-p)n-1

p2(1-p)n-2

pn

>>>>>>…>>由于p<<1，出錯越少的情況，發(fā)生概率越大，E的重量越輕，所以該譯碼方法實際上體現(xiàn)了最小距離譯碼準(zhǔn)則，即最大似然譯碼。依據(jù)：若BSC信道的差錯概率是p，則長度n的碼中錯誤概率：1016.3.3伴隨式與標(biāo)準(zhǔn)陣列譯碼

方法：(1)按最可能出現(xiàn)的2r個差錯圖案E，計算相應(yīng)的伴隨式S，并構(gòu)造伴隨式一差錯圖案表[(S,E)]。(2)對接收向量R計算伴隨式S。(3)查[(S,E)]表得E。(4)糾錯計算C=R-E。1026.3.3伴隨式與標(biāo)準(zhǔn)陣列譯碼例：設(shè)某（7,3）線性分組碼的一致校驗矩陣為：發(fā)送端發(fā)送的碼字為（注：接收端譯碼器并不知道發(fā)送碼字）。試討論下面三種接收情況下的判錯情形：1036.3.3伴隨式與標(biāo)準(zhǔn)陣列譯碼①接收端接收的碼字為②接收端接收的碼字為③接收端接收的碼字為解:①當(dāng)接收端接收的碼字為時，故譯碼器判為沒錯。1046.3.3伴隨式與標(biāo)準(zhǔn)陣列譯碼②當(dāng)接收端接收的碼字為時，又由其H陣知該(7,3)碼為能糾1個錯誤的碼型，且ST正好等于H陣中的第二列，因此可判定第二位有錯。1056.3.3伴隨式與標(biāo)準(zhǔn)陣列譯碼③當(dāng)接收端接收的碼字為時，譯碼器判為有錯。又由于此時的伴隨式ST與H中任一列均不同，故一定出現(xiàn)了兩位或兩位以上的錯誤，譯碼器無法判定錯誤究竟出現(xiàn)在哪些位上。1066.3.3伴隨式與標(biāo)準(zhǔn)陣列譯碼伴隨式計算電路(以上例中的(7,3)碼為例)設(shè)接收字為1076.3.3伴隨式與標(biāo)準(zhǔn)陣列譯碼碼字輸入移位寄存器組半加器1086.3.3伴隨式與標(biāo)準(zhǔn)陣列譯碼伴隨式計算電路組合邏輯電路糾錯譯碼電路…………輸入（信道輸出）譯碼輸出1096.3.3伴隨式與標(biāo)準(zhǔn)陣列譯碼4.標(biāo)準(zhǔn)陣列譯碼表上述的概率譯碼，如每接收一個碼R就要解一次線性方程，那就太麻煩了。好在伴隨式S的數(shù)目是有限的2n-k個，如果n-k不太大，我們可以預(yù)先把不同S下的方程組解出來，把各種情況下的最大概率譯碼輸出列成一個碼表。這樣，在實時譯碼時就不必再去解方程，而只要象查字典那樣查一下碼表，這樣構(gòu)造的表格叫做標(biāo)準(zhǔn)陣列譯碼表。1106.3.3伴隨式與標(biāo)準(zhǔn)陣列譯碼表中所列碼字是接收到的碼字R；將沒有任何差錯時的收碼R放在第一行，收碼等于發(fā)碼R=C(CCi,i=0,1,…2k-1),差錯圖案為全零E0=(0,0…0)，伴隨式為全零S0=(0,0…0)。由于有2k個碼字，碼表有2k列。

在第2到第n+1的n行中差錯圖案的所有重量為1(共n個)。1116.3.3伴隨式與標(biāo)準(zhǔn)陣列譯碼如果(1+n)<2n-k，再在下面行寫出全部帶有2個差錯的圖案(共個)。如果總行數(shù)(1+n+)仍然小于2n-k，再列出帶有3個差錯的圖案，以此類推，直到放滿2n-k行，每行一個Ej,對應(yīng)一個不同的伴隨式Sj。這樣，表的行數(shù)2n-k正好等于伴隨式的數(shù)目。1126.3.3伴隨式與標(biāo)準(zhǔn)陣列譯碼S0E0S1E1

SjEj

E0+C0=0+0=0E0+C1=C1E0+Ci=CiE1+C0=E1

E1+CiEj+C0=EjEj+C1Ej+Ci

E1+C1

1136.3.3伴隨式與標(biāo)準(zhǔn)陣列譯碼譯碼表中有2n-k行，每行是一個陪集，每陪集的第一個元素(位于第一列)叫陪集首。同一陪集（同一行）中的所有元素對應(yīng)共同的一個伴隨式。第一行陪集的陪集首是全零伴隨式S0所對應(yīng)的全零差錯圖案E0(無差錯)，而第j行陪集的陪集首是伴隨式Sj所對應(yīng)的重量最小的差錯圖案Ej(C0=0,Rj=Ej)。1146.3.3伴隨式與標(biāo)準(zhǔn)陣列譯碼譯碼表中有2k列，每列是一個子集，每子集的第一個元素(位于第一行)叫子集頭。同一子集（同一列）中的所有元素對應(yīng)同一個碼字，第一列子集的子集頭是全零碼字C0，而第i列子集的子集頭是碼字Ci(E0=0,Ri=Ci)。1156.3.3伴隨式與標(biāo)準(zhǔn)陣列譯碼例6.3一個(5,2)系統(tǒng)線性碼的生成矩陣是G=設(shè)收碼R=(10101)，構(gòu)造標(biāo)準(zhǔn)陣列譯碼表，譯出發(fā)碼的估值解：(1)構(gòu)造標(biāo)準(zhǔn)陣列譯碼表。分別以信息組m=(00)、(01)、(10)、(11)及已知的G求得4個許用碼字為C1=(00000)、C2=(10111)、C3=(01101)、C4=(11010)。1166.3.3伴隨式與標(biāo)準(zhǔn)陣列譯碼求出校驗矩陣：1176.3.3伴隨式與標(biāo)準(zhǔn)陣列譯碼列出方程組：伴隨式有2n-k=23=8種組合，差錯圖案中代表無差錯的有一種，代表一個差錯的圖案有種，代表兩個差錯的圖案有種。只需挑選其中的兩個，挑選方法可有若干種，不是唯一的。1186.3.3伴隨式與標(biāo)準(zhǔn)陣列譯碼先將Ej=(00000)、(10000)、(01000)、(00100)、(00010)、(00001)代入上面的線性方程組，解得對應(yīng)的Sj分別是(000)、(111)、(101)、(100)、(010)、(001)。剩下的伴隨式中，(011)所對應(yīng)的差錯圖案是2k個即(00011)、(10100)、(01110)、(11001),其中(00011)和(10100)并列重量最輕，任選其中一個如(00011)。同樣可得伴隨式(110)所對應(yīng)的最輕差錯圖案之一是(00110)。1196.3.3伴隨式與標(biāo)準(zhǔn)陣列譯碼S0=000E0+C0=00000C1=10111C2=01101C3=11010S1=111E1=10000001111110101010S2=101E2=01000111110010110010S3=100E3=00100100110100111110S4=010E4=00010101010111111000S5=001E5=00001101100110011011S6=011E6=00011101000111011001S7=110E7=001101000101011111001206.3.3伴隨式與標(biāo)準(zhǔn)陣列譯碼將接收碼R＝10101譯碼可選以下三種方法之一譯碼：(1)直接搜索碼表，查得(10101)所在列的子集頭是(10111)，因此譯碼輸出取為(10111)。

(2)先求伴隨式RHT=(10101)

HT=(010)=S4，確定S4所在行，再沿著行對碼表作一維搜索找到(10101),最后順著所在列向上找出碼字(10111)。1216.3.3伴隨式與標(biāo)準(zhǔn)陣列譯碼

(3)先求出伴隨式RHT=(010)=S4并確定S4所對應(yīng)的陪集首（差錯圖案）E4=(00010)，再將陪集首與收碼相加得到碼字C=R+E4=(10101)+(00010)=(10111)。上述三種方法由上而下，查表的時間下降而所需計算量增大，實際使用時可針對不同情況選用。1226.3.3伴隨式與標(biāo)準(zhǔn)陣列譯碼對上例作進(jìn)一步分析，還可以看到，該(5,2)碼的dmin=3,糾錯能力是t=INT[(3-1)/2]=1。因此，譯碼陣列中只有前6行具有唯一性、可靠性，真正體現(xiàn)了最大似然譯碼準(zhǔn)則，而第7、8行的差錯圖案(00011)和(00110)中包含兩個“1”，已超出了t=1的糾錯能力，譯碼已不可靠。1236.3.3伴隨式與標(biāo)準(zhǔn)陣列譯碼比如，當(dāng)收碼R＝(10100)時，根據(jù)碼表譯出的碼字是(10111)，與收碼R的漢明距離是2，然而收碼R與全零碼字(00000)的漢明距離也是2，為什么不能譯成(00000)呢？事實上，碼表的第7、8行本身就不是唯一的。注意在碼表計算過程中，伴隨式(011)所對應(yīng)的4個差錯圖案中有兩個并列重量最輕，如果當(dāng)時選的不是(00011)而是(10100)，那么碼表第7行就不是現(xiàn)在這樣了。1246.3.4完備碼(Perfectcode)任何一個二元(n,k)線性分組碼都有2n-k個伴隨式，假如該碼的糾錯能力是t，則對于任何一個重量小于等于t的差錯圖案，都應(yīng)有一個伴隨式與之對應(yīng)，也就是說，伴隨式的數(shù)目滿足條件上式稱作漢明限，任何一個糾t碼都應(yīng)滿足上述條件。1256.3.4完備碼(Perfectcode)某二元(n,k)線性分組碼能使等式

成立，即該碼的伴隨式數(shù)目不多不少恰好和不大于t個差錯的圖案數(shù)目相等，相當(dāng)于在標(biāo)準(zhǔn)譯碼陣列中能將所有重量不大于t的差錯圖案選作陪集首，而沒有一個陪集首的重量大于t，這時的校驗位得到最充分的利用。這樣的二元(n,k)線性分組碼稱為完備碼。

1266.3.4完備碼(Perfectcode)1.漢明碼(HammingCode)

漢明碼不是指一個碼，而是代表一類碼。漢明碼的糾錯能力t=1，既有二進(jìn)制的，也有非二進(jìn)制的。二進(jìn)制時，漢明碼碼長n和信息位k服從以下規(guī)律：(n,k)=(2m-1,2m-1-m)

其中m=n-k，是正整數(shù)。當(dāng)m＝3、4、5、6、7、8…時，有漢明碼(7,4)、(15,11)、(31,26)、(63,57)、(127,120)……。1276.3.4完備碼(Perfectcode)漢明碼是完備碼，因為它滿足上述等式。1286.3.4完備碼(Perfectcode)漢明碼的校驗矩陣H具有特殊的性質(zhì)，能使構(gòu)造方法簡化。一個(n,k)碼的校驗矩陣有n-k行和n列，二進(jìn)制時n-k個碼元所能組成的列矢量總數(shù)是2n-k-1,恰好和校驗矩陣的列數(shù)n=2m-1相等。只要排列所有列，通過列置換將矩陣H轉(zhuǎn)換成系統(tǒng)形式，就可以進(jìn)一步得到相應(yīng)的生成矩陣G。1296.3.4完備碼(Perfectcode)例6.4構(gòu)造一個m=3的二元(7，4)漢明碼。解：先利用漢明碼的特性構(gòu)造一個(7，4)漢明碼的校驗矩陣H，再通過列置換將它變?yōu)橄到y(tǒng)形式：

0001111列置換1110100 H= 0110011 0111010=[PT

I3] 1010101 1101001再得生成矩陣G為

1000101 G=[I4

P]=0100111 0010110 0001011 1306.3.4完備碼(Perfectcode)

2.高萊（Golay）碼是二進(jìn)制（23，12）線性碼，其最小距離dmin＝7，糾錯能力t=3。是完備碼，因為滿足等式

223-12=2048=在(23,12)碼上添加一位奇偶位即得二進(jìn)制線性（24，12）擴(kuò)展高萊碼，其最小距離dmin＝8。1316.3.5循環(huán)碼

1.循環(huán)碼的定義定義1：如將一個碼系的全部碼字分成若干組，則每組的所有碼字可由其中任一碼字的循環(huán)移位得到。如(7,3)循環(huán)碼分成兩個組

(0000000)

(0010111)(0101110)(1011100)(0111001)(1110010)(1100101)(1001011)1326.3.5循環(huán)碼又如：(7,4)循環(huán)碼分成四個組

(0000000)

(1111111)

(1000101)(0001011)(0010110)(0101100)(1011000)(0110001)(1100010)

(1001110)(0011101)(0111010)(1110100)(1101001)(1010011)(0100111)1336.3.5循環(huán)碼

定義2:一個(n,k)線性分組碼C，若它一個碼矢的每一循環(huán)移位都是C的一個碼字，則C是一個循環(huán)碼。

循環(huán)碼是一種線性碼，因此線性碼的一切特性均適合于循環(huán)碼；但它的特殊性是其循環(huán)性，碼字集合或者說碼組中任意一個碼字的循環(huán)移位得到的序列仍是該碼字集合中的碼字，即它對循環(huán)操作滿足封閉性。1346.3.5循環(huán)碼2.循環(huán)碼的多項式描述一般(n,k)線性分組碼的k個基底之間不存在規(guī)則的聯(lián)系，因此需用k個基底組成生成矩陣來表示一個碼的特征。而循環(huán)碼的k個基底可以是同一個基底循環(huán)k次得到，因此用一個基底就足以表示一個碼的特征。既然只有一個基底，就無需矩陣，只要用多項式作為數(shù)學(xué)工具就足夠了。1356.3.5循環(huán)碼3.循環(huán)碼的多項式定義把碼字C＝[cn-1cn-2

…c1c0]與一個不大于n-1次的碼多項式C(x)對應(yīng)起來。

碼多項式C(x)定義為：

C(x)=cn-1xn-1+cn-2xn-2

+…+c1x+c0

對于二進(jìn)制碼，ci{0,1},i=0,…，n-1。1366.3.5循環(huán)碼循環(huán)移一位：(cn-1cn-2

…c1c0)(cn-2

…c1c0cn-1)循環(huán)移一位：C0(x)=cn-1xn-1+cn-2xn-2+…+c1x+c0

C1(x)=

cn-2xn-1+cn-3xn-2+…+c0x+cn-1比較循環(huán)移位的前后，可用如下的多項式運(yùn)算來表達(dá)循環(huán)移位

移1位：

C1(x)=xC0(x) mod(xn+1)

移2位：

C2(x)=xC1(x)=x2C0(x) mod(xn+1)

移n-1位：Cn-1(x)=xCn-2(x)=xn-1C0(x) mod(xn+1)1376.3.5循環(huán)碼4.碼字的組成根據(jù)碼空間封閉性，碼字的線性組合仍是碼字。C(x)=a0C0(x)+a1xC0(x)+a2x2C0(x)+…+an-1xn-1C0(x)=(a0+a1x

+a2x2+…+an-1xn-1)C0(x)=A(x)C0(x) mod(xn

+1) 其中C0(x)是一個碼多項式，而A(x)是次數(shù)不大于n-1的任意多項式。對于二進(jìn)制碼，ai{0,1},i=0,…，n-1。1386.3.5循環(huán)碼5.生成多項式C(x)=m(x)g(x)碼多項式信息多項式生成多項式

生成多項式不是唯一的；

g(x)＝x

n-k

+gn-k-1x

n-k-1+…+g2x2+g1x+1

是(n-k)次的首一碼多項式，即(n-k)次項的系數(shù)為1。g(x)一定是(xn+1)的因子。1396.3.5循環(huán)碼

幾個關(guān)于生成多項式的定理

定理1：在(n,k)循環(huán)碼中，生成多項式g(x)是唯一的(n-k)次多項式，且次數(shù)是最低的。定理2：在(n,k)循環(huán)碼中，每個碼多項式C(x)都是生成多項式g(x)的倍式，而每個g(x)倍式的次數(shù)小于或等于(n-1)的多項式必為(n,k)循環(huán)碼的碼多項式。1406.3.5循環(huán)碼

定理3：(n,k)循環(huán)碼的生成多項式g(x)是xn+1的因式，即xn+1=h(x)g(x)定理4：若g(x)是一個(n-k)次多項式，且為xn+1的因式，則g(x)生成唯一一個(n-k)循環(huán)碼碼系。以上幾個定理說明：構(gòu)建一個(n,k)循環(huán)碼時，只要分解多項式xn+1的因式，從中取出(n-k)次因式作生成多項式即可。1416.3.5循環(huán)碼6.校驗多項式多項式xn+1可因式分解為xn+1＝g(x)h(x)的形式；如果g(x)代表(n,k)循環(huán)碼的生成多項式，則h(x)代表該循環(huán)碼的一致校驗多項式，其階次為k。h(x)的校驗作用表現(xiàn)在：任何碼多項式C(x)與h(x)的模xn+1乘積一定等于0，而非碼字與h(x)的乘積必不為0。

C(x)h(x)=m(x)g(x)h(x)=m(x)(xn+1)=0mod(xn+1)1426.3.5循環(huán)碼例6.5研究一個長度n=7的循環(huán)碼的構(gòu)成方法對(x7+1)作分解，找出n-k次因式。

x7+1＝(x+1)(x3+x2+1)(x3+x+1)，

n-k因式g(x)對偶式h(x) 循環(huán)碼

1(x+1) (x3+x2+1)(x3+x+1) (7,6)3(x3+x2+1)(x+1)(x3+x+1) (7,4)3(x3+x+1)(x+1)(x3+x2+1) (7,4)4(x+1)(x3+x2+1)(x3+x+1) (7,3)4(x+1)(x3+x+1)(x3+x2+1) (7,3)6(x3+x2+1)(x3+x+1)

(x+1) (7,1)1436.3.5循環(huán)碼構(gòu)成(7,3)循環(huán)碼： 選g(x)=(x+1)(x3+x+1)=(x4+x3+x2+1)，則C(x)=m(x)g(x)=(m2x2+m1x+m0)(x4+x3+x2+1)。當(dāng)輸入信息m=(011)時，m(x)=(x+1)，C(x)=(x+

1)(x4＋x3＋x2＋1)=x5+x2+x1+

1， 對應(yīng)碼矢C=(0100111)。1446.3.5循環(huán)碼信息矢量m(m2m1m0)碼矢C(c6c5c4c3c2c1c0)000001010011100101110111000000000111010111010010011111101001101001100111010100111456.3.5循環(huán)碼6.系統(tǒng)循環(huán)碼碼字的前k位原封不動照搬信息位而后面(n-k)位為校驗位：C(x)=xn-km(x)+r(x)產(chǎn)生系統(tǒng)循環(huán)碼的方法：將信息多項式m(x)預(yù)乘xn-k，即右移(n-k)位；將xn-km(x)除以g(x)，得余式r(x)；得系統(tǒng)循環(huán)碼的碼多項式：C(x)=xn-km(x)+r(x)。1466.3.5循環(huán)碼例6.6(7,3)循環(huán)碼生成多項式是g(x)=x4+x3+x2+1，產(chǎn)生系統(tǒng)循環(huán)碼。解：先以輸入信息m=(011)即m(x)=(x+1)為例，①.xn-km(x)=x4(x+1)=x5+x4

②.(x5+x4)除以(x4+x3+x2+

1)，得余式(x3+x)③.C(x)=xn-km(x)

+r(x)＝(x5+x4)+(x3+x),