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

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

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

個(gè)在qn個(gè)碼字中與信源符號(hào)組對(duì)應(yīng)的qk個(gè)碼字稱為許用碼字

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

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

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

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

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

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

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

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

)<dmin

時(shí),則R不是Ci

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

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

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

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

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

盡可能大的碼;dmin

一定,R盡可能高的碼。

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

a=b(modm):a除以m與b除以m(m>1)的余數(shù)相同，或稱為a和b對(duì)于模m同余。最小非負(fù)剩余:a=r(modm);0≤r<m;r為模m最小非負(fù)剩余。模m運(yùn)算:a,b∈{0,1,2,…,m-1}，r為最小非負(fù)剩余，將a+b=r(modm),a×b=r(modm)記為這種求a+b和a×b的模m最小非負(fù)剩余稱為模m的加法運(yùn)算和模m的乘法運(yùn)算。為了簡(jiǎn)單起見(jiàn),以后將運(yùn)算符號(hào)簡(jiǎn)記為+和×。基本概念/模運(yùn)算模2運(yùn)算(二進(jìn)制)

運(yùn)算法則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基本概念/模運(yùn)算模q運(yùn)算(q進(jìn)制)例:模3運(yùn)算+012001211202201×012000010122021基本概念線性分組碼碼字和：設(shè)Ci=(ci1,ci2,…,cin),Cj=(cj1,cj2,…,cjn)是二元碼C的兩個(gè)碼字,則Ci

與Cj

的和為Ci

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

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

的漢明重量

,簡(jiǎn)稱碼重

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

,或碼C最小重量，記為Wmin。推論：設(shè)Ci,Cj為二元分組碼C的任意兩個(gè)碼字,則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è)非空集合，*是G中的一個(gè)代數(shù)運(yùn)算，若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。如果這種運(yùn)算*滿足：條件1,2,3,4則G稱對(duì)代數(shù)運(yùn)算為一個(gè)群，或稱G為一個(gè)非交換群；條件1,2,3,4,5則稱G為一個(gè)交換群或Abel群。注意：上面的“*”代表某一種運(yùn)算符號(hào)。近世代數(shù)學(xué)初步/群的概念若運(yùn)算*是普通的加法“+”,則群稱為加群。若運(yùn)算*是普通的乘法“×”,則群稱為乘群。定義2：若群G僅有有限個(gè)原素則稱為有限群;否則為無(wú)限群。無(wú)限群的例子例1：整數(shù)集對(duì)加法構(gòu)成Abel群，對(duì)乘法不是群。例2：有理數(shù)、實(shí)數(shù)、復(fù)數(shù)集對(duì)加法構(gòu)成Abel群,不含0的有理數(shù)、實(shí)數(shù)、復(fù)數(shù)集對(duì)乘法構(gòu)成Abel群。有限群的例子例1：數(shù)0對(duì)加法構(gòu)成群,數(shù)1對(duì)乘法構(gòu)成群.例2：集合{0,1,2,…,m-1}對(duì)模m加法運(yùn)算構(gòu)成Abel群，對(duì)乘法不是群。近世代數(shù)學(xué)初步域的概念定義1：F是一個(gè)非空集合，對(duì)于F的任意兩個(gè)元素a和b，定義集合元素的加法運(yùn)算,記作a＋b;乘法運(yùn)算，記作ab;且有如下規(guī)則：加法運(yùn)算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é)初步/域的概念乘法運(yùn)算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；乘法對(duì)加法的分配律：若a,b,c∈F,有a(b＋c)=ab＋ac以上運(yùn)算規(guī)則都成立，則稱F對(duì)于所規(guī)定的加法運(yùn)算和乘法運(yùn)算是一個(gè)域。近世代數(shù)學(xué)初步/域的概念定義2：設(shè)F是一個(gè)域,如果F中的元素個(gè)數(shù)無(wú)限,則F稱為無(wú)限域。如果F中的元素個(gè)數(shù)有限,則F稱為有限域，也稱為迦羅華域，記作GF(q)。每個(gè)域必須有一個(gè)零元和一個(gè)單位元，最簡(jiǎn)單的就是二元域GF(2)。無(wú)限域的例子例：有理數(shù)、實(shí)數(shù)、復(fù)數(shù)集對(duì)加法,乘法構(gòu)成域。有限域的例子例：集合{0,1,2,…,m-1}對(duì)模m加法,乘法運(yùn)算構(gòu)成域。生成矩陣與校驗(yàn)矩陣生成矩陣對(duì)于二進(jìn)制線性分組碼，編碼運(yùn)算可以用矩陣形式表示：

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

；生成矩陣各行矢量(碼字)的對(duì)應(yīng)元素不相同的個(gè)數(shù)≥dmin。生成矩陣與校驗(yàn)矩陣校驗(yàn)矩陣(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)]碼字的校驗(yàn)位(

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)生成矩陣與校驗(yàn)矩陣/校驗(yàn)矩陣一致校驗(yàn)矩陣H(簡(jiǎn)稱校驗(yàn)矩陣)H=[PTI(n-k)](n-k)×n當(dāng)系統(tǒng)碼生成矩陣G確定后,校驗(yàn)矩陣H由生成矩陣中的分塊矩陣Pk×(n-k)確定。由生成矩陣G生成的任一碼字Ci

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

或HCiT=0(n-k)×1因此,校驗(yàn)矩陣H可以判斷是否為碼字。生成矩陣與校驗(yàn)矩陣/校驗(yàn)矩陣?yán)嚎紤]一個(gè)(7,4)碼，其生成矩陣是(1)對(duì)于信息組m=(1011)，編出的碼字是什么？(2)若接收到一個(gè)7位碼r=(1001101)，它是否是碼字？生成矩陣與校驗(yàn)矩陣/校驗(yàn)矩陣/例解：(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)生成矩陣與校驗(yàn)矩陣/校驗(yàn)矩陣/例(2)H矩陣判斷rHT是否等于0若r是某個(gè)碼字C，必有rHT=0；若rHT≠0，則r必定不是碼字。計(jì)算得rHT≠0，所以r不是碼字。伴隨式與譯碼差錯(cuò)圖案線性分組碼C的任一碼字Ci=(ci1,ci2,…,cin)經(jīng)信道傳輸后,接收到字R=(r1,r2,…,rn);令E=R-Ci=(r1-ci1,r2-ci2,…,rn-cin);這里稱E為差錯(cuò)圖案。根據(jù)模2運(yùn)算的性質(zhì),E=R+Ci

信道譯碼器碼字Ci接收碼字RCi的估值干擾伴隨式與譯碼/差錯(cuò)圖案E=0則接收字R是碼C的一碼字;否則，不是碼C的碼字。對(duì)于二元(n,k)碼,差錯(cuò)圖案E的分量中“1”的個(gè)數(shù)即為接收字R差錯(cuò)的個(gè)數(shù)。差錯(cuò)圖案出現(xiàn)t個(gè)差錯(cuò)的圖案?jìng)€(gè)數(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或差錯(cuò)圖案E有關(guān),與碼字Ci

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

個(gè)；而接收字R或差錯(cuò)圖案E有2n

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

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

時(shí),則S=RHT≠0。當(dāng)碼字Ci

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

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

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

1

0000000020001011

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

f(x)=a0xn

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

x

+

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

f(x)

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

,m(x)稱模多項(xiàng)式。或記為：a(x)=r(x)mod

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

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

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

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

xr-2+…+br)。

生成多項(xiàng)式以上性質(zhì)4表明一個(gè)循環(huán)碼可由次數(shù)最底的非零碼多項(xiàng)式g(x)生成。對(duì)于(n,k)循環(huán)碼,其信息位有k位m=(m1,m2,…,mk)，若有一個(gè)上述(n-k)次的g(x),將信息位表示為k-1次多項(xiàng)式,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)上式還可以寫(xiě)成顯然xk-1g(x)

,

xk-2g(x),

…

,

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

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

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

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

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

=(x+1

)(

x3+x2+1

)(

x3+x+1

)

1次因子有1個(gè):x+1

3次因子有2個(gè):x3+x2+1或x3+x+1

4次因子有2個(gè):x4+x2+x+1

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

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

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

xk-1+mk-2

xk-

2+…+m0

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