第九章糾錯編碼

第9章糾錯編碼9.1差錯控制5.2線性分組碼9.3循環(huán)碼9.4卷積碼9.1差錯控制9.1.1差錯控制9.1.2碼距與檢糾錯能力5.3.3最優(yōu)譯碼與最大似然譯碼差錯控制差錯類型隨機錯誤:數(shù)據(jù)流中發(fā)生的錯誤彼此無關(guān),表現(xiàn)為錯誤之間的無相關(guān)性.突發(fā)錯誤:數(shù)據(jù)流中一個錯誤的發(fā)生,帶來一連串錯誤的發(fā)生,表現(xiàn)為誤錯之間的相關(guān)性.差錯控制差錯控制系統(tǒng)前向糾錯方式(FEC)：發(fā)送端發(fā)送具有糾錯功能的碼,接收端收到這些碼后，通過譯碼器不僅能發(fā)現(xiàn)錯誤,而且能自行糾正錯誤。重傳反饋方式(ARQ)：發(fā)送端發(fā)送具有檢錯功能的碼,接收端收到這些碼后，譯碼器對發(fā)送的碼進行判決,接收端將判決的結(jié)果通過反饋信道告訴發(fā)送端,發(fā)送端將接收端認為有錯的消息再次發(fā)送,直到接收端認為正確為止.發(fā)送接收可以糾正錯誤的碼FEC發(fā)送接收可以糾正錯誤的碼ARQ應(yīng)答信號差錯控制/差錯控制系統(tǒng)狹義信息反饋系統(tǒng)(IRQ)：接收端將收到的消息原封不動地反饋到發(fā)送端,由發(fā)送端將反饋的消息比較,發(fā)現(xiàn)錯誤,再次發(fā)送?；旌霞m錯方式(HEC)發(fā)送接收可以發(fā)現(xiàn)糾正錯誤的碼HEC應(yīng)答信號發(fā)送接收信息信號IRQ信息信號交織器交錯（或稱交織）-----針對突發(fā)錯誤帶交錯器的傳輸系統(tǒng)信道噪聲造成的符號流中的突發(fā)差錯，有可能被均化而轉(zhuǎn)換為碼流上隨機的、可糾正的差錯。差錯控制糾錯碼的分類按譯碼器處理錯誤的性能分類能通過譯碼器自動發(fā)現(xiàn)錯誤的碼稱為檢錯碼;糾正錯誤的碼稱為糾錯碼;糾正刪除錯誤的碼稱為糾刪碼.按對信息位處理的方法分類分組碼卷積碼.差錯控制/分類按校驗位與信息位之間的關(guān)系分類線性碼非線性碼按能糾正錯誤的類型分類糾正隨機(獨立)錯誤的碼;糾正突發(fā)錯誤的碼;糾正同步錯誤的碼;糾正隨機錯誤與突發(fā)錯誤的碼.碼距與檢糾錯能力分組碼分組碼是信源輸出的q進制的源數(shù)據(jù)碼流按k個碼元(信息位)劃分為一段信息組m,通過編碼器按一定規(guī)則產(chǎn)生r個校驗(監(jiān)督)元，輸出長度n=k+r

個碼元的q進制碼字(碼組、碼矢)，此過程稱為分組碼編碼。碼距與檢糾錯能力/分組碼相關(guān)概念源數(shù)據(jù)按k個信息位組成的不同信息組有:M=qk

組按n個的碼元能組成的碼字共有:N=qn

個在qn個碼字中與信源符號組對應(yīng)的qk個碼字稱為許用碼字

,這qk個碼字集合記為C,稱為(n，k)分組碼;而其余qn-qk個碼字稱為禁用碼字。許用碼字表示為Ci=(ci1,ci2,…,cin)i=1,2,…,M。其中ci1,ci2,…,cin為碼元

,n為碼字的長度。編碼效率或碼率：R=k/n表示信息位在碼字中的比重,是衡量分組碼有效性的一個基本參數(shù)。碼距與檢糾錯能力碼距定義：設(shè)Ci=(ci1,ci2,…,cin),Cj=(cj1,cj2,…,cjn)是碼C的兩個碼字,Ci與Cj中cir≠cjr(r=1,2,…,n)的個數(shù)稱為Ci與Cj的漢明距離

,簡稱碼距，記為d(Ci,Cj)。定理：對于任意Ci,有d(Ci,Ci)=0對于任意Ci,Cj,有d(Ci,Cj)=d(Cj,Ci)

對于任意Ci,Cj,Cs,有d(Ci,Cj)+d(Cj,Cs)≥d(Ci,Cs)

碼距與檢糾錯能力/碼距定義：碼C的任意兩兩碼字的碼距中最小的碼距稱為碼C的最小距離

,記為dmin。推論1：若Ci,Cj

是碼C的任意兩個碼字,則d(Ci,Cj)≥dmin推論2：設(shè)碼C的最小距離為dmin,而Ci

是碼C的任一碼字，若有字R,當d(Ci,R

)<dmin

時,則R不是Ci

，就一定不是碼C的碼字。碼距與檢糾錯能力檢糾錯能力將二進制源數(shù)據(jù)碼流經(jīng)過如下幾種處理(編碼)后,在BSC信道中傳輸。幾種處理方法比較如下：不編碼若其中有碼元“0”錯成“1”或“1”錯成“0”。結(jié)論：接收端都無法檢查出其錯誤。將碼流中的碼元“0”→(00),“1”→(11)無論若(00)或(11)錯成(01)或(10),則接收端能檢查出其錯誤;但不能確定是(00)還是(11)若(00)錯成(11)或(11)錯成(00),則接收端無法檢出其錯誤。結(jié)論:能檢測1個隨機錯誤。碼距與檢糾錯能力/檢糾錯能力/幾種處理方法比較將碼流中的碼元“0”→(000),“1”→(111)無論(000)或(111)傳輸后有一個錯誤或有兩個錯誤,接收端能檢測其錯誤

;若(000)、(111)傳輸后只有一個錯誤,則接收端可將(001)、(010)、(100)譯碼為(000);將(011)、(101)、(110)譯碼為(111);若(000)、(111)傳輸后有兩個以下錯誤,則接收端無法將(011)、(101)、(110)正確地譯碼;若傳輸后(000)錯成(111)或(111)錯成(000),則接收端無法檢測其錯誤。結(jié)論:能檢測2個隨機錯誤,能糾正1個隨機錯誤。

結(jié)論：1、最小距離為dmin的(n,k)分組碼，能檢測出dmin－1個差錯。2、最小距離為dmin的(n,k)分組碼，能糾正t=INI[(dmin-1)/2]個差錯。3、糾錯能力總小于檢錯能力。注意：上面是分組碼單獨考慮檢錯或糾錯的情況。碼距與檢糾錯能力/檢糾錯能力同時考慮檢錯和糾錯結(jié)論：若最小距離為dmin的碼同時能檢ed個、糾ec個差錯，則必有ed+ec≤dmin-1

及ec≤ed碼距與檢糾錯能力糾錯分組碼中的兩個重要參數(shù)編碼效率:R=k/n碼C最小距離:dmin

糾錯碼的基本任務(wù)是構(gòu)造出當R一定,使得dmin

盡可能大的碼;dmin

一定,R盡可能高的碼。

9.2線性分組碼9.2.1基本概念9.2.2近世代數(shù)初步9.2.3生成矩陣與校驗矩陣9.2.4伴隨式與譯碼基本概念模運算(對于整數(shù))同余

a=b(modm):a除以m與b除以m(m>1)的余數(shù)相同，或稱為a和b對于模m同余。最小非負剩余:a=r(modm);0≤r<m;r為模m最小非負剩余。模m運算:a,b∈{0,1,2,…,m-1}，r為最小非負剩余，將a+b=r(modm),a×b=r(modm)記為這種求a+b和a×b的模m最小非負剩余稱為模m的加法運算和模m的乘法運算。為了簡單起見,以后將運算符號簡記為+和×?；靖拍?模運算模2運算(二進制)

運算法則1+1=0,1+0=0+1=1,1+1+1=1,1+1+1+1=0,…1×0=0,0×1=0,0×0=0,1×1=10-1=1,1-0=1,1-1=0+01001110×01000101基本概念/模運算模q運算(q進制)例:模3運算+012001211202201×012000010122021基本概念線性分組碼碼字和：設(shè)Ci=(ci1,ci2,…,cin),Cj=(cj1,cj2,…,cjn)是二元碼C的兩個碼字,則Ci

與Cj

的和為Ci

與Cj對應(yīng)碼元的模2運算;若Cs=(cs1,cs2,…,csn)且Cs=Ci+Cj即csr=cir+cjr(r=1,2,…,n)

。線性分組碼：設(shè)(n,k)分組碼C中的任意兩個碼字滿足以下兩個條件：C中有全0碼元的碼字;C中的任意兩個碼字和仍為碼C的碼字;則分組碼C稱為(n,k)線性分組碼。推論：線性分組碼任意兩個以上碼字的和仍為碼C的碼字。基本概念系統(tǒng)碼若信息組m的k個碼元以整體不變的形式,放在碼字的任意位置中,該碼為系統(tǒng)碼。否則稱為非系統(tǒng)碼。系統(tǒng)碼通常如下圖將信息組放在碼字的最左邊或最右邊。k位信息位n-k位校驗位n-k位校驗位k位信息位基本概念碼字的重量定義：(n,k)碼C的一個碼字Ci中非零碼元的個數(shù)稱為碼字Ci

的漢明重量

,簡稱碼重

,記為W(Ci)。定義：(n,k)碼C中所有非零碼字的漢明重量的最小值稱為碼C的最小漢明重量

,或碼C最小重量，記為Wmin。推論：設(shè)Ci,Cj為二元分組碼C的任意兩個碼字,則W(Ci+Cj)=d(Ci,Cj)。定理：二元(n,k)線性分組碼C的最小距離等于其最小重量?；靖拍罾涸嚇?gòu)造(5,2)線性分組碼,且dmin=3

信息組m：00011011

0000000001000100001100100001010011000111010000100101010010110110001101

01110

01111100001000110010100111010010101

10110

10111

1100011001

11010

11011

11100

11101

11110

111111組2組3組4組5組6組7組8組9組000000000000000000000000000000000000000000000010110101101011011010110101101011100111001110101011011010111100111011010111100111010110111111101110111100111101101111010111011100111001近世代數(shù)學(xué)初步群的概念定義1：G是一個非空集合，*是G中的一個代數(shù)運算，若1、封閉性：a,b∈G,有a*b∈G；2、結(jié)合律：a,b,c∈G,有(a*b)*c=a*(b*c)；3、存在單位元素e∈G,a∈G,有e*a=a*e=a；4、a∈G,存在逆元素a-1∈G,有a-1*a=a-1*a=e；5、交換律：a,b∈G,有a*b=b*a。如果這種運算*滿足：條件1,2,3,4則G稱對代數(shù)運算為一個群，或稱G為一個非交換群；條件1,2,3,4,5則稱G為一個交換群或Abel群。注意：上面的“*”代表某一種運算符號。近世代數(shù)學(xué)初步/群的概念若運算*是普通的加法“+”,則群稱為加群。若運算*是普通的乘法“×”,則群稱為乘群。定義2：若群G僅有有限個原素則稱為有限群;否則為無限群。無限群的例子例1：整數(shù)集對加法構(gòu)成Abel群，對乘法不是群。例2：有理數(shù)、實數(shù)、復(fù)數(shù)集對加法構(gòu)成Abel群,不含0的有理數(shù)、實數(shù)、復(fù)數(shù)集對乘法構(gòu)成Abel群。有限群的例子例1：數(shù)0對加法構(gòu)成群,數(shù)1對乘法構(gòu)成群.例2：集合{0,1,2,…,m-1}對模m加法運算構(gòu)成Abel群，對乘法不是群。近世代數(shù)學(xué)初步域的概念定義1：F是一個非空集合，對于F的任意兩個元素a和b，定義集合元素的加法運算,記作a＋b;乘法運算，記作ab;且有如下規(guī)則：加法運算1、a,b∈F,有a＋b∈F;2、a,b∈F,有a＋b=b＋a;3、a，b，c∈F,有(a＋b)＋c=a＋(b＋c);4、存在0∈F,a∈F,有a＋0=a；5、a∈F,存在-a∈F,有a＋(-a)=0;近世代數(shù)學(xué)初步/域的概念乘法運算1、a,b∈F,有ab∈F；2、a,b∈F,有ab=ba；3、a，b，c∈F,有(ab)c=a(bc)；4、存在e∈F,a∈F,有ae=a；5、a∈F，且a≠0,存在a-1∈F,有aa-1=e；乘法對加法的分配律：若a,b,c∈F,有a(b＋c)=ab＋ac以上運算規(guī)則都成立，則稱F對于所規(guī)定的加法運算和乘法運算是一個域。近世代數(shù)學(xué)初步/域的概念定義2：設(shè)F是一個域,如果F中的元素個數(shù)無限,則F稱為無限域。如果F中的元素個數(shù)有限,則F稱為有限域，也稱為迦羅華域，記作GF(q)。每個域必須有一個零元和一個單位元，最簡單的就是二元域GF(2)。無限域的例子例：有理數(shù)、實數(shù)、復(fù)數(shù)集對加法,乘法構(gòu)成域。有限域的例子例：集合{0,1,2,…,m-1}對模m加法,乘法運算構(gòu)成域。生成矩陣與校驗矩陣生成矩陣對于二進制線性分組碼，編碼運算可以用矩陣形式表示：

G稱為該碼的生成矩陣，是k×n(k行n列)矩陣：生成矩陣與校驗矩陣/生成矩陣例：試構(gòu)造(5,2)線性分組碼,且dmin=3，m=(m1m2)=(00),(01),(10),(11)。生成矩陣為：Ci=(m1m2m1m2m1+m2)(00)→(00000)(01)→(01011)(10)→(10101)(11)→(11110)生成矩陣與校驗矩陣/生成矩陣系統(tǒng)碼：(n,k)碼的任何生成矩陣G都可以通過行運算（以及列置換）簡化成“系統(tǒng)形式”：編碼時，信息組m乘以這種系統(tǒng)形式的生成矩陣G生成的(n,k)碼，稱為系統(tǒng)碼。生成矩陣如不具備式所示的系統(tǒng)形式，則該碼叫非系統(tǒng)碼。系統(tǒng)碼特點：前k位等于把信息組原封不動的搬到碼字的前k位；其余的n-k位叫冗余比特或一致校驗位，是前k個信息位的線性組合。生成矩陣與校驗矩陣/生成矩陣生成矩陣的特點生成矩陣不是唯一的;生成矩陣的行矢量均為線性分組碼的碼字;生成矩陣的行矢量是模2運算下線性無關(guān);線性分組碼任一碼字是行矢量模2運算下的線性組合。生成矩陣與校驗矩陣/生成矩陣如何獲得生成矩陣?例：試構(gòu)造(7,4)線性分組碼,且dmin=3。生成矩陣生成的線性分組碼要有盡可能大的dmin；生成矩陣的行矢量中的“1”的個數(shù)≥dmin

；生成矩陣各行矢量(碼字)的對應(yīng)元素不相同的個數(shù)≥dmin。生成矩陣與校驗矩陣校驗矩陣(n,k)線性分組碼為系統(tǒng)碼

,則碼字有(c1c2…ck

ck+1…cn)=(m1m2…mk

ck+1…cn)由生成矩陣G生成的碼字(c1c2…ck

ck+1…cn)=(m1m2…mk

)G=(m1m2…mk

)[Ik

Pk×(n-k)]碼字的校驗位(

ck+1…cn)=(m1m2…mk

)

Pk×(n-k)=(c1c2…ck

)Pk×(n-k)(c1c2…ck

)Pk×(n-k)-(

ck+1…cn)=01×(n-k)(c1c2…ck

)Pk×(n-k)+(

ck+1…cn)I(n-k)=01×(n-k)生成矩陣與校驗矩陣/校驗矩陣一致校驗矩陣H(簡稱校驗矩陣)H=[PTI(n-k)](n-k)×n當系統(tǒng)碼生成矩陣G確定后,校驗矩陣H由生成矩陣中的分塊矩陣Pk×(n-k)確定。由生成矩陣G生成的任一碼字Ci

均滿足下式,不是G生成碼字則不滿足下式CiHT=01×(n-k)

或HCiT=0(n-k)×1因此,校驗矩陣H可以判斷是否為碼字。生成矩陣與校驗矩陣/校驗矩陣例：考慮一個(7,4)碼，其生成矩陣是(1)對于信息組m=(1011)，編出的碼字是什么？(2)若接收到一個7位碼r=(1001101)，它是否是碼字？生成矩陣與校驗矩陣/校驗矩陣/例解：(1)設(shè)輸入4比特信息組m=(m1,m2,m3,m4)，碼字為Ci=(ci1ci2ci3ci4ci5ci6ci7)，由Ci=mG得Ci=(m1m2m3m4ci5ci6ci7)ci5=m1+m2+m3=0ci6=m2+m3+m4=0ci7=m1+m2+m4=0于是碼字C=(1011000)生成矩陣與校驗矩陣/校驗矩陣/例(2)H矩陣判斷rHT是否等于0若r是某個碼字C，必有rHT=0；若rHT≠0，則r必定不是碼字。計算得rHT≠0，所以r不是碼字。伴隨式與譯碼差錯圖案線性分組碼C的任一碼字Ci=(ci1,ci2,…,cin)經(jīng)信道傳輸后,接收到字R=(r1,r2,…,rn);令E=R-Ci=(r1-ci1,r2-ci2,…,rn-cin);這里稱E為差錯圖案。根據(jù)模2運算的性質(zhì),E=R+Ci

信道譯碼器碼字Ci接收碼字RCi的估值干擾伴隨式與譯碼/差錯圖案E=0則接收字R是碼C的一碼字;否則，不是碼C的碼字。對于二元(n,k)碼,差錯圖案E的分量中“1”的個數(shù)即為接收字R差錯的個數(shù)。差錯圖案出現(xiàn)t個差錯的圖案個數(shù)Cnt。伴隨式與譯碼伴隨式根據(jù)CiHT=01×(n-k)及R=Ci+E有RHT=(Ci+E)HT=CiHT+EHT=EHT

令S=RHT或S=EHT;這里S=(s1,s2,…,sn-k)這里稱S為伴隨式。伴隨式S僅與接收字R或差錯圖案E有關(guān),與碼字Ci

無關(guān)。由于伴隨式S是n-k維矢量,故不同S的個數(shù)只有2n-k

個；而接收字R或差錯圖案E有2n

個。因此,不同的接收字R或差錯圖案E有相同的伴隨式S。伴隨式與譯碼線性分組碼的譯碼原理生成矩陣G或校驗矩陣H確定后,就可以解決編碼問題，碼字經(jīng)過信道傳輸后,接收端獲得的只有R,而Ci

未知的，因此E也是未知的。如何根據(jù)H和R進行譯碼？伴隨式與譯碼/譯碼原理如果接收字無差錯,則R=Ci,則S=RHT=0；如果接收字有差錯，當差錯<dmin

時,則S=RHT≠0。當碼字Ci

錯為另一個碼字時,則S=RHT=0。如果接收到字R,計算S=RHT。如果S≠0,則接收字有差錯;如果S=0,不能肯定接收字無差錯;在有擾信道情況下,找到一個絕對無錯的譯碼方案是不可能的,只能選擇一種譯碼錯誤概率最小的譯碼方案。無論S≠0或S=0,均按最小距離原理譯碼。伴隨式與譯碼/譯碼原理理論根據(jù)：若BSC信道的差錯概率是p(p<<1),碼字的長度為n，則由上表中可以看出：差錯位數(shù)12…nW(E)12…n出現(xiàn)概率p(1-p)n-1p2(1-p)n-2…pn伴隨式與譯碼/譯碼原理出現(xiàn)差錯位數(shù)越小，即差錯圖案E的重量越小，出現(xiàn)的概率就越大。也就是說S(或者Ci的估值)對應(yīng)最小重量E的可能性最大。由于E=R+C，所以E的重量最小就等于d(R，C)最小。概率譯碼實際上體現(xiàn)了最小距離譯碼原則，也就是最大似然譯碼。伴隨式與譯碼/譯碼步驟1、S=RHT→S2、EHT=S→E3、C=R+E說明：在第二步中，要求差錯圖案E，就要求解線性方程組。注意：n-k個方程求解n個未知數(shù)，多個解。解線性方程組很困難，實時性很困難，怎么辦？伴隨式與譯碼/譯碼步驟解決方法——構(gòu)造標準陣列譯碼表。伴隨式S的數(shù)目是有限的2n-k個，如果n-k不太大，可以預(yù)先把不同S下的方程組解出來，把各種情況下的最大概率譯碼輸出列成一個碼表——標準陣列譯碼表。伴隨式與譯碼/譯碼步驟/標準陣列譯碼表一般構(gòu)造標準陣列譯碼表的方法與步驟：將沒有任何差錯的收碼R放在第1行，此時收碼等于發(fā)碼即R=C，差錯圖案E1=(0,0,…,0)，伴隨式S1=(0,0,…,0)。在第2行到第n+1行中填上所有重量為1的差錯圖案(共n個)。如果(1+n)<2n-k，則在下面n(n-1)/2行寫出全部帶有2個差錯的圖案E(共n(n-1)/2個)。如果(1+n+n(n-1)/2)<2n-k，再列出帶有3個差錯的圖案E，依此類推，直到放滿2n-k行，每行一個Ej，對應(yīng)一個不同的Sj。伴隨式與譯碼/譯碼步驟/標準陣列譯碼表在碼表中的第j行、第i列填入Cj+Ei。Cj表示第j個輸入碼字，所以該表共有2k列。如下表：Ej+CiEj+C2Ej+C1E2+CiE2+C2E2+C1E1+CiE1+C2E1+C1伴隨式與譯碼/譯碼步驟/標準陣列譯碼表例：某一個(5,2)系統(tǒng)線性碼的生成矩陣是設(shè)收碼是R=(10101)，請先構(gòu)造該碼的標準陣列譯碼表，然后譯出發(fā)碼的估值C。解：(1)構(gòu)造標準陣列譯碼表信息組m=(00),(01),(10),(11)。①根據(jù)公式C=mG可得到四個可用碼字：C1=(00000),C2=(01101),C3=(10111),C4=(11010)伴隨式與譯碼/譯碼步驟/標準陣列譯碼表/例②求校驗矩陣H③根據(jù)S=EHT可得到④根據(jù)概率譯碼的規(guī)則選擇合適的差錯圖案E伴隨式有23=8種組合，而差錯圖案中，無差錯的有1種，1個差錯的5種，2個差錯的有10種。伴隨式與譯碼/譯碼步驟/標準陣列譯碼表/例要選擇8個重量最輕的差錯圖案E與8個伴隨式相對應(yīng)。選擇方法是：先選擇1種無差錯的圖案和5種有1個差錯的圖案，再從10種有2個差錯的圖案中選擇2個。E5=00010S5=010E6=00001S6=001E4=00100S4=100E3=01000S3=101E2=10000S2=111E1=00000S1=000差錯圖案E伴隨式S先將無差錯和只有1個差錯的6種圖案代入表達式，解得對應(yīng)的伴隨式，如右表所示：從表中可以看出，剩下的兩個伴隨式為：S7=(011)，S8=(110)伴隨式與譯碼/譯碼步驟/標準陣列譯碼表/例從公式可以算出，伴隨式S7(011)所對應(yīng)的差錯圖案有(00011),(10100),(01110),(11001)。上述四個差錯圖案中，(00011)和(10100)并列重量最輕，任選其中一個，例如S7=(10100)。從公式可以算出，伴隨式S8(110)所對應(yīng)的差錯圖案有(11100),(00110),(01011),(10001)。上述四個差錯圖案中，(00110)和(10001)并列重量最輕，任選其中一個，例如S8=(10001)。伴隨式與譯碼/譯碼步驟/標準陣列譯碼表/例⑤根據(jù)伴隨式和與其對應(yīng)的差錯圖案填寫標準陣列譯碼表：S1=000E1+C1=00000C2=01101C3=10111C4=11010S2=111E2=10000111010011101010S3=101E3=01000001011111110010S4=100E4=00100010011001111110S5=010E5=00010011111010111000S6=001E6=00001011001011011011S7=011E7=10100110010001101110S8=110E8=10001111000011001011陪集陪集首子集子集頭伴隨式與譯碼/譯碼步驟/標準陣列譯碼表/例(2)對于收碼R=(10101)，可有以下三種譯碼方法：①直接搜索碼表，查得(10101)所在的子集頭是(10111)，因此譯碼輸出為(10111)。②可以先求出伴隨式RHT=(10101)HT=(010)=S5，在搜索碼表的第5行找到(10101)，最后找到子集頭是(10111)，即為譯碼輸出碼字。③先求出伴隨式RHT=(10101)HT=(010)=S5，再在表中查出對應(yīng)的差錯圖案E5=(00010)，通過計算得到碼字C=R+E5=(10101)+(00010)=(10111)。伴隨式與譯碼/譯碼步驟/標準陣列譯碼表/例小結(jié)：(1)建立標準陣列譯碼表，實際上就是把最有可能產(chǎn)生差錯的碼字出現(xiàn)差錯的可能情況全部列出來，供譯碼時直接查表。(2)可以看出該(5,2)系統(tǒng)線性碼的碼字dmin=3，糾錯能力t=1，即譯碼表的最后兩行的差錯圖案都是有2個錯誤的，超出了分組碼的糾錯能力，譯碼不可靠。(3)譯碼表的最后兩行，差錯圖案的選擇不是唯一的，就可能導(dǎo)致了譯碼的不可靠性。9.3循環(huán)碼9.3.1GF(2)域上的多項式9.3.2多項式表示9.3.3生成多項式9.3.4生成矩陣循環(huán)碼循環(huán)碼是線性分組碼的一個子集,循環(huán)碼有更好的代數(shù)結(jié)構(gòu),其編碼器和譯碼器可實現(xiàn)性好。循環(huán)碼的數(shù)學(xué)基礎(chǔ)主要是近世代數(shù)。碼字的循環(huán)移位左循環(huán)移位右循環(huán)移位

(1011000)→(0110001)(1011000)→(0101100)

移位1次移位1次以后所指的碼字循環(huán)移位均為左循環(huán)移位，簡稱循環(huán)移位，字長為n的碼字循環(huán)移位n次后又回復(fù)到原碼字。定義：一個(n,k)線性分組碼C,若其任一碼字的一個循環(huán)移位仍然是碼C的一個碼字,則碼C是一個循環(huán)碼。循環(huán)碼例：(7,4)循環(huán)碼按信息位排序

1

0000000020001011

(生成子序列)13001011024010110055101100011601100016711000101281000101890011101(序列2+序列3)3100111010711111010014121101001131310100111014010011141510011109161111111(序列2+序列11)15GF(2)域上的多項式

f(x)=a0xn

+a1xn-1+a2n-2xn-2+…an-1

x

+

an，其中ai∈{0,1},i=0,1,…,n。則稱

f(x)

為GF(2)域上的多項式。GF(2)域上的多項式的運算規(guī)則f1(x)與f2(x)的加,減,乘運算與實數(shù)域上多項式運算規(guī)則相同，但其系數(shù)按模2運算。f1(x)與f2(x)的加,減,乘仍為GF(2)域上的多項式。注意：f(x)+f(x)=0GF(2)域上的多項式余式設(shè)a(x),m(x)為GF(2)域上的多項式，若a(x)=b(x)m(x)+r(x)r(x)的次數(shù)小于m(x)的次數(shù)，則稱r(x)為a(x)除以m(x)的余式

,m(x)稱模多項式?；蛴洖椋篴(x)=r(x)mod

m(x)任意a(x)對于模m(x)的余式r(x)的集合稱多項式剩余環(huán)。GF(2)域上的多項式/求余式求余式基本方法是長除法。例：用長除法求模xn+1的余式。x6+x3+x2+1modx4+1=x3+1GF(2)域上的多項式/求余式x8+x7+x5+x4+x2+x+1modx4+1=x3+x2+1多項式表示碼多項式對于碼長為n的二元循環(huán)碼的任一碼字，都可以用GF(2)域上的一個≤(n-1)次多項式表示。為了書寫方便，以后將碼C中的任意碼字Ci

簡寫為C。定義：碼長為n的碼字C=(cn-1cn-2…c1c0)用如下n-1次多項式表示，則C(x)稱循環(huán)碼的碼多項式。多項式表示/碼多項式從定義可以看出：碼多項式C(x)的系數(shù)與碼字C的碼元是一一對應(yīng)的，因此碼多項式C(x)與碼字C也是一一對應(yīng)的。循環(huán)碼可以用一組碼多項式描述。例：(0101100)→C(x)=x5+x3+x2

(1101001)→C(x)=x6+x5+x3+1

多項式表示碼字循環(huán)移位的碼多項式描述碼字的循環(huán)移位可表示為與之對應(yīng)的多項式變化為多項式表示/碼字循環(huán)移位通過比較循環(huán)移位前后的形式和結(jié)果，可用多項式的運算來表示循環(huán)移位：多項式表示碼多項式的性質(zhì)性質(zhì)1：循環(huán)碼C任意兩個或兩個以上的碼多項式之和仍是循環(huán)碼C的碼多項式。定義：循環(huán)碼C的次數(shù)最低的非零碼多項式記為g(x)。性質(zhì)2：循環(huán)碼C的碼多項式g(x)是唯一的。性質(zhì)3：循環(huán)碼C的碼多項式g(x)的常數(shù)項是1。性質(zhì)4：多項式C(x)的次數(shù)≤(n-1)次,C(x)是碼長為n的循環(huán)碼C的碼多項式的充要條件為C(x)=b(x)g(x)。這里b(x)=(b1xr-1+b2

xr-2+…+br)。

生成多項式以上性質(zhì)4表明一個循環(huán)碼可由次數(shù)最底的非零碼多項式g(x)生成。對于(n,k)循環(huán)碼,其信息位有k位m=(m1,m2,…,mk)，若有一個上述(n-k)次的g(x),將信息位表示為k-1次多項式,m(x)=mk-1

xk-1+mk-2

xk-

2+

…

+

m0

，則C(x)=m(x)g(x)=mk-1xk-1g(x)

+mk-2

xk-2g(x)+…+m0g(x)上式還可以寫成顯然xk-1g(x)

,

xk-2g(x),

…

,

g(x)是線性無關(guān)的,且其線性組合有2k

個次數(shù)≤(n-1)次的碼多項式C(x),其中任意兩個碼多項式仍然是2k個碼多項式中之一。(線性特性)這里將g(x)

稱為(n,k)循環(huán)碼的生成多項式。生成多項式兩個定理：定理1：(n,k)循環(huán)碼的生成多項式g(x)是xn

+1因式。定理2：若g(x)是n–k次多項式,且是xn

+1因式,則g(x)生成一個(n,k)循環(huán)碼。生成多項式構(gòu)造(n,k)循環(huán)碼的步驟①對(xn+1)作因式分解，找出其中(n-k)次因式。②以該(n-k)次因式為生成多項式g(x)，與不高于(k-1)次的信息多項式m(x)相乘，即得到碼多項式C(x)=m(x)g(x)，C(x)的次數(shù)不高于(k-1)+(n-k)=(n-1)次。說明：xn+1的因式如何求,是數(shù)學(xué)領(lǐng)域的一個問題。生成多項式例：研究一個長度n=7的循環(huán)碼的構(gòu)造方法x7+1

=(x+1

)(

x3+x2+1

)(

x3+x+1

)

1次因子有1個:x+1

3次因子有2個:x3+x2+1或x3+x+1

4次因子有2個:x4+x2+x+1

或x4+x3+x2+16次因子有1個:x6+x5+x4+x3+x2+x+1

∴生成多項式g(x)的n–k有6種選擇。生成多項式例：x10+1=(x+1)(x+1)(x4+x3+x2+x+1)(x4+x3+x2+x+1)x+1x2+1

x4+

x3+x2+x+1x5+1

x6+

x5+x+1x8+x6+x4+x2+1x9+x8+x7+x6+x5+x4+x3+x2+x+1因子有1次,2次,4次,5次,6次,8次,9次生成多項式例：(7,4)循環(huán)碼生成多項式g(x)可選n-k=7-4=3次多項式，即(x3+x2+1)或(x3+x+1)。選擇g(x)=(x3+x2+1)，設(shè)信息多項式為m(x)=m3x3+m2x2+m1x+m0循環(huán)編碼后所得到的碼多項式為若m=(0110)，則代入上式得到生成多項式在GF(2)中，(m3m2m1m0)共有16種組合，對應(yīng)16個碼字，由上面公式可得到(7,4)循環(huán)碼的碼字如下表：信息比特碼字信息比特碼字信息比特碼字000100011010011001011100000000000010001101001100101110101111111101000110100110010111001000110100001010111001110110100011010111001001110100011100111001011110100011011111001010可以看出：整個碼集有4組碼字循環(huán)。生成多項式幾個相關(guān)性質(zhì)一般情況下，xn+1=h(x)g(x)①最小多項式：在GF(2)上不能再分解的因式叫最小多項式。生成多項式g(x)可以是最小多項式，也可以不是最小多項式。②如果g(x)代表(n,k)循環(huán)碼的生成多項式，則h(x)代表(n,k)循環(huán)碼的一致校驗多項式,其階次為k。h(x)的校驗作用：任何碼多項式C(x)與h(x)的模xn+1乘積一定等于0，而非碼多項式與h(x)的模xn+1乘積一定不等于0

。即生成多項式③g(x)和h(x)地位同等。可以用g(x)生成一個循環(huán)碼，也可以用h(x)生成一個循環(huán)碼，此時h(x)用作生成多項式，而g(x)用作一致校驗多項式。由g(x)生成的(n,k)循環(huán)碼和由h(x)生成的(n,n-k)循環(huán)碼互為對偶碼。④反多項式設(shè)f(x)是k次多項式，則f(x)的反多項式定義為結(jié)論：在二元域中，若f(x)是xn+1的一個因式，那么它的反多項式也是xn+1的一個因式。生成矩陣當循環(huán)碼的生成多項式g(x)給定后，我們可用如下方法得到生成矩陣G。我們?nèi)(x)本身和g(x)移位k-1次所得的k-1個碼字作為k個基底，從而得到循環(huán)碼的生成矩陣。若循環(huán)碼生成多項式g(x)為g(x)左移k-1次得到生成矩陣寫成矩陣形式為對于二進制而言，上面矩陣中的參數(shù)gi∈{0,1}，i=1,2,…,n-k-1。注意：通過這種方法得到的生成矩陣不是系統(tǒng)形式。生成矩陣例：g(x)=(x3+x2+1)，則生成矩陣G為g(x)所對應(yīng)的矢量xg(x)所對應(yīng)的矢量x3g(x)所對應(yīng)的矢量x2g(x)所對應(yīng)的矢量結(jié)論：生成矩陣G的k重列矢量是由g(x)所對應(yīng)的矢量和其循環(huán)左移k-1次得到的k-1重列矢量組成。生成矩陣系統(tǒng)循環(huán)碼設(shè)信息位多項式為m(x)=mk-1

xk-1+mk-2

xk-

2+…+m0

系統(tǒng)碼的碼多項式為C(x)=xn-km(x)+r(x)，r(x)是次數(shù)小于(n-k)的多項式。若C(x)是(n,