ECC-BCH-编码-原理

UniversityofScienceandTechnologyofChina2019/12/213.1引言BCH码是一类最重要的循环码，能纠正多个随机错误，它是1959年由Bose、Chaudhuri及Hocquenghem各自独立发现的二元线性循环码，人们用他们的名字字头命名为BCH码。在前面的讨论中，我们所做的只是构造一个码，然后计算它的最小距离，从而估计出它的纠错能力，而在BCH码中，我们将采用另外一种方法：先说明我们希望它能纠错的个数，然后构造这种码。UniversityofScienceandTechnologyofChina2019/12/223.2BCH码简述若循环码的生成多项式具有如下形式：g(x)=LCM[m1(x),m3(x),…,m2t-1(x)]其中LCM表示最小公倍式，t为纠错个数，mi(x)为素多项式，则由此生成的循环码称为BCH码，其最小码距(d0称为设计码距)，它能纠正t个随机独立差错。BCH码的码长n=2m-1或是n=2m-1的因子120tdd本原BCH码非本原BCH码UniversityofScienceandTechnologyofChina2019/12/23举例说明例3.1:BCH(15,5)码，可纠正3个随机独立差错，即t=3n=15=2m-1,som=4查不可约多项式表可得m1(x)=(23)8=010011=x4+x+1m3(x)=(37)8=011111=x4+x3+x2+x+1m5(x)=(07)8=000111=x2+x+1这样g(x)=LCM[m1(x),m3(x),m5(x)]=(x4+x+1)(x4+x3+x2+x+1)(x2+x+1)=x10+x8+x5+x4+x2+x+17132120tddUniversityofScienceandTechnologyofChina2019/12/24例3.2:BCH(31,16)码，可纠正3个随机独立差错，即t=3n=31=2m-1,som=5查不可约多项式表可得m1(x)=(45)8=100101=x5+x2+1m3(x)=(75)8=111101=x5+x4+x3+x2+1m5(x)=(67)8=110111=x5+x4+x2+x+1这样g(x)=LCM[m1(x),m3(x),m5(x)]=x15+x11+x10+x9+x8+x7+x5+x3+x2+x+17132120tddUniversityofScienceandTechnologyofChina2019/12/25部分不可约多项式表2阶173阶1134阶1233375075阶145375567UniversityofScienceandTechnologyofChina2019/12/26n≤31的本原BCH码nktg(x)7411315111231572721155324673126145312123551311631076573111554233253167313365047UniversityofScienceandTechnologyofChina2019/12/27部分非本原BCH码nkdg(x)179572721163432112516632167126357214964321523127534325554102041279310010012776700700733673043UniversityofScienceandTechnologyofChina2019/12/283.3有限域一个元素个数有限的域称为有限域，或者伽罗华域(Galoisfield);有限域中元素的个数为一个素数，记为GF(p),其中p为素数；一个大于1的整数，如果它的正因数只有1和它本身，就叫做素数，否则就叫做合数。有限域中运算满足交换律:a+b=b+a,a·b=b·a结合律:(a+b)+c=a+(b+c),a·(b·c)=(a·b)·c和分配律:a·(b+c)=a·b+a·cUniversityofScienceandTechnologyofChina2019/12/29可以将GF(p)延伸为一个含有pm个元素的域，称为GF(p)的扩展域，表示为GF(pm)，m是一个非零正整数。注意：GF(p)是GF(pm)的子集。二进制域GF(2)是扩展域GF(2m)的一个子域，类似于实数域是复数域的一个子域一样。除了数字0和1之外，在扩展域中还有特殊的元素，用一个新的符号a表示。GF(2m)中任何非0元素都可由a的幂次表示。UniversityofScienceandTechnologyofChina2019/12/210有限元素的集合GF(2m)，只能含有2m个元素，并且对乘法封闭，其约束条件为：根据这个多项式限制条件，任何幂次等于或超过2m-1的域元素都可降阶为下述幂次小于2m-1的元素：这样，GF(2m)的元素可表示为：01)12(ma11)12()2(nnnaaaamm},,,,,0{)2(22210maaaaGFmUniversityofScienceandTechnologyofChina2019/12/211扩展域GF(2m)中的加法在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的取值。UniversityofScienceandTechnologyofChina2019/12/212域元素基本元素x0x1x20000a0100a1010a2001a3110a4011a5111a6101a7100多项式为f(x)=1+x+x3的GF(8)的元素与基本元素之间的映射UniversityofScienceandTechnologyofChina2019/12/213有限域中两个元素的加法定义为两个多项式中同幂次项系数进行模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，则该多项式是本原的。UniversityofScienceandTechnologyofChina2019/12/214例3.3本原多项式的辨别(1)p1(x)=1+x+x4(2)p2(x)=1+x+x2+x3+x4分析:(1)通过验证这个幂次为m=4的多项式是否能够整除,但不能整除1≤n15范围内的xn+1，就可以确定它是否为本原多项式。经反复计算，p1(x)是本原多项式，p2(x)不是，因为它能整除x5+1。1111512xxxmnUniversityofScienceandTechnologyofChina2019/12/215部分本原多项式mm31+x+x3111+x2+x1141+x+x4121+x+x4+x6+x1251+x2+x5131+x+x3+x4+x1361+x+x6141+x+x6+x10+x1471+x3+x7151+x+x1581+x2+x3+x4+x8161+x+x3+x12+x1691+x4+x9171+x3+x17101+x3+x10181+x7+x18UniversityofScienceandTechnologyofChina2019/12/216考虑一个本原多项式定义的有限域的例子选择p(x)=1+x+x3，多项式的幂次为m=3,所以由p(x)所定义的域中包含了2m=23=8个元素。求解p(x)的根就是指找到x使p(x)=0。我们所熟悉的二进制数0和1不能满足，因为p(1)=1,p(0)=1(运用模2运算)。由基本代数学理论我们知道，对于幂次为m的多项式必然有m个根。对于这个例子，p(x)=0有3个根，由于这3个根不可能位于与p(x)系数相同的有限域中，而是位于扩展域GF(23)中。用扩展域的元素a来定义多项式p(x)的根，可写成如下形式：p(a)=0UniversityofScienceandTechnologyofChina2019/12/217即1+a+a3=0a3=1+a这意味着a3可以表示为更低阶a项的加权和。类似地有：a4=a*a3=a*(1+a)=a+a2a5=a*a4=a*(a+a2)=a2+a3=1+a+a2a6=a*a5=a*(1+a+a2)=a+a2+a3=1+a2a7=a*a6=a*(1+a2)=a+a3=1=a0所以，有限域GF(23)的8个元素为{0,a0,a1,a2,a3,a4,a5,a6}UniversityofScienceandTechnologyofChina2019/12/218这8个元素中哪些是p(x)=0的3个根呢？我们可通过枚举找到！p(a0)=1,a0不是p(a1)=1+a+a3=0,a1是p(a2)=1+a2+a6=1+a0=0,a2是p(a3)=1+a3+a9=1+a3+a2=1+a5=a4,a3不是p(a4)=1+a4+a12=1+a4+a5=1+a0=0,a4是同理可计算p(a5)、p(a6)都不等于0，所以p(x)=1+x+x3的3个根是a,a2,a4UniversityofScienceandTechnologyofChina2019/12/219p(x)=1+x+x3,GF(8)加法运算表+a0a1a2a3a4a5a6a00a3a6a1a5a4a2a1a30a4a0a2a6a5a2a6a40a5a1a3a0a3a1a0a50a6a2a4a4a5a2a1a60a0a3a5a4a6a3a2a00a1a6a2a5a0a4a3a10UniversityofScienceandTechnologyofChina2019/12/220p(x)=1+x+x3,GF(8)乘法运算表×a0a1a2a3a4a5a6a0a0a1a2a3a4a5a6a1a1a2a3a4a5a6a0a2a2a3a4a5a6a0a1a3a3a4a5a6a0a1a2a4a4a5a6a0a1a2a3a5a5a6a0a1a2a3a4a6a6a0a1a2a3a4a5UniversityofScienceandTechnologyofChina2019/12/221如果GF(p)上的所有元素(除0外)都可表示为某元素a的幂，则a称为GF(p)上的本原元。例3.4考虑GF(5)，因为p=5是个素数，模算数可以进行。考虑该域上的元素2，20=1(mod5)=1,21=2(mod5)=222=4(mod5)=4,23=8(mod5)=3因此，所有GF(5)上的非零元素，即{1,2,3,4}都可以表示成2的幂，故2是GF(5)上的本原元；大家可以验证，3也是GF(5)上的本原元。UniversityofScienceandTechnologyofChina2019/12/222GF(pm)中，在模p(x)运算下的扩域上，x所表示的元素是本原元。例如:用本原多项式p(x)=1+x+x3来构造GF(8)，设GF(8)上的本原元为a,通过将a的幂模p(a)得到GF(8)上的所有元素。a的幂GF(8)上的元素a01a1aa2a2a3a+1a4a2+aa5a2+a+1a6a2+1UniversityofScienceandTechnologyofChina2019/12/223定理:设b1,b2,…,bp-1为GF(p)上的非零域元素，则xp-1+1=(x+b1)(x+b2)…(x+bp-1)从循环码知识我们知道，为了找到分组长度为n的循环码的生成多项式，首先