循環(huán)碼與近世代數(shù)補(bǔ)充

1、第四講循環(huán)碼與近世代數(shù)補(bǔ)充回顧 編碼設(shè)計(jì)就是在n維有限域空間中找到抽取2k個(gè)許用碼字的方法，方法數(shù)非常巨大 為了簡(jiǎn)化好碼搜索、便于分析及簡(jiǎn)化譯碼方法，引入了線性約束，即只研究線性分組碼 但只有線性分組約束還不夠，例如對(duì)碼距的分析仍很復(fù)雜，譯碼算法隨n-k指數(shù)增漲 因此需要引入進(jìn)一步的約束循環(huán)碼一種特殊的線性分組碼 循環(huán)算子L：對(duì)n重碼字A=(an-1, an-2, an-3, , a2, a1, a0)，有B = L(A) = (bn-1, bn-2, bn-3, , b2, b1, b0) = (an-2, an-3, , a2, a1, a0, an-1) 循環(huán)特性：對(duì)任意許用碼字C，則L

2、(C)也是許用碼字 循環(huán)碼： C及它的任意次循環(huán)得到的碼字之間任意線性組合都是許用碼字。 注意：這里提到線性組合，就意味著要定義符號(hào)間的加法和乘法，為了簡(jiǎn)化分析，我們只考慮碼字序列中的符號(hào)只取自于有限域的情況（定義了兩種運(yùn)算的符號(hào)集不一定要求是有限域）。循環(huán)碼的生成元 顯然，任取一個(gè)碼字，集合C, L(C), L2(C), L3(C), .及其線性組合，構(gòu)成了一個(gè)線性循環(huán)子碼，C就稱為這個(gè)線性循環(huán)子碼的生成元 問(wèn)題：能否用生成元完全描述循環(huán)碼？滿足什么樣條件的循環(huán)碼可以有較好的距離特性？多項(xiàng)式的引入 如果將碼字描述成n階多項(xiàng)式的形式，A(x)= an-1xn-1+an-2xn-2 +an-3x

3、n-3+ +a2x2+a1,x+a0，則循環(huán)算子就可以描述為L(zhǎng)(A(x)=xA(x) mod (xn-1) 便于描述：對(duì)于循環(huán)碼定義，給定生成元所對(duì)應(yīng)的多項(xiàng)式為A(x)，則對(duì)任何一個(gè)多項(xiàng)式D(x)，有D(x)A(x) mod (xn-1)為許用碼字多項(xiàng)式的引入（續(xù)） 這里并沒(méi)有限定D(x)的冪次，但可以肯定的一點(diǎn)是不同的D(x)A(x) mod (xn-1)是有限的，因?yàn)閮绱涡∮趎的有限域上的多項(xiàng)式是有限的。 許用碼字個(gè)數(shù)由A(x)決定，這也決定了碼集的冗余度和糾錯(cuò)能力，什么樣的A(x)可以得到什么樣的冗余度？哪些A(x)是等價(jià)的？這些都是下面要研究的多項(xiàng)式的引入（續(xù)） 便于分析 當(dāng)A(x)與

4、(xn-1)的最高次公因式為g(x)時(shí)，A(x)=g(x)b(x)， (xn-1)=g(x)h(x)，當(dāng)D(x)=q(x)h(x)+r(x)，r(x)冪次小于h(x)的冪次時(shí)，有：D(x)*A(x)mod (xn-1) =q(x)h(x)g(x)b(x)+r(x)A(x)mod (xn-1) =r(x)A(x)mod (xn-1) 。也就是說(shuō)對(duì)冪次高于h(x)冪次減1的D(x)，所得的碼多項(xiàng)式必與冪次低于h(x)的多項(xiàng)次所生成的碼相同。 即許用碼字個(gè)數(shù)不大于冪次低于h(x)的多項(xiàng)式個(gè)數(shù)。多項(xiàng)式的引入 而如果有兩個(gè)冪次小于h(x)的多項(xiàng)式r1(x)和r2(x)，它們與A(x)作模(xn-1) 相

5、乘有相同的結(jié)果，則有r1(x)- r1(x)g(x)b(x) =q(x)g(x)h(x) = r1(x)- r2(x)b(x)modh(x)=0 = r1(x)- r2(x) =0。 因此許用碼字個(gè)數(shù)必等于冪次低于h(x)的多項(xiàng)式個(gè)數(shù)。近世代數(shù)的引入 事實(shí)上，用多項(xiàng)式表示的循環(huán)碼可以充分利用近世代數(shù)的知識(shí)，形成一套較完整的描述和研究方法 為了深入了解循環(huán)碼的原理與研究方法，有必要補(bǔ)充一些近世代數(shù)特別是有限域的知識(shí)。下面將不加證明地引入一系列重要的定義和定理，具體證明和相關(guān)推論可參考有關(guān)書(shū)籍代數(shù)基礎(chǔ) 群 子群 陪集 環(huán) 子環(huán) 理想：如果I是R的子環(huán)，在R中任取r，在I中任取a，均有ar=ra屬于

6、I，則I為R的一個(gè)理想環(huán)（續(xù)） 主理想：可換環(huán)中，I(a)=ra+na | rR, nZ為R的一個(gè)主理想（其中na表示n個(gè)a相加）。a為該主理想的生成元。 多項(xiàng)式剩余類環(huán)：以一個(gè)多項(xiàng)式為模的剩余類環(huán) 以f(x)為生成元，生成理想If(x)，以此理想把Fp(x)（GF(p)上的多項(xiàng)式全體）的陪集構(gòu)成模f(x)的剩余類環(huán)（乘法為模f(x)的多項(xiàng)式乘法）域的乘法結(jié)構(gòu) 循環(huán)群，據(jù)群所定義的加法，對(duì)某一個(gè)元（生成元）任意次重復(fù)運(yùn)算得到的群（包括零元）。（在域中我們所考慮的循環(huán)群指的是域中的乘法群） 元素的級(jí)數(shù)：對(duì)元素a，滿足na=0的最小的非0的n即為a的級(jí)。 有限循環(huán)群的階數(shù)：生成元的級(jí)域的乘法結(jié)構(gòu)（

7、續(xù)） 階為n的循環(huán)群中每個(gè)元素的級(jí)都是n的因子，因此當(dāng)n為素?cái)?shù)時(shí)任何非零元的級(jí)都是n，即都是生成元 域的乘法群必為某一個(gè)元素生成的循環(huán)群，即q元域中必能找到一個(gè)，其階為q-1。即所有有限域元素都能表示成生成元的冪次的形式，此時(shí)的生成元稱為本原元。因此當(dāng)q-1為素?cái)?shù)時(shí)，任何非零元都是生成元和本原元域的加法結(jié)構(gòu) 域的特征：滿足ne=0的最小n值為域的特征，注意這里e為乘法單位元，0為域的零元，n取自正整數(shù) 元素的周期：對(duì)域中元素a，滿足na=0的最小n值為a的周期。（注意對(duì)于域而言，在加法上用周期，在乘法上用級(jí)）域的加法結(jié)構(gòu)（續(xù)） 域中非0元的周期都相同，且與域的特征相等 有限域的域整數(shù)：即單位元

8、的n次相加構(gòu)成的素子域，它與模p的整數(shù)域GF(p)同構(gòu) GP(p)為GF(pm)的基域，GF(pm)為GF(p)的擴(kuò)域域的多項(xiàng)式結(jié)構(gòu) 對(duì)GF(p)上的多項(xiàng)式f(x)，若有一個(gè)根為w，則 也是該多項(xiàng)式的根，據(jù)此可望寫(xiě)出其一組根，甚至全部根 而若wGF(pm)，則有 =w。當(dāng)w的級(jí)為pm -1時(shí)，w, wp, , , 構(gòu)成f(x)的共軛根系。共軛根系中的各根均不相等npw2pw1mpwmpw域的多項(xiàng)式結(jié)構(gòu)（續(xù)） 系數(shù)取自GF(p)的，以w為根的所有首一多項(xiàng)式中，次數(shù)最低的稱為w的最小多項(xiàng)式m(x)，w的最小多項(xiàng)式的次數(shù)m稱為w的次數(shù)，稱w為m次域元素 m(x)在GF(p)上不可約 若w也是f(x)

9、的根，則m(x)可整除f(x) 若w取自GF(pm)，則有m(x)可整除xxmp最小多項(xiàng)式與本原多項(xiàng)式 m次域元素的最小多項(xiàng)式，在GF(p)上不可約，但在GF(pm)上可以完全分解成一次因式之積。 在GF(pm)中，以本原元為根的最小多項(xiàng)式稱為該域的本原多項(xiàng)式 GF(pm)的本原多項(xiàng)式的根級(jí)數(shù)均為pm-1，且本原多項(xiàng)式必為m次多項(xiàng)式最小多項(xiàng)式的根 w為最小多項(xiàng)式的根，若w是特征為p的有限域F上的m次元素，則所有小于m次的多項(xiàng)式f(x)將w代入，得到的集合構(gòu)成pm階子域。（以最小多項(xiàng)式為模） 對(duì)于m次元素w，有1,w,w2,wm-1線性無(wú)關(guān)，可作為域空間的基多項(xiàng)式的周期 多項(xiàng)式的周期，對(duì)多項(xiàng)式f(x)，它所能整除的xL-1中最小的L值稱為f(x)的周期。 對(duì)GF(p)上的m次本原多項(xiàng)式f(x)，其周期為pm-1 有限域的階（元素個(gè)數(shù)）必為其特征（素子域的階）之冪 GF(p)上的d次即約多項(xiàng)式f(x