信息论与编码理论 第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