第七章BCH码 陆以勤 2005年5月
第七章 BCH码 陆以勤 2005年5月
一、在扩展域描述和构成循环码 素多项式 a g(x)f(x) f2(X)…f() 存在最小分裂域 最小多项式 qm g(X)=(X-01)(X-02).(X-).…(X-0n-k) 最小多项式 ↓↓↓↓ m(x)m2(x)m(x) mnk(x) g(x)=LCM(m(x),m(x),...,m(x),.....mn-k(x)) 如果41,02是共扼根，则m1=m2(x
一、在扩展域描述和构成循环码 Fq g(x) = f1 (x) f2 (x)…. fj (x) 存在最小分裂域 Fqm g(x)=(x-1 )(x-2 )…(x-j )…. (x-n-k ) 素多项式 最小多项式 g(x)=LCM(m1 (x), m1 (x),…, mj (x),…., mn-k (x)) m1 (x) m2 (x) mj (x) mn-k (x) 最小多项式 如果j1， j2是共扼根，则mj1(x)=mj2(x)
一、在扩展域从描述和构成循环码 定理1：设Fg上的循环码的生成多项式g(凶)在最小分裂域Fqm上的根为o1, 02,,0nk。则Fq上多项式c(X)=Cn-X1+Cn2X2+..+c1+c是一个码字多项 式的充要条件是Hc=0,其中： a H= "1 号* 。C=(Cm-1,Cn-2,,C1,C0) a a Cn-k 1 计算在Fgm上进行。 证明：（一）必要性 C(x)=a(x)g(X)=Cn-1X-1 +Cn2x2+...+Cx+Co c()=Cn14r1+cn24n2+.+C141+co=a(c)g()=a(c)*0=0,G=1,2,,n-k) (二)充分性 设c(X)满足Hc=0,c(X)=g(X)q(X)+s(X),对于j=1,2,,n-k, c(o)=g(o)9(o)+s(c)=0*q(c)+s(c)=cn-14n1+cn-241n-2+.+c14,+co=0 则s(c)=0,即s()在Fm上的根为a1,2,,nk,又as(X)<0g(),所以s(=0 即c()=g()q(),所以c(X)是码字多项式
一、在扩展域从描述和构成循环码 定理1：设Fq上的循环码的生成多项式g(x)在最小分裂域Fqm上的根为1， 2，…, n-k。则Fq上多项式c(x)= cn-1x n-1 +cn-2x n-2+…+c1x+c0是一个码字多项 式的充要条件是Hc T=0,其中: , ( , ,..., , ) ....... 1 ....... ...... ...... ...... ...... ...... 1 ...... 1 H 1 2 1 0 1 2 2 2 2 1 2 1 2 1 1 1 c c c c c n n n k n n k n n k n n n n − − − − − − − − − − − = = 计算在Fqm上进行。 证明：（一）必要性 设c(x)=a(x)g(x)= cn-1x n-1 +cn-2x n-2+…+c1x+c0 c(j )= cn-1j n-1 +cn-2j n-2+…+c1j +c0=a(j )g(j )=a(j )*0=0，(j=1,2,…, n-k) (二）充分性 设c(x)满足HcT=0，c(x)=g(x)q(x)+s(x)，对于j=1,2,…, n-k， c(j )=g(j )q(j )+s(j )=0*q(j )+s(j )=cn-1j n-1 +cn-2j n-2+…+c1j +c0=0 则s(j )=0，即s(x)在Fqm上的根为1，2，…, n-k，又s(x)< g(x), 所以s(x)=0 即c(x)=g(x)q(x)，所以c(x)是码字多项式
把H中的o=1,n-k, L,m-1 Bim-1 BC-1 R(n-1) t=0,.n-1)用F。上的m重表 1.m-2 1,m-2 % … … 4… 示 B%” % 阳 % (a)° cd=(B9m1B9mn-2…P%月 (a) (a1)n-1 (a1) P im-I % m” a3 i,m-2 共扼根 a=a9 %” % 阳 吧 Fm % 线性相关 j.m-I j,m-1 BC-2 %2 中 年年 % % 去掉线性 相关的行 (a)-1 B-y) n-k,m-I C n-k,m-1 Bkm-1 n-k.m-I BCNn-2 B阳km-2 BCkm-2 B2m-2 C=(%mn-1B%m-2…β%) (a)° 年甲 00年 年 e 中 P 动 BOka BCko
− − − − − − − − − − − − − − − −−−− − −− − −−−− − −− − −− −− −− −−−−− −−−−− −− −− −− −−−−− −−−−− −− −− −− −−−−− −−−−− (0) n k,0 (0) n k,m 2 (0) n k,m 1 (1) n k,0 (1) n k,m 2 (1) n k,m 1 (t) n k,0 (t) n k,m 2 (t) n k,m 1 (n 2 ) n k,0 (n 2 ) n k,m 2 (n 2 ) n k,m 1 (n 1 ) n k,0 (n 1 ) n k,m 2 (n 1 ) n k,m 1 (0) j,0 (0) j,m 2 (0) j,m 1 (1) j,0 (1) j,m 2 (1) j,m 1 (t) j,0 (t) j,m 2 (t) j,m 1 (n 2 ) j,0 (n 2 ) j,m 2 (n 2 ) j,m 1 (n 1 ) j,0 (n 1 ) j,m 2 (n 1 ) j,m 1 (0) i,0 (0) i,m 2 (0) i,m 1 (1) i,0 (1) i,m 2 (1) i,m 1 (t) i,0 (t) i,m 2 (t) i,m 1 (n 2 ) i,0 (n 2 ) i,m 2 (n 2 ) i,m 1 (n 1 ) i,0 (n 1 ) i,m 2 (n 1 ) i,m 1 (0) 1,0 (0) 1,m 2 (0) 1,m 1 (1) 1,0 (1) 1,m 2 (1) 1,m 1 (t) 1,0 (t) 1,m 2 (t) 1,m 1 (n 2 ) 1,0 (n 2 ) 1,m 2 (n 2 ) 1,m 1 (n 1 ) 1,0 (n 1 ) 1,m 2 (n 1 ) 1,m 1 β ... ββ β ... ββ ... β ... ββ ... β ... ββ β ... ββ ... ... ... ... ... ... ... β ... ββ β ... ββ .... β ... ββ ... β ... ββ β ... ββ ... ... ... ... ... ... ... β ... ββ β ... ββ ... β ... ββ ... β ... ββ β ... ββ ... ... ... ... ... ... ... β ... ββ β ... ββ ... β ... ββ ... β ... ββ β ... ββ ( 1 ) n - 1 ( 1 ) t ( 1 ) 0 ( j ) n - 1 (t) T j, (t) j,m (t) j,m tj α (β ,β ,...,β ) = − 1 − 2 0 ( j ) 0 线性相关 把 H中的 j t (j=1,…n -k, t=0,..n - 1）用 F q上的 m重表 示 (t) T j, (t) j,m (t) j,m tj α (β ,β ,..., β ) = − 1 − 2 0 共扼根 ( i ) t s q α j = α i 去掉线性 相关的行
，在扩展域从描述和构成循环码 定理2：若H在Fom中第行元素和第i行相应元素为q次幂，则在F。 中，第行分裂的m行与第行分裂的m行之间，行线性相关。 已知g(x)在扩展域Fqm中根，生成Fg上的循环码 Fgm={0,,02,,0qm1} 设o1,2,.,0n-k为gX的根，且： 9()根 共扼根系 级 最小多项式 01 Ri m i(x) 01,02,..,an-k中共扼根属于 02 Ri2 ei2 m2() 同一共扼根系，即Rih,R2,Rin k中可能重复，而m,(),m2,…， Qin-k e in-k m in-k(x) min.k有相同。 而g(Xn-1,1,2,,n-k也为X0-1的根，即(o)n=1,由循环群的性质( a为n级元素，则am=e一nlm),得o1,o2,,0n-k的级数为n的因数（必要条件）， 可取n=LCM(ei,ei2,ein-kd 方法：g-LcM(m,的，m2闪，mhW)} 去掉重复部分 方法2：直接由构造H
一、在扩展域从描述和构成循环码 定理2: 若H在Fqm中第j行元素和第i行相应元素为q次幂，则在Fq 中，第j行分裂的m行与第i行分裂的m行之间，行线性相关。 已知g(x)在扩展域Fqm中根，生成Fq上的循环码 Fqm={0,, 2 ,…, qm-1 } 设i1 , i2 ,…, in-k为g(x)的根，且： g(x)根 共扼根系 级 最小多项式 i1 R i1 e i1 m i1 (x) i2 R i2 e i2 m i2 (x) … … … …. in-k R in-k e in-k m in-k (x) 而g(x)|xn -1, i1 , i2 ,…, in-k也为 x n -1的根，即(ik) n=1, 由循环群的性质（ a为n 级元素，则a m = e n| m ),得i1 , i2 ,…, in-k的级数为n的因数(必要条件)， 可取 n=LCM(e i1 , e i2 ,…, e in-k ) 方法1：g(x)=LCM (m i1 (x) , m i2 (x) ,…, m in-k (x) ) 方法2：直接由构造H。 i1 , i2 ,…, in-k中共扼根属于 同一共扼根系，即R i1 , R i2 ,…, R ink中可能重复，而mi1 (x), m i2 (x), …, m in-k (x)有相同。 去掉重复部分