信息论和编码第六章.ppt
86页
CompanyLOGO第六章循环码循环码 主要内容1234循环码的码多项式循环码的码多项式循环码的码多项式循环码的码多项式循环码编码循环码编码循环码编码循环码编码CRCCRC码码码码RSRS码码码码BCHBCH码码码码65乘法电路乘法电路乘法电路乘法电路 一、循环码的码多项式 例例4.1.1 汉明循环码C的生成矩阵G和校验矩阵H 依次令m=(0000) …(1111)代入方程C＝＝mG 可得16个码字经分析，将16个码字归结为4个循环环 第一循环 第二循环 第三循环 第四循环 (1011000) (1110100) (0000000) (1111111) (0110001) (1101001) (1100010) (1010011) (1000101) (0100111) (0001011) (1001110) (0010110) (0011101) (0101100) (0111010) 循环码的多项式描述循环码的多项式描述GF(2)上n维矢量空间Vn中的任一矢量V= (vn-1,…,v1,v0) vi GF(2) 可与GF(2)域上多项式V(x) 一一对应如下：V= (vn-1,…,v1,v0) V(x)= vn-1 xn-1+…+v1 x+v0多项式的各系数就是矢量各元素的值，x的幂次指示对应元素所在位置。
码空间是矢量空间Vn的一个子空间，因此n重矢量不一定是码矢量，n次多项式不一定是码多项式位于码空间的矢量叫码矢，对应的多项式为码多项式我们约定：以下所说的码字、码组、码矢和码多项式等术语具有相同的物理意义，只是描述角度和表达方式不同而已 码码矢矢C0= (cn-1,…,c1,c0) 右右循循环环一一位位C1= (cn-2,…,c1, c0, cn-1,)也是码矢它们各自对应的码多项式是也是码矢它们各自对应的码多项式是:C0(x)= cn-1 xn-1+ cn-2 xn-2+…+c1 x+c0C1(x)= cn-2 xn-1+ cn-3 xn-2+…+c0 x+cn-1比较两者，可知比较两者，可知C1(x)=xC0(x), mod (xn +1) (4-2)以以此此类类推推，，循循环环码码循循环环移移2位位、、移移3位位、、移移n-1位位后后仍然应是码字仍然应是码字, 于是得到下面一系列等式：于是得到下面一系列等式： C2(x)= xC1(x) = x2C0(x), mod (xn +1) C3(x)= xC2(x) = x3C0(x), mod (xn +1) : : C n-1 (x)= xC n-2(x) = xn-1C0(x), mod (xn +1) 由由码码空空间间的的封封闭闭性性，，可可知知码码多多项项式式C0(x),…, C n-1(x)的的线性组合仍应是码多项式：线性组合仍应是码多项式：C(x)=an-1xn-1C0(x)+an-2xn-2C0(x)+…+a1xC0(x)+a0C0(x) = (an-1 xn-1+ an-2 xn-2+…+a1 x+a0)C0(x) = A(x) C0(x) mod (xn +1) (4-3) C0(x)是是码码多多项项式式，，A(x)是是n-1次次多多项项式式，，但但不不一一定定是是码码多多项项式式。
式式(4-3)给给出出的的结结论论是是：：码码多多项项式式与与任任意意n -1次多项式作运算后，结果一定回落到码空间次多项式作运算后，结果一定回落到码空间 二、循环码编码 定定理理4. 2 在在一一个个GF(2)域域上上的的 (n, k)循循环环码码中中，，一一定定存在唯一的一个次数最低的存在唯一的一个次数最低的(n-k)次次首一码多项式首一码多项式g(x) = xn-k+ gn-k -1 x n-k -1+…+g1 x+1使使所所有有码码多多项项式式都都是是g(x)的的倍倍式式，，且且所所有有小小于于n次次的的g(x)的倍式都是码多项式的倍式都是码多项式 即即 C(x)＝＝m(x)g(x) 及及 g(x)| C(x)““所有小于所有小于n次的次的g(x)的倍式都是码多项式的倍式都是码多项式” 意味意味着着m(x)g(x)一定是码字，其中一定是码字，其中m(x)是是GF(2)上小于上小于k次的任意多项式，以致它与次的任意多项式，以致它与(n-k)次的次的g(x)相乘后所相乘后所得倍式的次数一定小于得倍式的次数一定小于n次 定理定理4. 3 (n，，k)循环码的生成多项式循环码的生成多项式g(x)一定是一定是(xn-1)的因式，即一定存在一个多项式的因式，即一定存在一个多项式h(x)，，满足满足(xn-1)＝＝g(x) h(x) 或或 g(x)| (xn-1)反之，如果反之，如果g(x)是是(xn-1)的（的（n-k））次因式，次因式，g(x)一定是某一定是某(n，，k)循环码的生成多项式。
循环码的生成多项式 上上述述定定理理告告诉诉了了构构造造(n，，k)循循环环码码的的方方法法如下：如下：① ① 对对xn-1 (在在二二元元域域中中等等效效于于对对xn+1)实实行行因式分解因式分解, 找出其中的（找出其中的（n-k））次因式②② 以以找找出出的的（（n-k））次次因因式式为为循循环环码码生生成成多多项项式式g(x)，，与与信信息息多多项项式式m(x)相相乘乘，，即即得码多项式：得码多项式：C(x)= m(x) g(x) 例例4. 2 分析码长分析码长n=7的所有可能二进制循环码的所有可能二进制循环码解解：：将将GF(2)上上多多项项式式 (x7＋＋1)因因式式分分解解，，或或查查表表4.6 m=3一行，得：一行，得： (x7＋＋1)= (x＋＋1) (x3＋＋x＋＋1) (x3＋＋x2＋＋1) 因此因此(x7＋＋1)因式的次数可以有以下四种因式的次数可以有以下四种1次次 (x＋＋1)3次次 (x3＋＋x＋＋1)或或(x3＋＋x2＋＋1)4次次 (x＋＋1) (x3＋＋x＋＋1) 或或 (x＋＋1) (x3＋＋x2＋＋1) 6次次 (x3＋＋x＋＋1) (x3＋＋x2＋＋1) (n-k)可取可取1、、3、、4、、6, 因此断言：因此断言：存在存在(7,6)，， (7,4) ，， (7,3) ，， (7,1) 循环码，循环码，而不存在而不存在(7,2) ，， (7,5) 循环码。
循环码 i最小多项式最小多项式 i最小多项式最小多项式 i最小多项式最小多项式 i最小多项式最小多项式m = 21(0,1,2) m = 31(0,1,3)3(0,2,3) m = 41(0,1,4)3(0,1,2,3,4)5(0,1,2)7(0,3,4)m = 51(0,2,5)3(0,2,3,4,5)5(0,1,2,4,5)7(0,1,2,3,5) 11(0,1,3,4,5)15(0,3,5) m = 61(0,1,6)3(0,l,2,4,6)5(0,l,2,5,6)7(0,3,6) 9(0,2,3)11(0,2,3,5,6)13(0,1,3,4;6)15(0,2,4,5,6) 21(0,1,2)23(0,1,4,5,6)27(0,1,3)31(0,5,6)m = 71(0,3,7)3(0,1,2,3,7)5(0,2,3,4,7)7(0,1,2,4,5,6,7) 9(0,1,2,3,4,5,7)11(0,2,4,6,7)13(0,1,7)15(0,1,2,3,5,6,7) 19(0,1,6,7)21(0,2,5,6,7)23(0,6,7)27(0,1,4,6,7) 29(0,1,3,5,7)31(0,4,5,6,7)43(0,l,2,5,7)47(0,3,4,5,7) 55(0,2,3,4,5,6,7)63(0,4,7) m = 81(0,2,3,4,8)3(0,1,2,4,5,6,8)5(0,1,4,5,6,7,8)7(0,3,5,6,8) 9(0,2,3,4,5,7,8)11(0,1,2,5,6,7,8)13(0,1,3,5,8)15(0,1,2,4,6,7,8) 17(0,1,4)19(0,2,5,6,8)21(0,l,3,7,8)23(0,1,5,6,8) 25(0,1,3,4,8)27(0,1,2,3,4,5,8)29(0,2,3,7,8)31(0,2,3,5,8)表表4-6二元扩域二元扩域GF(2m)中连续幂次根所对应的最小多项式中连续幂次根所对应的最小多项式 要构成要构成(7,3)循环码，循环码，(n-k)=4的因式有的因式有(x＋＋1) (x3＋＋x＋＋1) 或或(x＋＋1) (x3＋＋x2＋＋1)两个，任选其中一个两个，任选其中一个,比如比如g(x)=(x+1)(x3+x+1)=(x4+x3+x2+1)作生成多项式作生成多项式, 令令 C(x)= m(x) g(x) =(m2x2+m1x+m0) (x4+x3+x2+1)可产生循环码集。
例如可产生循环码集例如m=(011)即即 m(x)=( x +1)时时 ( x+ 1)(x4＋＋x3＋＋x2＋＋1) = x5+ x2+ x1+ 1 对应码矢对应码矢C = ( 0100111 )类推，得全部码集类推，得全部码集经检验，符合经检验，符合“码字的循环仍是码字码字的循环仍是码字”信息位信息位m000001010011100101110111码矢码矢C00000000011101011101001001111110100110100110011101010011 构码也有好坏之分比如构造一个构码也有好坏之分比如构造一个(15,10)循环码，循环码，x15+1=(x+1)(x2+x+1)(x4+x+1)(x4+x3+1)(x4+x3+x2+x+1) 由于由于n-k=5 方案方案1：：g1(x)= (x+1) (x4+ x+1)= x5+ x4+x2+1 方案方案2：：g2(x)= (x+1) (x4+x3+x2+x+1)= x5 + 1g(x)一般就是最轻码，一般就是最轻码， g1(x) 、、 g2(x)的的重量分别是重量分别是４和２，因此４和２，因此g1(x)优于优于g2(x)。
用用上上述述方方法法可可得得循循环环码码，，但但未未必必是是系系统统的的若若想想得得到到系系统统循循环环码码，，即即码码字字的的前前k位位原原封封不不动动照照搬搬信信息位而后息位而后(n-k)位为校验位，具有如下形式位为校验位，具有如下形式 C(x) = xn-k m(x) + r (x) (4-5)r(x)是是与与码码字字中中(n-k)个个校校验验元元相相对对应应的的(n-k-1)次次多多项式，可将式项式，可将式(4-5)写成写成 xn-k m(x)= C(x) + r (x) 等等式式两两边边除除以以生生成成多多项项式式g(x)，，由由于于g(x)能能整整除除C(x) ，，deg[r (x)] < deg[g(x)] ,因此有因此有 r (x)= xn-k m(x) mod g(x)即即r(x)等于等于xn-k m(x)除以除以g(x)的余式 于是得到了产生系统循环码的具体方法于是得到了产生系统循环码的具体方法①①. 将信息多项式将信息多项式m(x)预乘预乘xn-k, 即右移（即右移（n-k））位 ②②. 将将xn-km(x)除以除以g(x)，，得余式得余式r (x)。
③③. 系统循环码的码多项式可写成：系统循环码的码多项式可写成： C(x) =xn-km(x) + r (x) 例例4.3 (7,3)循循环环码码的的生生成成多多项项式式是是g(x)=x4+x3+x2+1,用式用式(4-6)产生循环码集产生循环码集解：当输入信息解：当输入信息 m＝＝(011)即即m(x) = ( x +1)时，时，①① xn-km(x) = x4( x +1) = x5+ x4 ②②( x5+ x4)除以除以(x4+ x3+ x2+ 1) 得余式得余式(x3+ x)③③C(x)=xn-km(x)+r(x) =(x5+x4)+(x3+x),对应码矢对应码矢(0111010)依次将依次将(000)…(111)代入代入可得表可得表4-2表4-1对比，对比，码集未变码集未变(2个循环环个循环环)而映射规则变了而映射规则变了信信息息位位m000001010011100101110111码矢码矢C00000000011101010011101110101001110101001111010011110100 三、循环码的矩阵描述三、循环码的矩阵描述 根据定理根据定理4.3，应有，应有 xn-1=g(x) h(x)(4-7)如如果果g(x)是是循循环环码码的的生生成成多多项项式式，，那那么么h(x)一一定定就就是是循循环环码码的的校校验验多多项项式式。
这这是是因因为为对对于于任任意意一个码多项式一个码多项式C(x)，，必有必有 C(x)h(x)=0 mod (xn-1) ∵C(x)h(x) = m(x)g(x) h(x) = m(x) (xn-1)是是(xn-1)的倍式，一定能被的倍式，一定能被(xn-1)整除整除∴∴ mod (xn-1) 运算后必定为零运算后必定为零 =[mk-1 mk-2…m0] =[mk-1 mk-2…m0] 其中，g(x)=gn-k xn-k+…+ g1 x + g0 将将矩矩阵阵中中的的多多项项式式改改写写成成对对应应的的n重重矢矢量量形形式式，，得得矢量的矩阵表达式：矢量的矩阵表达式： C=(cn-1,…c1, c0)=[mk-1,…m1, m0] = mG （（4-10））这里，定义这里，定义(k n)矩阵矩阵G为为循环码的生成矩阵循环码的生成矩阵 生成矩阵生成矩阵G的每一行是的每一行是n重空间的一个基底，重空间的一个基底，也是也是k维维n重码空间的一个基底在一般线性重码空间的一个基底。
在一般线性分组码的生成矩阵中，这些基底除线性无关分组码的生成矩阵中，这些基底除线性无关外没有什么特殊关系然而从上式看到，循外没有什么特殊关系然而从上式看到，循环码生成矩阵的环码生成矩阵的k个基底，是一个基底个基底，是一个基底(gn-k …… g1 g0 0 …… 0)的循环移位得出的因此只要知的循环移位得出的因此只要知道一个基底，其它道一个基底，其它(k-1)个基底可通过循环移个基底可通过循环移位得到 循环码的循环码的(n-k)n阶的校验矩阵可写为：阶的校验矩阵可写为：H= (4-13)循循环环码码生生成成矩矩阵阵G与与校校验验矩矩阵阵的的乘乘积积一一定定是是的零阵 GHT＝＝0 (4-14) 例例4.1.4 以以 x3+ x+1为生成多项式生成一个（为生成多项式生成一个（7, 4））循环码循环码,求此码的生成矩阵和校验矩阵如果要求求此码的生成矩阵和校验矩阵如果要求生成的（生成的（7, 4）循环码是系统的，生成矩阵该作）循环码是系统的，生成矩阵该作如何改变？如何改变？解：查因式分解表可知解：查因式分解表可知 x7+1=(x+1) (x3+ x2+1) (x3+ x+1) 本题本题n-k = 7- 4 = 3, 因此生成多项式因此生成多项式g(x)应是应是3次。
次x7+1) 有两个有两个3次因式，取其中任意一个都能生成次因式，取其中任意一个都能生成（（7, 4）循环码现取）循环码现取g(x)=x3+ x+1，则，则h(x)= (x+1) (x3+ x2+1)= x4+ x2+ x+1 由式（由式（4-10），（），（4-13）可得）可得 1011000 ①① 1110100G = 0101100 ②② H= 0111010 0010110 ③③ 0011101 0001011④④对矩阵对矩阵G的行进行运算，将第的行进行运算，将第①①+③③+④④行作为行作为第第1行，第行，第②②+④④行相加后作为第行相加后作为第2行，得：行，得： 1000101 ①①+③③+④④ 1110100 G= 0100111 ②②+④④ H= 0111010 0010110 1101001 0001011这就是系统循环码的生成矩阵和校验矩阵。
这就是系统循环码的生成矩阵和校验矩阵 表表4-4 分组码与循环码的对比分组码与循环码的对比 一般线性分组码一般线性分组码用生成矩阵描述（式用生成矩阵描述（式3-2）） G循环码循环码k个基底相互独立个基底相互独立k个基底由一个基底循环而来个基底由一个基底循环而来有有k×n个独立参数个独立参数gij只有只有n-k-1个独立参数个独立参数gn-k-1~ g1(g0 、、gn-k恒为恒为1)编码电路用矩阵编码电路用矩阵(二维二维)实现实现 编码电路用除法器编码电路用除法器(一维一维)实现实现用生成多项式描述用生成多项式描述 G= gn-k … g1 g0 0 … 00 gn-k … g1 g0 0 … 0 0 …0 gn-k … g1 g0 00 … 0 gn-k … g1 g0 四、四、CRC码码 (7,4)(7,4)循环码循环码 (5,2)(5,2)缩短循环码缩短循环码1000101 G= 0100111 Gs= 10110 0010110 01011 0001011循环码码字循环码码字(00000)(10110)(01011)(11101)(00000)(10110)(01011)(11101)。
缩短循环码码字的循环移位不再一定是码字，它已失缩短循环码码字的循环移位不再一定是码字，它已失去了循环码去了循环码“循环循环”的外部特性但它是循环码的子的外部特性但它是循环码的子集，可以想象：它仍由集，可以想象：它仍由(7,4)(7,4)循环编码器产生，只是循环编码器产生，只是传输时有选择地少传传输时有选择地少传2 2位，仅输出码字的前位，仅输出码字的前5 5位而已因此它仍然具有循环码编译码器实现简单的优点因此它仍然具有循环码编译码器实现简单的优点 循环冗余校验码循环冗余校验码（（CRC-Cyclic Redundancy check））循环冗余校验码循环冗余校验码(CRC)是一种系统的缩短循环码，是一种系统的缩短循环码，广泛应用于帧校验中广泛应用于帧校验中 C(x): n位位 (先发先发)高次高次 低次低次m(x)的的k个系数对应个系数对应k位帧信息，位帧信息，r(x)的的(n-k)个系数对个系数对应帧校验（应帧校验（CRC)位从纠错码角度，整个位从纠错码角度，整个n位帧位帧（或称分组、信元、单元、包等）就是一个码字或称分组、信元、单元、包等）就是一个码字。
m(x): k位位 r(x): n-k位位 其中其中m(x): (k-1)次多项式次多项式r(x): (n-k-1)次多项式次多项式C(x): (n-1)次多项式次多项式g(x): (n-k)次多项式次多项式 对于系统循环码，发码端：对于系统循环码，发码端： C(x) = xn-k m(x) + r (x) 其中其中r (x) 等于等于xn-k m(x)除以除以g(x)后的余式后的余式 接收码流如无误码，应有收码接收码流如无误码，应有收码R(x) 等于发码等于发码C(x) R(x)= C(x)= xn-k m(x) + r (x) = q(x) g(x) 这时这时, 收码收码R(x) 应能被生成多项式应能被生成多项式g(x)整除如果不整除如果不能整除，必是传输中出了误码能整除，必是传输中出了误码 例例4.6 某某CRC码的生成多项式码的生成多项式 g(x)=x4+x+1如果想发送一如果想发送一串信息串信息110001…的前的前6位并加上位并加上CRC校验，发码应如何安排校验，发码应如何安排？收码又如何检验？？收码又如何检验？–解：解：本题本题deg[g(x)]= 4 = n-k , 信息多项式信息多项式 m(x)= x5+x4+1 即即k = 6, 因此得因此得 n = 10，， xn-k m(x)=x4( x5+ x4+1)= x9+ x8+ x4 该码多项式对应的码字是该码多项式对应的码字是(1100010000)。
将将xn-k m(x)除以除以g(x),得余式得余式r(x)= x3+x2 ,于是发码于是发码 C(x)= xn-k m(x) + r (x) = x9+ x8+ x4 +x3+x2 对应的码字是对应的码字是 (1100011100) 接收端的接收端的CRC校验就是做除法如果收码无误，校验就是做除法如果收码无误， g(x)应应能能整除整除R(x); 反之，若余式不等于零，说明一定有差错反之，若余式不等于零，说明一定有差错 发端和收端除法器的运算过程发端和收端除法器的运算过程 110100 11010010011/1100010000 1100010000 10011/ 1100011100 10011 + (余式余式) 1100 10011 10111 1100011100 10111 10011 10011 10000 信息位信息位 CRC 10011 10011 10011 (余式余式)1100 (余式余式) 0000 发端发端收端收端 除法器求余式除法器求余式 放入放入CRC 位位 收码除以收码除以g(x) 看余式是否为看余式是否为0 循环冗余校验码是缩短循环码循环冗余校验码是缩短循环码“循环”表现在g(x)是循环码生成多项式，“冗余”表现在固定长度的校验位。
既然是循环码，应有g(x)h(x)= xn+1，这里g(x)的次数(n-k) 是作为xn+1因式的各最小多项式次数的组合，即CRC码校验位数(n-k) 与帧长n或信息位长k有关联，并非任意的但在帧校验的实际应用中，帧长n不能是固定的所以工程应用中都是先设计一个原始循环码(n0,k0),再缩短任意i位而得到(n0-i , k0-i) = (n,k) 任意码长的CRC码由于缩短，CRC码失去了循环码的外部循环特性，但循环码的内在特性依然存在，其纠错能力可以通过循环码来分析，编、解码电路也可利用循环码来实现 国际上常用的国际上常用的CRC码有：码有：CRC-ITU-T g(x)= x16+ x12+ x5+ 1 CRC-12 g(x)= x12+ x11+ x3+ x2+ x+ 1CRC-16 g(x)= x16+ x15+ x2+1 CRC-32 g(x)= x32+ x26+ x23+ x22+ x16+ x12+ x11+ x10 + x8+ x7+ x5+ x4+ x2+ x+ 1 CRC IS-95 CDMA g(x)= x30+ x29+ x21+ x20+ x15+ x13 + x12+ x11 + x8+ x7+ x6+ x2+ x+ 1 CRC码的信息位虽然是可变长度的，但也受最大长码的信息位虽然是可变长度的，但也受最大长度的限制。
以度的限制以CRC-16为例，它的生成多项式为例，它的生成多项式g(x)= x16+ x15+ x2+1=( x+ 1)( x15+ x+1)其中其中x15+ x+1是本原多项式，能够整除的（是本原多项式，能够整除的（xn+1）中）中n最小值是最小值是215-1=32767, 所以原始循环码所以原始循环码n=32767，，n-k=16, 是（是（32767, 32751）循环码该码共有码字）循环码该码共有码字232751个，其中最高位为个，其中最高位为0的占一半的占一半(232751-1个个)，前，前2位位为为0的是一半的一半的是一半的一半(232751-2个个) …以此类推以此类推将前将前i位位都是都是0的码的码 (232751-i个个)看作一个子码集，去掉前面看作一个子码集，去掉前面i个个0构成（构成（n0-i, k0-i））缩短码，这就是可变长度的缩短码，这就是可变长度的（（n,k））CRC码，它保留了（码，它保留了（32767, 32751）循环码）循环码的特性，也决定了用的特性，也决定了用CRC-16校验时的最大信息位长校验时的最大信息位长度不能超过度不能超过32751 注意到：注意到：CRC-ITU-T、、CRC-16、、CRC IS-95 CDMA和和CRC-12都含有因式都含有因式( x+ 1)，，生成多项生成多项式的项数都是偶数式的项数都是偶数。
可以证明，若生成多项式可以证明，若生成多项式g(x)中含有因式中含有因式(x+1)，，则此码不含奇数重量码字，则此码不含奇数重量码字，其作用等效于奇偶校验偶重其作用等效于奇偶校验偶重g(x) 能检出所有奇能检出所有奇数差错的原因可从以下两方面来理解：数差错的原因可从以下两方面来理解：1.循环码所有基底是一个基底的循环对于等重、循环码所有基底是一个基底的循环对于等重、偶重的基底，其线性组合仍然是偶数重量偶重的基底，其线性组合仍然是偶数重量2.（组合时要么两个（组合时要么两个“ 1”在同一位置加成在同一位置加成“ 0”，重量减，重量减2；要么两个；要么两个“ 1” 在不同位置相加，重量增在不同位置相加，重量增2)3.2.将将x=1代入码多项式，得代入码多项式，得0为偶重，得为偶重，得1为奇重为奇重4. C(x) |x=1= C(1) = m(1)g(1) = m(1) 0=0 CRC码码生成多项式生成多项式CRC最大码长最大码长CRC-12 x12+ x11+ x3+ x2+ x+ 112211－－1=2047x16+ x12+ x5+ 116215－－1=32767CRC-16 x16+ x15+ x2+116215－－1=32767CRC-32 x32+ x26+ x23+ x22+ x16+ x12+ x11+ x10+ x8+ x7+ x5+ x2+ x4+ x+ 132231－－1 检检 错错 能能 力力1. 所有奇数个差错（此码重为偶数）所有奇数个差错（此码重为偶数）2. 所有所有≤5个的随机差错个的随机差错3. 所有长度所有长度≤12的单个突发差错的单个突发差错4. 以以(1-2-13)的概率检出长度＝的概率检出长度＝17的单个突发差错的单个突发差错5. 以以(1-2-12)的概率检出长度的概率检出长度>17的单个突发差错的单个突发差错6. 所有长度所有长度≤2的两个突发差错的两个突发差错1. 所有奇数个差错（此码重为偶数）所有奇数个差错（此码重为偶数）2. 所有所有≤3个的随机差错个的随机差错3. 所有长度所有长度≤16的单个突发差错的单个突发差错4. 以以(1-2-17)的概率检出长度＝的概率检出长度＝17的单个突发差错的单个突发差错5. 以以(1-2-16)的概率检出长度的概率检出长度>17的单个突发差错的单个突发差错6. 所有长度各所有长度各≤2的两个突发差错的两个突发差错同上同上CRC-ITU-T1. 所有奇数个差错（此码重为偶数）所有奇数个差错（此码重为偶数）2. 所有所有≤14个的随机差错个的随机差错3. 所有长度所有长度≤32的单个突发差错的单个突发差错4. 以以(1-2-33)的概率检出长度＝的概率检出长度＝33的单个突发差错的单个突发差错5. 以以(1-2-32)的概率检出长度的概率检出长度>33的单个突发差错的单个突发差错6. 所有长度各所有长度各≤2的两个突发差错的两个突发差错CRCITU-T 五、五、BCH码码 BCH码是纠错能力可控的纠随机差错码，是循环码是纠错能力可控的纠随机差错码，是循环码的子类。
码的子类该码有严格的代数结构，生成多项式该码有严格的代数结构，生成多项式g(x)与最小距离与最小距离dmin有密切关系，使设计者可以根据对有密切关系，使设计者可以根据对d dminmin的要求，轻易地构造出具有预定纠错能力的码的要求，轻易地构造出具有预定纠错能力的码 BCH编、译码电路比较简单，易于工程实现，在编、译码电路比较简单，易于工程实现，在中、短码长情况下的性能接近理论最佳值因此中、短码长情况下的性能接近理论最佳值因此BCH码不仅在编码理论上占有重要地位，而且也是实际使码不仅在编码理论上占有重要地位，而且也是实际使用最广泛的码之一用最广泛的码之一 Bose Chandhari BCH HocquenghemBCH码最初是定义在码最初是定义在GF(2)域上的二进制码，后被推域上的二进制码，后被推广到多元域广到多元域GF(q)上 xn-1 因式分解因式分解 (4-17)这里，既约因式这里，既约因式m mj j( (x x) )（（j=0,j=0,……, ,l l-1-1））分成两部分，它们的乘积分成两部分，它们的乘积分别是分别是g g( (x x) )和和 h h( (x x) )。
循环码并不强调循环码并不强调g g( (x x) )的既约性，它可以是的既约性，它可以是既约的，也可以是非既约的若某既约因式既约的，也可以是非既约的若某既约因式m mj j( (x x) )是非既约是非既约g g( (x x) )的一个因式，必有的一个因式，必有 m mj j( (x x) | ) | g g( (x x) | () | (x xn n-1)-1) (4-18) (4-18) 换一个角度，如果将换一个角度，如果将( (x xn n-1)-1)看成是一个看成是一个n n次多项式，那么它次多项式，那么它在复数域应该有在复数域应该有n n个根，记作个根，记作a ai i，，i i=0,=0,……, ,n n-1-1，，此时此时( (x xn n-1)-1)可表可表示成示成x xn n-1=(-1=(x x- -a a0 0) () (x x- -a a1 1) ) ……( (x x- -a an n-1-1) ) (4-19) (4-19)比较式比较式4-174-17和式和式4-194-19，式，式4-174-17中的因式中的因式m mj j( (x x) )既然已经达到既然已经达到““既约既约””，就不能再分解，那式，就不能再分解，那式4-194-19又从何而来呢？又从何而来呢？ 例例4 -7 （（x4-1））在不同域上的因式分解在不同域上的因式分解在实数域的分解：在实数域的分解：x x4 4-1=-1= ( (x x2 2+1)(+1)(x x+1)(+1)(x x-1)-1)在复数域的分解：在复数域的分解：x x4 4-1=-1= ( (x x+ +i i) () (x x- -i i) () (x x+1)(+1)(x x-1)-1)在二元域的分解：在二元域的分解：x x4 4-1=-1= x x4 4+1= (+1= (x x+1)(+1)(x x+1) (+1) (x x+1)(+1)(x x+1)+1)上例说明：域不同则分解亦不同，在一个域的既约不等于在另上例说明：域不同则分解亦不同，在一个域的既约不等于在另一个域的既约。
一个域的既约既约多项式既约多项式m mj j( (x x) )在在GF(2)GF(2)上不能再分解，其系数在数域取值于上不能再分解，其系数在数域取值于{0,1}{0,1}；但它在二元扩域；但它在二元扩域GF(2GF(2m m) )未必就不能再分解，因未必就不能再分解，因GF(2GF(2m m) ) 是是多项式域，系数取值于多项式域，系数取值于{ { 0 0、、 1 1、、 2 2、、……、、 } }于是问题变于是问题变为为( (x xn n-1)-1)能否在能否在GF(2GF(2m m) )完全分解？如何分解？分解后如何用于纠完全分解？如何分解？分解后如何用于纠错编码设计？编码和译码又如何实现？错编码设计？编码和译码又如何实现？ 根根据据定定理理4. 1，，只只要要找找到到与与循循环环码码对对应应的的主主理理想想中中的一个的一个n 阶元素，就可以将阶元素，就可以将(xn -1)在在GF(2m)上完全上完全分解为分解为 xn-1 =证：若证：若 a是是循环群循环群n 阶元素，必有阶元素，必有an = 1 即即(an -1)=0 将将ai,i=0…n-1代入代入(xn-1)验根，验根， 得得 (ai)n-1= (a n) i -1= (1)i-1= 0∴ ∴ ai,i=0…n-1是是(xn-1)的的n个根个根，，以根为一次项可将以根为一次项可将(xn-1 )完全分解为完全分解为 xn-1=(x-a0) (x-a1) ……(x-an-1) 问题问题1. 码长码长n与扩域次数与扩域次数m有何关系？有何关系？2. GF(2m)上的根上的根ai与二元域多项式与二元域多项式mj(x)有何关系？有何关系？ 二二元元扩扩域域GF(2m)是是由由一一m次次本本原原多多项项式式生生成成的的。
当当n=2m-1时时，，这这个个n阶阶域域元元素素a就就是是(2m-1)阶阶本本原原元元，，资资料料中中通通常常用用 表表示示本本原原元元；；当当n<(2m-1)且且n|(2m-1)时时，，这这个个n阶阶域域元元素素a为为非非本本原原元元，，通通常常用用 表表示示非非本本原原元元这这里里不不强强调调域域元元素素是是否否本本原原，，所所以以用用中中性性字母字母a来表示 = xn-1 = GF(2m)扩域扩域 | GF(2)域域 系数系数1既是扩域又是二元域元素既是扩域又是二元域元素或改变顺序为或改变顺序为 = = xn-1 若若(xn-1)的某一个根的某一个根ai , i {0,1…n-1}又是某个既约因又是某个既约因式式mj(x), j {0,1…l-1}的根，也是的根，也是(n-k)次生成多项式次生成多项式g(x)的根，那么必有的根，那么必有a为为n阶本原元时：阶本原元时： (x-ai) | mj(x) | g(x) | (xn-1)=( )(4-22)a为为n阶非本原元时：阶非本原元时： (x-ai) | mj(x) | g(x) | (xn-1) | ( ) (4-23)以上两式说明：生成多项式以上两式说明：生成多项式g(x)的（的（n-k））个根也是个根也是(xn-1)的根，只要能够以适当的方法找出这些根，就的根，只要能够以适当的方法找出这些根，就可以从这些根得到生成多项式可以从这些根得到生成多项式g(x)。
研究表明，有重根的研究表明，有重根的g(x)不能产生好码不能产生好码而如果而如果 (xn-1)无重根，则无重根，则g(x)肯定无重根肯定无重根在在GF(qm)上上(xn-1)无重根的充要条件是无重根的充要条件是n、、q互素这就解释了为什么二进制码（这就解释了为什么二进制码（q=2））码长都是奇数码长都是奇数的原因xn-1)的的n个根中，个根中，(n-k)个根也是个根也是g(x)的根，剩下的的根，剩下的k个根一定也是个根一定也是h(x)的根 因此如果因此如果 (xn-1)无重根，无重根，h(x)肯定也无重根肯定也无重根 至此，实际上已找到了用至此，实际上已找到了用(xn-1)在在GF(2m)域上的根域上的根来构造循环码的方法，那就是：来构造循环码的方法，那就是：①① 在在(xn-1)的的n个根中选取若干个个根中选取若干个r1、、r2…rj, 其中其中 rj {ai},i=0,1…n-1②②找出各根对应的既约多项式找出各根对应的既约多项式r1→m1(x)、、 r2→m2(x)…rj→mj (x)③③求出这些既约多项式的最小公倍式：求出这些既约多项式的最小公倍式： g(x)=LCM[m1(x), m2(x)…mj (x)] LCM (Least Common Multiple) - 最小公倍式最小公倍式若选取的根是连续幂次的根，则所得的若选取的根是连续幂次的根，则所得的g(x)可以产可以产生一个生一个BCH码，否则就是一般的循环码。
码，否则就是一般的循环码 1 BCH1 BCH码的定义码的定义 GF(q)域循环码生成多项式域循环码生成多项式g(x)，，若含有若含有2t个连个连续幂次的根续幂次的根 ，则由，则由g(x)生成的生成的(n,k)循环码称为循环码称为q进制进制BCH码连续幂次起始值连续幂次起始值m0的的选取并无多大实际意义，通常固定取选取并无多大实际意义，通常固定取m0= =1 若若q=2，，称为二进制（二元）称为二进制（二元）BCH码 若根若根a是本原元是本原元 ，称该码为本原，称该码为本原BCH码，其码码，其码长长n=qm-1 若根若根a是非本原元是非本原元 ，称该码为非本原，称该码为非本原BCH码，码，其码长其码长n是是qm-1的因子，满足的因子，满足n | (qm-1) BCH码限定理码限定理：若若BCH码生成多项式码生成多项式g(x)中含有中含有2t个连续幂次的根，则该码的最小距离个连续幂次的根，则该码的最小距离dmim 2t+1证明：∵ BCH码多项式C(x)=m(x)g(x)∴ g(x)的2t个连续幂次根、…、2t也是C(x)的根设 C(x)= c0+ c1x + c2 x2+…+ cn-1 xn-1以根x = 代入， 得 c0+ c1 + c2 2+…+ cn-1 n-1 = 0以x = 2代入，得 c0+c12 +c2(2) 2+…+cn-1(2)n-1= 0 ┇以x = 2t代入，得c0+c12t+c2(2t)2+…+cn-1(2t)n-1= 0 将上面将上面2t个方程写作矩阵形式，得个方程写作矩阵形式，得CAT= 0(4-24) 其中其中 A = =可见，可见，A是范得蒙矩阵。
数学证明：范得蒙矩阵一是范得蒙矩阵数学证明：范得蒙矩阵一定是满秩矩阵，即定是满秩矩阵，即矩阵矩阵A的秩是的秩是2t或者说有或者说有2t列线性列线性无关码的最小距离无关码的最小距离dmin等于校验矩阵中线性无关等于校验矩阵中线性无关的列数加的列数加1，因此，因此BCH码的码的dmin = 2t +1 (4-26) 1 2 … n-1 1 2 (2)2… (2) n-1 ┇1 2t (2t)2… (2t) n-1 1 2 … n-1 1 2 (2)2… (n-1)2 ┇1 2t (2)2t… (n-1)2t 2 2 本原本原BCHBCH码构造法码构造法① ① 由关系式由关系式n=2m-1算出算出m，，查表查表4-5，找到一个，找到一个m次次本原多项式本原多项式P(x)，，产生一个产生一个GF(2m)扩域② ② 在在GF(2m)上找一个本原元上找一个本原元 ，分别计算，分别计算2t个连续个连续幂次根幂次根 、、 2、、…、、 2t所对应的所对应的GF(2)域上的最小多域上的最小多项式项式m1(x)、、m2(x)…m2t(x)。
m 8时连续幂次根时连续幂次根 i所所对应的最小多项式见表对应的最小多项式见表4-6③ ③ 计算这些最小多项式的最小公倍式，得到生成多计算这些最小多项式的最小公倍式，得到生成多项式项式g (x) g(x)=LCM[m1(x) m2(x)… m2t(x)] (4-27)④④ 由关系式由关系式C(x)=m(x)g(x) 求求BCH码字 对于二元对于二元BCH码，无需列出全部码，无需列出全部2t个连续幂次的个连续幂次的根，而只要列出其中一半（奇数幂次的根）就可根，而只要列出其中一半（奇数幂次的根）就可以了这是因为任何一个偶数以了这是因为任何一个偶数ie 可写成一个小于它可写成一个小于它的奇数的奇数io 与与2的的l次幂的乘积次幂的乘积 ie =io 2l , io 最小多项式，在计算最小公倍式时将不起作用 i最小多项式最小多项式 i最小多项式最小多项式 i最小多项式最小多项式 i最小多项式最小多项式m = 21(0,1,2) m = 31(0,1,3)3(0,2,3) m = 41(0,1,4)3(0,1,2,3,4)5(0,1,2)7(0,3,4)m = 51(0,2,5)3(0,2,3,4,5)5(0,1,2,4,5)7(0,1,2,3,5) 11(0,1,3,4,5)15(0,3,5) m = 61(0,1,6)3(0,l,2,4,6)5(0,l,2,5,6)7(0,3,6) 9(0,2,3)11(0,2,3,5,6)13(0,1,3,4;6)15(0,2,4,5,6) 21(0,1,2)23(0,1,4,5,6)27(0,1,3)31(0,5,6)m = 71(0,3,7)3(0,1,2,3,7)5(0,2,3,4,7)7(0,1,2,4,5,6,7) 9(0,1,2,3,4,5,7)11(0,2,4,6,7)13(0,1,7)15(0,1,2,3,5,6,7) 19(0,1,6,7)21(0,2,5,6,7)23(0,6,7)27(0,1,4,6,7) 29(0,1,3,5,7)31(0,4,5,6,7)43(0,l,2,5,7)47(0,3,4,5,7) 55(0,2,3,4,5,6,7)63(0,4,7) m = 81(0,2,3,4,8)3(0,1,2,4,5,6,8)5(0,1,4,5,6,7,8)7(0,3,5,6,8) 9(0,2,3,4,5,7,8)11(0,1,2,5,6,7,8)13(0,1,3,5,8)15(0,1,2,4,6,7,8) 17(0,1,4)19(0,2,5,6,8)21(0,l,3,7,8)23(0,1,5,6,8) 25(0,1,3,4,8)27(0,1,2,3,4,5,8)29(0,2,3,7,8)31(0,2,3,5,8)表表4-6二元扩域二元扩域GF(2m)中连续幂次根所对应的最小多项式中连续幂次根所对应的最小多项式 比如比如t=4时时8个连续幂次根个连续幂次根 2 3 4 5 6 7 8中，中， 2 4 8是共轭元，是共轭元， 3 6是共轭元，于是是共轭元，于是g(x)=LCM[m1(x) m2(x) m3(x) m4(x) m5(x)m6(x)m7(x)m8(x)]= LCM{[m1(x) m2(x) m4(x) m8(x)] [ m3(x) m6(x)] m5(x) m7(x)}= LCM[m1(x) m3(x) m5(x) m7(x)]因此因此对于二进制码，构造本原对于二进制码，构造本原BCH码的步骤改为码的步骤改为: : ②②分别计算分别计算t个连续奇次幂之根个连续奇次幂之根 、、 3… 2t-1所对应所对应的最小多项式的最小多项式m1(x)、、m3(x)…m2t-1(x)。 当码长当码长n确定后，确定后，BCH码纠错能力码纠错能力t的选择并不是任意的选择并不是任意的，而要受到一定限制的，而要受到一定限制 对于对于q元元BCH码，码，2t个根对应个根对应2t个最小多项式，每个个最小多项式，每个最小多项式的次数不会超过最小多项式的次数不会超过m，，于是于是2t个最小多项式个最小多项式的最小公倍式的最小公倍式g(x)的次数的次数deg[g(x)] = (n-k) ≤2tm (4-29) 对于二元对于二元BCH码，码，t个根对应个根对应t个最小多项式，因此个最小多项式，因此 deg[g(x)] = (n-k) ≤tm(4-30) (xn-1)一共有一共有n个根，连续幂次根不能超过根的总数个根，连续幂次根不能超过根的总数 2t n (4-31)式式(4-29) (4-30)给出了给出了t的下限，式的下限，式(4-31)给出了给出了t的上的上限 例例4.8 设计一个码长设计一个码长n = 15的二元本原的二元本原BCH码，在不码，在不同纠错能力下的生成多项式应是怎样的？同纠错能力下的生成多项式应是怎样的？解解：∵∵ 15=24-1∴∴本题本题m = 4①①第一步：查表，找到一个第一步：查表，找到一个m=4的本原多项式的本原多项式P(x)=x4+ x+1。 令令 是该本原多项式是该本原多项式P(x)的根，满足的根，满足 4+ +1=0由式(4-31)，本码纠错能力，本码纠错能力t 7②②第二步：对于二元码，分别计算第二步：对于二元码，分别计算t=7个连续奇次幂个连续奇次幂之根之根 3 5 7 9 11 13所对应的最小多项式本例所对应的最小多项式本例可参考例可参考例2.2.3的表的表2-3，我们看到，我们看到 3、、 9是共轭元，是共轭元， 7、、 11和和 13是共轭元（利用教材是共轭元（利用教材p124“共轭根系共轭根系”定义分析）定义分析） 根和根所对应的最小多项式（例根和根所对应的最小多项式（例2.10）如下：）如下：根根 m1(x) =p(x)=x4+ x+1 根根 3 m3(x) =(x+a3) (x+a(x+a6 6) (x+a) (x+a9 9) ) (x+a(x+a1212) )=x4+ x3+ x2+ x+1 根根 5 m5(x) =(x+a5)(x+a10)=x2+ x+1 根根 7 m7(x) =x4+ x3+ 1 根根 9同同 3，，根根 11、、 13同同 7。 这里，这里，m(x)的全部根为下列系列：的全部根为下列系列：并把并把w序列换成序列换成a的序列 ③ ③ 第三步：求最小公倍式得到生成多项式第三步：求最小公倍式得到生成多项式g g( (x x) )●●若若t t =1=1，，g g1(1(x x)=LCM[)=LCM[m m1(1(x x)] = )] = x x4+4+ x x+1+1g g1(1(x x) )是是4 4次多项式，即次多项式，即n-kn-k=4=4，，∴ ∴ k k =15-4=11, =15-4=11, 这就是这就是(15,11)BCH(15,11)BCH码，也是汉明码码，也是汉明码●●若若t t=2=2，，g g2(2(x x)=LCM[)=LCM[m m1(1(x x),), m m3(3(x x)] =)] = m m1(1(x x) ) m m3(3(x x) =) = x x8+8+ x x7+7+ x x6+6+x x4+14+1，，deg[deg[g g2(2(x x)]= )]= n-kn-k = 8= 8，，∴ ∴ k k =15-8=7=15-8=7，这是，这是(15,7) BCH(15,7) BCH码。 码 ●若若t=3，， g3(x)=LCM[m1(x), m3(x), m5(x)] = m1(x) m3(x) m5(x) = x10+ x8+ x5+ x4+x2 + x +1，， deg[g3(x)]= n-k = 10，， ∴∴ k =15-10=5，，这是这是(15,5) BCH码●若若t=4，， g4(x)=LCM[m1(x), m3(x), m5(x), m7(x)] = m1(x) m3(x) m5(x) m7(x) = x14+ x13+ x12+ x11+x10+ x9+ x8+ x7+x6 + x5+ x4+ x3 +x2 + x +1 deg[g4(x)]= n-k = 14，， ∴∴ k =15-14=1，，这是这是(15,1) BCH码 ●若若t=5，，g5(x)=LCM[m1(x), m3(x), m5(x), m7(x), m9(x)] = m1(x) m3(x) m5(x) m7(x)= g4(x)●若若t=6，，g6(x)=LCM[m1(x), m3(x), m5(x), m7(x), m9(x) , m11(x)]= m1(x) m3(x) m5(x) m7(x)= g4(x) ●若若t=7，，g7(x)=LCM[m1(x),m3(x),m5(x),m7(x), m9(x), m11(x),m13(x)]=m1(x) m3(x) m5(x) m7(x)=g4(x)可见，当可见，当t=4、、5、、6、、7时的时的BCH码均是码均是(15,1)码，码，生成多项式生成多项式g4(x)拥有拥有x的所有各次幂，意味着编码的所有各次幂，意味着编码时将一位信息时将一位信息“0”或或“1”重复发送重复发送15次。 因此，次因此，实际上只有实际上只有t=1,2,3的的(15,11)、、(15,7)、、(15,5) BCH码码才有实用价值才有实用价值 非本原非本原BCH码与本原码与本原BCH码的主要区别码的主要区别在于所用的根是否本原元在于所用的根是否本原元 当码长当码长n和纠错能力和纠错能力t给定后，本原给定后，本原BCH码码的根的根 一定是一定是n=2m-1阶阶, n已知就是已知就是m已知，因已知，因而而GF(qm)好找 非本原非本原BCH码的根码的根 是是n阶元素阶元素, 满足满足n | (qm-1)，， n已知不等于已知不等于m已知，需要多一道计已知，需要多一道计算 已知已知n和和t后二元非本原后二元非本原BCH码的设计步骤：码的设计步骤：① ① 求出满足求出满足 n | (2m-1)关系的关系的m的最小值的最小值n是是(2m-1) 的因子，可以借助的因子，可以借助2m-1的素因子分解表（如表的素因子分解表（如表4-7））来寻找来寻找m值② ② 查表查表4-5，找出一个，找出一个m阶的本原多项式阶的本原多项式P(x)，， 产生一个二元扩域产生一个二元扩域GF(2m)。 ③ ③ 以以P(x)的根的根 为中介找出一个为中介找出一个n阶的非本原元阶的非本原元 ④ ④ 计算与计算与 、、 3、、 5… 2t-1对应的最小多项式对应的最小多项式m1(x)、、m3(x)…m2t-1(x)⑤⑤ 求生成多项式求生成多项式g(x)=LCM[m1(x) m3(x)… m2t-1(x)] 表表4-7 2m-1的素因子分解（的素因子分解（m<34）） m 素因子分解素因子分解 m素因子分解素因子分解m素因子分解素因子分解12345678910111373 5313 3 71273 5 177 733 11 3123 8912131415161718192021223 3 5 7 1381913 43 1277 31 1513 5 17 2571310713 3 3 7 19 735242873 5 5 1l 31 417 7 127 3373 23 89 683232425262728293031323347 1784813 3 5 7 13 17 24131 601 18013 2731 81917 73 2626573 5 29 43 113 127233 1103 20893 3 7 11 31 151 33121474836473 5 17 257 655377 23 89 599479 例例4.9 试设计一个码长试设计一个码长n = 23，，纠两个随机差错纠两个随机差错(t =2)的二元的二元BCH码。 码 解：解： ① ① 由于码长由于码长n 2m-1比如比如15、、31、、 … 255…等值，可知等值，可知要求设计的是二元非本原要求设计的是二元非本原BCH码检查能被码检查能被n=23整除的整除的2m-1(表表4-7)，，m的最小值是的最小值是11 (211-1=2047=89×23,能够整除能够整除23)，所，所以取以取m=11② ② 查表查表4-5, 得得11阶的本原多项式是阶的本原多项式是P(x)=x11+x2+1令令 是本原多项式是本原多项式P(x)的根，满足的根，满足 11+ 2+1= 0由于 是本原是本原元，它的阶数是元，它的阶数是211-1=2047，满足，满足 2047=1 ③ ③ 为了得到为了得到23阶域元素，将阶域元素，将 2047=1改写为改写为 2047 = 89×23 = ( 89)23 = ( )23 = 1, 式中式中 = 89 事实上，事实上， 0, 1, 2, 3,… 2047 本身都是域元素，本身都是域元素， 只是将域只是将域元素元素 89定义为域元素定义为域元素 而已。 由于而已由于( 89)23 = ( )23 = 1，因此可，因此可断言断言 是一个是一个23阶的非本原元阶的非本原元 ④ ④ 求求 连续奇幂次的根所对应的最小多项式连续奇幂次的根所对应的最小多项式 首先找出首先找出 的所有共轭元，然后再来计算最小多的所有共轭元，然后再来计算最小多项式 的共轭元有：的共轭元有： , 2, 4, 8, 16, 32= 23 9= 9, 18, 36= 23 13= 13, 26= 3, 6, 12, 24= 因因 24= 完成了一个周期，所以这个周期的完成了一个周期，所以这个周期的11个域元素个域元素都是共轭元将它们重新按幂次顺序排列就是：都是共轭元将它们重新按幂次顺序排列就是： , 2, 3, 4, 6, 8, 9, 12, 13, 16, 18由此可断定该由此可断定该BCH码的生成多项式码的生成多项式g(x)至少是至少是11次多项式，有次多项式，有11个根。 个根 同理可得另一组共轭元同理可得另一组共轭元 5, 10, 20, 17, 11, 22, 21, 19, 15, 7, 14，也是，也是11个 第一组第一组 所对应的最小多项式为所对应的最小多项式为m1(x)=(x+ )(x+ 2)(x+ 3)(x+ 4)(x+ 6)(x+ 8)(x+ 9) (x+ 12)(x+ 13)(x+ 16)(x+ 18) = x11+ x9+ x7+x6 + x5 + x +1在上式运算过程中用到在上式运算过程中用到 23=1, = 89, 11+ 2+1= 0等关系式等关系式⑤⑤本题本题t =2，，∵∵ 和和 3是共轭元是共轭元, m1(x)= m3(x)∴∴ g(x)=LCM[m1(x) m3(x)] = m1(x) = x11+ x9+ x7+x6 + x5 + x +1∵∵ deg[g(x)] = n-k = 11, k = 23-11=12∴∴由由g(x)可可以以产产生生一一个个(23,12)二二元元非非本本原原BCH码码，，它它就就是是著著名名的的戈戈莱莱码码（（Golay）），，该该码码是是完完备备码码，，复杂度适中而纠错能力强，实践中应用广泛。 复杂度适中而纠错能力强，实践中应用广泛 BCH码限所保证的最小距离码限所保证的最小距离dmin=2t+1指的是指的是dm的下的下限，并不是说码的最小距离一定是限，并不是说码的最小距离一定是2t+12t+1又称是又称是码的设计距离，而设计后所得码的码的设计距离，而设计后所得码的dmin称为码的实际称为码的实际距离，实际距离大于等于设计距离一般可以通过距离，实际距离大于等于设计距离一般可以通过观察生成多项式的重量（项数）来估计最小距离观察生成多项式的重量（项数）来估计最小距离比如例比如例4-8中，按中，按t=1、、2、、3设计的生成多项式设计的生成多项式g1(x)、、g2(x)、、g3(x)的重量即的重量即dm分别是分别是3、、5、、7，实际距离与，实际距离与设计距离完全相同但在例设计距离完全相同但在例4-9中，中，t=2时设计距离是时设计距离是2t+1＝＝5，，而实际距离（而实际距离（g(x)的重量）是的重量）是7，因此该码，因此该码应能纠三个差错，大于设计的应能纠三个差错，大于设计的t=2 如果要求的码长如果要求的码长n既不是既不是2m-1又不是又不是2m-1的因的因子，那么就不能直接得到子，那么就不能直接得到BCH码，但可以通过码码，但可以通过码的扩展和缩短间接地得到。 的扩展和缩短间接地得到 (n,k,d) 扩展扩展 (n+1,k,d+1)扩展扩展BCH码码 (23,12,7) 扩展扩展 (24,12,8)扩展戈莱码扩展戈莱码(纠纠3检检4) 扩展戈莱码在实践中用得很多，比如扩展戈莱码在实践中用得很多，比如ITU-T H.324（（PSTN和无线信道上低比特率的多媒体通和无线信道上低比特率的多媒体通信协议）采用的就是信协议）采用的就是(24,12)扩展扩展Golay码相反，码相反，也可以从也可以从(n,k,d)BCH码出发，构成码出发，构成(n-i,k-i,d)缩短缩短BCH码缩短BCH码的编，译码电路只是在原码的编，译码电路只是在原BCH码电路基础上稍作修改即可码电路基础上稍作修改即可 表表4-8 BCH码主要参数码主要参数GF(q)本原本原BCH码码GF(2)本本原原BCH码码GF(2)非本非本原原BCH码码qm-12m-12m-1的因子的因子 2mt mt mt< qm/2< 2m/2< n/2 2t+1 2t+1 2t+1 码长码长n校验元校验元(n-k)纠错能力纠错能力t最小距离最小距离dmg(x)的根的根 m0, m0+1… m0+2t-1 , 2… 2t , 2… 2t 六、六、RS码码 RS码码= Reed-Solomon code=里德里德-索洛蒙码，索洛蒙码，是是BCH码最重要的一个子类。 可视为码最重要的一个子类可视为BCH码的特例码的特例,是是m=1, m0=1时的时的q元本原元本原BCH码 由由于于最最小小多多项项式式的的次次数数不不会会超超过过m, 当当m=1时时，，2t个个连连续续幂幂次次的的根根(x- ) (x- 2) … (x- 2t)既既是是q元元扩扩域域GF(q1)上上的的根根多多项项式式，，又又是是q元元基基域域GF(q)上上的的最最小小多多项项式式这这种种性性质质给给多多元元BCH码码的的设设计计带带来来了了很很多多的的方方便便，，因因为为在在前前面面已已经经看看到到，，由由扩扩域域i次次幂幂根根 i求求基基域域对对应应的的最最小小多多项项式式是是十十分分麻麻烦烦的的事事，，而而RS码码的的一一次次根根式式(x- )就是最小多项式，无需另外再去计算就是最小多项式，无需另外再去计算 本原本原RS码具有如下参数码具有如下参数码长：码长：n=q-1校验位：校验位：n-k=2t最小距离：最小距离：dmin=2t+1生成多项式：生成多项式：g(x)=( x- )( x- 2)…( x- 2t) =an-k xn-k+ an-k-1 xn-k-1 +…+ a1x+a0 (4-32)式中，式中，g(x)的各次系数的各次系数 ai 取自扩域取自扩域GF(q1)。 ai {0,1, , 2,…, q-2} (i=0…n-k) (4-33)由由以上参数可见以上参数可见 dmin= 2t+1 = n-k +1 因此，因此， RS码也是码也是MDC码（极大最小距离）码（极大最小距离） 注意：注意：GF(q)和和GF(q1)含义不同含义不同 GF(q)是是数域，数域， q必须是素数必须是素数 GF(q1)是是多项式域，多项式域，q不一定是素数，不一定是素数，工程上，工程上，q通常取为通常取为2的幂次GF(8)???01234567表表4-9 用用x3+x+1产生的产生的GF(81)GF(81)多项式多项式3重重000 0 0110 0 1 0 1 0 2 21 0 0 3 +10 1 1 4 2+ 1 1 0 5 2+ +11 1 1 6 2+11 0 14+5=1 mod 8 3 + 4 = 6 4的乘法逆元？的乘法逆元？ 例例4.10 试设计一个试设计一个(7,3,5)本原本原RS码。 码解解：：由由于于码码长长n=q-1＝＝7，，可可断断定定码码元元是是8进进制制的的8进进制制域元素可以用根的幂次、多项式或域元素可以用根的幂次、多项式或3重矢量表示重矢量表示 若若令令 是是本本原原多多项项式式p(x)=x3+x+1的的根根，，即即 3= +1，可以列出表，可以列出表4-9 因题中要求因题中要求dm=5 ∴∴t = INT[(dm-1)/2]=2这这说说明明生生成成多多项项式式g(x)有有4个个连连续续根根 、、 2、、 3、、 4由由(式式4-32) g(x)=(x- )(x- 2) (x- 3) (x- 4) =[x2-( + 2)x+ 3][x2-( 3+ 4)x+ 7]=[x2- 4x+ 3][x2- 6x+1] = x4-( 6+ 4)x3+ (1+ 10+ 3) x2-( 4+ 9) x+ 10 = x4+ 3x3+ x2+ x+ 3 在上式运算中用到了关系式在上式运算中用到了关系式 3= +1以及二元扩域的一以及二元扩域的一些运算规则，比如些运算规则，比如 i+ i= 0、、 7= 1等等。 此此8进制进制(7,3,5)RS码的生成矩阵为：码的生成矩阵为： G = 通过矩阵行运算可以将它系统化通过矩阵行运算可以将它系统化,得得G = 1 3 1 3 0 0 第第①①行行0 1 3 1 3 0 第第②②行行0 0 1 3 1 3 第第③③行行 1 0 0 4 1 4 5 ①+②①+②× 3 +③+③× 20 1 0 2 1 6 6 ②+③②+③× 30 0 1 3 1 3 ③③生成多项式的运算同样可用除法器实现，生成多项式的运算同样可用除法器实现，只是所作的运算是只是所作的运算是GF(81)域的乘、加运算域的乘、加运算 例：用上面设计的例：用上面设计的(7,3,5)本原本原RS码，对一个二元序码，对一个二元序列（列（111011010……）实行编码实行编码解：将二元序列化作解：将二元序列化作GF(81)元素，得元素，得 m:（（111011010）） ( 5 3 ) C=mG= ( 5 3 ) = ( 5, 3, , 9+ 5+ 4, 5+ 3+ , 2+ 2+ 2 , 3+ 2+ 4) = ( 5 , 3 , , 6, 4 , 2 , 1)对应的对应的(21,9)二进制衍生码字是：二进制衍生码字是：（（111 011 010 101 110 100 001））1 0 0 4 1 4 50 1 0 2 1 6 60 0 1 3 1 3 (7,3,5)RS码码的的t=2，能纠，能纠2个差错。 个差错 衍生为衍生为 (21,9)二元码后，纠随机差错能力与原二元码后，纠随机差错能力与原(7,3)RS码一样码一样t=2，，还能纠长度还能纠长度≤4的任何突发差错的任何突发差错这是因为信道上长度为这是因为信道上长度为4的突发差错最多影响到两个的突发差错最多影响到两个二进制二进制3重矢量，相当于两个重矢量，相当于两个8进码元出错，仍在进码元出错，仍在t=2范围之内范围之内 ( 5 , 3 , , 6, 4 , 2 , 1)（（111, 011, 010, 101, 110, 100, 001））能纠的随机差错能纠的随机差错 （（111, 011, 010, 101, 110, 100, 001））能纠的突发差错能纠的突发差错（（111, 011, 010, 101, 110, 100, 001））（（111, 011, 010, 101, 110, 100, 001）） 不能纠不能纠 上述这种用二进制码表示的上述这种用二进制码表示的q进制进制RS码称为该码称为该RS码的二进衍生码，衍生指码的二进衍生码，衍生指GF(q1)和和GF(2)两个域间的映两个域间的映射。 可以证明，这种映射是把线性码映射成线性码，射可以证明，这种映射是把线性码映射成线性码，映射后的二进衍生码一定是线性分组码，但不一定是映射后的二进衍生码一定是线性分组码，但不一定是循环码 一一般般来来说说，，一一个个随随机机差差错错能能力力为为t的的RS码码，，其其二二进进衍衍生生码码可可以以纠纠正正小小于于等等于于t个个随随机机差差错错，，或或者者纠纠正正单单个长度为个长度为b的突发差错，的突发差错， b≤(t-1)m+1(4-35)以及其它大量错误图样以及其它大量错误图样 可见，二进衍生码特别适用于纠突发差错，这就可见，二进衍生码特别适用于纠突发差错，这就是它在无线通信中被广泛采用的原因是它在无线通信中被广泛采用的原因 q进进制制RS码码也也可可以以扩扩展展对对于于(n,k,d)RS码码(n=q-1)，，可可以以给给每每个个码码字字：：(C0, C1,…, Cn-1)增增加加一个全校验位一个全校验位Cn (mod q) (4-36)使此扩展使此扩展RS码字的全体码元码字的全体码元C0, C1,……, Cn-1之和为之和为零。 可以证明：如果该码字生成多项式零可以证明：如果该码字生成多项式g(x)不含不含(x-1)因子因子 (或或1不是不是g(x)的根的根)，那么加了一个全校，那么加了一个全校验位后，能使扩展码的最小距离增加验位后，能使扩展码的最小距离增加1，即得到，即得到(n+1,k,d+1)扩展扩展RS码比如上例码比如上例 (7,3,5)RS码扩展码扩展出来的出来的(8,3,6)码，其二进衍生码是码，其二进衍生码是(24,9)二元码二元码 IBM 3370磁盘存储系统采用磁盘存储系统采用256进制进制( (255, ,252) ) RS码的缩短码，并对应成码的缩短码，并对应成8比特比特(1(1字节字节) )一组的二进制一组的二进制衍生码该码的基本参数是：衍生码该码的基本参数是：q=28=256, n=q-1 =255, t=1该RS码的码元取自本原多项式码的码元取自本原多项式P(x)=x8+ x4+ x3+ x2+1生成的扩域生成的扩域GF(28), 通过列出类似表通过列出类似表4-9那样的对照表，可以找出域元素运算及与二进制那样的对照表，可以找出域元素运算及与二进制8重矢量映射（衍生）关系，其生成多项式是重矢量映射（衍生）关系，其生成多项式是 g(x)=(x- -1)(x-1) (x- )使用时，一个扇区的使用时，一个扇区的512字节加一个字节加一个0字节变为字节变为513字节，分成字节，分成3组、每组组、每组513 3＝＝171字节，编成字节，编成3个由个由( (255，，252)缩短下来的缩短下来的( (174，，171) RS码字。 实际介码字实际介质中使用的是（质中使用的是（8××174，，8××171））RS衍生码 在在CD 唱片中，采用了两级纠错加交织器的差错控唱片中，采用了两级纠错加交织器的差错控制方案纠错码用的是制方案纠错码用的是q=28=256进制的进制的(255，，251) RS码，纠错能力码，纠错能力t =2使用时，将它缩短为使用时，将它缩短为(28,24)的外码和的外码和(32,28)的内码两种的内码两种 每秒每秒44.1k采样、每采样、每采样采样16比特的数字音频码流比特的数字音频码流(16×44.1k= 1.41Mb/s)被被分割成分割成24字节（字节（192bit））的信息组，每字节对应一的信息组，每字节对应一个个256进制的码元，经（进制的码元，经（28，，24））RS编码器编出编码器编出28字节（字节（224bit））一组的一组的256进制的外码码元这些码进制的外码码元这些码元经元经4行行5列列(4×5字节交织器字节交织器)交织后由交织后由(32，，28) RS编码器二次编码，输出编码器二次编码，输出32字节（字节（256bit））一组内码一组内码码元，每码元写入码元，每码元写入CD盘的一个字节。 读出是写入盘的一个字节读出是写入的逆过程，包括的逆过程，包括RS（（32，，28））内码译码、去交织和内码译码、去交织和RS（（28，，24））外码译码外码译码 整个过程中，整个过程中，24字节音频信号转为字节音频信号转为32字节字节磁盘存储，码率为磁盘存储，码率为0.75，要求，要求CD盘的读出速率盘的读出速率至少大于至少大于1.41 0.75=1.88Mb/s (没考虑其它任何没考虑其它任何开销开销) 具体译码中，当内码遇到一个可检不可纠具体译码中，当内码遇到一个可检不可纠的差错时将会对外码发送一个信息以提高外码的差错时将会对外码发送一个信息以提高外码的纠错能力；当差错超过外码的纠错能力时，的纠错能力；当差错超过外码的纠错能力时，会对播放系统发送一个信息，将该译码样值删会对播放系统发送一个信息，将该译码样值删除而改用前、后样值的插值除而改用前、后样值的插值(interpolating)如如果差错太多而超出了插值运算的能力，播放系果差错太多而超出了插值运算的能力，播放系统将插入一段静音统将插入一段静音(mute)替代这个突发差错替代这个突发差错 在宇航中，在宇航中，RS码和卷积码是一对黄金搭配，码和卷积码是一对黄金搭配，用于深空用于深空(deep space)通信中的纠错编码。 深空信通信中的纠错编码深空信道属随机差错信道，用卷积码比较合适但一旦信道属随机差错信道，用卷积码比较合适但一旦信道噪声超出卷积码的纠错能力，就将导致突发性质道噪声超出卷积码的纠错能力，就将导致突发性质的译码差错，这时用的译码差错，这时用RS码来对付将是最佳选择码来对付将是最佳选择在在“探险者号探险者号”(Voyager) 飞向木星和土星的旅程飞向木星和土星的旅程中，信息就是以中，信息就是以RS码为外码、卷积码为内码的级码为外码、卷积码为内码的级联码实现信道编码的这种级联码性能优良，已被联码实现信道编码的这种级联码性能优良，已被认为是一种宇航通信标准而称为认为是一种宇航通信标准而称为‘NASA’码，可带码，可带来来5～～7dB的编码增益的编码增益 探险者探险者Voyager采用了采用了(255,223)RS码，在误比码，在误比特率特率Pb=10-6时可获得时可获得2.5dB额外编码增益（与仅用额外编码增益（与仅用卷积码相比）该卷积码相比）该RS码每码字的码每码字的255个码元取值于个码元取值于256进制进制GF（（256））的衍生二进制扩域的衍生二进制扩域GF（（28），），生成扩域元素的本原多项式是生成扩域元素的本原多项式是P(x)=x8+ x4+ x3+ x2+ 1，，生成多项式是生成多项式是 g(x)=（（x- ）（）（x- 2）（）（x- 3））…（（x- 32））式中式中 是本原多项式是本原多项式P(x)的根。 由于生成多项式含的根由于生成多项式含32个连续幂次的根，可知该码的纠错能力个连续幂次的根，可知该码的纠错能力 t =16码码元（元（256进制），或长度进制），或长度121 (式式4-35)的二进制突发的二进制突发差错。
