信息论与编码理论 第8章循环码 习题解答-20071211

第8章 循环码

习题答案：

1. 已知(8, 5)线性分组码的生成矩阵为

11 G001（1）证明该码是循环码；

111000000010001000100

01000101100001（2）求该码的生成多项式g(x)。

（1）证明如下：

1 1 1 1 0 0 0 01 1 1 1 0 0 0 01 0 0 0 1 0 0 0 0 1 1 1 1 0 0 0 (1)(2)(2)(3)0 1 0 0 0 1 0 0 0 1 0 0 0 1 0 0 0 0 1 0 0 0 1 00 0 1 0 0 0 1 01 1 1 0 0 0 0 11 1 1 0 0 0 0 11 1 1 1 0 0 0 01 1 1 1 0 0 0 00 1 1 1 1 0 0 0 0 1 1 1 1 0 0 0 (3)(4)(1)(5)0 0 1 1 1 1 0 0 0 0 1 1 1 1 0 0 0 0 1 0 0 0 1 00 0 0 1 1 1 1 01 1 1 0 0 0 0 11 1 1 0 0 0 0 11 1 1 1 0 0 0 01 1 1 1 0 0 0 00 1 1 1 1 0 0 0 0 1 1 1 1 0 0 0 (4)(5)0 0 1 1 1 1 0 0 0 0 1 1 1 1 0 0 0 0 0 1 1 1 1 00 0 0 1 1 1 1 00 0 0 1 0 0 0 10 0 0 0 1 1 1 1由生成矩阵可知为（8、5）循环码。 （2）生成多项式如下：

g(x)x3x2x1

1

信息论与编码理论

2. 证明：x10x8x5x4x2x1为(15, 5)循环码的生成多项式，并写出信

息多项式为m(x)x4x1时的码多项式（按系统码的形式）。

由定理8-1可知（n，k）循环码的生成多项式g(x)为xn+1的因子， g(x)为n-k次多项式，本题目中知：g(x)x10x8x5x4x2x1为一个10次多项式，n-k=15-5=10

并且：(x151)mod(x10x8x5x4x2x1)0

所以：x10x8x5x4x2x1是x151的一个因子，也是循环码的生成多项式。

按系统码构造多项式如下：

m(x)x4x1

m(x)xnk(x4x1)x10x14x11x10b(x)(m(x)xnk)mod(x10x8x5x4x2x1) x8x7x6xc(x)m(x)xnkb(x)x14x11x10x8x7x6x

3. 已知(7, 4)循环码的生成多项式为g(x)x3x1，信息多项式为

m(x)x31，分别由编码电路和代数计算求其相应的码多项式C(x)。 由题目可知代数计算求解过程如下：

m(x)x31m(x)xnkx6x3b(x)(m(x)xnk)mod(x3x1)x2x c(x)m(x)xnkb(x)x6x3x2xc(1001110)由编码电路进行求解： 编码电路如下所示：

2

信息论与编码理论

门1D0+D1D2+或门c(x)m编码过程如下： 时钟 0 1 2 3 4 5 6 7 信息元 1 0 0 1 寄存器码字 D0 D1 D2 0 0 0 1 1 0 0 1 1 1 1 1 0 1 1 0 0 1 0 0 0 0 0 0 输出码字 1 0 0 1 1 1 0 可得：c(x)x6x3x2x

4. 令(15, 11)循环码的生成多项式为g(x)x4x1，计算

（1）若信息多项式为m(x)x10x81，试求编码后的系统码字； （2）求接收码组R(x)x14x4x1的校正子多项式。

(1)解题过程如下：

m(x)x10x81m(x)xnkm(x)x4x14x12x4b(x)(m(x)xnk)mod(x4x1)x21c(x)m(x)xnkb(x)x14x12x4x21c(1010000000010101)（2）校正多项式如下所示：

R(x)x14x4x13S(x)mod(g(x))x1 4g(x)xx15. 码长为n=15的本原BCH码，求不同纠错能力下的BCH码各自的生成多项式

g(x)。

3

信息论与编码理论

n2m115m4

纠错能力：t2m18，所以最多能纠正7个错误码。

有限域GF（24），4次本原多项式f(x)x4x1，α为f(x)的一个根，可知：

410，计算2t=14个连续幂次为对应的最小多

项式：

m1(x)x4x1,m2(x)x4x1,m3(x)x4x3x2x1m4(x)x4x1,m5(x)x2x1,m6(x)x4x3x2x1m7(x)x4x31,m8(x)x4x1,m9(x)x4x1m10(x)x2x1,m11(x)x4x3x2x1m12(x)x4x3x2x1,m13(x)x2x1,m3(x)x4x31

(1) t=1的码字： (15，11)BCH码 g1(x)Lcm(m1(x))x4x1 (2)t=2的码字：(15，7)BCH码

g2(x)Lcm(m1(x)m3(x))x8x7x6x41 (3)t=3的码字：(15，5)BCH码

g3(x)Lcm(m1(x)m3(x)m5(x))x10x8x5x4x2x1 (4) t=4的码字：(15，1)BCH码

g4(x)x14x13x12x11x10x9x8x7x6x5x4x3x2x1 (5) t=5的码字：(15，1)BCH码

g5(x)x14x13x12x11x10x9x8x7x6x5x4x3x2x1 (6) t=6的码字：(15，1)BCH码

g6(x)x14x13x12x11x10x9x8x7x6x5x4x3x2x1 (7) t=7的码字：(15，1)BCH码

g7(x)x14x13x12x11x10x9x8x7x6x5x4x3x2x1

6． 构造一个能纠正t=3个错误符号，码长为15，m=4的RS码，并求其生成矩阵。

码长：n=q-1，q2m16，m=4

4

信息论与编码理论

dmin2t17

n-k=2t=6 k=n-2t=15-6=9 可知RS码为：（5，9）码

设α为本原多项式f(x)x4x1的根，即：41

t=3，生成多项式g(x)有6个连续的根，

g(x)(xxxxxx)x610x5x44x36x29x6

（15，9）的RS码的生成矩阵如下：

1 α10 α14 α4 α6 α9 α6 0 0 0 0 0 0 0 00 1 α10 α14 α4 α6 α9 α6 0 0 0 0 0 0 0 0 0 1 α10 α14 α4 α6 α9 α6 0 0 0 0 0 0140 0 0 1 α10 α α4 α6 α9 α6 0 0 0 0 00 0 0 0 1 α10 α14 α4 α6 α9 α6 0 0 0 0 0 0 0 0 0 1 α10 α14 α4 α6 α9 α6 0 0 0 0 0 0 0 0 0 1 α10 α14 α4 α6 α9 α6 0 00 0 0 0 0 0 0 1 α10 α14 α4 α6 α9 α6 00 0 0 0 0 0 0 0 1 α10 α14 α4 α6 α9 α65