单击此处编辑母版标题样式,*,*,U,niversity of,S,cience and,T,echnology of,C,hina,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,2024/11/17,1,3.1,引言,BCH码是一类最重要的循环码，能订正多个随机错误，它是1959年由Bose、Chaudhuri及Hocquenghem各自独立觉察的二元线性循环码，人们用他们的名字字头命名为BCH码。,在前面的争论中，我们所做的只是构造一个码，然后计算它的最小距离，从而估量出它的纠错力气，而在BCH码中，我们将承受另外一种方法：先说明我们希望它能纠错的个数，然后构造这种码。,2024/11/17,2,3.2 BCH,码简述,假设循环码的生成多项式具有如下形式：,g(x)=LCMm1(x),m3(x),m2t-1(x),其中LCM表示最小公倍式，t为纠错个数，mi(x)为素多项式，则由此生成的循环码称为BCH码，其最小码距 (d0称为设计码距)，它能订正t个随机独立过失。,BCH码的码长n=2m-1或是n=2m-1的因子,本原,BCH,码,非本原,BCH,码,2024/11/17,3,举例说明,例3.1:BCH(15,5)码，可订正3个随机独立过失，即t=3,n=15=2m-1,so m=4,查不行约多项式表可得,m1(x)=(23)8=010011=x4+x+1,m3(x)=(37)8=011111=x4+x3+x2+x+1,m5(x)=(07)8=000111=x2+x+1,这样 g(x)=LCMm1(x),m3(x),m5(x),=(x4+x+1)(x4+x3+x2+x+1)(x2+x+1),=x10+x8+x5+x4+x2+x+1,2024/11/17,4,例3.2:BCH(31,16)码，可订正3个随机独立过失，即t=3,n=31=2m-1,so m=5,查不行约多项式表可得,m1(x)=(45)8=100101=x5+x2+1,m3(x)=(75)8=111101=x5+x4+x3+x2+1,m5(x)=(67)8=110111=x5+x4+x2+x+1,这样 g(x)=LCMm1(x),m3(x),m5(x),=x15+x11+x10+x9+x8+x7+x5,+x3+x2+x+1,2024/11/17,5,局部不行约多项式表,2,阶,1,7,3,阶,1,13,4,阶,1,23,3,37,5,07,5,阶,1,45,3,75,5,67,2024/11/17,6,n,31,的本原,BCH,码,n,k,t,g(x),7,4,1,13,15,11,1,23,15,7,2,721,15,5,3,2467,31,26,1,45,31,21,2,3551,31,16,3,107657,31,11,5,5423325,31,6,7,313365047,2024/11/17,7,局部非本原BCH码,n,k,d,g(x),17,9,5,727,21,16,3,43,21,12,5,1663,21,6,7,126357,21,4,9,643215,23,12,7,5343,25,5,5,4102041,27,9,3,1001001,27,7,6,7007007,33,6,7,3043,2024/11/17,8,3.3,有限域,一个元素个数有限的域称为有限域，或者伽罗华域(Galois field);,有限域中元素的个数为一个素数，记为GF(p),其中p为素数；,一个大于1的整数，假设它的正因数只有1和它本身，就叫做素数，否则就叫做合数。,有限域中运算满足,交换律:a+b=b+a,ab=b a,结合律:(a+b)+c=a+(b+c),a(bc)=(ab)c,和安排律:a(b+c)=a b+a c,2024/11/17,9,可以将GF(p)延长为一个含有pm个元素的域，称为GF(p)的扩展域，表示为GF(pm)，m是一个非零正整数。留意：GF(p)是GF(pm)的子集。,二进制域GF(2)是扩展域GF(2m)的一个子域，类似于实数域是复数域的一个子域一样。除了数字0和1之外，在扩展域中还有特殊的元素，用一个新的符号a表示。GF(2m)中任何非0元素都可由a的幂次表示。,2024/11/17,10,有限元素的集合GF(2m)，只能含有2m个元素，并且对乘法封闭，其约束条件为：,依据这个多项式限制条件，任何幂次等于或超过2m-1的域元素都可降阶为下述幂次小于2m-1的元素：,这样，GF(2m)的元素可表示为：,2024/11/17,11,扩展域,GF(2,m,),中的加法,在GF(2m)中，将每个非0元素用多项式ai(x)表示，其系数至少有一个不为0。对于i=0,1,2,2m-2，有：,ai=ai(x),=ai,0+ai,1x+ai,2x2+ai,m-1xm-1,考虑m=3,有限域表示为GF(23),下表为上式描述的根本元素x0,x1,x2映射为7个元素ai和一个0元素。表中的各行是二进制数字序列，代表上式中的系数ai,0、ai,1、ai,2的取值。,2024/11/17,12,域,元,素,基本元素,x,0,x,1,x,2,0,0,0,0,a,0,1,0,0,a,1,0,1,0,a,2,0,0,1,a,3,1,1,0,a,4,0,1,1,a,5,1,1,1,a,6,1,0,1,a,7,1,0,0,多项式为f(x)=1+x+x3的GF(8)的元素与根本元素之间的映射,2024/11/17,13,有限域中两个元素的加法定义为两个多项式中同幂次项系数进展模2加，即,ai+aj=(ai,0+aj,0)+(ai,1+aj,1)x+,+(ai,m-1+aj,m-1)xm-1,有限域的本原多项式：由于这些函数用来定义有限域GF(2m)。,一个多项式是本原多项式的充要条件：一个m阶的不行约多项式f(x)，假设f(x)整除xn+1的最小正整数n满足n=2m-1，则该多项式是本原的。,2024/11/17,14,例3.3 本原多项式的区分,(1)p1(x)=1+x+x4,(2)p2(x)=1+x+x2+x3+x4,分析:(1)通过验证这个幂次为m=4的多项式是否能够整除 ,但不能整除1n2时所建立的码长为n=q-1的q进制BCH码，称为RS码。当q=2m(m1)，码元符号取自域GF(2m)的二进制RS码可用来订正突发错误。,输入信息分为k*m比特一组，即每个符号有m比特，k个符号形成一组。,2024/11/17,45,一个可纠t个符号错误的RS码，有如下参数,码长：n=2m-1 符号 或 m(2m-1)bit,信息段：k 符号 或 km bit,监视段：n-k=2t 符号 或 m(n-k)=2mt bit,最小码距：d=2t+1 符号 或 md=m(2t+1)bit,例3.8 试构造一个能纠3个错误符号，码长n=15,m=4的RS码。,解：t=3,n=15,m=4,所以有,码距：d=2t+1=7个符号(28bit),监视段：2t=6个符号(24bit),信息段：n-6=9个符号(36bit),码长：n=15个符号(60bit),因此该码是(15,9)RS码，也可看作是(60,36)二进制码；,2024/11/17,46,最小距离为,d,的,RS,码生成多项式应具有如下形式：,g(x)=(x+a)(x+a,2,)(x+a,d-1,),本例中，,d=7,g(x)=(x+a)(x+a,2,)(x+a,6,),=x,6,+a,10,x,5,+a,14,x,4,+a,4,x,3,+a,6,x,2,+a,9,x+a,6,其中,a,i,是,GF(q),中的一个元素。,RS,码生成多项式的次数总是,2t,！,