第九章 循环码
9.1 什么是循环码？如何用多项式来描述一个循环码？
解答： 一个线性分组码，若具有如下特性，则称为循环码。设码字 c=(cn-1 cn-2 ? c1 c0) 将码元左移一位，得 c1=(cn-2 ?c1 c0 cn-1) 也是一个码字，则称此分组码为循环码。 把码长为n的码组中的各码元当作n-1次多项式的系数
若码组C=（cn-1，cn-2，??，c1，c0)，则其相应的码多项式为： C(x)= cn-1xn-1+ cn-1xn-1+ ??+ c1x+ c0
对应于每一码字，可以写出相应的码字多项式(最高次数小于n次) C (x) = c n-1 x n-1 +cn-2 x n-2+?+c1 x +c0 C1(x) = cn-2 x n-1+c n-3 x n-2+?+c0 x +c n-1 C2(x) = cn-3xn-1+cn-4xn-2+?+cn-1x+cn-2 Cn-1(x) =c0 xn-1+cn-1xn-2+?+c2 x+c1 对于上述多项式，有
x ?C (x) + C1 (x) = cn-1 x n + cn-1 = cn-1 (xn + 1 ) x ?C (x) + C1 (x) ≡0 mod (xn +1) C1 (x) ≡x?C (x)
x2? C (x) + C2 (x) = cn-1 (xn +1) C2 (x) ≡ x2 ?C (x) mod (xn +1)
Ci (x) ≡xi ?C(x) mod (xn + 1)
C n-1 (x)≡x n-1 C1(x) mod (xn+1) 得出结论：
在循环码中，若C(x)是一个长为n的许用码组，则xi? C(x)在按模xn+1运算下，也是一许用码组。即若
xi? C(x)≡Ci(x) （模xn+1）
则Ci(x) 也是一许用码组，且为C(x)码组向左循环移位i次的结果。
9.2 循环码的生成多项式是如何定义的？ 生成多项式g(x)有什么特点和性质？
答：若一个循环码的所有码子多项式都是一个次数最低的非零首一多项式g(x)的倍式，则g(x)生成该码，并称g(x)为该码的生成元或者生成多项式。 g(x)的特点和性质：
1.g(x)是一个次数最低的唯一的首一多项式，其次数r=n-k正好是码字中检验元的数目。
n
2.生成多项式g(x)是x-1的因式。
n
3.由x-1=g(x)h(x),h(x)称为校验多项式。对于任意一个(n,k)循环码，必有g(x)h(x)=0mod nT
x-1及G·H=0.
9.3 循环码的生成多项式g(x)和校验多项式h(x)之间有什么关系？如何在已知码的生成多项式和校验多项式的情况下，得到对应的生成矩阵和校验矩阵？
解：
n
若g（x）是（n,，k）循环码的生成多项式，则有校验多项式h(x)使g(x) h(x)=x-1,h(x)
T
为k次多项式。且有生成矩阵G和校验矩阵H，G H=0.
n-k n-k-1
若有生成多项式g(x)=gn-k x+ gn-k-1 x + ??+g1 x+g0 ，由于k个码多项式必线性无关，故可以构造出生成矩阵G
g1g00??^0??gn?kgn?k?1???0?gn?kgn?k?1??g1g0??0? G????????0??0gn?k??g1g0??同样的，也能通过h(x)求出校验矩阵H。
9.4试述利用生成多项式
实现循环编码的步骤。如何用电路实现编码。
成为
，
答：系统循环码的编码方法：首先将信息元多项式m(x)乘以然后将
而得到码字多项式
。
用电路实现编码可采用以入信息元组冲在1到
从个节拍内，
以生成多项
得到余式
,该余式就是校验元多项式，从
为除式的除法电路。在除法电路的基础上，将输
乘以
。移位脉
个寄存器的高端输入，相当于
打向“1”，各信息元直接经
除以
输出，成为系统码的前
的运算。运算结束到
个节拍内，
个码元；同时它们又依次进入除法电路，进行时留在移位寄存器中的存数就是余式
的系数。然后，cp在
打向“2”，使移位寄存器中的各校验元依次输出，形成一个长为的码字。
9.5 利用接收序列y(x)的伴随式s(x)进行检错的原理是什么？
答：接收端译码器由伴随式确定错误图样然后从接收到的码字中减去错误图样。
9.6 什么样的运算叫做s(x)的自发运算？它对循环码的译码有何意义？
解答：若S(x)是接收码字多项式R(x)的伴随式，则R(x)的一次循环移位
xR(x) (mod xn?1)的伴随式S1(x)是S(x)在伴随式计算电路中无输入
时，右移一位的结果（称称为自发运算），即有
1
把某一可纠正的错误图样e(x)及其所有的小于等于n－1次的循环移位归成一类，用一个错误图样来代表。译码时只要计算这个错误图样的伴随式，该类中其它错误图样的伴随式都可由该伴随式在g(x)除法电路中循环移位来得到。
把某一可纠正的错误图样e(x)及其所有的小于等于n－1次的循环移位归成一类，用一个错误图样来代表。译码时只要计算这个错误图样的伴随式，该类中其它错误图样的伴随式都可由该伴随式在g(x)除法电路中循环移位来得到。
9.7 Meggit通用译码器有什么特点？为什么这种译码器能够实现连续译码输出？ 答：特点：将s(x)计算电路与s(x)自发运算电路并行完成，实现了连续译码输出。
因为接收码字y(x)一方面被送入n级移位寄存器，一方面被送入s(x)计算电路，经n节拍后，将在s(x)计算电路中得到的s(x)送入自发运算电路。 S(x)自发运算电路在结构上与s(x)计算电路相同。从n+1拍至2n拍完成该码字对应伴随式的自发运算及纠错、译码输出。于此同时，第二个接收码字一方面被送入n级移位寄存器，一方面被送入s(x)计算电路。可见，前一个码字的纠错译码过程与后一个码字的s(x)计算过程在时间上是重叠的。虽然每一个码字在译码器中仍需逗留2n拍，但从整体上，该译码器实现了连续译码输出。
42
9.8 已知（7,3）码的生成多项式g(x)=x+x+x+1，求其校验多项式h(x) 解：
方法一：
733242
因为x-1 =（x+1）（x+x+1）(x+x+1)，而g(x)=x+x+x+1，
732
且g(x) h(x) =0 mod x-1 ，所以得h(x) = x+x+1.
方法二：
T
由于有生成矩阵G和校验矩阵H，使G H= 0 所以可以通过上式得到
S(x)?xS(x)modg(x)?1?0 H???0??0 9.9
1100011010113
01012
00100?0?? 0??1?所以可以得到h(x)=x+x+1.
在GF(2)上可分解为以下既约多项式的乘积：
当构成（15，9）码时，有多少种不同的选择？分别写出对应的生成多项式。 解：根据题意：
。
该多项式构成（15，9）码共有3种不同的选择，生成多项式分别为：
9.10设(15,7)循环码是由g(x)=y(x)=
是码多项式吗？求y(x)的伴随式。
生成的。试回答：
答：y(x) = x7+x5+x3+x+1不是码多项式。
s(x) = y(x) [mod g(x)]= x7+x5+x3+x+1。
4
9.11 设计一个由g(x)= x+x+1 生成的（15,11）循环汉明码的编码器。 解答：循环汉明码编码器如下所示：
9.12 证明：x+x+x+x+x+x+1为（15，5）循环码的生成多项式，并求： （1）该码的生成矩阵。
42
（2）当信息多项式为m(x)= x+x+x+1时的系统码多项式。 （3）画出以g(x)除法电路为核心的n-k级编码器。
1085415
证明： (x+x+x+x+x2+x+1)| x-1 且最高次10=15-5，故为该码的生成矩阵。
10
8
5
4
2
?1?0?（1）生成矩阵G??0??0??000110111000000?10011011100000??01001101110000?
?00100110111000?00010011011100??10
5
3
（2）校验多项式r(x)=x*m(x) mod g(x)=x+x+1 101412111053
系统码多项式为：x*m(x)+ r(x)= x+x+x+x+x+x+1
（3）编码器：
9.13 证明：由g(x)=x+x+x+x+x+1可生成一个（21,11）循环码。画出此码的伴随式计
175
算电路。若接受码字多项式为y=x+x+1,其伴随式是什么？ 解：
2110764211872107642
因为x+1 = (x+x+x+x+x+1)*(x+x+x+x+1)，因为g(x)=x+x+x+x+x+1，所以
11872
校验多项式为h(x)= x+x+x+x+1.故可以生成一个（21,11）的循环码。
107642
由于S(x)=y(x) mod g(x)，所以得到s(x)=x+x+x+x+1.
（i）ii8643
则伴随式的通式为s(x)=xs(x)=x(x+x+x+x+1) 9.14 已知一个
循环码的生成多项式
，
是
的一个因子。求证：
8
6
4
3
（1）设n为奇数，则全1的n重矢量不是一个码字；
（2）设n为偶数，则全1的n重矢量是一个码字。
证明：（1）用多项式表示全1的n重矢量：
若则由于
为一个码字多项式
即
是
的一个解 时，时，
当n为奇数时，当n为奇数时，
即证得n为奇数时，则全1的n重矢量不是一个码字； n为偶数时，则全1的n重矢量是一个码字。