第五講——循環(huán)碼

1、第五講循環(huán)碼回顧（1） 為了簡化好碼搜索、便于分析及簡化譯碼方法，在線性運算封閉約束的基礎上，又加入了循環(huán)封閉的約束 當循環(huán)碼用多項式表示時，可以很好的利用近世代數(shù)的知識，因此介紹了一些基礎知識和概念回顧（2） 群：子群和陪集 環(huán)：子環(huán)、理想、主理想、多項式剩余類環(huán) 域的乘法結構：域的乘法群是循環(huán)群、元素的級、循環(huán)群的階、生成元，域的本原元回顧（3） 域的加法結構：域的特征、元素的周期、素子域、基域與擴域 域的多項式結構：共軛根系、w的最小多項式、本原多項式、用最小多項式根表示的域、多項式的周期 剩余類線性結合代數(shù)，當以xn-1為模時，循環(huán)子空間與理想等價，生成多項式。有限域舉例 構造一個4元

2、環(huán)：整數(shù)環(huán)中的模4剩余類環(huán) 構造一個4元域： 模4運算沒有逆 4=22，因此可以從GF(2)形成擴域 找一個GF(2)一的2次不可約多項式：f(x)=x2+x+1 找到用多項式表示的GF(22)的另兩個元素：a=x，b=x+1。（即所有低于2次的多項式） 定義GF(2)上的模f(x)運算，得到乘法表，顯然a與b互逆。 可以驗證a和b是f(x)的兩個根，構成共軛根系，顯然它們不屬于GF(2)，而屬于擴域 由于乘法群的階數(shù)22-1=3是一個素數(shù)，a和b的級都是3，因此它們都是本原元，f(x)是一個GF(2)上的本原多項式循環(huán)碼的生成多項式 （回顧）以xn-1為模的剩余類代數(shù)中，循環(huán)子空間與理想等價

3、。其生成元中次數(shù)最低的首一多項式為生成多項式 循環(huán)碼的生成多項式必為xn-1的因子，同一個循環(huán)子空間可以有多個生成元，而所有這些生成元都應與xn-1有公因式，此公因式化為首一多項式即為其生成多項式。 反之，若g(x)|(xn-1)，則g(x)可以生成一個循環(huán)碼，且當g(x)為n-k次多項式時，可生成(n,k)碼互反多項式與零空間 由于xn-1 可被g(x)整除，xn-1=g(x)h(x) 若h(x)=htxt+ht-1xt-1+h1x+h0，則h*(x)= h0 xt+h1xt-1+ht-1x+ht為h(x)的互反多項式 g(x)和h*(x)均可生成長度為n的循環(huán)碼，且互為零空間子碼 對于循環(huán)

4、碼C1和C2，如果有C1C2，則稱C1為C2的子碼 若g1(x)生成碼C1，g2(x)生成碼C2，而g2(x)|g1(x)，即g1(x)可以被g2(x)整除，或g2(x)是g1(x)的一個因子，則C1C2，即C1為C2的子碼系統(tǒng)循環(huán)碼 根據(jù)生成多項式g(x)可以直接對k-1次信息多項式d(x)編碼，即c(x)=d(x)g(x) mod xn-1，當g(x)可以整除xn-1時，構成循環(huán)碼。 系統(tǒng)碼指的是在編碼序列中包含所有信息位的編碼。上述方法形成的循環(huán)碼不是系統(tǒng)碼。 系統(tǒng)循環(huán)碼的生成：C(x) = d(x)xn-k + r(x) 0 mod g(x)。即將信息序列左移n-k位，加上一個n-k-

5、1次的校驗多項式r(x)，其中的r(x)= -d(x)xn-k mod g(x)。 用生成多項式的根定義循環(huán)碼 研究表明，生成多項式有重根的碼一般都要比無重根的碼差，因此只考慮無重根的碼，或構造無重根的多項式。 GF(q)上多項式xn-1無重根的充要條件是n與q互素。因此對GF(2)而言，充要條件即為n為奇數(shù)。合法碼字與生成多項式的根 若g(x)有r個不相等的根，則每個根必為每個碼多項式的根，因此可將所有根代入是否為零來驗證是否為碼多項式。（此處的運算是在擴域GF(qm)上的） 每個根都可有一個最小多項式，而生成多項式則是所有根的最小多項式的最小公倍式 每個根都有級數(shù)ei，即 ，則碼長為所有級

6、的最小公倍數(shù) 同一共軛根系的根在驗證碼字時的效果相同，因此只需考慮其中一個即可1iei用指定的根求生成多項式 給定必含根，求生成多項式g(x)時，要先找出各個根的最小多項式（可計算或查表），然后求它們的公倍式。由于共軛根系的最小多項式相同，因此首先要找出必含根中包括哪幾個共軛根系用根形成生成多項式舉例 GF(211)中，為本原元，令=89，求以、2、3、4為根的二進制循環(huán)碼。的級數(shù)為211-1=2047=8923，23=(89)23=1，因此的級為23，如果以為根，則它的共軛根系也為根：、2、4、8、16、32=9、18、36=13、26=3、6、12。例（續(xù)） 由于所要求的其它必含根2、3、

7、4都包括在這個共軛根系中，它們有相同的最小多項式g(x)=m(x) =(x-)(x-2) (x-4) (x-8) (x-16) (x-9) (x-18) (x-13) (x-3) (x-6) (x-12) = x11 + x9 + x6 + x5 + x4 + x2 + 1 這部是著名的Golay碼，能糾3個錯，是一種完備碼。（上面的化簡中要用到m()=0和=89 ）BCH碼 用GF(qm)中的n級元素的-1個連續(xù)冪次為根的多項式生成的循環(huán)碼稱為BCH碼。它的自由距不小于。如果根集中有本原元。則碼長n=qm-1，稱為本原BCH碼RS碼 GF(q)上的碼長N=q-1的本原BCH碼稱RS碼 RS碼的符號域與根域相同 RS碼生成多項式g(x)=(x-m0) (x-m0+1)(x-m0+-2)，常取m0=1。其碼距為。即生成的碼為(n,k,d)=(q-1, q-, )。因此RS