第五章循環(huán)碼

第五章循環(huán)碼循環(huán)碼的數(shù)學(xué)概念循環(huán)碼：若線性碼C=[n,k]滿足（c0,c1,...,cn-2,cn-1）C:（cn-1,c0,c1,...,cn-2）C,則稱為循環(huán)碼。數(shù)學(xué)上,碼字循環(huán)是碼多項(xiàng)式乘x(左循環(huán))或x-1(右循環(huán))取模xn-1的余式.循環(huán)碼的數(shù)學(xué)定義是模xn-1剩余類環(huán)中由一個(gè)n-k次首一多項(xiàng)式g(x)生成的主理想（定理1,2）.可證（定理3）,g(x)|xn-1;反過(guò)來(lái),由xn-1的任一r次因式生成的模xn-1剩余類環(huán)的主理想必是一個(gè)[n,n-r]循環(huán)碼.循環(huán)碼之所以重要，是因?yàn)橹灰业絻H對(duì)某位進(jìn)行操作(如大數(shù)邏輯譯碼)的方法，就可以通過(guò)循環(huán)移位實(shí)現(xiàn)對(duì)所有的位進(jìn)行操作。注意:1) 循環(huán)碼的碼字多項(xiàng)式是g(x)的倍式摸xn-1的余式,實(shí)際上是碼字多項(xiàng)式g(x)循環(huán)移位的線性組合.0010111(x+1)g(x)1001011011100111100101100101101110001011100010111(x+1)g(x)1001011011100111100101100101101110001011100000000000000000g(x)0001101g(x)1000110110100010100010100011011010000110100001101g(x)1000110110100010100010100011011010000110101111111(x31111111(x3+x+1)g(x)002) 循環(huán)碼有可能有多個(gè)循環(huán)模式(至少有g(shù)(x)和0兩個(gè)),如下圖是由g(x)=x3+x2+1生成的循環(huán)碼.二、循環(huán)碼的校驗(yàn)矩陣H和生成矩陣G由于g(x),xg(x),...,xk-1g(x)是k個(gè)線性無(wú)關(guān)的碼字,所以生成矩陣G為G= (1)設(shè)xn-1=g(x)h(x),h(x)=稱為碼校驗(yàn)多項(xiàng)式,其反多項(xiàng)式h*(x)=，取H=, (2)可證HGT=0,所以(2)確定的H是校驗(yàn)矩陣。(1)式和(2)式確定G的H不是標(biāo)準(zhǔn)形式。系統(tǒng)碼的碼字應(yīng)有C(x)=m(x)xn-k+r(x)的形式，其中m(x)是信息多項(xiàng)式，r(x)是監(jiān)督多項(xiàng)式.因?yàn)镃(x)=m(x)xn-k+r(x)0(modg(x))，所以r(x)-m(x)xn-k(modg(x))，取mi(x)=xk-i(i=1,2,...,k),可得相應(yīng)的監(jiān)督多項(xiàng)式ri(x)-mi(x)xn-kxk-ixn-kxn-i(modg(x))(i=1,2,...,k),從而可求得構(gòu)成系統(tǒng)碼生成矩陣的k個(gè)碼字，Ci(x)=mi(x)xn-k+ri(x)(i=1,2,...,k)，因此G的標(biāo)準(zhǔn)形式為G=,其中，ri(x)-xn-i(modg(x))(i=1,2,...,k)。由G的標(biāo)準(zhǔn)形式可輕易求出H的標(biāo)準(zhǔn)形式.三、xn-1的因式分解由上面的分析可知,要構(gòu)造一個(gè)Fq上[n,k]循環(huán)碼,關(guān)鍵是要找到生成多項(xiàng)式g(x),而g(x)是xn-1的n-k次因式.因此對(duì)xn-1的因式分解是構(gòu)造循環(huán)碼的關(guān)鍵問(wèn)題.當(dāng)n=qm-1從第四章可知，在Fq的擴(kuò)展域={0，，2,...,=1}上可分解為=(x-)(x-2)......(x-),把上的元素分成不同的共軛根系(設(shè)為s個(gè)),設(shè)第k個(gè)共軛根系的共軛根為:wk,wkq,,...,,l為使=wk最小的正整數(shù)(如果q為素?cái)?shù),n為wk的階,l為q對(duì)模n的方次數(shù)),則含這個(gè)共軛根系的因子的乘積(x-wk)(x-wkq)(x-)...(x-)是Fq上的l次素多項(xiàng)式mk(x)(mk(x)是wk,wkq,,...,的最小多項(xiàng)式),因此=.特別地,當(dāng)n=2m-1,n-k=m(g(x)的次數(shù)為m)時(shí),可查表求上的m次本原多項(xiàng)式p(x),由第四章定理20(課本定理4.6.7,p144)可知,p(x)|xn-1,可以證明(參看華工出版社R.E.Blahut《差錯(cuò)控制碼的理論與實(shí)踐》，p.85),由p(x)生成的循環(huán)碼d=3,因此是一個(gè)漢明碼.當(dāng)nqm-1,但n|qm-1,可在中找階為n的元素,則生成的n階循環(huán)群含有xn-1=0的全部根.四、在擴(kuò)展域中描述和構(gòu)造循環(huán)碼在擴(kuò)展域中研究問(wèn)題往往可以幫助理解問(wèn)題和簡(jiǎn)化問(wèn)題的復(fù)雜性,在擴(kuò)展域中描述和構(gòu)造循環(huán)碼最簡(jiǎn)單的例子是把的所有非0元素組成矩陣[2...]然后把每一元素轉(zhuǎn)化為F2上的m重從而可得F2上的矩陣,它是[2m-1,2m-1-m,3]漢明碼的校驗(yàn)矩陣.Fq上的循環(huán)碼的生成多項(xiàng)式g(x)在最小分裂域上的根為1,2,...,n-k(設(shè)g(x)在上無(wú)重根,其充要條件是(n,q)=1),則Fq上n維矢重C是碼字多項(xiàng)式的充要條件是HCT=0,其中,H=(計(jì)算在上進(jìn)行),設(shè)H中的jt(j=1,...,n-k,t=1,...,n)的多項(xiàng)式表示為,用Fq上的m重(m-1m-2...)T代替jt,則H化為Fq的矩陣H,但尚不是監(jiān)督矩陣,因?yàn)镠內(nèi)可能含有線性相關(guān)的行.可證,同一共軛根系分裂出的行之間是線性相關(guān)的,所以,同一共軛根系的共軛根中,只保留其中之一即可.這樣處理后的矩陣仍可能有線性相關(guān)的行(如全0行),去掉后得到的n-kn矩陣就是監(jiān)督矩陣.五、縮短循環(huán)碼縮短循環(huán)碼是在循環(huán)碼[n,k]去掉i位信息位得到的[n-i,k-i]碼,技術(shù)上,去掉的i位信息位可看作是0.這樣縮短循環(huán)碼可認(rèn)為是循環(huán)碼的子集,從而可利用循環(huán)碼的編譯碼電路.幾何上,縮短循環(huán)碼[n-i,k-i]是循環(huán)碼[n,k]的碼空間與n-i維超平面的交集,所以碼的最小距離不會(huì)縮小,糾錯(cuò)能力不會(huì)下降.縮短循環(huán)碼的生成矩陣和監(jiān)督矩陣縮短循環(huán)碼[n-i,k-i]的生成矩陣G是循環(huán)碼[n,k]的生成矩陣G去掉前i行和前i列而成;而縮短循環(huán)碼[n-i,k-i]的監(jiān)督矩陣H是循環(huán)碼[n,k]的監(jiān)督矩陣H去掉前i列而成.六、循環(huán)碼的編碼電路Fq上的循環(huán)碼的編碼電路是如何從信息多項(xiàng)式m(x),生成碼多項(xiàng)式C(x),因此編碼電路不是構(gòu)成整個(gè)碼空間,而是對(duì)應(yīng)于信息多項(xiàng)式的qk個(gè)碼字.基于g(x)的n-k級(jí)編碼器1. 非系統(tǒng)碼:乘g(x)電路原理: C(x)m(x)g(x)(modxn-1),若m(x),k,則C(x)=m(x)g(x).因此可把m(x)作為信息多項(xiàng)式,這樣,編碼電路實(shí)際上是一個(gè)乘g(x)電路.2. 系統(tǒng)碼:除g(x)電路原理: C(x)m(x)xn-k+r(x)0(modg(x))r(x)-m(x)xn-k(modg(x)).因此可先把m(x)移動(dòng)n-k位得m(x)xn-k然后除-g(x)取余,再加上m(x)xn-k基于h(x)的k級(jí)編碼器原理: 因g(x)為首一多項(xiàng)式,h(x)=(xn-1)/g(x)亦為首一多項(xiàng)式,由(1)式可得=0因此有 cn-k-1=-(h0cn-1+h1cn-2+...+hk-1cn-k), 即由信息位cn-1...cn-k求出第一個(gè)校驗(yàn)位cn-k-1cn-k-2=-(h0cn-2+h1cn