第四章 BCH码-1ppt课件

通信工程系移动通信教研室,信道编码,29.04.2020,.,2,第四章BCH码,4.1BCH码概述4.2预备知识：有限域基础4.3BCH码的构造4.4BCH码的编码4.5BCH码的译码,29.04.2020,.,3,本章要求,了解BCH码的提出与发展掌握：扩域GF(2m)的概念、构造及域元素的运算BCH码的基本概念与构造方法BCH码的编码方法与迭代译码算法,29.04.2020,.,4,第四章BCH码,4.1BCH码概述4.2预备知识：有限域基础4.3BCH码的构造4.4BCH码的编码4.5BCH码的译码,29.04.2020,.,5,4.1BCH码概述,BCH码的提出与发展1959年，霍昆格姆(Hocquenghem)，1960年博斯(Bose)和查德胡理(Chaudhuri)，各自独立地提出了二元BCH码的构造方法。1960年，彼得森(Peterson)从理论上提出了二元BCH码的译码算法。1966年，伯利坎普(Berlekamp)提出了BCH码的迭代译码算法，使BCH码进入实用。七十年代以后BCH码得到了极为广泛的应用，如磁记录、CD/VCD/DVD、深空及卫星通信等。,29.04.2020,.,6,4.1BCH码概述,BCH码的提出与发展对BCH码的后续研究主要集中在译码算法的简化，如减少迭代次数、快速译码算法、提高纠错能力、软判决译码等。,29.04.2020,.,7,4.1BCH码概述,BCH码的特点BCH码是线性分组码的重要子类，再具体讲，是循环码子类。BCH码具有构造方便、编码简单以及译码易于实现等优点，而且BCH码有完备的代数理论支持。BCH码的生成多项式与最小距离d有密切关系，使设计者可以根据d的需要轻易构造出具有预定纠错能力的编码方案。纠错能力强，中短码长下的性能接近理论值。,BCH码是迄今为止研究最为详尽、分析最为透彻、取得成果最多、应用最为广泛的码类之一。,29.04.2020,.,8,第四章BCH码,4.1BCH码概述4.2预备知识：有限域基础4.3BCH码的构造4.4BCH码的编码4.5BCH码的译码,29.04.2020,.,9,4.2预备知识：有限域基础,有限域的基本概念GF(2)上的多项式GF(2)的扩域GF(2m)用m次本原多项式构造扩域GF(2m)扩域GF(2m)的表示方式扩域GF(2m)的性质GF(2m)中元素的最小多项式,29.04.2020,.,10,4.2预备知识：有限域基础,有限域的基本概念域的定义：对于非空元素集合F，若定义两种代数运算”+”和“*”，且满足以下条件：1)、F关于“+”运算构成交换群2)、F中全体非0元素对“*”运算构成交换群3)、两种运算满足分配律则称F构成域。如果F中元素个数有限，则称该域为有限域或伽罗华(Galois)域，记为GF(q)。,29.04.2020,.,11,4.2预备知识：有限域基础,有限域的基本概念例：集合0,1对模2加和模2乘构成二元域，记为GF(2)；例：如果q为素数，则集合0,1,q-1对模q加和乘构成q元域GF(q)；,29.04.2020,.,12,4.2预备知识：有限域基础,有限域的基本概念有限域的生成元：对于GF(q)，其中一定存在非0元素g，其各次幂能生成域中的所有非0元素，则g称为该域的生成元或本原元。,例如：GF(5)=0,1,2,3,4中，g=1g01g11g21g31g=2g01g12g24g33g=3g01g13g24g32g=4g01g14g21g34,生成元,29.04.2020,.,13,4.2预备知识：有限域基础,有限域的基本概念GF(q)中元素的阶：由GF(q)中元素的幂所能生成域元素的个数称为该元素的阶。例如：GF(5)中，2、3的阶为4；1的阶为1；4的阶为2定理：有限域GF(q)中，本原元的阶为q-1，其余非零元素的阶均为q-1的因子。说明：后面我们仅讨论二元域GF(2)及其扩域GF(2q)，所有结论均可推广到q元域GF(q)。,29.04.2020,.,14,4.2预备知识：有限域基础,GF(2)上的多项式GF(2)上的多项式：系数取自GF(2)的多项式如：f(x)=x+1、f(x)=x3+x+1等定理：若f(x)是GF(2)上的m次多项式，则：既约多项式：如果GF(2)上的m次多项式f(x)除了1和它本身之外不能被其它多项式整除，则称f(x)为GF(2)上的既约多项式。,29.04.2020,.,15,4.2预备知识：有限域基础,GF(2)上的多项式多项式的周期：多项式f(x)的周期定义为f(x)能整除xn-1的最小的n本原多项式：如果GF(2)上的m次既约多项式f(x)=xm+fm-1xm-1+f1x+1的周期为n=2m-1，则称f(x)为GF(2)上的m次本原多项式。本原多项式一定是既约的，既约多项式未必是本原的。反多项式：设f(x)是GF(2)上的m次多项式，则f*(x)=xmf(x-1)称为f(x)的反多项式。如果多项式f(x)是既约多项式，则其反多项式f*(x)一定是既约多项式；如果多项式f(x)是本原多项式，则其反多项式f*(x)也一定是本原多项式。,29.04.2020,.,16,4.2预备知识：有限域基础,GF(2)的扩域GF(2m)扩域GF(2m)：设p(x)为GF(2)上的m次既约多项式，模p(x)的所有2m个余式在模p(x)加法和乘法下构成2m元域，称为GF(2)的扩域(也称为模p(x)的剩余类域)，记为GF(2m)。例如：设p(x)=x3+x+1，则：0,1,x,x2,x+1,x2+x,x2+x+1,x2+1构成扩域GF(23)。,29.04.2020,.,17,4.2预备知识：有限域基础,GF(2)的扩域GF(2m)GF(2)=0,1称为GF(2m)的基域。注意：GF(23)不能写成GF(8)，其含义不同。GF(q)表示的是数域，而GF(qm)则是多项式域、GF(q)的扩域。不同的m次既约多项式的剩余类域是同构的,29.04.2020,.,18,4.2预备知识：有限域基础,GF(2)的扩域GF(2m)定理1：如果p(x)是GF(2)上的m次本原多项式，则扩域GF(2m)的所有非零元素在模p(x)乘运算下构成循环群。,若一个群G的每个元都是G中的某个固定元的次幂，则称G为循环群，也称G是由生成的群，记为G=()。,29.04.2020,.,19,4.2预备知识：有限域基础,GF(2)的扩域GF(2m)定理1：如果p(x)是GF(2)上的m次本原多项式，则扩域GF(2m)的所有非零元素在模p(x)乘运算下构成循环群。例如：设p(x)=x3+x+1，则：0,1,x,x2,x+1,x2+x,x2+x+1,x2+1构成扩域GF(23)。其中(x+1)的各次幂对p(x)取模，可以生成扩域集合中的所有非0多项式，所以该扩域中所有非零元素在模p(x)运算下构成循环群。(x+1)0=1；(x+1)1=x+1；(x+1)2=x2+1；(x+1)3=x2(x+1)4=x2+x+1；(x+1)5=x；(x+1)6=x2+x；,29.04.2020,.,20,4.2预备知识：有限域基础,GF(2)的扩域GF(2m)推论：扩域GF(2m)中至少存在一个本原元(代表一个次数小于m的多项式)，其各次幂0,1,2,构成GF(2m)的全部非零元素。定理2：GF(2)上的m次本原多项式p(x)在扩域GF(2m)上一定有根，假设其根为，则一定是本原元。根据以上定理，我们可以用GF(2)上的m次本原多项式p(x)来构造扩域GF(2m)。,29.04.2020,.,21,4.2预备知识：有限域基础,用m次本原多项式构造扩域GF(2m)构造扩域GF(2m)的步骤：找一个GF(2)上的m次本原多项式p(x)令为P(x)在GF(2m)上的根取的各次幂0,1,2,构成GF(2m)的全部非零元素加上零元素0即构成扩域GF(2m)例如：用本原多项式p(x)=x3+x+1和p(x)=x3+x2+1分别构造扩域GF(23),29.04.2020,.,22,4.2预备知识：有限域基础,用m次本原多项式构造扩域GF(2m),GF(23)/p(x)=x3+x+10,0=1,1=,2=2,3=+14=2+,5=2+1,6=2+1,GF(23)/p(x)=x3+x2+10,0=1,1=,2=2,3=2+1,4=2+1,5=+1,6=2+,29.04.2020,.,23,4.2预备知识：有限域基础,扩域GF(2m)的表示方式,GF(23)/p(x)=x3+x+100000010011010221003+101142+11052+111162+1101,GF(23)/p(x)=x3+x2+1000000100110102210032+110142+11115+101162+110,29.04.2020,.,24,4.2预备知识：有限域基础,扩域GF(2m)的性质定理1：扩域GF(2m)上非零元素k的阶一定是2m-1的因子，阶为：n=(2m-1)/(k,2m-1)。其中：(k,2m-1)表示k和2m-1的最大公约数。例如：GF(23)中，0的阶为1，其余非零元素的阶均为7。GF(24)中，定义：如果GF(2m)中元素k的阶小于2m-1，则称该元素为非本原元。,29.04.2020,.,25,4.2预备知识：有限域基础,扩域GF(2m)的性质定理2：扩域GF(2m)上的所有非零元素都是GF(2)上多项式在扩域GF(2m)上的根。即：例如：在扩域GF(23)上可以验证：x7-1=(x-1)(x-)(x-2)(x-3)(x-4)(x-5)(x-6),29.04.2020,.,26,4.2预备知识：有限域基础,扩域GF(2m)的性质定理3：如果f(x)是GF(2)上的多项式，是扩域GF(2m)中元素，则有：例如：GF(23)/p(x)=x3+x+1上：F(x)=x2+x(2+)2=4+2=2+2=,0,0=1,1=,2=2,3=+1,4=2+,5=2+1,6=2+1,29.04.2020,.,27,4.2预备知识：有限域基础,扩域GF(2m)的性质定理4：如果GF(2m)中元素是二元多项式f(x)在GF(2m)上的根，则：的2j（j=1,2,）次幂也一定是f(x)在GF(2m)上的根。例如：GF(23)/p(x)=x3+x+1上：是p(x)=x3+x+1的根，2,4,8=同样是p(x)在GF(23)上的根。即：P()=P(2)=P(4)=0费尔马定理：如果是扩域GF(2m)上的非零元素，则有：,29.04.2020,.,28,4.2预备知识：有限域基础,GF(2m)中元素的最小多项式共轭根系：如果扩域元素是GF(2)上多项式f(x)的根，则也一定是f(x)的根，称为一个共轭根系。一个共轭根系至多包含m个共轭元素。最小多项式：以扩域GF(2m)上的非零元素为根的最低次多项式称为的最小多项式，记为M(x)，如果元素的共轭根系有k（km）个共轭元素，则：,29.04.2020,.,29,4.2预备知识：有限域基础,GF(2m)中元素的最小多项式最小多项式的性质：1)、GF(2m)上元素的最小多项式在GF(2)上一定是既约的。2)、GF(2m)上本原元的最小多项式一定是m次本原多项式，非本原元的最小多项式是次数小于等于m的既约多项式。定理：GF(2)上的多项式一定可以分解成GF(2m)上所有共轭根系的最小多项式之积。如果GF(2m)上一共有k个共轭根系，则有：,29.04.2020,.,30,4.2预备知识：有限域基础,举例：已知GF(2)上的本原多项式p(x)=x4+x+1、构造扩域GF(24)，并计算各非零元素的阶、找出GF(24)上各非零元素的共轭元（共轭根系）、求出各共轭根系的最小多项式,29.04.2020,.,31,举例扩域GF(24)及非零元素的阶：元素多项式阶元素多项式阶0073+11511182+1151593+52215102+13335113+2+154+115123+2+1552+3133+2+11563+25143+115,4.2预备知识：有限域基础,扩域GF(2m)上非零元素k的阶一定是2m-1的因子，阶为：n=(2m-1)/(k,2m-1)。,29.04.2020,.,32,4.2预备知识：有限域基础,举例扩域GF(24)上的共轭根系与最小多项式：共轭根系0=1,29.04.2020,.,33,4.2预备知识：有限域基础,举例扩域GF(24)上的共轭根系与最小多项式：共轭根系0=1,2,4,8,29.04.2020,.,34,4.2预备知识：有限域基础,举例扩域GF(24)上的共轭根系与最小多项式：共轭根系0=1,2,4,83,6,9,12,29.04.2020,.,35,4.2预备知识：有限域基础,举例扩域GF(24)上的共轭根系与最小多项式：共轭根系0=1,2,4,83,6,9,125,10,29.04.2020,.,36,4.2预备知识：有限域基础,举例扩域GF(24)上的共轭根系与最小多项式：共轭根系0=1,2,4,83,6,9,125,107,11,13,14,29.04.2020,.,37,4.2预备知识：有限域基础,举例扩域GF(24)上的共轭根系与最小多项式：共轭根系最小多项式0=1,2,4,83,6,9,125,107,11,13,14,29.04.2020,.,38,4.2预备知识：有限域基础,举例扩域GF(24)上的共轭根系与最小多项式：共轭根系最小多项式0=1M0(x)=x+1,2,4,83,6,9,125,107,11,13,14,29.04.2020,.,39,4.2预备知识：有限域基础,举例扩域GF(24)上的共轭根系与最小多项式：共轭根系最小多项式0=1M0(x)=x+1,2,4,8M1(x)=x4+x+13,6,9