2001 Copyright SCUT DT&P Labs 1
数字通信原理
（ 9-2）
2001 Copyright SCUT DT&P Labs 2
第十一章 差错控制编码
2001 Copyright SCUT DT&P Labs 3
11.3 循环码
1.循环码的基本概念
（ 1） 定义 对线性分组码 C,如对任意 Ci? C,Ci 循环左移或循环右移任意位后得到的码组 Ci’ 仍然有 Ci’? C,则称 C为循环码 。
（ 2） 码多项式为用代数理论研究循环码，可将码组用多项式表示，该多项式称为码多项式。
一般地，长为 n的码组 Cn-1Cn-2…C1C0,对应码多项式 T(x)
式中,xi系数对应码字中 Ci的取值。
012211,..)( CxCxCxCxT nnnn
2001 Copyright SCUT DT&P Labs 4
11.3 循环码
（ 2） 码多项式（续前）
例,（ 7,3）码字,1001110 对应 x6＋ x3＋ x2＋ x
对二进制码组,T(x)的系数只在二元域上取值，二元域上加乘运算规则如下：
加运算,
乘运算,
减法和除法可由加法和乘法定义。
011101110000
111101010000
2001 Copyright SCUT DT&P Labs 5
11.3 循环码
（ 3） 同余类的概念在整数除法中，取定除数 n,可将所有整数按除以 n所得余数进行分类，余数相同的数称为关于 n的 同余类 。
一般地，若
（ Q为整数,p < n）（ 模 n）
则记为：
所有余数为 p的整数属于关于 n的一个同余类。
n
pQ
n
m
nn pm?
2001 Copyright SCUT DT&P Labs 6
11.3 循环码
（ 3） 同余类的概念（续前）
类似地，可以定义关于多项式 N(x)的同余类，若式中 Q(x)为整式，余式 R(x)的幂 < N(x)的幂 。
上式可写成：
记为：
例：在系数为二元域的多项式中，有因为：
从而有上述结论。
)(
)()(
)(
)(
xN
xRxQ
xN
xF
)()()()( xRxNxQxF
)(m o d)()( xNxRxF?
1mod1 nn xx
1
11
1
11
1
nn
n
n
n
xx
x
x
x
2001 Copyright SCUT DT&P Labs 7
（ 3） 同余类的概念（续前） 11.3 循环码定理 1 若 T(x)是长度为 n的循环码中的一个码多项式，则 xiT(x)按模
xn＋ 1运算的余式必为循环码中的另一码多项式 。
证明：设 i＝ 1,有余式为 。对应码组 Cn-1Cn-2…C1C0
左循环一位之后的得到的码组：
Cn-2…C1C0Cn-1。
xCxCxCxCxxT nnnn 021121,..)(
1
...
1
...1
1
...
1
)(
10
2
1
1
2
1
10
2
1
1
21
0
2
1
1
21
n
n
n
n
n
n
n
n
n
n
n
n
n
n
n
n
n
x
CxCxCxC
C
x
CxCxCxCxC
x
xCxCxCxC
x
xxT
102112,., nnn CxCxCxC
2001 Copyright SCUT DT&P Labs 8
（ 3） 同余类的概念（续前） 11.3 循环码
（接 定理 1证明），若 i＝ 2
显然，余式为 对应码组 Cn-1Cn-2…C1C0左循环两位之后的得到的码组。
一般地，对任意 i有：
余式对应 Cn-1Cn-2…C1C0左循环 i位之后的得到的码组。 证毕
1
.,,
1
.,,
1
.,,1
1
)(
1
)(
21
2
0
3
1
1
3
21
1
2
0
3
12
1
10
2
1
1
21
2
n
nn
n
n
nn
n
n
n
n
n
n
n
n
n
n
n
nn
x
CxCxCxCxC
CxC
x
xCxCxCxC
xC
x
CxCxCxCxCx
x
xxTx
x
xTx
1
......)(
1
)( 2211011
n
in
i
n
i
n
in
in
n
i
x
CxCxCxCxCxQ
x
xTx
2001 Copyright SCUT DT&P Labs 9
11.3 循环码
（ 3） 循环码的生成多项式 g(x)及生成矩阵一般地，线性分组可表示为矩阵 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)。
QICCCGCCCC kknnnknnn |.....,2121
2001 Copyright SCUT DT&P Labs 10
（ 3） 循环码的生成多项式 g(x)及生成矩阵 11.3 循环码循环码生成矩阵 G(x)
其中,g(x)称为循环码 码生成多项式 。
)(
)(
.,,,,,
)(
)(
][
2
1
xg
xxg
xgx
xgx
xG
k
k
2001 Copyright SCUT DT&P Labs 11
（ 3） 循环码的生成多项式 g(x)及生成矩阵 11.3 循环码定理 2 在循环码中,n－ k次的码多项式 g(x)有一个且只有一个 。
证明,
（ 1）在含个信息位的循环码中，除全 0码外，其它码组最多只有
k-1个连 0。否则，经循环移位后前面 k个信息码元为 0，而监督码元不全为 0的码组，这在线性分组码中是不可能的。
（ 2） n－ k次的码多项式 g(x)的常数项不能为 0，否则该多项式右移一位就会出现 k个连 0的情况。
（ 3） n－ k次的码多项式 g(x)只可能有一个，若有两个，两多项式相加后由线性分组码的封闭性仍为码多项式，但由于 n－ k
次项和常数项相消，会产生 k＋ 1连 0的情况，由（ 1）分析，
这是不可能的。 综上（ 1）、（ 2）和（ 3）,证毕 。
2001 Copyright SCUT DT&P Labs 12
（ 3） 循环码的生成多项式 g(x)及生成矩阵 11.3 循环码定理 3 在循环码中，所有的码多项式 T(x)都能够被 g(x)整除 。
证明,因为任一码多项式都可由其信息码元和生成矩阵 G[x]确定,
g(x)为码多项式 T(x)的一个因式，所以 T(x)可被 g(x)整除。 证毕推论,次数不大于 k－ 1次的任何多项式与 g(x)的乘积都是码多项式 。
)()()(.,,
)(.,,)()(
)(
)(
.,,,,,
)(
)(
.,,][.,,)(
2
2
1
1
2
2
1
1
2
1
2121
xgxIxgCxCxC
xgCxgxCxgxC
xg
xxg
xgx
xgx
CCCxGCCCxT
kn
k
n
k
n
kn
k
n
k
n
k
k
knnnknnn
2001 Copyright SCUT DT&P Labs 13
（ 3） 循环码的生成多项式 g(x)及生成矩阵 11.3 循环码定理 4 循环码（ n,k） 的生成多项式 g(x)是 xn＋ 1的一个因式 。
证明,因为 g(x)幂为 n－ k,因而可得其中 R(x)的幂小于 n。 由定理 1,R(x)是码多项式，又由定理 3，有
R(x)=I(x)g(x),即有移项整理得：
即 g(x)是 xn＋ 1的一个因式。 证毕
1
)(1
1
)(
nn
k
x
xR
x
xgx
)()(1)(1)( xgxIxxRxxgx nnk
)()()()()()()(1 xgxhxgxIxxgxIxgxx kkn
2001 Copyright SCUT DT&P Labs 14
（ 3） 循环码的生成多项式 g(x)及生成矩阵 11.3 循环码称 为循环码的 一致效验多项式 。
对任一码多项式,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)
即若 T(x)是许用码组对应的多项式，其 乘积 h(x)T(x)一定可被
xn＋ 1整除 。
生成多项式 g(x)的 三个性质 （充要条件）：
（ 1） g(x)是 n－ k次多项式；
（ 2） g(x)的常数项不等于 0；
（ 3）是 xn＋ 1的一个因式。
)(
1)(
xg
xxh n
2001 Copyright SCUT DT&P Labs 15
11.3 循环码
（ 4） 循环码的编码和译码采用前面定义的循环码生成矩阵：
对应的系数矩阵 G一般 不 符合
G＝ [Ik,Q]
形式。编码输出结果相当于 I(x)g(x),所得码组为非系统码结构。
信息码和监督码不容易区分。
例,
若生成多项式 g(x)＝ x4+x3+x2+1 对应生成矩阵 G[x]对应的系数矩阵为：
)(
.,,,,,
)(
][
1
xg
xgx
xG
k
1011100
0101110
0010111
)(
.,,,,,
)(
][
1
xg
xgx
xG
k
2001 Copyright SCUT DT&P Labs 16
（ 4） 循环码的编码和译码 11.3 循环码系统结构循环码的编码方法
（ a） 以 xn-k乘信息多项式 I(x),I(x)? xn-k I(x)；（ 幂 < n）
（ 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)
因为 Q(x)的幂次数小于 k,所以 Q(x)g(x)一定是循环码的码多项式，显然（ *）定义的 C(x)为一种系统码结构的循环码。
2001 Copyright SCUT DT&P Labs 17
（ 4） 循环码的编码和译码 11.3 循环码循环码编码器的电路实现
（ a） 多项式除法 多项式除法可用带反馈的移位寄存器实现。
例：除数为 g(x)＝ x6＋ x5＋ x4＋ x3＋ 1 除法电路如下图，反馈的接入由 g(x)确定除法运算的实现先将移位寄存器清,0” ；
进行 n次移位，将被除数全部送入除法器后，在寄存器内即可得到相应的余式。
x 6x 5x 4
＋ ＋ ＋D D D D D ＋ D
x 31
2001 Copyright SCUT DT&P Labs 18
（ 4） 循环码的编码和译码 11.3 循环码
（接上例）计算 C(x)/g(x),其中 C(x)=x13+x11+x10+x7+x4+x3+x+1
除法运算在移位进行了 r-1位后才开始，运算完成后，要将余式移出，还要做 r-1次移位。速度较慢。
移位序号 输入 移位寄存器内容 输出商 反馈信号
0
1
2
3
4
5
6
7
8
9
10
11
12
13
14
0
1
0
1
1
0
0
1
0
0
1
1
0
1
1
H 000000 L
100000
010000
101000
110100
011011
001101
000001
100111
110100
111010
111101
111001
011011
001010
余数
0
0
0
0
0
0
1
1
1
0
0
1
1
1
0
000000
000000
000000
000000
000000
000000
000000
100111
100111
100111
000000
000000
100111
100111
100111
2001 Copyright SCUT DT&P Labs 19
（ 4） 循环码的编码和译码 11.3 循环码实际应用的循环码编码电路特点,采用,预先乘 xn-k方案,（信号直接到达最后一级），边移位边做除法运算，当 k个信息码输入后，同时完成了除法运算。
（ a） 当信息位输入时，开关 K1,K2合 下,k个信息位经 K2逐位输出，同时直接送到最高位做除法运算：
D D ＋ D ＋ D ＋
x 4x
31 x 2
K
1
K
2
输入 输出
)(.,,,,,)()()(
)( 2211
xg
xC
xg
xC
xg
xC
xg
xIx knknnnnnkn
2001 Copyright SCUT DT&P Labs 20
（ 4） 循环码的编码和译码 11.3 循环码实际应用的循环码编码电路
（ b） 当信息位全部输入后，相应除法运算完成，开关 K1,K2合 上,
将余数顺序输出。
例：设 I(x)=x2＋ x＋ 1? 111,xn-k＝ x7－ 3＝ x4,xn-kI(x)＝ 1110000
商为,100，余数为,0100
上述运算也可看作下列分别运算的结果：
商为,110＋ 11＋ 1? 100
余数,1110＋ 0111＋ 1101? 0100
11101
0100100
11101
1110000
11101
1110110
11101
1000000
1 1 1 0 1
0 1 1 111
1 1 1 0 1
0 1 0 0 0 0 0
1 1 1 0 1
11011
1 1 0 1
0 0 1 0 0 0 0
2001 Copyright SCUT DT&P Labs 21
（ 4） 循环码的编码和译码 11.3 循环码循环码译码电路
（ a） 循环码的译码过程由收到的码多项式 R(x)计算校正子多项式 S(x),；
由 S(x)确定误码的错误图样 E(x)；
将 E(x)与 R(x)相加，纠正错误 （ 若在纠错范围内）。
一般地，对矩阵形式的线性分组码，校正子 S为：
对于循环码：
有误码，
无误码
0
,0
)( xS
TTTTT EHEHCHHECRHS )(
)(m o d)(
)(m o d)()(
xgxE
xgxRxS
余式
2001 Copyright SCUT DT&P Labs 22
（ 4） 循环码的编码和译码 11.3 循环码除法电路的性质某码组循环移位 i次的校正子等于原码组校正子在除法电路中循环移位 i次所得的结果。
设 Si(x)为码多项式 R(x)循环移位 i次后计算得到的校正子：
因为：
故有：
即：
利用上述性质，可得：某个可纠正的错误图样 E(x)的 i次循环移位
xiE(x)必定也是可以纠正的错误图样，从而可把 E(x),xE(x),…
xiE(x)规为一类，用一个错误图样作代表，由此，所需识别的
)(m o d)()( xgxRxxS ii?
)(m o d)()( xgxRxS?
)(m o d)()( xgxRxxSx ii?
)(m o d)()( xgxSxxS ii?
2001 Copyright SCUT DT&P Labs 23
（ 4） 循环码的编码和译码 11.3 循环码除法电路的性质所需识别的错误图样数由
（ 5） 纠错译码原理
a.计算 S(x)＝ R(x)/g(x)
b.确定错误图样 S(x)?E(x)
c.根据 E(x)纠错。
ti inti in CC 1 111
校正子计算电路,S ( x )
错误图样识别：E ( x )
1 2 3 n-k......
缓冲移位寄存器 ＋
R(x)
C(x)
2001 Copyright SCUT DT&P Labs 24
11.3 循环码
（ 5） 纠正单个错误的译码电路根据上节讨论，当用于纠正单个错误时，只需要记住一个错误图样。 E(x)识别电路可用简单的逻辑电路来实现 。
例：已知 g(x)＝ x4＋ x3＋ x2＋ 1
错误图样,E,1000000? S(x)＝ x3＋ x2＋ x S,1110
错误图样,E,0100000? S(x)＝ x2＋ x ＋ 1 S,0111
循环移一位后,S,0111? S,1110
错误图样,E,0010000? S(x)＝ x2＋ x ＋ 1 S,0111
循环移一位后,S,1011? S,1110
再循环移一位后,S,0111? S,1110
其它一位出错的情形同理可纠正。
2001 Copyright SCUT DT&P Labs 25
D D ＋ D ＋ D
x
4
x
31
x
2
输入输出
＋
与门
D D D D D DD＋
11.3 循环码
（ 5） 纠正单个错误的译码电路（续前）
数字通信原理
（ 9-2）
2001 Copyright SCUT DT&P Labs 2
第十一章 差错控制编码
2001 Copyright SCUT DT&P Labs 3
11.3 循环码
1.循环码的基本概念
（ 1） 定义 对线性分组码 C,如对任意 Ci? C,Ci 循环左移或循环右移任意位后得到的码组 Ci’ 仍然有 Ci’? C,则称 C为循环码 。
（ 2） 码多项式为用代数理论研究循环码，可将码组用多项式表示，该多项式称为码多项式。
一般地，长为 n的码组 Cn-1Cn-2…C1C0,对应码多项式 T(x)
式中,xi系数对应码字中 Ci的取值。
012211,..)( CxCxCxCxT nnnn
2001 Copyright SCUT DT&P Labs 4
11.3 循环码
（ 2） 码多项式（续前）
例,（ 7,3）码字,1001110 对应 x6＋ x3＋ x2＋ x
对二进制码组,T(x)的系数只在二元域上取值，二元域上加乘运算规则如下：
加运算,
乘运算,
减法和除法可由加法和乘法定义。
011101110000
111101010000
2001 Copyright SCUT DT&P Labs 5
11.3 循环码
（ 3） 同余类的概念在整数除法中，取定除数 n,可将所有整数按除以 n所得余数进行分类，余数相同的数称为关于 n的 同余类 。
一般地，若
（ Q为整数,p < n）（ 模 n）
则记为：
所有余数为 p的整数属于关于 n的一个同余类。
n
pQ
n
m
nn pm?
2001 Copyright SCUT DT&P Labs 6
11.3 循环码
（ 3） 同余类的概念（续前）
类似地，可以定义关于多项式 N(x)的同余类，若式中 Q(x)为整式，余式 R(x)的幂 < N(x)的幂 。
上式可写成：
记为：
例：在系数为二元域的多项式中，有因为：
从而有上述结论。
)(
)()(
)(
)(
xN
xRxQ
xN
xF
)()()()( xRxNxQxF
)(m o d)()( xNxRxF?
1mod1 nn xx
1
11
1
11
1
nn
n
n
n
xx
x
x
x
2001 Copyright SCUT DT&P Labs 7
（ 3） 同余类的概念（续前） 11.3 循环码定理 1 若 T(x)是长度为 n的循环码中的一个码多项式，则 xiT(x)按模
xn＋ 1运算的余式必为循环码中的另一码多项式 。
证明：设 i＝ 1,有余式为 。对应码组 Cn-1Cn-2…C1C0
左循环一位之后的得到的码组：
Cn-2…C1C0Cn-1。
xCxCxCxCxxT nnnn 021121,..)(
1
...
1
...1
1
...
1
)(
10
2
1
1
2
1
10
2
1
1
21
0
2
1
1
21
n
n
n
n
n
n
n
n
n
n
n
n
n
n
n
n
n
x
CxCxCxC
C
x
CxCxCxCxC
x
xCxCxCxC
x
xxT
102112,., nnn CxCxCxC
2001 Copyright SCUT DT&P Labs 8
（ 3） 同余类的概念（续前） 11.3 循环码
（接 定理 1证明），若 i＝ 2
显然，余式为 对应码组 Cn-1Cn-2…C1C0左循环两位之后的得到的码组。
一般地，对任意 i有：
余式对应 Cn-1Cn-2…C1C0左循环 i位之后的得到的码组。 证毕
1
.,,
1
.,,
1
.,,1
1
)(
1
)(
21
2
0
3
1
1
3
21
1
2
0
3
12
1
10
2
1
1
21
2
n
nn
n
n
nn
n
n
n
n
n
n
n
n
n
n
n
nn
x
CxCxCxCxC
CxC
x
xCxCxCxC
xC
x
CxCxCxCxCx
x
xxTx
x
xTx
1
......)(
1
)( 2211011
n
in
i
n
i
n
in
in
n
i
x
CxCxCxCxCxQ
x
xTx
2001 Copyright SCUT DT&P Labs 9
11.3 循环码
（ 3） 循环码的生成多项式 g(x)及生成矩阵一般地，线性分组可表示为矩阵 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)。
QICCCGCCCC kknnnknnn |.....,2121
2001 Copyright SCUT DT&P Labs 10
（ 3） 循环码的生成多项式 g(x)及生成矩阵 11.3 循环码循环码生成矩阵 G(x)
其中,g(x)称为循环码 码生成多项式 。
)(
)(
.,,,,,
)(
)(
][
2
1
xg
xxg
xgx
xgx
xG
k
k
2001 Copyright SCUT DT&P Labs 11
（ 3） 循环码的生成多项式 g(x)及生成矩阵 11.3 循环码定理 2 在循环码中,n－ k次的码多项式 g(x)有一个且只有一个 。
证明,
（ 1）在含个信息位的循环码中，除全 0码外，其它码组最多只有
k-1个连 0。否则，经循环移位后前面 k个信息码元为 0，而监督码元不全为 0的码组，这在线性分组码中是不可能的。
（ 2） n－ k次的码多项式 g(x)的常数项不能为 0，否则该多项式右移一位就会出现 k个连 0的情况。
（ 3） n－ k次的码多项式 g(x)只可能有一个，若有两个，两多项式相加后由线性分组码的封闭性仍为码多项式，但由于 n－ k
次项和常数项相消，会产生 k＋ 1连 0的情况，由（ 1）分析，
这是不可能的。 综上（ 1）、（ 2）和（ 3）,证毕 。
2001 Copyright SCUT DT&P Labs 12
（ 3） 循环码的生成多项式 g(x)及生成矩阵 11.3 循环码定理 3 在循环码中，所有的码多项式 T(x)都能够被 g(x)整除 。
证明,因为任一码多项式都可由其信息码元和生成矩阵 G[x]确定,
g(x)为码多项式 T(x)的一个因式，所以 T(x)可被 g(x)整除。 证毕推论,次数不大于 k－ 1次的任何多项式与 g(x)的乘积都是码多项式 。
)()()(.,,
)(.,,)()(
)(
)(
.,,,,,
)(
)(
.,,][.,,)(
2
2
1
1
2
2
1
1
2
1
2121
xgxIxgCxCxC
xgCxgxCxgxC
xg
xxg
xgx
xgx
CCCxGCCCxT
kn
k
n
k
n
kn
k
n
k
n
k
k
knnnknnn
2001 Copyright SCUT DT&P Labs 13
（ 3） 循环码的生成多项式 g(x)及生成矩阵 11.3 循环码定理 4 循环码（ n,k） 的生成多项式 g(x)是 xn＋ 1的一个因式 。
证明,因为 g(x)幂为 n－ k,因而可得其中 R(x)的幂小于 n。 由定理 1,R(x)是码多项式，又由定理 3，有
R(x)=I(x)g(x),即有移项整理得：
即 g(x)是 xn＋ 1的一个因式。 证毕
1
)(1
1
)(
nn
k
x
xR
x
xgx
)()(1)(1)( xgxIxxRxxgx nnk
)()()()()()()(1 xgxhxgxIxxgxIxgxx kkn
2001 Copyright SCUT DT&P Labs 14
（ 3） 循环码的生成多项式 g(x)及生成矩阵 11.3 循环码称 为循环码的 一致效验多项式 。
对任一码多项式,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)
即若 T(x)是许用码组对应的多项式，其 乘积 h(x)T(x)一定可被
xn＋ 1整除 。
生成多项式 g(x)的 三个性质 （充要条件）：
（ 1） g(x)是 n－ k次多项式；
（ 2） g(x)的常数项不等于 0；
（ 3）是 xn＋ 1的一个因式。
)(
1)(
xg
xxh n
2001 Copyright SCUT DT&P Labs 15
11.3 循环码
（ 4） 循环码的编码和译码采用前面定义的循环码生成矩阵：
对应的系数矩阵 G一般 不 符合
G＝ [Ik,Q]
形式。编码输出结果相当于 I(x)g(x),所得码组为非系统码结构。
信息码和监督码不容易区分。
例,
若生成多项式 g(x)＝ x4+x3+x2+1 对应生成矩阵 G[x]对应的系数矩阵为：
)(
.,,,,,
)(
][
1
xg
xgx
xG
k
1011100
0101110
0010111
)(
.,,,,,
)(
][
1
xg
xgx
xG
k
2001 Copyright SCUT DT&P Labs 16
（ 4） 循环码的编码和译码 11.3 循环码系统结构循环码的编码方法
（ a） 以 xn-k乘信息多项式 I(x),I(x)? xn-k I(x)；（ 幂 < n）
（ 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)
因为 Q(x)的幂次数小于 k,所以 Q(x)g(x)一定是循环码的码多项式，显然（ *）定义的 C(x)为一种系统码结构的循环码。
2001 Copyright SCUT DT&P Labs 17
（ 4） 循环码的编码和译码 11.3 循环码循环码编码器的电路实现
（ a） 多项式除法 多项式除法可用带反馈的移位寄存器实现。
例：除数为 g(x)＝ x6＋ x5＋ x4＋ x3＋ 1 除法电路如下图，反馈的接入由 g(x)确定除法运算的实现先将移位寄存器清,0” ；
进行 n次移位，将被除数全部送入除法器后，在寄存器内即可得到相应的余式。
x 6x 5x 4
＋ ＋ ＋D D D D D ＋ D
x 31
2001 Copyright SCUT DT&P Labs 18
（ 4） 循环码的编码和译码 11.3 循环码
（接上例）计算 C(x)/g(x),其中 C(x)=x13+x11+x10+x7+x4+x3+x+1
除法运算在移位进行了 r-1位后才开始，运算完成后，要将余式移出，还要做 r-1次移位。速度较慢。
移位序号 输入 移位寄存器内容 输出商 反馈信号
0
1
2
3
4
5
6
7
8
9
10
11
12
13
14
0
1
0
1
1
0
0
1
0
0
1
1
0
1
1
H 000000 L
100000
010000
101000
110100
011011
001101
000001
100111
110100
111010
111101
111001
011011
001010
余数
0
0
0
0
0
0
1
1
1
0
0
1
1
1
0
000000
000000
000000
000000
000000
000000
000000
100111
100111
100111
000000
000000
100111
100111
100111
2001 Copyright SCUT DT&P Labs 19
（ 4） 循环码的编码和译码 11.3 循环码实际应用的循环码编码电路特点,采用,预先乘 xn-k方案,（信号直接到达最后一级），边移位边做除法运算，当 k个信息码输入后，同时完成了除法运算。
（ a） 当信息位输入时，开关 K1,K2合 下,k个信息位经 K2逐位输出，同时直接送到最高位做除法运算：
D D ＋ D ＋ D ＋
x 4x
31 x 2
K
1
K
2
输入 输出
)(.,,,,,)()()(
)( 2211
xg
xC
xg
xC
xg
xC
xg
xIx knknnnnnkn
2001 Copyright SCUT DT&P Labs 20
（ 4） 循环码的编码和译码 11.3 循环码实际应用的循环码编码电路
（ b） 当信息位全部输入后，相应除法运算完成，开关 K1,K2合 上,
将余数顺序输出。
例：设 I(x)=x2＋ x＋ 1? 111,xn-k＝ x7－ 3＝ x4,xn-kI(x)＝ 1110000
商为,100，余数为,0100
上述运算也可看作下列分别运算的结果：
商为,110＋ 11＋ 1? 100
余数,1110＋ 0111＋ 1101? 0100
11101
0100100
11101
1110000
11101
1110110
11101
1000000
1 1 1 0 1
0 1 1 111
1 1 1 0 1
0 1 0 0 0 0 0
1 1 1 0 1
11011
1 1 0 1
0 0 1 0 0 0 0
2001 Copyright SCUT DT&P Labs 21
（ 4） 循环码的编码和译码 11.3 循环码循环码译码电路
（ a） 循环码的译码过程由收到的码多项式 R(x)计算校正子多项式 S(x),；
由 S(x)确定误码的错误图样 E(x)；
将 E(x)与 R(x)相加，纠正错误 （ 若在纠错范围内）。
一般地，对矩阵形式的线性分组码，校正子 S为：
对于循环码：
有误码，
无误码
0
,0
)( xS
TTTTT EHEHCHHECRHS )(
)(m o d)(
)(m o d)()(
xgxE
xgxRxS
余式
2001 Copyright SCUT DT&P Labs 22
（ 4） 循环码的编码和译码 11.3 循环码除法电路的性质某码组循环移位 i次的校正子等于原码组校正子在除法电路中循环移位 i次所得的结果。
设 Si(x)为码多项式 R(x)循环移位 i次后计算得到的校正子：
因为：
故有：
即：
利用上述性质，可得：某个可纠正的错误图样 E(x)的 i次循环移位
xiE(x)必定也是可以纠正的错误图样，从而可把 E(x),xE(x),…
xiE(x)规为一类，用一个错误图样作代表，由此，所需识别的
)(m o d)()( xgxRxxS ii?
)(m o d)()( xgxRxS?
)(m o d)()( xgxRxxSx ii?
)(m o d)()( xgxSxxS ii?
2001 Copyright SCUT DT&P Labs 23
（ 4） 循环码的编码和译码 11.3 循环码除法电路的性质所需识别的错误图样数由
（ 5） 纠错译码原理
a.计算 S(x)＝ R(x)/g(x)
b.确定错误图样 S(x)?E(x)
c.根据 E(x)纠错。
ti inti in CC 1 111
校正子计算电路,S ( x )
错误图样识别：E ( x )
1 2 3 n-k......
缓冲移位寄存器 ＋
R(x)
C(x)
2001 Copyright SCUT DT&P Labs 24
11.3 循环码
（ 5） 纠正单个错误的译码电路根据上节讨论，当用于纠正单个错误时，只需要记住一个错误图样。 E(x)识别电路可用简单的逻辑电路来实现 。
例：已知 g(x)＝ x4＋ x3＋ x2＋ 1
错误图样,E,1000000? S(x)＝ x3＋ x2＋ x S,1110
错误图样,E,0100000? S(x)＝ x2＋ x ＋ 1 S,0111
循环移一位后,S,0111? S,1110
错误图样,E,0010000? S(x)＝ x2＋ x ＋ 1 S,0111
循环移一位后,S,1011? S,1110
再循环移一位后,S,0111? S,1110
其它一位出错的情形同理可纠正。
2001 Copyright SCUT DT&P Labs 25
D D ＋ D ＋ D
x
4
x
31
x
2
输入输出
＋
与门
D D D D D DD＋
11.3 循环码
（ 5） 纠正单个错误的译码电路（续前）
