第七章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)有相同。 去掉重复部分
一、在扩展域从描述和构成循环码 方法1：g()=LCM(mi,(),m2(☒，，mink） 方法2：直接由构造H。 在每个共扼根系选取一个共扼根（一般选次数最小的，计算简单），得 o1,c2,..,cw,构成H: (ai)"-1(a1)-2 a 1 (a)n-1（ah)"-2 ab H= (a)-1(a)n-2 ajm 把H中的o1,o2,..,ow转为m重，H仍有线性相关的行，在这些行中 保留一行，其余去掉
一、在扩展域从描述和构成循环码 方法1：g(x)=LCM (m i1 (x) , m i2 (x) ,…, m in-k (x) ) 方法2：直接由构造H。 在每个共扼根系选取一个共扼根（一般选次数最小的，计算简单）,得 j1 , j2 ,…, jw , 构成H: = − − − − − − ) ) ....... 1 ....... ...... ...... ...... ...... ) ) ...... 1 ) ) ...... 1 H 1 2 1 2 1 2 2 2 2 1 1 1 w w w j n j n j j n j n j j n j n j （ （ （ （ （ （ 把H中的j1 , j2 ,…, jw转为m重，H仍有线性相关的行，在这些行中 保留一行，其余去掉
一 、在扩展域从描述和构成循环码 例（例5.5)：求以F16中o,02,03,04,05为根的F2上的循环码。 分析：，2,34,5 同一共扼根系，级15， 另一共扼根系，级5， 另一共扼根系，级3， 最小多项式x4+x+1 最小多项式x4+x3+x2+x+1 最小多项式x2++1 g()=LCM(x4+X+1,X4+x3+x2+x+1,X2+X+1)=(X4+x+1)(x4+x3+x2+X+1)(X2+x+1) (素多项式) =X10+Xx8+x5+x4+x2+X+1 n=LCM(15,5,3)=15 ag(X)=n-k=15-k=10,k=5 0 0 与课本 0 0 不同， 1 0 可按个 0 人习惯 1 0 1 1 H= (a3)4 (a3)13 0 0 0 1 0 全0， (a5)14 (a5)3 as 1 0 a 1 1 0 0 1 去掉 0 0 1 1 8 共4×3-2=10行 相同，去 0 掉1行 1 0 1
一、在扩展域从描述和构成循环码 例（例5.5)：求以F16中, 2 , 3 , 4 , 5为根的F2上的循环码。 分析： , 2 , 3 , 4 , 5 同一共扼根系, 级15， 最小多项式x 4+x+1 另一共扼根系, 级5， 最小多项式x 4+x3+x2+x+1 另一共扼根系, 级3， 最小多项式x 2+x+1 g(x)=LCM(x4+x+1, x4+x3+x2+x+1, x2+x+1)=(x4+x+1)( x4+x3+x2+x+1)( x2+x+1) (素多项式） = x10+x8+x5+x4+x2+x+1 n=LCM(15,5,3)=15 g(x)=n-k=15-k=10, k=5 = = = 1 0 ... 0 1 1 1 ... 1 0 1 1 ... 1 0 0 0 ... 0 0 1 0 ... 0 1 1 1 ... 0 0 1 0 ... 0 0 1 1 ... 1 0 1 1 ... 0 1 0 0 ... 1 0 0 1 ... 0 0 1 1 ... 0 0 ...... 1 ...... 1 ...... 1 ) ) ...... 1 ) ) ...... 1 ...... 1 H 1 0 5 5 1 2 9 3 1 4 1 3 5 1 4 5 1 3 5 3 1 4 3 1 3 3 1 4 1 3 （ （ （ （ 与课本 不同， 可按个 人习惯 全0， 去掉 相同，去 掉1行 共43-2=10行
二、二进制BCH码 若g(X)在扩展域Fqm上的根为c1,o2,,0n-k,则 「(a4)-1( a4)"-2 a H= （a2)-1(a2)-2 a 1 (a)n-(a)n-2 an-k 若i1,2,ink中含有1,2，…，d-1,则抽这d-1行和任意d-1列，得 ai- (a2) (a-i)h (a)k (aa-la 每一列提取公因式，得 H=ai+ja+.+jd ah - =a+j++j (aa) （)-2(a-2 (a)4-2 d-2>ju>jv2l
二、二进制BCH码 若g(x)在扩展域Fqm上的根为i1 , i2 ,…, in-k，则 = − − − − − − − − − ) ) ....... 1 ....... ...... ...... ...... ...... ) ) ...... 1 ) ) ...... 1 H 1 2 1 2 1 2 2 2 2 1 1 1 n k n k n k i n i n i i n i n i i n i n i （ （ （ （ （ （ 若i1 ,i2 ,…, in-k中含有1,2,…,d-1, 则抽这d-1行和任意d-1列，得 1 2 1 1 2 1 1 2 1 ) ) ....... ( ) ....... ...... ...... ...... ) ) ...... ( ) ...... 1 1 1 2 2 2 − − − − − − d d d d j d j d j j j j j j j （ （ （ （ 每一列提取公因式，得 − + + + − − − + + + = = − − − − − 2 1 ... 2 2 2 ... ( ) ) ) ....... ) ....... ...... ...... ...... ...... 1 1 ...... 1 H 1 2 1 1 2 1 1 2 1 1 2 1 u v d u v d d d d j j j j j j j j d j d j d j j j j j j （ （ （
二、二进制BCH码 若i1,2,,ink中含有1,2…，d-1,则抽这d-1行和任意d-1列，得 a ) - (a2)y (a)h (a): (a4-1) 每一列提取公因式，得 1 H=a+j2+.+ju- =atatt Π(a.-a) ()-2 ( (aa)4-2 d-2>ju>jvzl 范得蒙行列式，若g(没有重根，即o,≠o,则行列式不为零，行列式对应的 矩阵满秩，原矩阵任意d-1列线性无关，所以码的距离至少为d。 1.定理3：F。上多项式xn1在最小分裂域无重根的充要条件为 (n,q)=1
二、二进制BCH码 若i1 ,i2 ,…, in-k中含有1,2,…,d-1, 则抽这d-1行和任意d-1列，得 1 2 1 1 2 1 1 2 1 ) ) ....... ( ) ....... ...... ...... ...... ) ) ...... ( ) ...... 1 1 1 2 2 2 − − − − − − d d d d j d j d j j j j j j j （ （ （ （ 每一列提取公因式，得 − + + + − − − + + + = = − − − − − 2 1 ... 2 2 2 ... ( ) ) ) ....... ) ....... ...... ...... ...... ...... 1 1 ...... 1 H 1 2 1 1 2 1 1 2 1 1 2 1 u v d u v d d d d j j j j j j j j d j d j d j j j j j j （ （ （ 范得蒙行列式，若g(x)没有重根，即ju， jv , 则行列式不为零，行列式对应的 矩阵满秩，原矩阵任意d-1列线性无关，所以码的距离至少为d。 1. 定理3：Fq上多项式x n -1在最小分裂域无重根的充要条件为 (n,q)=1
二、二进制BCH码 2.定义：设F2上循环码的生成多项式g(X在扩展域F2m上的根含有0，o2, o3,.,0d1(其中为本原元)，则这种循环码称为二元（狭义)本 原BCH码 3.定理4：本原BCH码的最小距离dmin≥d. 4.BCH码设计步骤 1)给定n,t,找合适的F2m,使n=2m-1或n2m-1,且(n,2m)=1(保证无重根)； 2) 选0,02,03，，02t为根，把它们组成不同的根系R1,R2,,R,,Rs, 最多2t个，而o和o2属于同一共扼根系，偶数下标一律取消，所以s≤t。 对于每一根系R,求其最小多项式m(),则 g(x)=m(x)m2(x)...m(x)...mg(x) a°g(X)=n-k≤mt(a°m(Xy≤m) n=LCM(e1,e2,,e,…,es） e,为R根系的根的级数，含本原元
二、二进制BCH码 2. 定义：设F2上循环码的生成多项式g(x)在扩展域F2m上的根含有, 2 , 3 , …, d-1 (其中为本原元），则这种循环码称为二元（狭义）本 原BCH码 3. 定理4：本原BCH码的最小距离dmind. 4. BCH码设计步骤 1）给定n,t,找合适的F2m，使n=2m-1或n|2m-1,且(n, 2m)=1(保证无重根); 2）选, 2 , 3 , …, 2t为根，把它们组成不同的根系R1 , R2 ,…, Rj , …, Rs , 对于每一根系Rj，求其最小多项式mj (x),则 g(x)=m1 (x)m2 (x)…mj (x)…ms (x) g(x)=n-kmt ( mj (x) m) n=LCM(e1 ,e2 ,…,ej ,…,es ) 最多2t个，而j和2j属于同一共扼根系，偶数下标一律取消，所以st。 ej为Rj根系的根的级数，含本原元