第四章BCH码1.ppt

通信工程系移通信工程系移动动通信教研室通信教研室信道编码第四章 BCH码4.1 BCH4.1 BCH码码概述概述4.2 4.2 预备预备知知识识：有限域基：有限域基础础4.3 BCH4.3 BCH码码的构造的构造4.4 BCH4.4 BCH码码的的编码编码4.5 BCH4.5 BCH码码的的译码译码9/16/20242整理整理ppt本章要求p了解了解BCHBCH码码的提出与的提出与发发展展p掌握：掌握：n扩扩域域GF(2GF(2m m) )的概念、构造及域元素的运算的概念、构造及域元素的运算nBCHBCH码码的基本概念与构造方法的基本概念与构造方法nBCHBCH码码的的编码编码方法与迭代方法与迭代译码译码算法算法9/16/20243整理整理ppt第四章 BCH码4.1 BCH4.1 BCH码码概述概述4.2 4.2 预备预备知知识识：有限域基：有限域基础础4.3 BCH4.3 BCH码码的构造的构造4.4 BCH4.4 BCH码码的的编码编码4.5 BCH4.5 BCH码码的的译码译码9/16/20244整理整理ppt4.1 BCH码概述pBCHBCHBCHBCH码码码码的提出与的提出与的提出与的提出与发发发发展展展展n n1959195919591959年，霍昆格姆年，霍昆格姆年，霍昆格姆年，霍昆格姆(Hocquenghem)(Hocquenghem)(Hocquenghem)(Hocquenghem)，，，，1960196019601960年博斯年博斯年博斯年博斯(Bose)(Bose)(Bose)(Bose)和和和和查查查查德胡理德胡理德胡理德胡理(Chaudhuri)(Chaudhuri)(Chaudhuri)(Chaudhuri)，各自独立地提出了二，各自独立地提出了二，各自独立地提出了二，各自独立地提出了二元元元元BCHBCHBCHBCH码码码码的构造方法。

的构造方法的构造方法的构造方法n n1960196019601960年，彼得森年，彼得森年，彼得森年，彼得森(Peterson)(Peterson)(Peterson)(Peterson)从理从理从理从理论论论论上提出了二元上提出了二元上提出了二元上提出了二元BCHBCHBCHBCH码码码码的的的的译码译码译码译码算法n n1966196619661966年，伯利坎普年，伯利坎普年，伯利坎普年，伯利坎普(Berlekamp)(Berlekamp)(Berlekamp)(Berlekamp)提出了提出了提出了提出了BCHBCHBCHBCH码码码码的迭代的迭代的迭代的迭代译译译译码码码码算法，使算法，使算法，使算法，使BCHBCHBCHBCH码进码进码进码进入入入入实实实实用n n七十年代以后七十年代以后七十年代以后七十年代以后BCHBCHBCHBCH码码码码得到了极得到了极得到了极得到了极为为为为广泛的广泛的广泛的广泛的应应应应用，如磁用，如磁用，如磁用，如磁记录记录记录记录、、、、CD/VCD/DVDCD/VCD/DVDCD/VCD/DVDCD/VCD/DVD、深空及、深空及、深空及、深空及卫卫卫卫星通信等。

星通信等星通信等星通信等9/16/20245整理整理ppt4.1 BCH码概述pBCHBCH码码的提出与的提出与发发展展n对对BCHBCH码码的后的后续续研究主要集中在研究主要集中在译码译码算法算法的的简简化，如减少迭代次数、快速化，如减少迭代次数、快速译码译码算算法、法、提高提高纠错纠错能力能力、、软软判决判决译码译码等9/16/20246整理整理ppt4.1 BCH码概述pBCHBCH码码的特点的特点nBCHBCH码码是是线线性分性分组码组码的重要子的重要子类类，，再具体再具体讲讲，是，是循循环码环码子子类类nBCH码码具有构造方便、具有构造方便、编码简单编码简单以及以及译码译码易于易于实现实现等等优优点，而且点，而且BCH码码有完有完备备的代数理的代数理论论支支持nBCH码码的生成多的生成多项项式与最小距离式与最小距离d有密切关系，有密切关系，使使设计设计者可以根据者可以根据d的需要的需要轻轻易构造出具有易构造出具有预预定定纠错纠错能力的能力的编码编码方案n纠错纠错能力能力强强，，中短中短码长码长下的性能接近理下的性能接近理论值论值BCH码码是迄今是迄今为为止研究止研究最最为详为详尽、分析最尽、分析最为为透透彻彻、、取得成果最多、取得成果最多、应应用最用最为为广泛的广泛的码类码类之一。

之一9/16/20247整理整理ppt第四章 BCH码4.1 BCH4.1 BCH码码概述概述4.2 4.2 预备预备知知识识：有限域基：有限域基础础4.3 BCH4.3 BCH码码的构造的构造4.4 BCH4.4 BCH码码的的编码编码4.5 BCH4.5 BCH码码的的译码译码9/16/20248整理整理ppt4.2 预备知识：有限域基础p有限域的基本概念有限域的基本概念pGF(2)GF(2)上的多上的多项项式式pGF(2)GF(2)的的扩扩域域GF(2GF(2m m) )p用用m m次本原多次本原多项项式构造式构造扩扩域域GF(2GF(2m m) )p扩扩域域GF(2GF(2m m) )的表示方式的表示方式p扩扩域域GF(2GF(2m m) )的性的性质质pGF(2GF(2m m) )中元素的最小多中元素的最小多项项式式9/16/20249整理整理ppt4.2 预备知识：有限域基础p有限域的基本概念有限域的基本概念n域的定域的定义义：：对对于非空元素集合于非空元素集合F F，若定，若定义义两种代数运算两种代数运算”+””+”和和“*”“*”，且，且满满足以下条件：足以下条件：1)1)、、F F关于关于“+”“+”运算构成交运算构成交换换群群2)2)、、F F中全体非中全体非0 0元素元素对对“*”“*”运算构成交运算构成交换换群群3)3)、两种运算、两种运算满满足分配律足分配律 则则称称F F构成域。

构成域n如果如果F F中元素个数有限，中元素个数有限，则则称称该该域域为为有限域或有限域或伽伽罗华罗华(Galois)(Galois)域，域，记为记为GF(q)GF(q)9/16/202410整理整理ppt4.2 预备知识：有限域基础p有限域的基本概念有限域的基本概念n例：集合例：集合{0,1}{0,1}对对模模2 2加和模加和模2 2乘构成二元乘构成二元域，域，记为记为GF(2)GF(2)；；n例：如果例：如果q q为为素数素数，，则则集合集合{0,1,…,q-1}{0,1,…,q-1}对对模模q q加和乘构成加和乘构成q q元域元域GF(q)GF(q)；；9/16/202411整理整理ppt4.2 预备知识：有限域基础p有限域的基本概念有限域的基本概念n有限域的生成元：有限域的生成元：对对于于GF(q)GF(q)，其中一定存在非，其中一定存在非0 0元素元素g g，其各次，其各次幂幂能生成域中的所有非能生成域中的所有非0 0元素，元素，则则g g称称为该为该域的生成元或本原元域的生成元或本原元例如：GF(5)={0,1,2,3,4}中，g = 1 g0 ≡ 1 g1 ≡ 1 g2 ≡ 1 g3 ≡ 1g = 2 g0 ≡ 1 g1 ≡ 2 g2 ≡ 4 g3 ≡ 3g = 3 g0 ≡ 1 g1 ≡ 3 g2 ≡ 4 g3 ≡ 2g = 4 g0 ≡ 1 g1 ≡ 4 g2 ≡ 1 g3 ≡ 4生成元生成元生成元生成元9/16/202412整理整理ppt4.2 预备知识：有限域基础p有限域的基本概念有限域的基本概念nGF(q)GF(q)中元素的中元素的阶阶：由：由GF(q)GF(q)中元素的中元素的幂幂所能生所能生成域元素的个数称成域元素的个数称为该为该元素的元素的阶阶。

n例如：例如：GF(5)GF(5)中，中，2 2、、3 3的的阶为阶为4 4；；1 1的的阶为阶为1 1；；4 4的的阶为阶为2 2n定理：有限域定理：有限域GF(q)中，本原元的中，本原元的阶为阶为q-1，其，其余非零元素的余非零元素的阶阶均均为为q-1的因子n说说明：后面我明：后面我们仅讨论们仅讨论二元域二元域GF(2)及其及其扩扩域域GF(2q)，所有，所有结论结论均可推广到均可推广到q元域元域GF(q)9/16/202413整理整理ppt4.2 预备知识：有限域基础pGF(2)GF(2)GF(2)GF(2)上的多上的多上的多上的多项项项项式式式式n nGF(2)GF(2)GF(2)GF(2)上的多上的多上的多上的多项项项项式：系数取自式：系数取自式：系数取自式：系数取自GF(2)GF(2)GF(2)GF(2)的多的多的多的多项项项项式式式式如：如：如：如：f(x)=x+1f(x)=x+1f(x)=x+1f(x)=x+1、、、、f(x)=xf(x)=xf(x)=xf(x)=x3 3 3 3+x+1 +x+1 +x+1 +x+1 等等等等n n定理：若定理：若定理：若定理：若f(x)f(x)f(x)f(x)是是是是GF(2)GF(2)GF(2)GF(2)上的上的上的上的m m m m次多次多次多次多项项项项式，式，式，式，则则则则：：：：n n既既既既约约约约多多多多项项项项式：如果式：如果式：如果式：如果GF(2)GF(2)GF(2)GF(2)上的上的上的上的m m m m次多次多次多次多项项项项式式式式f(x)f(x)f(x)f(x)除了除了除了除了1 1 1 1和它和它和它和它本身之外不能被其它多本身之外不能被其它多本身之外不能被其它多本身之外不能被其它多项项项项式整除，式整除，式整除，式整除，则则则则称称称称f(x)f(x)f(x)f(x)为为为为GF(2)GF(2)GF(2)GF(2)上上上上的既的既的既的既约约约约多多多多项项项项式。

式9/16/202414整理整理ppt4.2 预备知识：有限域基础pGF(2)GF(2)GF(2)GF(2)上的多上的多上的多上的多项项项项式式式式n n多多多多项项项项式的周期：多式的周期：多式的周期：多式的周期：多项项项项式式式式f(x)f(x)f(x)f(x)的周期定的周期定的周期定的周期定义为义为义为义为f(x)f(x)f(x)f(x)能整除能整除能整除能整除x x x xn n n n-1-1-1-1的最小的的最小的的最小的的最小的n n n nn n本原多本原多本原多本原多项项项项式：如果式：如果式：如果式：如果GF(2)GF(2)GF(2)GF(2)上的上的上的上的m m m m次既次既次既次既约约约约多多多多项项项项式式式式f(x)=xf(x)=xf(x)=xf(x)=xm m m m+f+f+f+fm-1m-1m-1m-1x x x xm-1 m-1 m-1 m-1 +…+f+…+f+…+f+…+f1 1 1 1x+1x+1x+1x+1的周期的周期的周期的周期为为为为n=2n=2n=2n=2m m m m-1-1-1-1，，，，则则则则称称称称f(x)f(x)f(x)f(x)为为为为GF(2)GF(2)GF(2)GF(2)上的上的上的上的m m m m次本原多次本原多次本原多次本原多项项项项式。

式 本原多本原多本原多本原多项项项项式一定是既式一定是既式一定是既式一定是既约约约约的，既的，既的，既的，既约约约约多多多多项项项项式未必是本原的式未必是本原的式未必是本原的式未必是本原的n n反多反多反多反多项项项项式：式：式：式：设设设设f(x)f(x)f(x)f(x)是是是是GF(2)GF(2)GF(2)GF(2)上的上的上的上的m m m m次多次多次多次多项项项项式，式，式，式， 则则则则f f f f* * * *(x)=x(x)=x(x)=x(x)=xm m m mf(xf(xf(xf(x-1-1-1-1) ) ) )称称称称为为为为f(x)f(x)f(x)f(x)的反多的反多的反多的反多项项项项式 如果多如果多如果多如果多项项项项式式式式f(x)f(x)是既是既是既是既约约约约多多多多项项项项式，式，式，式，则则则则其反多其反多其反多其反多项项项项式式式式f f* *(x)(x)一定是既一定是既一定是既一定是既约约约约多多多多项项项项式；式；式；式； 如果多如果多如果多如果多项项项项式式式式f(x)f(x)是本原多是本原多是本原多是本原多项项项项式，式，式，式，则则则则其反多其反多其反多其反多项项项项式式式式f*(x)f*(x)也一定是本原多也一定是本原多也一定是本原多也一定是本原多项项项项式。

式9/16/202415整理整理ppt4.2 预备知识：有限域基础pGF(2)GF(2)GF(2)GF(2)的的的的扩扩扩扩域域域域GF(2GF(2GF(2GF(2m m m m) ) ) )n n扩扩扩扩域域域域GF(2GF(2GF(2GF(2m m m m) ) ) )：：：：设设设设p(x)p(x)p(x)p(x)为为为为GF(2)GF(2)GF(2)GF(2)上的上的上的上的m m m m次既次既次既次既约约约约多多多多项项项项式，模式，模式，模式，模p(x)p(x)p(x)p(x)的所有的所有的所有的所有2 2 2 2m m m m个余式在模个余式在模个余式在模个余式在模p(x)p(x)p(x)p(x)加法和乘法下构成加法和乘法下构成加法和乘法下构成加法和乘法下构成2 2 2 2m m m m元域，元域，元域，元域，称称称称为为为为GF(2)GF(2)GF(2)GF(2)的的的的扩扩扩扩域域域域( ( ( (也称也称也称也称为为为为模模模模p(x)p(x)p(x)p(x)的剩余的剩余的剩余的剩余类类类类域域域域) ) ) )，，，，记为记为记为记为GFGFGFGF(2(2(2(2m m m m) ) ) )。

n n例如：例如：例如：例如： 设设设设p(x)=xp(x)=xp(x)=xp(x)=x3 3 3 3+x+1+x+1+x+1+x+1，，，，则则则则：：：：{0, 1, x, x{0, 1, x, x{0, 1, x, x{0, 1, x, x2 2 2 2, x+1, x, x+1, x, x+1, x, x+1, x2 2 2 2+x, x+x, x+x, x+x, x2 2 2 2+x+1, x+x+1, x+x+1, x+x+1, x2 2 2 2+1}+1}+1}+1}构成构成构成构成扩扩扩扩域域域域GFGFGFGF(2(2(2(23 3 3 3) ) ) )9/16/202416整理整理ppt4.2 预备知识：有限域基础pGF(2)GF(2)GF(2)GF(2)的的的的扩扩扩扩域域域域GF(2GF(2GF(2GF(2m m m m) ) ) )n nGF(2)={0, 1}GF(2)={0, 1}GF(2)={0, 1}GF(2)={0, 1}称称称称为为为为GF(2GF(2GF(2GF(2m m m m) ) ) )的基域n n注意：注意：注意：注意：GF(2GF(2GF(2GF(23 3 3 3) ) ) )不能写成不能写成不能写成不能写成GF(8)GF(8)GF(8)GF(8)，其含，其含，其含，其含义义义义不同。

不同GF(q)GF(q)GF(q)GF(q)表示的是数域，而表示的是数域，而表示的是数域，而表示的是数域，而GF(qGF(qGF(qGF(qm m m m) ) ) )则则则则是多是多是多是多项项项项式域、式域、式域、式域、GF(q)GF(q)GF(q)GF(q)的的的的扩扩扩扩域n n不同的不同的不同的不同的m m m m次既次既次既次既约约约约多多多多项项项项式的剩余式的剩余式的剩余式的剩余类类类类域是域是域是域是同构同构同构同构的的的的9/16/202417整理整理ppt4.2 预备知识：有限域基础pGF(2)GF(2)GF(2)GF(2)的的的的扩扩扩扩域域域域GF(2GF(2GF(2GF(2m m m m) ) ) )n n定理定理定理定理1 1 1 1：如果：如果：如果：如果p(x)p(x)p(x)p(x)是是是是GF(2)GF(2)GF(2)GF(2)上的上的上的上的m m m m次本原多次本原多次本原多次本原多项项项项式，式，式，式，则扩则扩则扩则扩域域域域GFGFGFGF(2(2(2(2m m m m) ) ) )的所有非零元素在模的所有非零元素在模的所有非零元素在模的所有非零元素在模p(x)p(x)p(x)p(x)乘运算下构成循乘运算下构成循乘运算下构成循乘运算下构成循环环环环群。

群若一个群若一个群G的每个元都是的每个元都是G中的某个固定元中的某个固定元α的次的次幂幂，，则则称称G为为循循环环群，也称群，也称G是由是由α生成的群，生成的群，记为记为G=(α)9/16/202418整理整理ppt4.2 预备知识：有限域基础pGF(2)GF(2)GF(2)GF(2)的的的的扩扩扩扩域域域域GF(2GF(2GF(2GF(2m m m m) ) ) )n n定理定理定理定理1 1 1 1：如果：如果：如果：如果p(x)p(x)p(x)p(x)是是是是GF(2)GF(2)GF(2)GF(2)上的上的上的上的m m m m次本原多次本原多次本原多次本原多项项项项式，式，式，式，则扩则扩则扩则扩域域域域GFGFGFGF(2(2(2(2m m m m) ) ) )的所有非零元素在模的所有非零元素在模的所有非零元素在模的所有非零元素在模p(x)p(x)p(x)p(x)乘运算下构成循乘运算下构成循乘运算下构成循乘运算下构成循环环环环群n n例如：例如：例如：例如：设设设设p(x)=xp(x)=xp(x)=xp(x)=x3 3 3 3+x+1+x+1+x+1+x+1，，，，则则则则：：：：{0, 1, x, x{0, 1, x, x{0, 1, x, x{0, 1, x, x2 2 2 2, x+1, , x+1, , x+1, , x+1, x x x x2 2 2 2+x, x+x, x+x, x+x, x2 2 2 2+x+1, x+x+1, x+x+1, x+x+1, x2 2 2 2+1}+1}+1}+1}构成构成构成构成扩扩扩扩域域域域GF(2GF(2GF(2GF(23 3 3 3) ) ) )。

其中其中其中其中(x+1)(x+1)(x+1)(x+1)的各次的各次的各次的各次幂对幂对幂对幂对p(x)p(x)p(x)p(x)取模，可以生成取模，可以生成取模，可以生成取模，可以生成扩扩扩扩域集合中域集合中域集合中域集合中的所有非的所有非的所有非的所有非0 0 0 0多多多多项项项项式，所以式，所以式，所以式，所以该扩该扩该扩该扩域中所有非零元素在模域中所有非零元素在模域中所有非零元素在模域中所有非零元素在模p(x)p(x)p(x)p(x)运算下构成循运算下构成循运算下构成循运算下构成循环环环环群x+1)(x+1)(x+1)(x+1)0 0 0 0=1=1=1=1；；；；(x+1)(x+1)(x+1)(x+1)1 1 1 1=x+1=x+1=x+1=x+1；；；；(x+1)(x+1)(x+1)(x+1)2 2 2 2= = = =x x x x2 2 2 2+1+1+1+1；；；；(x+1)(x+1)(x+1)(x+1)3 3 3 3= x= x= x= x2 2 2 2(x+1)(x+1)(x+1)(x+1)4 4 4 4=x=x=x=x2 2 2 2+x+1+x+1+x+1+x+1；；；；(x+1)(x+1)(x+1)(x+1)5 5 5 5=x=x=x=x；；；；(x+1)(x+1)(x+1)(x+1)6 6 6 6=x=x=x=x2 2 2 2+x+x+x+x；；；；9/16/202419整理整理ppt4.2 预备知识：有限域基础pGF(2)GF(2)GF(2)GF(2)的的的的扩扩扩扩域域域域GF(2GF(2GF(2GF(2m m m m) ) ) )n n推推推推论论论论：：：：扩扩扩扩域域域域GF(2GF(2GF(2GF(2m m m m) ) ) )中至少存在一个本原元中至少存在一个本原元中至少存在一个本原元中至少存在一个本原元α (αα (αα (αα (α代表一代表一代表一代表一个次数小于个次数小于个次数小于个次数小于m m m m的多的多的多的多项项项项式式式式) ) ) )，其各次，其各次，其各次，其各次幂幂幂幂αααα0 0 0 0,α,α,α,α1 1 1 1,α,α,α,α2 2 2 2,…, ,…, ,…, ,…, 构成构成构成构成GF(2GF(2GF(2GF(2m m m m) ) ) )的全部非零元素。

的全部非零元素的全部非零元素的全部非零元素n n定理定理定理定理2 2 2 2：：：： GF(2) GF(2) GF(2) GF(2)上的上的上的上的m m m m次本原多次本原多次本原多次本原多项项项项式式式式p(x)p(x)p(x)p(x)在在在在扩扩扩扩域域域域GF(2GF(2GF(2GF(2m m m m) ) ) )上上上上一定有根，假一定有根，假一定有根，假一定有根，假设设设设其根其根其根其根为为为为αααα，，，，则则则则αααα一定是本原元一定是本原元一定是本原元一定是本原元n n根据以上定理，我根据以上定理，我根据以上定理，我根据以上定理，我们们们们可以用可以用可以用可以用GF(2)GF(2)GF(2)GF(2)上的上的上的上的m m m m次本原多次本原多次本原多次本原多项项项项式式式式p(x)p(x)p(x)p(x)来构造来构造来构造来构造扩扩扩扩域域域域GF(2GF(2GF(2GF(2m m m m) ) ) ) 9/16/202420整理整理ppt4.2 预备知识：有限域基础p用用用用m m m m次本原多次本原多次本原多次本原多项项项项式构造式构造式构造式构造扩扩扩扩域域域域GF(2GF(2GF(2GF(2m m m m) ) ) )n n构造构造构造构造扩扩扩扩域域域域GF(2GF(2GF(2GF(2m m m m) ) ) )的步的步的步的步骤骤骤骤：：：：① ① ① ① 找一个找一个找一个找一个GF(2)GF(2)GF(2)GF(2)上的上的上的上的m m m m次本原多次本原多次本原多次本原多项项项项式式式式p(x)p(x)p(x)p(x)② ② ② ② 令令令令αααα为为为为P(x)P(x)P(x)P(x)在在在在GF(2GF(2GF(2GF(2m m m m) ) ) )上的根上的根上的根上的根③ ③ ③ ③ 取取取取αααα的各次的各次的各次的各次幂幂幂幂αααα0 0 0 0,α,α,α,α1 1 1 1,α,α,α,α2 2 2 2,…, ,…, ,…, ,…, 构成构成构成构成GF(2GF(2GF(2GF(2m m m m) ) ) )的全的全的全的全部非零元素部非零元素部非零元素部非零元素④ ④ ④ ④ 加上零元素加上零元素加上零元素加上零元素0 0 0 0即构成即构成即构成即构成扩扩扩扩域域域域GF(2GF(2GF(2GF(2m m m m) ) ) )n n例如：用本原多例如：用本原多例如：用本原多例如：用本原多项项项项式式式式 p(x)=x p(x)=x p(x)=x p(x)=x3 3 3 3+x+1 +x+1 +x+1 +x+1 和和和和 p(x)=x p(x)=x p(x)=x p(x)=x3 3 3 3+x+x+x+x2 2 2 2+1 +1 +1 +1 分分分分别别别别构造构造构造构造扩扩扩扩域域域域GF(2GF(2GF(2GF(23 3 3 3) ) ) )9/16/202421整理整理ppt4.2 预备知识：有限域基础p用用用用m m m m次本原多次本原多次本原多次本原多项项项项式构造式构造式构造式构造扩扩扩扩域域域域GF(2GF(2GF(2GF(2m m m m) ) ) )GF(2GF(2GF(2GF(23 3 3 3)/p(x)=x)/p(x)=x)/p(x)=x)/p(x)=x3 3 3 3+x+1+x+1+x+1+x+1 0,α 0,α 0,α 0,α0 0 0 0=1,α=1,α=1,α=1,α1 1 1 1=α,α=α,α=α,α=α,α2 2 2 2=α=α=α=α2 2 2 2 ,α ,α ,α ,α3 3 3 3=α+1=α+1=α+1=α+1 α α α α4 4 4 4=α=α=α=α2 2 2 2+α,α+α,α+α,α+α,α5 5 5 5=α=α=α=α2 2 2 2+α+1,α+α+1,α+α+1,α+α+1,α6 6 6 6=α=α=α=α2 2 2 2+1+1+1+1GF(2GF(2GF(2GF(23 3 3 3)/p(x)=x)/p(x)=x)/p(x)=x)/p(x)=x3 3 3 3+x+x+x+x2 2 2 2+1+1+1+1 0,α 0,α 0,α 0,α0 0 0 0=1,α=1,α=1,α=1,α1 1 1 1=α,α=α,α=α,α=α,α2 2 2 2=α=α=α=α2 2 2 2 ,α ,α ,α ,α3 3 3 3=α=α=α=α2 2 2 2+1,+1,+1,+1, α α α α4 4 4 4=α=α=α=α2 2 2 2+α+1,α+α+1,α+α+1,α+α+1,α5 5 5 5=α+1,α=α+1,α=α+1,α=α+1,α6 6 6 6=α=α=α=α2 2 2 2+α+α+α+α9/16/202422整理整理ppt4.2 预备知识：有限域基础p扩扩域域GF(2GF(2m m) )的表示方式的表示方式GF(23)/p(x)=x3+x+1 0 0 000α0 1 001α1 α 010α2 α2 100α3 α+1 011α4 α2+α 110α5 α2+α+1 111α6 α2+1 101GF(23)/p(x)=x3+x2+1 0 0 000α0 1 001α1 α 010α2 α2 100α3 α2+1 101α4 α2+α+1 111α5 α+1 011α6 α2+α 1109/16/202423整理整理ppt4.2 预备知识：有限域基础p扩扩域域GF(2GF(2m m) )的性的性质质n定理定理1 1：：扩扩域域GF(2GF(2m m) )上非零元素上非零元素ααk k的的阶阶一定是一定是2 2m m-1-1的因子，的因子，阶为阶为：：n=(2n=(2m m-1)/(k,2-1)/(k,2m m-1)-1)。

其中：其中：(k,2(k,2m m-1)-1)表示表示k k和和2 2m m-1-1的最大公的最大公约约数n例如：例如：GF(2GF(23 3) )中，中，αα0 0的的阶为阶为1 1，其余非零元素，其余非零元素的的阶阶均均为为7 7GF(2GF(24 4) )中，中，…………n定定义义：如果：如果GF(2GF(2m m) )中元素中元素ααk k的的阶阶小于小于2 2m m-1-1，，则则称称该该元素元素为为非本原元非本原元9/16/202424整理整理ppt4.2 预备知识：有限域基础p扩扩域域GF(2GF(2m m) )的性的性质质n定理定理2 2：：扩扩域域GF(2GF(2m m) )上的所有非零元素都是上的所有非零元素都是GF(2)GF(2)上多上多项项式式 在在扩扩域域GF(2GF(2m m) )上的根即：上的根即：n例如：在例如：在扩扩域域GF(2GF(23 3) )上可以上可以验证验证：：x x7 7-1=(x-1)(x-α)(x-α-1=(x-1)(x-α)(x-α2 2)(x-α)(x-α3 3)(x-α)(x-α4 4)(x-)(x-αα5 5)(x-α)(x-α6 6) )9/16/202425整理整理ppt4.2 预备知识：有限域基础p扩扩域域GF(2GF(2m m) )的性的性质质n定理定理3 3：如果：如果f(x)f(x)是是GF(2)GF(2)上的多上的多项项式，式，ββ是是扩扩域域GF(2GF(2m m) )中元素，中元素，则则有：有：n例如：例如：GF(2GF(23 3)/p(x)=x)/p(x)=x3 3+x+1+x+1上：上：F(x)=xF(x)=x2 2+x+x(α(α2 2+α)+α)2 2 = α = α α α4 4+α+α2 2 = α = α2 2+α+α+α+α2 2 = α = α0,α0,α0 0=1,α=1,α1 1=α,α=α,α2 2=α=α2 2 ,α,α3 3=α+1,α=α+1,α4 4=α=α2 2+α,α+α,α5 5=α=α2 2+α+1,α+α+1,α6 6=α=α2 2+1+19/16/202426整理整理ppt4.2 预备知识：有限域基础p扩扩域域GF(2GF(2m m) )的性的性质质n定理定理4 4：如果：如果GF(2GF(2m m) )中元素中元素ββ是二元多是二元多项项式式f(x)f(x)在在GF(2GF(2m m) )上的根，上的根，则则：：ββ的的2 2j j（（j=1,2,…j=1,2,…）次）次幂幂也一定是也一定是f(x)f(x)在在GF(2GF(2m m) )上的根。

上的根n例如：例如：GF(2GF(23 3)/p(x)=x)/p(x)=x3 3+x+1+x+1上：上： α α是是p(x)= xp(x)= x3 3+x+1+x+1的根，的根，αα2 2, α, α4 4, α, α8 8=α=α同同样样是是p(x)p(x)在在GFGF(2(23 3) )上的根即：上的根即：P(α)=P(αP(α)=P(α2 2)=P(α)=P(α4 4)=0)=0n费费尔尔马马定理：如果定理：如果ββ是是扩扩域域GF(2GF(2m m) )上的非零元素，上的非零元素，则则有：有：9/16/202427整理整理ppt4.2 预备知识：有限域基础pGF(2GF(2m m) )中元素的最小多中元素的最小多项项式式n共共轭轭根系：如果根系：如果扩扩域元素域元素ββ是是GF(2)GF(2)上多上多项项式式f(x)f(x)的根，的根，则则 也一定是也一定是f(x)f(x)的根，称的根，称 为为一个共一个共轭轭根系一个共一个共轭轭根系至多包含根系至多包含m m个共个共轭轭元素。

元素n最小多最小多项项式：以式：以扩扩域域GF(2GF(2m m) )上的非零元素上的非零元素ββ为为根的最低根的最低次多次多项项式称式称为为ββ的最小多的最小多项项式，式，记为记为M Mββ(x)(x)，如果元素，如果元素ββ的共的共轭轭根系有根系有k k（（k≦mk≦m）个共）个共轭轭元素，元素，则则：：9/16/202428整理整理ppt4.2 预备知识：有限域基础pGF(2GF(2m m) )中元素的最小多中元素的最小多项项式式n最小多最小多项项式的性式的性质质：：1)1)、、GF(2GF(2m m) )上元素上元素ββ的最小多的最小多项项式在式在GF(2)GF(2)上一定是既上一定是既约约的的2)2)、、GF(2GF(2m m) )上本原元的最小多上本原元的最小多项项式一定是式一定是m m次本原多次本原多项项式，非本原元的最小多式，非本原元的最小多项项式是次数小于等于式是次数小于等于m m的既的既约约多多项项式n定理：定理：GF(2)GF(2)上的多上的多项项式式 一定可以分解成一定可以分解成GF(2GF(2m m) )上上所有共所有共轭轭根系的最小多根系的最小多项项式之式之积积。

如果如果GF(2GF(2m m) )上一共有上一共有k k个共个共轭轭根系，根系，则则有：有：9/16/202429整理整理ppt4.2 预备知识：有限域基础p举举例：例：已知已知GF(2)GF(2)上的本原多上的本原多项项式式p(x)=xp(x)=x4 4+x+1+x+1①①、构造、构造扩扩域域GF(2GF(24 4) )，并，并计计算各非零元素算各非零元素的的阶阶②②、找出、找出GF(2GF(24 4) )上各非零元素的共上各非零元素的共轭轭元元（共（共轭轭根系）根系）③③、求出各共、求出各共轭轭根系的最小多根系的最小多项项式式9/16/202430整理整理pptp举举例例——扩扩域域GF(2GF(24 4) )及非零元素的及非零元素的阶阶：：元素元素 多多项项式式 阶阶 元素元素 多多项项式式 阶阶 0 0 α 0 0 α7 7 α α3 3+α+1 15+α+1 15 1 1 1 α 1 1 1 α8 8 α α2 2+1 15+1 15 α α 15 α α α 15 α9 9 α α3 3+α 5+α 5 α α2 2 α α2 2 15 α 15 α1010 α α2 2+α+1 3+α+1 3 α α3 3 α α3 3 5 α 5 α1111 α α3 3+α+α2 2+α 15+α 15 α α4 4 α+1 15 α α+1 15 α1212 α α3 3+α+α2 2+α+1 5+α+1 5 α α5 5 α α2 2+α 3 α+α 3 α1313 α α3 3+α+α2 2+1 15+1 15 α α6 6 α α3 3+α+α2 2 5 α 5 α1414 α α3 3+1 15+1 154.2 预备知识：有限域基础扩扩域域GF(2m)GF(2m)上非零元素上非零元素ααk k的的阶阶一定是一定是2m-12m-1的因子，的因子，阶为阶为：：n=(2m-1)/(k,2m-1)n=(2m-1)/(k,2m-1)。

9/16/202431整理整理ppt4.2 预备知识：有限域基础p举举例例——扩扩域域GF(2GF(24 4) )上的共上的共轭轭根系与最小多根系与最小多项项式：式：共轭根系 α0=1 9/16/202432整理整理ppt4.2 预备知识：有限域基础p举举例例——扩扩域域GF(2GF(24 4) )上的共上的共轭轭根系与最小多根系与最小多项项式：式：共轭根系 α0=1 α, α2, α4, α8 9/16/202433整理整理ppt4.2 预备知识：有限域基础p举举例例——扩扩域域GF(2GF(24 4) )上的共上的共轭轭根系与最小多根系与最小多项项式：式：共轭根系 α0=1 α, α2, α4, α8 α3, α6, α9, α12 9/16/202434整理整理ppt4.2 预备知识：有限域基础p举举例例——扩扩域域GF(2GF(24 4) )上的共上的共轭轭根系与最小多根系与最小多项项式：式：共轭根系 α0=1 α, α2, α4, α8 α3, α6, α9, α12 α5, α10 9/16/202435整理整理ppt4.2 预备知识：有限域基础p举举例例——扩扩域域GF(2GF(24 4) )上的共上的共轭轭根系与最小多根系与最小多项项式：式：共轭根系 α0=1 α, α2, α4, α8 α3, α6, α9, α12 α5, α10 α7, α11, α13, α149/16/202436整理整理ppt4.2 预备知识：有限域基础p举举例例——扩扩域域GF(2GF(24 4) )上的共上的共轭轭根系与最小多根系与最小多项项式：式：共轭根系 最小多项式 α0=1 α, α2, α4, α8 α3, α6, α9, α12 α5, α10 α7, α11, α13, α149/16/202437整理整理ppt4.2 预备知识：有限域基础p举举例例——扩扩域域GF(2GF(24 4) )上的共上的共轭轭根系与最小多根系与最小多项项式：式：共轭根系 最小多项式 α0=1 M0(x) = x+1 α, α2, α4, α8 α3, α6, α9, α12 α5, α10 α7, α11, α13, α149/16/202438整理整理ppt4.2 预备知识：有限域基础p举举例例——扩扩域域GF(2GF(24 4) )上的共上的共轭轭根系与最小多根系与最小多项项式：式：共轭根系 最小多项式 α0=1 M0(x) = x+1 α, α2, α4, α8 M1(x) = x4+x+1 α3, α6, α9, α12 α5, α10 α7, α11, α13, α149/16/202439整理整理ppt4.2 预备知识：有限域基础p举举例例——扩扩域域GF(2GF(24 4) )上的共上的共轭轭根系与最小多根系与最小多项项式：式：共轭根系 最小多项式 α0=1 M0(x) = x+1 α, α2, α4, α8 M1(x) = x4+x+1 α3, α6, α9, α12 M3(x) = x4+x3+x2+x+1 α5, α10 M5(x) = x2+x+1 α7, α11, α13, α149/16/202440整理整理ppt4.2 预备知识：有限域基础p举举例例——扩扩域域GF(2GF(24 4) )上的共上的共轭轭根系与最小多根系与最小多项项式：式：共轭根系 最小多项式 α0=1 M0(x) = x+1 α, α2, α4, α8 M1(x) = x4+x+1 α3, α6, α9, α12 M3(x) = x4+x3+x2+x+1 α5, α10 M5(x) = x2+x+1 α7, α11, α13, α14 M7(x) = x4+x3+19/16/202441整理整理ppt4.2 预备知识：有限域基础p举举例例——扩扩域域GF(2GF(24 4) )上的共上的共轭轭根系与最小多根系与最小多项项式：式：共轭根系 最小多项式 α0=1 M0(x) = x+1 α, α2, α4, α8 M1(x) = x4+x+1 α3, α6, α9, α12 M3(x) = x4+x3+x2+x+1 α5, α10 M5(x) = x2+x+1 α7, α11, α13, α14 M7(x) = x4+x3+1可以验证：x15-1 = M0(x) M1(x) M3(x) M5(x) M7(x)9/16/202442整理整理pptp作作业业：：已知已知GF(2)GF(2)上的本原多上的本原多项项式式p(x)=xp(x)=x4 4+x+x3 3+1+1①①、构造、构造扩扩域域GF(2GF(24 4) )，并，并计计算各非零元素算各非零元素的的阶阶②②、找出、找出GF(2GF(24 4) )上各非零元素的共上各非零元素的共轭轭元元（共（共轭轭根系）根系）③③、求出各共、求出各共轭轭根系的最小多根系的最小多项项式式4.2 预备知识：有限域基础9/16/202443整理整理ppt。