1、University of Science and Technology of China2023-1-301Coding Theory周武旸周武旸中国科学技术大学中国科学技术大学 个人通信与扩频实验室个人通信与扩频实验室University of Science and Technology of China2023-1-302第三章第三章 BCH码码3.1 引言引言3.2 BCH码简述码简述3.3 有限域有限域3.4 BCH码的编码码的编码3.5 BCH码的译码码的译码3.6 戈雷戈雷(Golay)码码3.7 Reed-Solomon码码University of Science and
2、Technology of China2023-1-3033.1 引言引言BCH码是一类最重要的循环码，能纠正多个码是一类最重要的循环码，能纠正多个随 机 错 误，它 是随 机 错 误，它 是 1 9 5 9 年 由年 由 B o s e、Chaudhuri及及Hocquenghem各自独立发各自独立发现的二元线性循环码，人们用他们的名字字头现的二元线性循环码，人们用他们的名字字头命名为命名为BCH码。码。在前面的讨论中，我们所做的只是构造一个码，在前面的讨论中，我们所做的只是构造一个码，然后计算它的最小距离，从而估计出它的纠错然后计算它的最小距离，从而估计出它的纠错能力，而在能力，而在BCH
3、码中，我们将采用另外一种码中，我们将采用另外一种方法：先说明我们希望它能纠错的个数，然后方法：先说明我们希望它能纠错的个数，然后构造这种码。构造这种码。University of Science and Technology of China2023-1-3043.2 BCH码简述码简述若循环码的生成多项式具有如下形式：若循环码的生成多项式具有如下形式：g(x)=LCMm1(x),m3(x),m2t-1(x)其中其中LCM表示最小公倍式，表示最小公倍式，t为纠错个数，为纠错个数，mi(x)为素多项式，则由此生成的循环码称为为素多项式，则由此生成的循环码称为BCH码，其最小码距码，其最小码距 (
4、d0称为称为设计码距设计码距)，它能纠正，它能纠正t个随机独立差错。个随机独立差错。BCH码的码长码的码长n=2m-1或是或是n=2m-1的因子的因子120tdd本原本原BCH码码非本原非本原BCH码码University of Science and Technology of China2023-1-305举例说明举例说明例例3.1:BCH(15,5)码，可纠正码，可纠正3个随机独立个随机独立差错，即差错，即t=3 n=15=2m-1,so m=4查不可约多项式表可得查不可约多项式表可得m1(x)=(23)8=010011=x4+x+1m3(x)=(37)8=011111=x4+x3+x2
5、+x+1m5(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+17132120tddUniversity of Science and Technology of China2023-1-306例例3.2:BCH(31,16)码，可纠正码，可纠正3个随机独立个随机独立差错，即差错，即t=3 n=31=2m-1,so m=5查不可约多项式表可得查不可约多项式表可得m1(x)=(45)8=100101=x5+x2+1m3(x)=(75)8=11
6、1101=x5+x4+x3+x2+1m5(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+17132120tddUniversity of Science and Technology of China2023-1-307部分不可约多项式表部分不可约多项式表2阶阶173阶阶1134阶阶1233375075阶阶145375567University of Science and Technology of China2023-1-308n 31的本原的本原BCH
7、码码nktg(x)7411315111231572721155324673126145312123551311631076573111554233253167313365047University of Science and Technology of China2023-1-309部分非本原部分非本原BCH码码nkdg(x)179572721163432112516632167126357214964321523127534325554102041279310010012776700700733673043University of Science and Technology of Ch
8、ina2023-1-30103.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+
9、a cUniversity of Science and Technology of China2023-1-3011可以将可以将GF(p)延伸为一个含有延伸为一个含有pm个元素的域，个元素的域，称为称为GF(p)的扩展域，表示为的扩展域，表示为GF(pm)，m是是一个非零正整数。注意：一个非零正整数。注意：GF(p)是是GF(pm)的的子集。子集。二进制域二进制域GF(2)是扩展域是扩展域GF(2m)的一个子域，的一个子域，类似于实数域是复数域的一个子域一样。除了类似于实数域是复数域的一个子域一样。除了数字数字0和和1之外，在扩展域中还有特殊的元素，之外，在扩展域中还有特殊的元素，用一个新的
10、符号用一个新的符号a表示。表示。GF(2m)中任何非中任何非0元素都可由元素都可由a的幂次表示。的幂次表示。University of Science and Technology of China2023-1-3012有限元素的集合有限元素的集合GF(2m)，只能含有，只能含有2m个元个元素，并且对乘法封闭，其约束条件为：素，并且对乘法封闭，其约束条件为：根据这个多项式限制条件，任何幂次等于或超根据这个多项式限制条件，任何幂次等于或超过过2m-1的域元素都可降阶为下述幂次小于的域元素都可降阶为下述幂次小于2m-1的元素：的元素：这样，这样，GF(2m)的元素可表示为：的元素可表示为：01)1
11、2(ma11)12()2(nnnaaaamm,0)2(22210maaaaGFmUniversity of Science and Technology of China2023-1-3013扩展域扩展域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,x
12、2映射为映射为7个元素个元素ai和一个和一个0元素。表中的各行是二进制数字元素。表中的各行是二进制数字序列，代表上式中的系数序列，代表上式中的系数ai,0、ai,1、ai,2的取的取值。值。University of Science and Technology of China2023-1-3014域域元元素素基本元素基本元素x0 x1x20000a0100a1010a2001a3110a4011a5111a6101a7100多项式为多项式为f(x)=1+x+x3的的GF(8)的元素与的元素与基本元素之间的映射基本元素之间的映射University of Science and Techno
13、logy of China2023-1-3015有限域中两个元素的加法定义为两个多项式中有限域中两个元素的加法定义为两个多项式中同幂次项系数进行模同幂次项系数进行模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，则该多项式是
14、，则该多项式是本原的。本原的。University of Science and Technology of China2023-1-3016例例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码可用来纠正突码可用来纠正突发错误
15、。发错误。输入信息分为输入信息分为k*m比特一组，即每个符号有比特一组，即每个符号有m比特，比特，k个符号形成一组。个符号形成一组。University of Science and Technology of China2023-1-3047一个可纠一个可纠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 试构造一个
16、能纠试构造一个能纠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)二进制码；二进制码；University of Science and Technology of China2023-1-3048最小距离为最小距离为d的的RS码生成多项式应具有如下形式：码生成多项式应具有如下形式：g(x)=(x+a)(x+a2)(x+ad-1)本例中，本例中，d=7 g(x)=(x+a)(x+a2)(x+a6)=x6+a10 x5+a14x4+a4x3+a6x2+a9x+a6其中其中ai是是GF(q)中的一个元素。中的一个元素。RS码生成多项式的次数总是码生成多项式的次数总是2t！
