1
7
1
001101
1
8
0
000001
1
9
0

100111
0
10
1
110100
0
11
1
111010
1
12
0
111101
1
13
1
111001
1
14
1
011011
0
001010
余数
000000 000000 000000 000000 000000 000000 000000 100111 100111 100111 000000 000000 100111 100111 100111
即若T(x)是许用码组对应的多项式，其乘积h(x)T(x)一定可被 xn＋1整除。
生成多项式g(x)的三个性质（充要条件）： （1）g(x)是n－k次多项式； （2）g(x)的常数项不等于0； （3）是xn＋1的一个因式。
2001 Copyright
SCUT DT&P Labs
14
11.3 循环码
00 0 011 10 1 11 0
乘运算：
00 0
01 0
10 1
11 1
减法和除法可由加法和乘法定义。
2001 Copyright
SCUT DT&P Labs
4
11.3 循环码
（3）同余类的概念
在整数除法中，取定除数n，可将所有整数按除以n所得余数进行
分类，余数相同的数称为关于n的同余类。
推论：次数不大于k－1次的任何多项式与g(x)的乘积都是码多项式。
2001 Copyright
SCUT DT&P Labs
12
（3）循环码的生成多项式g(x)及生成矩阵
11.3 循环码
定理 4 循环码（n，k）的生成多项式g(x)是xn＋1的一个因式。
证明：因为g(x)幂为n－k，因而可得
xk g(x) xn 1
（b）用g(x)除xn-k I(x)得余式R(x) ( 幂 < n-k ) 即
xn-k I(x)＝Q(x)g(x)+R(x)
取码多项式
C(x)= xn-k I(x)+R(x)
（*）
上述编码方式的合理性：
C(x)= xn-k I(x)+R(x)＝[Q(x)g(x)+R(x)]+R(x)=Q(x)g(x)
1
x2
x3
x4
D
D＋D＋D ＋
输入
输出 K2
（a）当信息位输入时，开关K1、K2合下，k个信息位经K2逐位输
出，同时直接送到最高位做除法运算：
xnk I (x) Cn1xn1 Cn2 xn2 ...... Cnk xnk
g(x) g(x) g(x)
g(x)
2001 Copyright
SCUT DT&P Labs
xT (x) xn 1
Cn 1 x n
Cn2 xn1 ... C1x2 xn 1
C0x
Cn1
xn
1
Cn2 xn1 ... C1x2 xn 1
C0 x Cn1
Cn1
Cn2
x n 1
... C1x2 xn 1
C0
x
Cn1
余式为
Cn2 xn1 ... C1。x2 对 C应0 x码组CnC1n-1Cn-2…C1C0左
矩阵为：
xk1g(x) 1 1 1 0 1 0 0
G[ x]
......
0
1
1
1
0
1
0
g(x) 0 0 1 1 1 0 1
2001 Copyright
SCUT DT&P Labs
15
（4）循环码的编码和译码
11.3 循环码
系统结构循环码的编码方法
（a）以xn-k乘信息多项式I(x)，I(x) xn-k I(x)；（幂 < n）
T (x) Cn1xn1 Cn2 xn2 ... C1x C0 式中，xi系数对应码字中Ci的取值。
2001 Copyright
SCUT DT&P Labs
3
11.3 循环码
（2）码多项式（续前） 例： （7,3）码字：1001110 对应 x6＋x3＋x2＋x 对二进制码组，T(x)的系数只在二元域上取值，二元域上加乘 运算规则如下： 加运算：
因为Q(x)的幂次数小于k，所以Q(x)g(x)一定是循环码的码多项
式，显然（*）定义的C(x)为一种系统码结构的循环码。
2001 Copyright
SCUT DT&P Labs
16
（4）循环码的编码和译码
11.3 循环码
循环码编码器的电路实现
（a）多项式除法 多项式除法可用带反馈的移位寄存器实现。
除法运算在移位进行了r-1位后才开始，运算完成后，要将余式
移出，还要做r-1次移位。速度较慢。
2001 Copyright
SCUT DT&P Labs
18
（4）循环码的编码和译码
11.3 循环码
实际应用的循环码编码电路
特点：采用“预先乘xn-k方案”（信号直接到达最后一级），边移位
边做除法运算，当k个信息码输入后，同时完成了除法运算。 K1
2001 Copyright
SCUT DT&P Labs
9
（3）循环码的生成多项式g(x)及生成矩阵 循环码生成矩阵G(x)
xk1g(x)
x
k
2
g
(
x)
G[x] ......
xg(x)
g(x)
其中，g(x)称为循环码码生成多项式。
11.3 循环码
2001 Copyright
SCUT DT&P Labs
矩阵G中每一行均为一许用码组，如第i行对应第i个信息位为1， 其余为0时生成的码组。 由于G中包含一个Ik分块，所以G为k个独立的码组组成的矩阵。 即：任一线性分组码码组均可由k个线性无关的码组组合而成。
利用上述线性分组码的性质，设g(x)为幂次数为n－k，且 常数项不为0的多项式，则由
g(x)，xg(x),……，xk-2g(x)，xk-1g(x) 可构成循环码生成矩阵G(x)。
（2） n－k次的码多项式g(x)的常数项不能为0，否则该多项式
右移一位就会出现k个连0的情况。
（3） n－k次的码多项式g(x)只可能有一个，若有两个，两多项
式相加后由线性分组码的封闭性仍为码多项式，但由于n－k
次项和常数项相消，会产生k＋1连0的情况，由（1）分析，
这是不可能的。 综上（1）、（2）和（3），证毕。
循环一位之后的得到的码组：
Cn-2…C1C0Cn-1。
2001 Copyright
SCUT DT&P Labs
7
（3）同余类的概念（续前）
11.3 循环码
（接定理1证明），若i＝2
x2T (x)
xn 1
xxT (x)
xn 1
x
Cn1
xn
1
Cn2 xn1 xn
... C1x2 1
C0x
即g(x)是xn＋1的一个因式。证毕
2001 Copyright
SCUT DT&P Labs
13
（3）循环码的生成多项式g(x)及生成矩阵
11.3 循环码
称
h(x) 为x循n 环1 码的一致效验多项式。
g(x)
对任一码多项式，T(x)＝I(x)g(x)，有 h(x)T(x)=h(x)[I(x)g(x)]=[h(x)g(x)]I(x)=(xn+1)I(x)
N ( x)
N ( x)
式中Q(x)为整式，余式R(x)的幂 < N(x)的幂。 上式可写成：
F(x) Q(x)N(x) R(x)
记为： F(x) R(x) modN (x) 例：在系数为二元域的多项式中，有
1 xn
因为：
xn xn 11 1 1 xn 1 xn 从1而有上x述n 结1论。
modxn 1
数字通信原理 （9-2）
2001 Copyright
SCUT DT&P Labs
1
第十一章 差错控制编码
2001 Copyright
SCUT DT&P Labs
2
11.3 循环码
1.循环码的基本概念 （1）定义 对线性分组码C，如对任意 Ci C， Ci 循环左移或循
环右移任意位后得到的码组Ci’ 仍然有Ci’ C ，则称C为循 环码。 （2）码多项式 为用代数理论研究循环码，可将码组用多项式表示，该多项 式称为码多项式。 一般地，长为n的码组Cn-1Cn-2…C1C0，对应码多项式T(x)
Cn1
Cn1x
Cn2 xn
... C1x3 xn 1
C0 x2
Cn1x
Cn1x
Cn2
Cn3 xn1
...
C1x3 C0 x2 xn 1
Cn1x
Cn2
显然，余式为对应码组Cn-1Cn-2…C1C0左循环两位之后的得到的码 组。
一般地xxi，Tn (对x1)任 Q意(ix有) ：Cni1xn1
1
R(x) xn 1
其中R(x)的幂小于n。由定理1，R(x)是码多项式，又由定理3，有
R(x)=I(x)g(x)，即有
xk g(x) xn 1 R(x) xn 1 I (x)g(x)
移项整理得：
xn 1 xk g(x) I (x)g(x) xk I (x) g(x) h(x)g(x)
2001 Copyright