第3章CyclicCodes_hcp

1、2021-11-25天津大学电子信息工程学院1 Cyclic codes are a subclass of linear block codes. Found first by Prange in 1957. BCH and Reed-Solomon codes are a class of cyclic codes. Based on the mathematical theory of finite fields or Calois fields.Chapter 3 Cyclic Codes2021-11-25天津大学电子信息工程学院2 BCH codes Presented respe

2、ctively by Bose and Chaudhuri in 1960 , and by Hocquenghem in 1959. BCH is a kind of binary cyclic code. RS codes Structured by Reed and Solomon in 1960. RS is a kind of nonbinary cyclic code.2021-11-25天津大学电子信息工程学院33.1 Description of cyclic codes1. Definition A linear (n,k) code is called a Cyclic c

3、ode if all cyclic shifts of a codeword are also a codeword.Hence, if (cn-1 ， ， c1 ，c0) is a codeword of a cyclic code, then so is its cyclic shift (cn-2， ， c1，c0 ， cn-1 ) or (c0， cn-1 ，c2 ， c1).2021-11-25天津大学电子信息工程学院4 Denoted by polynomial form for ci GF(2)， If Its cyclic right shift is a codeword a

4、nd there are110121210(,)( )nnnnnCcccC xcxcxc xc),(1110cccCn),(10121nnccccC10331210122110)()(nnnnnnnnncxcxcxcxCcxcxcxcxC2021-11-25天津大学电子信息工程学院5 So that )1mod()()(01nxxxCxC)1mod()()()(,)1mod()()()()1mod()()()(012103230212nnnnnnxxCxxxCxCxxCxxxCxCxxCxxxCxC2021-11-25天津大学电子信息工程学院6The space of cyclic codes

5、 is close, sois also a codeword. C0(x) is a code polynomial at code space. A(x) belong to a vector space with n dimensions.)1mod()()()()()()()()()()()()(00012211000102201100112211nnnnnnnnnnnnnxxCxAxCaxaxaxaxCaxxCaxCxaxCxaxCaxCaCaxCaxC2021-11-25天津大学电子信息工程学院72. Two theorems about cyclic codes定理定理3.13.

6、1在一个GF(2)域上的(n，k)循环码中，一定存在唯一的次数最低的n-kn-k次首一码多项首一码多项式式g(xg(x) ),为：使所有的所有的码多项式码多项式都是都是g(x)g(x)的倍式的倍式，且所有的小于小于n n次的次的g(x)g(x)的倍式的倍式都是码多项式。1)(111xgxgxxgknknkn2021-11-25天津大学电子信息工程学院8 结论：结论：码多项式一定可以写成码多项式一定可以写成 的形的形式。式。 m(x) 的次数一定小于的次数一定小于 。g gn-kn-k和和g g0 0恒等于恒等于 。g(xg(x) )被称作被称作 。2021-11-25天津大学电子信息工程学院9

7、定理定理3.23.2（存在性定理）（存在性定理） (n,k)(n,k)循环码的循环码的生成多项式生成多项式g(x)g(x)一一定是定是x xn n-1-1的因式的因式。 即一定存在一个多项式即一定存在一个多项式h(x)h(x)，满，满足足x xn n-1=h(x)g(x)-1=h(x)g(x)，或者，或者g(x)| xg(x)| xn n-1-1；反之，如果反之，如果g(x)g(x)是是x xn n-1-1的的n-kn-k次因式，次因式，g(x)g(x)一定是某个一定是某个(n(n，k)k)循环码的生成循环码的生成多项式。多项式。2021-11-25天津大学电子信息工程学院10（1 1）对）对

8、x xn n-1(-1(在二元域中等效于在二元域中等效于x xn n+1)+1)进行因进行因式分解，找出其中的式分解，找出其中的n-kn-k次因式；次因式；既约性问题？因式分解的三种情况？3.2 构成循环码的方法构成循环码的方法2021-11-25天津大学电子信息工程学院11（2 2）找到了找到了n-kn-k次因式，作为循环码生成多次因式，作为循环码生成多项式项式g(x),g(x),与信息多项式与信息多项式m(x)m(x)相乘，即得到相乘，即得到码多项式：码多项式：其中，m(xm(x) )最高为最高为k-1k-1次信息多项式次信息多项式；)()()(xgxmxC0111011)(),(mxmx

9、mxmmmmmkkk2021-11-25天津大学电子信息工程学院12例例3-1分析码长分析码长n=7n=7的二进制循环码的所有可能结构。的二进制循环码的所有可能结构。解：解：2021-11-25天津大学电子信息工程学院13 若选择g(x)= (x+1)(x3+x+1 )= x4+ x3 + x2 +1为生成多项式； 则码多项式为C(x)=m(x)g(x)=(m2x2+m1x+1) (x4+ x3 + x2 +1)； 若m=(011)，m(x)=x+1，)0100111(1)1)(1()(25234CxxxxxxxxC信息矢量(m2m1m0)码矢量(c6c5c4c3 c2c1c0)0000000

10、0000010011101010011101001101001111001110100101110100111010011101111010011(7(7，3)3)循环码码集循环码码集2021-11-25天津大学电子信息工程学院14 上述方法得到的循环码不是系统码不是系统码。 系统码系统码：构成的码字前面是k位是原信息比特 m(x)是是k-1k-1次，放在最高位次，放在最高位n-1n-1次次，后面是n-k为校验位，即有如下形式： r(x)是码字中n-kn-k个校验元个校验元对应的n-k-1n-k-1次次多项式： 计算方法：)()()(xrxmxxCkn2021-11-25天津大学电子信息工程学

11、院15产生系统循环码产生系统循环码的步骤的步骤：（1）信息多项式m(x)乘以xn-k，相当于循环右移n-k位；（2）用m(x) xn-k除以g(x)，得到余式r(x)。（3）系统码的码多项式就可以写成：)()()(xrxmxxCkn2021-11-25天津大学电子信息工程学院16根据定理根据定理3.2,3.2,有有如果如果g(xg(x) )是码生成多项式，那么是码生成多项式，那么h(xh(x) )一定是循环码的校验多项式，对于任一定是循环码的校验多项式，对于任意的一个码多项式意的一个码多项式C(xC(x) )，有：，有：证明：证明：)()(1xhxgxn)1mod(0)()(nxxhxC202

12、1-11-25天津大学电子信息工程学院173.3 循环码的矩阵描述 由前面的式子， 可以用矩阵表示为：)()()()()()()()(01110111xgmxxgmxgxmxgmxmxmxgxmxCkkkk01021110110111011,)()()(,)(gxgxgxgxgxgxgxgxgmmmxgxxgxgxmmmxCknknknknkknknkkk2021-11-25天津大学电子信息工程学院18 将矩阵中的多项式改成矢量，得到矢量矩阵表达式为： 由定理3.2，有mGgggggggggmmmcccxCknknkknkn010101010110110000000,),()(个k-1个0)(

13、)()(10101hxhxhgxgxgxhxgxkkknknn2021-11-25天津大学电子信息工程学院19 校验矩阵可以写成： 这样有，kkkhhhhhhhhhH10021100000TGH2021-11-25天津大学电子信息工程学院203.4 缩短循环码 Reason Purpose Rule of selection 在（n,k）循环码的2k个码字中挑选，选择前i个信息比特位均为0的码字（共有2k-i个这样的码字）,作为（n-i，k-i）缩短循环）缩短循环码的码字码的码字。2021-11-25天津大学电子信息工程学院21缩短循环码的特点：缩短循环码的特点：是是(n(n，k)k)循环码的

14、子集；循环码的子集；纠错能力不变；纠错能力不变；循环性丧失。循环性丧失。2021-11-25天津大学电子信息工程学院223.5 循环冗余校验码（CRC） 是一种系统缩短循环码系统缩短循环码，广泛应用于帧校验。CRC码的帧结构：习惯上仅将习惯上仅将n-kn-k校验部分称为校验部分称为CRCCRC码码。 对于系统码，在发送端：r(xr(x) )等于等于x xn-kn-km(xm(x) )除以除以g(xg(x) )后的余式后的余式。m(x),共k位r(x),n-k位)()()(xrxmxxCkn2021-11-25天津大学电子信息工程学院23 对于接收码接收码R(x)，如果无误码无误码应该有： 没有

15、误码时，R(x)应该能被生成多项式g(x)整除。即 如果不能整除，必定在传输中出现了误码。)()(xCxR)()()()()()(xgxqxrxmxxCxRkn)()()()(xrxgxqxmxkn2021-11-25天津大学电子信息工程学院24例例3-2 某CRC码的生成多项式g(x)=x4+x+1，如果想发送一串信息110001的前6位，并加上CRC校验，发送码应该如何安排发送码应该如何安排？接收码应接收码应该如何校验该如何校验？解：解：2021-11-25天津大学电子信息工程学院25 两边除以g(x)= x4+x+1 ， 得余式：r(x)=x3+x2 所以发送码发送码为： 对应的矢量为（

16、1100011100）。23489)()()(xxxxxxrxmxxCkn)(11001001110000100111011110011110001000000101110011余式2021-11-25天津大学电子信息工程学院26 在接收端，实际的方法是做除法： 无误码，R(x)除以g(x)，余式为0； 有误码，余式不为0)0(000010011100111001110111100110110001111000101110011余式为2021-11-25天津大学电子信息工程学院27 国际上常用的循环码 CRC-ITU-T：国际电联定义的CRC，用于X.25、7号信令等应用中。 CRC-12：

17、CRC-16：用于美国的二进制同步系统； CRC-32：用于以太网、ATM等。 CRC-IS-95 CDMA：1)(51216xxxxg1)(231112xxxxxxg1)(21516xxxxg1)(245781011121622232632xxxxxxxxxxxxxxxg1)(26781112131520212930 xxxxxxxxxxxxxxg2021-11-25天津大学电子信息工程学院28CRC（循环冗余校验码） 循环性？ 冗余性？设计CRC 先设计循环码（ n0，k0 ）； 再缩短 i 位，得到（ n0 - i ， k0 - i ）=（n,k）。纠错能力 与循环码相同； 循环性丧失。

18、2021-11-25天津大学电子信息工程学院293.6 BCH码 是纠错能力可控纠错能力可控的循环码； g(x)与dmin关系密切。根据dmin，可以轻易地构造出具有特定纠错能力纠错能力的码的码； 于1959年 由Hocquenghem、1960年 由Bose和Chandhari 分别 独立提出。2021-11-25天津大学电子信息工程学院30一般分组码与循环码的比较一般分组码分组码生成矩阵循环码循环码生成矩阵k个基底相互独立k个基底由一个基底循环而来有kn个独立的参数gij 。只有n-k-1个独立的参数gn-k-1 g1 （ g0和 gn-k的值恒为1 ）。010101010000000gg

19、gggggggGknknkkn个0001)1(01011)1(10)1(1)1()1)(1(gggggggggGnnkknkk个基底 ?2021-11-25天津大学电子信息工程学院31分组码分组码循环码：循环码：“基底基底”的产生方式的产生方式；循环码循环码 BCH BCH码：码：码生成多项式产生方式码生成多项式产生方式： 循环码用用GF(2)GF(2)上多项式上多项式定义定义； BCH码是用用GF(2GF(2m m) )扩展域上的根扩展域上的根定义。2021-11-25天津大学电子信息工程学院323.6.1 用根定义循环码 由定理定理3.13.1和定理3.2，构造构造(n(n，k)k)循环码

20、循环码： 先对xn-1做因式分解，化成 l 个既约因式个既约因式nj(x)的的乘积乘积； 用一个因式或多个既约因式的乘积一个因式或多个既约因式的乘积，构成n-k次多项式，即循环码的码生成多项式g(x)； 用数学描述：)()()(110 xhxgxnxljjn因式分解2021-11-25天津大学电子信息工程学院33 g(x) 可以是既约的，也可是非既约的。 若一个既约因式既约因式 nj(x)是非既约非既约g(xg(x) )的一一个因式个因式，可写成： 关键问题：关键问题：如何分解如何分解xn-1； 在复数域， xn-1可以分解成：可以分解成：)1( | )(| )(njxxgxn)()(1110

21、nnaxaxaxx2021-11-25天津大学电子信息工程学院34例例3-3对x4-1在实数域、复数域和二元域进行因式分解。 解：解： 在实数域： x4-1=(x2+1) (x+1) (x-1) 在复数域： x4-1=(x+i) (x-i) (x+1) (x-1) 在二元域： x4-1= x4+1=(x+1) (x+1) (x+1) (x+1)2021-11-25天津大学电子信息工程学院35由定理由定理3.23.2：以GF(2)上的本原多项式做模乘，可以生成GF(2m) 上一个多项式循环群一个多项式循环群。 在扩展域GF(2m)中，至少存在一个本原元至少存在一个本原元 ，它的各次幂0 ， 1，

22、 2， ，等于扩展域GF(2m)的全部非0的域元素。 本原元本原元 的阶阶 。 n阶 非本原元非本原元 的阶阶一定是 。22 m2021-11-25天津大学电子信息工程学院36定理3.3： 若GF(2m)上n n阶域元素阶域元素 是是 x xn n-1 -1 的根的根，则一定有：证明：证明：101()nniixx2021-11-25天津大学电子信息工程学院37 因此，要对xn-1进行分解 在GF(2m)域上，关键是：找到一个找到一个n n阶域元素阶域元素 ，使使 n-1=0； n = 2m-1， 是本原元本原元； n 2m-1， 且 n | (2m-1)， 是非本是非本原元原元。2021-11

23、-25天津大学电子信息工程学院38 综合前面的分析xn-1可以在不同的域中分解成：)()()(1)(1010 xhxgxpxxljjnnii GF(2m)扩展域 GF(2)域2021-11-25天津大学电子信息工程学院39 总可以找到 xn-1的的某个根根 i i 0，1，n-1，是一个既约因式 pj(x) j 0，1，l-1的根的根；而pj(x)是g(x)的一个因式的一个因式，那么有有： i是 n n 阶阶本原元时，有 i是 n n阶阶 非本原元时，有11| )(| )(| )(12mxxxgxpxnji)1( | )1( | )(| )(| )(12mxxxgxpxnji2021-11-2

24、5天津大学电子信息工程学院40 分析表明: ?（1）g(xg(x) )的的 n-kn-k 个根个根 一定一定是xn-1的根；根；（2）用根构成循环码的关键：）用根构成循环码的关键：找到这些根，找到这些根，构成构成g(x) 。 有有重根的g(x)不能生成好码； xn-1无重根，g(x)一定无重根； GF(qm)上， xn-1无重根的充分必要条件：充分必要条件：n n和和q q互互素素。（3） xn-1的根中，根中，g(x)有 个根，其余 的 个根一定是 的根。a2021-11-25天津大学电子信息工程学院41在在 GF(2GF(2m m) )上，上，用用x xn n-1-1的根的根构造循环码：构

25、造循环码：(1) 在xn-1的n个根中，选择其中的n-k个根r1， r2， rn-k， rj i，i = 0，1，n-1，j=1 ，2，n-k。(2)找出各个根所对应的既约多项式：(3)求出这些既约多项式的最小公倍式最小公倍式每个p（x）都能整除g(x)：如果选则的根具有连续的幂次，g(x)生成一个BCH码。否则为一般循环码。)(),(),(2211xprxprxprknkn)(),(),()(21xpxpxpLCMxgkn2021-11-25天津大学电子信息工程学院423.6.2 BCH 码的设计q进制BCH码的定义：对GF(q)上 循环码的生成多项式g(x)，若含有 2t 2t 个个连续幂

26、次连续幂次的根的根， 则由g(x)生成的 (n,k) 循环码称为q 进制的BCH码。若q=2，则称为二进制二进制（二元）BCH码。,121000tmmm2021-11-25天津大学电子信息工程学院43 本原BCH码? 码长n=qm-1 非本原BCH码? 码长 n | qm-1 连续幂次根的 数目 2t? 连续幂次的初始值 m0 的选择？2021-11-25天津大学电子信息工程学院44定理定理3.43.4（BCHBCH码限定理）码限定理）若BCH码生成多项式g(x)中含有2t个连续幂次的根，则该码的最小距离dmin2t+1。证明：证明：2021-11-25天津大学电子信息工程学院45210121

27、222 22101212222210121( )0()()()0()()()0nnnntttt nnCccccCccccCcccc210121( )nnC xcc xc xcx设码多项式为：用根用根 x = ， x = 2， x = 2t代入，有：代入，有：2021-11-25天津大学电子信息工程学院46 写成矩阵形式， C=(c0，c1，cn-1) 是 1n 阶矩阵； A是由 的2t个根的各次幂构成，是2t n阶矩阵，结构为：A被称为范德蒙（Vandermonde）矩阵。0TGA122221222212)()(1)()(11ntttnnA2021-11-25天津大学电子信息工程学院47 范德

28、蒙矩阵一定是满秩的范德蒙矩阵一定是满秩的。 矩阵A（ 2t n阶）的秩是2t； 矩阵A 有有2t2t列线性无关列线性无关。 CAT=0，A A是是 。定理定理3.53.5 分组码分组码的最小距离dmin等于等于校验矩阵校验矩阵中线性无中线性无关的列数关的列数+1+1，因此BCH码的最小距离为：可纠t个错误。12min td2021-11-25天津大学电子信息工程学院481 1、构造、构造本原本原BCHBCH码码已知条件：已知条件： 码长码长n n、纠错能力纠错能力t t构造步骤：构造步骤：（1）n = 2m-1，查表查表3.1找一个 m m次次本原多项式P(x)，产生一个GF(2m)扩展域。2

29、021-11-25天津大学电子信息工程学院49m多项式的非0项m多项式的非0项m 多项式的非0项11 01212 7 4 3 023 23 5 022 1 01313 4 3 1 024 24 4 3 1 033 1 01414 12 11 1 025 25 3 044 1 01515 1 026 26 8 7 1 055 2 01616 5 3 2 027 27 8 7 1 066 1 01717 3 028 28 8 077 1 01818 7 029 29 2 088 6 5 1 01919 6 5 1 030 30 16 15 1 099 4 02020 3 031 31 3 010

30、10 3 02121 2 032 32 28 27 1 011 11 2 02222 1 033 33 13 0表3.1 本原多项式表（m34）2021-11-25天津大学电子信息工程学院50（2）在GF(2m)上找一个本原元本原元 利用本原多项式利用本原多项式P(x)P(x)的根的根； 需要得到 2t 个连续幂次 ， 2， 2t 对应的GF(2)域上的最小多项式 p1(x)， p2(x) ， p2t(x)； 查表查表3.23.2 得到 i i 对应的最小多项式对应的最小多项式。2021-11-25天津大学电子信息工程学院51表3.2二元扩展域二元扩展域GF(2m)中连续幂次根所对应的最小多项

31、式i最小多项式i最小多项式i最小多项式i最小多项式m=2 1(0,1,2)m=3 1(0,1,3)3(0,2,3)m=4 1(0,1,4)3(0,1,2,3,4)5(0,1,2)7(0,3,4)m=5111(0,2,5)(0,1,3,4,5)315(0,2,34,5)(0,3,5)5(0,1,2,4,5)7(0,1,2,3,5)m=61921(0,1,6)(0,2,3)(0,1,2)31123(0,1,2,4,6)(0,2,3,5,6)(0,1,4,5,6)51327(0,1,2,5,6)(0,1,3,4,6)(0,1,3)71531(0,3,6)(0,2,4,5,6)(0,5,6)m=7 1

32、9192955(0,3,7)(0,1,2,3,4,5,7)(0,1,6,7)(0,1,3,5,7)(0,2,3,4,5,6,7)311213163(0,1,2,3,7)(0,2,4,6,7)(0,2,5,6,7) (0,4,5,6,7)(0,4,7)5132343(0,2,3,4,7)(0,1,7)(0,6,7)(0,1,2,5,7)7152747(0,1,2,4,5,6,7) (0,1,2,3,5,6,7)(0,1,4,6,7)(0,3, 4,5,7)2021-11-25天津大学电子信息工程学院52（3）计算最小多项式的最小公倍式最小公倍式，得到g(x)：（4）C(x) = m(x) g(x

33、)，计算得到 BCH的码字。)(),(),()(21xpxpxpLCMxgkn2021-11-25天津大学电子信息工程学院53 对于二元BCH， 第2步可以简化： 一个偶数偶数 ie可以写成一个小于或等于它的一个小于或等于它的奇数奇数 io 与 2l 之积，即有： 一个根的偶次幂可写成：一个根的偶次幂可写成：1213221 2 ;41 2 ;63 2 ;8 1 2 .leoii 如：loloeiii22)(2021-11-25天津大学电子信息工程学院54例例3-4根据二元域的特殊性质，试推导t=4时二元BCH的生成多项式g(x)表示式。解：解：2021-11-25天津大学电子信息工程学院55参

34、数参数 n n、k k、t t 和和 m m 之间的关系：之间的关系：q元BCH码，有：二元BCH码，有： xn-1共有n个根，连续幂次根的个数：tmknxg2)(degtmknxg)(degnt 22021-11-25天津大学电子信息工程学院56例例3-5设计一个码长 n = 15的本原BCH码，问在不同纠错能力下的生成多项式g(x)是什么？解：解：2021-11-25天津大学电子信息工程学院572 2、构造、构造非本原非本原BCHBCH码码 非本原非本原BCHBCH码与本原码与本原BCHBCH码码： 区别区别：根是不是本原的，由给定的n确定； 本原BCH码：n 和 t 给定，由n= 2m-

35、1，n已已知等于知等于m已知已知，因此GF(qm)能确定； 非本原BCH码：n | 2m-1， n已知不等于已知不等于m已已知知，多一个计算m的步骤；2021-11-25天津大学电子信息工程学院58已知条件：已知条件： 码长码长 n n、纠错能力纠错能力t t构造步骤：构造步骤：（1）找满足 n | (2m-1)关系的最小m 。借助2m-1的素因子分解表素因子分解表3.33.3来查找m值。例例3-6 n=23，利用素因子分解表3.3求m值。解：解：2021-11-25天津大学电子信息工程学院59表3.3 2m-1的素因子分解（m34）m素因子分解m素因子分解m素因子分解11123 3 5 7

36、132347 17848123138191243 3 5 7 13 17 24137143 43 1272531 601 1801435157 31 151263 2731 8191531163 5 17 257277 73 26265763 3 717131071283 5 29 43 113 1277127183 3 3 7 19 7329233 1103 208983 5 171952428730337113115133197 73203 5 11 31 4131214748367103 11 31217 7 127 337323 5 17 257 655372021-11-25天津大学

37、电子信息工程学院60（2）查表3.1 ，找一个m阶的本原多项式P(x)，生成一个二元扩展域GF(2m)。（3）以 P(x) 的根为中介，找一个 n阶阶 的非非本原元本原元 ，使nm122021-11-25天津大学电子信息工程学院61（4）计算与 ， 3， 5， 2t-1 对应的最小多项式m1(x)，m3(x) ，m2t-1(x) 。（5）计算生成多项式g(x) = LCM m1(x)，m3(x) ，m2t-1(x) 2021-11-25天津大学电子信息工程学院62例例3-7 试设计一个码长n=23，纠两个随机错误 (t=2) 的二元二元BCH码。 解：解：2021-11-25天津大学电子信息工

38、程学院63（4）求连续奇次幂对应的最小多项式： 先找出共轭元： 11个域元素都是共轭元，g(x)至少是11次的124231223623332621313131323362918299992332216282422232254321)( ,)( ,)( :,)( :,)( ,)( :,:18161312986432,2021-11-25天津大学电子信息工程学院64 对应的最小多项式m1(x)（5）t=2时，生成多项式g(x)为构成了(23，12)非本原BCH码，即著名的二元二元高莱码高莱码。g(x)m1(x)有几个连续幂次的根？1)()()()()()()()()()(567911181613129864321xxxxxxxxxxxxxxxxxxm1)()()(56791121xxxxxxxmxmLCMxg2021-11-25天津大学电子信息工程学院653 3、几点说明、几点说明 (1) 为了求g(x)，必须先求GF(2