1,循环码的多项式描述
2,循环码的生成多项式
3,系统循环码
4,多项式运算电路
5,循环码的编码电路
6,循环码的译码
7,循环汉明码
8,缩短循环码
循环码
(1) 循环码的性质
? 循环码是线性分组码的一个重要子类；
? 由于循环码具有 优良的代数结构,使得可用简
单的反馈移位寄存器实现编码和伴随式计算，
并可使用多种简单而有效的译码方法；
? 循环码是研究最 深入,理论最 成熟,应用最 广
泛 的一类线性分组码。
(2) 循环码的定义
? 循环码,如果 (n,k) 线性分组码的任意码矢
C=(Cn－ 1,Cn－ 2,…,C0)
的 i 次循环移位，所得矢量
C(i)=(Cn－ 1－ i,Cn－ 2－ i,…,C0,Cn－ 1,…,Cn－ i)
仍是一个码矢，则称此线性码为 (n,k) 循环码。
(3) 码多项式
? 码多项式,为了运算的方便，将码矢的各分量作为多
项式的系数，把码矢表示成多项式，称为码多项式。
其一般表示式为
C(x)=Cn－ 1xn－ 1+Cn－ 2xn－ 2+… +C0)
? 码多项式 i 次循环移位的表示方法
记码多项式 C(x)的一次左移循环为 C(1)(x), i 次左移
循环为 C(i)(x)
? 码多项式的模 (xn+1) 运算
? 0和 1两个元素模 2运算下构成域。
+ 0 1
0 0 1
1 1 0
× 0 1
0 0 0
1 0 1
? 码矢 C 循环 i 次所得码矢的码多项式
? C(x) 乘以 x，再除以 (xn+1)，得
上式表明,码矢循环一次的码多项式 C(1)(x) 是原码
多项式 C(x)乘以 x 除以 (xn+1) 的余式。写作
因此,C(x) 的 i 次循环移位 C(i)(x) 是 C(x) 乘以 xi
除以 (xn+1) 的余式，即
? 结论,循环码的码矢的 i 次循环移位等效于将码多
项式乘 xi 后再模 (xn+1)。
(4) 举例,(7,3) 循环码
可由任一个码矢，比如 (0011101) 经过循环移位，
得到其它 6个非 0码矢；
也可由相应的码多项式 (x4+x3+x2+1)，乘以
xi(i=1,2,…,6)，再模 (x7+1)运算得到其它 6个非 0码
多项式。移位过程和相应的多项式运算如表 6.3.1所
示。
表 6,3,1 循环码的循环移位
移位次数 码 字 码多项式
0 001 1 101 x
4
+ x
3
+ x
2
+1 ( 模 x
7
+ 1)
1 01 1 1010 x ( x
4
+ x
3
+ x
2
+ 1) ≡ x
5
+ x
4
+ x
3
+ x ( 模 x
7
+ 1)
2 1 1 10100 x
2
( x
4
+ x
3
+ x
2
+ 1) ≡ x
6
+ x
5
+ x
4
+ x
2
( 模 x
7
+ 1)
3 1 101001 x
3
( x
4
+ x
3
+ x
2
+ 1) ≡ x
6
+ x
5
+ x
3
+1 ( 模 x
7
+ 1)
4 101001 1 x
4
( x
4
+ x
3
+ x
2
+ 1) ≡ x
6
+ x
4
+ x +1 ( 模 x
7
+ 1)
5 01001 1 1 x
5
( x
4
+ x
3
+ x
2
+ 1) ≡ x
5
+ x
2
+ x +1 ( 模 x
7
+ 1)
6 1001 1 10 x
6
( x
4
+ x
3
+ x
2
+ 1) ≡ x
6
+ x
3
+ x
2
+ x ( 模 x
7
+ 1)
(1) 循环码的生成矩阵
? 根据循环码的循环特性，可由一个码字的循环移位得
到其它的非 0码字。在 (n,k) 循环码的 2k 个码字中，
取前 (k－ 1) 位皆为 0的码字 g(x)（其次数 r=n－ k），
再经 (k－ 1) 次循环移位，共得到 k 个码字,
g(x),xg(x),…,xk－ 1 g(x)
这 k 个码字显然是相互独
立的，可作为码生成矩阵
的 k 行，于是得到 循环码
的生成矩阵 G(x)
(2) 循环码的生成多项式
? 码的生成矩阵一旦确定，码就确定了；
? 这就说明,(n,k) 循环码可由它的一个 (n－ k) 次码多
项式 g(x) 来确定；
? 所以说 g(x) 生成了 (n,k) 循环码，因此 称 g(x) 为码
的生成多项式 。
(3) 生成多项式 和 码多项式 的关系
? 定理, 在 (n,k) 循环码中，生成多项式 g(x) 是
惟一的 (n－ k) 次码多项式，且次数是最低的 。
? 定理,在 (n,k) 循环码中，每个码多项式 C(x)
都是 g(x) 的倍式；而每个为 g(x) 倍式且次数
小于或等于 (n－ 1) 的多项式，必是一个码多
项式 。
? 定理 6.3.3(定理 6.3.2的逆定理 ),在一个 (n,k) 线
性码中，如果全部码多项式都是最低次的 (n－ k)
次码多项式的倍式，则此线性码为一个 (n,k) 循
环码 。
注,一般说来，这种循环码仍具有把 (n,k) 线性码
码中任一非 0码矢循环移位必为一码矢的循环特性，但从
一个非 0码矢出发，进行循环移位，就未必能得到码的所
有非 0码矢了。所以称这种循环码为 推广循环码 。
? 码字循环关系图
? 单纯循环码的 码字循环图,(7,3)循环码
0 0 1 0 1 1 1 1 0 0 1 0 1 1
1 1 0 0 1 0 1
1 1 1 0 0 1 0
0 1 1 1 0 0 1
1 0 1 1 1 0 0
0 1 0 1 1 1 0
0 0 0 0 0 0 0
图 6, 3, 1 ( 7,3 ) 循 环 码 的 循 环 关 系 图
? 推广循环码的 码字循环图,(6,3)循环码
1 0 0 1 0 0
0 1 0 0 1 0
0 0 1 0 0 1
1 1 1 1 1 1
图 6, 3, 2 ( 6,3 ) 循 环 码 的 循 码 字 环 关 系 图
1 0 1 1 0 1
0 1 1 0 1 1
0 0 0 0 0 0
(4) 如何寻找一个合适的生成多项式
? 由下面式子可知：循环码的多项式等于信息多项式乘
以生成多项式。
这说明,对一个循环码只要生成多项式一旦确定，码
就确定了，编码问题就解决了。
所以, 作一循环码的关键，就在于寻找一个适当的生
成多项式 。
? 定理, (n,k) 循环码的生成多项式 g(x) 是
(xn+1)的因式，即 xn+1=h(x)?g(x)。
? 定理,若 g(x) 是一个 (n－ k) 次 多项式，且为
(xn+1) 的因式，则 g(x) 生成一个 (n,k) 循环
码。
结论, 当求作一个 (n,k)循环码时，只要分解多项
式 (xn+1),从中取出 (n－ k)次因式作生成多项
式即可 。
? 举例：求 (7,3) 循环码的生成多项式。
[解 ]：
分解多项式 xn+1，取其 4次因式作生成多项式
x7+1= (x+1) (x3+x2+1) (x3+x+1)
可将一次和任一个三次因式的乘积作为生成多项式，
因而可取
g1(x)= (x+1) (x3+x2+1) = x4+x2+x+1
或 g2(x)= (x+1) (x3+x+1) = x4+x3+x2+1
(5) 循环码的监督多项式和监督矩阵
? 循环码的监督多项式,设 g(x) 为 (n,k) 循环码的生成多
项式，必为 (xn+1) 的因式，则有 xn+1=h(x)?g(x)，式中
h(x) 为 k 次多项式，称为 (n,k) 循环码的监督多项式。
? (n,k) 循环码也可由其监督多项式完全确定。
? 举例, (7,3) 循环码 x7+1= (x3+x+1)(x4+x2+x+1)
? 4次多项式为生成多项式
g(x)=x4+x2+x+1=g4x4+g3x3+g2x2+g1x+g0
? 3次多项式是监督多项式
h(x)=x3+x+1=h3x3+h2x2+h1x+h0
? 循环码的监督矩阵
? 由等式 x7+1= h(x)?g(x) 两端同次项系数相等得
? 将上面的方程组
写成矩阵形式
? 上式中，列阵的元素是生成多项式 g(x) 的系数，
是一个码字，那么第一个矩阵则为 (7,3)循环码的 监
督矩阵,即
? 循环码监督矩阵的构成
? 由式 (6.3.2) 可见，监督矩阵的第一行是码的监督
多项式 h(x) 的系数的 反序排列,第二、三、四行
是第一行的移位；
? 可用监督多项式的系数来构成监督矩阵
? (n,k) 循环码的监督矩阵
? 对偶问题
? 如果 xn+1=h(x)?g(x)，其中 g(x) 为 (n－ k) 次多
项式，以 g(x)为生成多项式，则生成一个 (n,k) 循
环码；
? 以 h(x) 为生成多项式，则生成 (n,n－ k) 循环码；
? 这两个循环码互为对偶码。
线性码的译码是根据接收字多项式的伴随式和可纠的错
误图样间的一一对应关系，由伴随式得到错误图样；
循环码是线性码的一个特殊子类，循环码的译码与线性
码的译码步骤基本一致。不过由于循环码的循环特性，
使它的译码更加简单易行；
循环码的译码过程仍包括三个步骤：
接收多项式的伴随式计算；
求伴随式对应的错误图样；
用错误图样纠错。
6.3.6 循环码的译码
(1) 根据伴随式定义 ST=HRT 计算伴随式 S
? 设
? 设
的行矢量。表示
其中
H
h
h
h
h
H
)0,,2,1(
0
2
1
?
?
?????
??
?
?
?
?
?
??
?
?
?
?
?
? ??
??
knkniikn
kn
1 2 0
11 1 1 1
2 2 2 2 2
0 0 0 0 0
S (,,,)
S H R
hRhh
hh hR
R
hh hR
n k n k
TT
T
nkn k n k n n k
T
n k n k n n k T nk
T
S S S
SR
SR
SR
? ? ? ?
??? ? ? ? ? ? ?
? ? ? ? ? ? ? ??
?
?
??? ? ? ? ? ? ? ?
??? ? ? ? ? ? ? ?
??? ? ? ? ? ? ? ?
? ? ?
??? ? ? ? ? ? ? ?
??? ? ? ? ? ? ? ?
??
? ? ? ? ? ? ? ? ??
,得 到 伴 随 式 各 分 量 的 表 示 式
? 这是前面介绍过的由接收矢量相应分量直接求和计
算伴随式的方法，对所有线性码都适用。
?
?
?
?
?
?
?
?
?
?
????
????
T
T
knkn
T
knkn
S
S
S
Rh
Rh
Rh
00
22
11
?
所以
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
??
??
???
??
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
???
0
1
2
3
045
156
3456
346
0
1
2
3
4
5
6
1000110
0100011
0010111
0001101
S
S
S
S
RRR
RRR
RRRR
RRR
R
R
R
R
R
R
R
TT
RHS
)11.2.6(11 nkkn ??? ? GmC
? ? )12.2.6(rkknk ?? ? QIG
? ? ? ?
kr
T
rk
T
krrk
rkrSrkkS
????
??
??
??
PQPQ
IPHQIG
)()( 或
(4) 接收字循环移位的伴随式与伴随式循环移位的关系
? 定理 6.3.7：设 S(x) 为接收矢量 R(x) 的伴随式，则
R(x) 的循环移位 xR(x) (mod (xn+1) ) 的伴随式 S(1)(x)
等于伴随式 S(x) 的循环移位 xS(x) (mod g(x) )，即
S(1)(x)≡ xS(x) (mod g(x) )
? 上式说明, 接收矢量的循环移位（ mod (xn+1) 运算下）
与伴随式在模 g(x) 运算下（即在除以 g(x) 的伴随式
计算电路中）的循环移位是一一对应的。
2,循环码的生成多项式
3,系统循环码
4,多项式运算电路
5,循环码的编码电路
6,循环码的译码
7,循环汉明码
8,缩短循环码
循环码
(1) 循环码的性质
? 循环码是线性分组码的一个重要子类；
? 由于循环码具有 优良的代数结构,使得可用简
单的反馈移位寄存器实现编码和伴随式计算，
并可使用多种简单而有效的译码方法；
? 循环码是研究最 深入,理论最 成熟,应用最 广
泛 的一类线性分组码。
(2) 循环码的定义
? 循环码,如果 (n,k) 线性分组码的任意码矢
C=(Cn－ 1,Cn－ 2,…,C0)
的 i 次循环移位，所得矢量
C(i)=(Cn－ 1－ i,Cn－ 2－ i,…,C0,Cn－ 1,…,Cn－ i)
仍是一个码矢，则称此线性码为 (n,k) 循环码。
(3) 码多项式
? 码多项式,为了运算的方便，将码矢的各分量作为多
项式的系数，把码矢表示成多项式，称为码多项式。
其一般表示式为
C(x)=Cn－ 1xn－ 1+Cn－ 2xn－ 2+… +C0)
? 码多项式 i 次循环移位的表示方法
记码多项式 C(x)的一次左移循环为 C(1)(x), i 次左移
循环为 C(i)(x)
? 码多项式的模 (xn+1) 运算
? 0和 1两个元素模 2运算下构成域。
+ 0 1
0 0 1
1 1 0
× 0 1
0 0 0
1 0 1
? 码矢 C 循环 i 次所得码矢的码多项式
? C(x) 乘以 x，再除以 (xn+1)，得
上式表明,码矢循环一次的码多项式 C(1)(x) 是原码
多项式 C(x)乘以 x 除以 (xn+1) 的余式。写作
因此,C(x) 的 i 次循环移位 C(i)(x) 是 C(x) 乘以 xi
除以 (xn+1) 的余式，即
? 结论,循环码的码矢的 i 次循环移位等效于将码多
项式乘 xi 后再模 (xn+1)。
(4) 举例,(7,3) 循环码
可由任一个码矢，比如 (0011101) 经过循环移位，
得到其它 6个非 0码矢；
也可由相应的码多项式 (x4+x3+x2+1)，乘以
xi(i=1,2,…,6)，再模 (x7+1)运算得到其它 6个非 0码
多项式。移位过程和相应的多项式运算如表 6.3.1所
示。
表 6,3,1 循环码的循环移位
移位次数 码 字 码多项式
0 001 1 101 x
4
+ x
3
+ x
2
+1 ( 模 x
7
+ 1)
1 01 1 1010 x ( x
4
+ x
3
+ x
2
+ 1) ≡ x
5
+ x
4
+ x
3
+ x ( 模 x
7
+ 1)
2 1 1 10100 x
2
( x
4
+ x
3
+ x
2
+ 1) ≡ x
6
+ x
5
+ x
4
+ x
2
( 模 x
7
+ 1)
3 1 101001 x
3
( x
4
+ x
3
+ x
2
+ 1) ≡ x
6
+ x
5
+ x
3
+1 ( 模 x
7
+ 1)
4 101001 1 x
4
( x
4
+ x
3
+ x
2
+ 1) ≡ x
6
+ x
4
+ x +1 ( 模 x
7
+ 1)
5 01001 1 1 x
5
( x
4
+ x
3
+ x
2
+ 1) ≡ x
5
+ x
2
+ x +1 ( 模 x
7
+ 1)
6 1001 1 10 x
6
( x
4
+ x
3
+ x
2
+ 1) ≡ x
6
+ x
3
+ x
2
+ x ( 模 x
7
+ 1)
(1) 循环码的生成矩阵
? 根据循环码的循环特性，可由一个码字的循环移位得
到其它的非 0码字。在 (n,k) 循环码的 2k 个码字中，
取前 (k－ 1) 位皆为 0的码字 g(x)（其次数 r=n－ k），
再经 (k－ 1) 次循环移位，共得到 k 个码字,
g(x),xg(x),…,xk－ 1 g(x)
这 k 个码字显然是相互独
立的，可作为码生成矩阵
的 k 行，于是得到 循环码
的生成矩阵 G(x)
(2) 循环码的生成多项式
? 码的生成矩阵一旦确定，码就确定了；
? 这就说明,(n,k) 循环码可由它的一个 (n－ k) 次码多
项式 g(x) 来确定；
? 所以说 g(x) 生成了 (n,k) 循环码，因此 称 g(x) 为码
的生成多项式 。
(3) 生成多项式 和 码多项式 的关系
? 定理, 在 (n,k) 循环码中，生成多项式 g(x) 是
惟一的 (n－ k) 次码多项式，且次数是最低的 。
? 定理,在 (n,k) 循环码中，每个码多项式 C(x)
都是 g(x) 的倍式；而每个为 g(x) 倍式且次数
小于或等于 (n－ 1) 的多项式，必是一个码多
项式 。
? 定理 6.3.3(定理 6.3.2的逆定理 ),在一个 (n,k) 线
性码中，如果全部码多项式都是最低次的 (n－ k)
次码多项式的倍式，则此线性码为一个 (n,k) 循
环码 。
注,一般说来，这种循环码仍具有把 (n,k) 线性码
码中任一非 0码矢循环移位必为一码矢的循环特性，但从
一个非 0码矢出发，进行循环移位，就未必能得到码的所
有非 0码矢了。所以称这种循环码为 推广循环码 。
? 码字循环关系图
? 单纯循环码的 码字循环图,(7,3)循环码
0 0 1 0 1 1 1 1 0 0 1 0 1 1
1 1 0 0 1 0 1
1 1 1 0 0 1 0
0 1 1 1 0 0 1
1 0 1 1 1 0 0
0 1 0 1 1 1 0
0 0 0 0 0 0 0
图 6, 3, 1 ( 7,3 ) 循 环 码 的 循 环 关 系 图
? 推广循环码的 码字循环图,(6,3)循环码
1 0 0 1 0 0
0 1 0 0 1 0
0 0 1 0 0 1
1 1 1 1 1 1
图 6, 3, 2 ( 6,3 ) 循 环 码 的 循 码 字 环 关 系 图
1 0 1 1 0 1
0 1 1 0 1 1
0 0 0 0 0 0
(4) 如何寻找一个合适的生成多项式
? 由下面式子可知：循环码的多项式等于信息多项式乘
以生成多项式。
这说明,对一个循环码只要生成多项式一旦确定，码
就确定了，编码问题就解决了。
所以, 作一循环码的关键，就在于寻找一个适当的生
成多项式 。
? 定理, (n,k) 循环码的生成多项式 g(x) 是
(xn+1)的因式，即 xn+1=h(x)?g(x)。
? 定理,若 g(x) 是一个 (n－ k) 次 多项式，且为
(xn+1) 的因式，则 g(x) 生成一个 (n,k) 循环
码。
结论, 当求作一个 (n,k)循环码时，只要分解多项
式 (xn+1),从中取出 (n－ k)次因式作生成多项
式即可 。
? 举例：求 (7,3) 循环码的生成多项式。
[解 ]：
分解多项式 xn+1，取其 4次因式作生成多项式
x7+1= (x+1) (x3+x2+1) (x3+x+1)
可将一次和任一个三次因式的乘积作为生成多项式，
因而可取
g1(x)= (x+1) (x3+x2+1) = x4+x2+x+1
或 g2(x)= (x+1) (x3+x+1) = x4+x3+x2+1
(5) 循环码的监督多项式和监督矩阵
? 循环码的监督多项式,设 g(x) 为 (n,k) 循环码的生成多
项式，必为 (xn+1) 的因式，则有 xn+1=h(x)?g(x)，式中
h(x) 为 k 次多项式，称为 (n,k) 循环码的监督多项式。
? (n,k) 循环码也可由其监督多项式完全确定。
? 举例, (7,3) 循环码 x7+1= (x3+x+1)(x4+x2+x+1)
? 4次多项式为生成多项式
g(x)=x4+x2+x+1=g4x4+g3x3+g2x2+g1x+g0
? 3次多项式是监督多项式
h(x)=x3+x+1=h3x3+h2x2+h1x+h0
? 循环码的监督矩阵
? 由等式 x7+1= h(x)?g(x) 两端同次项系数相等得
? 将上面的方程组
写成矩阵形式
? 上式中，列阵的元素是生成多项式 g(x) 的系数，
是一个码字，那么第一个矩阵则为 (7,3)循环码的 监
督矩阵,即
? 循环码监督矩阵的构成
? 由式 (6.3.2) 可见，监督矩阵的第一行是码的监督
多项式 h(x) 的系数的 反序排列,第二、三、四行
是第一行的移位；
? 可用监督多项式的系数来构成监督矩阵
? (n,k) 循环码的监督矩阵
? 对偶问题
? 如果 xn+1=h(x)?g(x)，其中 g(x) 为 (n－ k) 次多
项式，以 g(x)为生成多项式，则生成一个 (n,k) 循
环码；
? 以 h(x) 为生成多项式，则生成 (n,n－ k) 循环码；
? 这两个循环码互为对偶码。
线性码的译码是根据接收字多项式的伴随式和可纠的错
误图样间的一一对应关系，由伴随式得到错误图样；
循环码是线性码的一个特殊子类，循环码的译码与线性
码的译码步骤基本一致。不过由于循环码的循环特性，
使它的译码更加简单易行；
循环码的译码过程仍包括三个步骤：
接收多项式的伴随式计算；
求伴随式对应的错误图样；
用错误图样纠错。
6.3.6 循环码的译码
(1) 根据伴随式定义 ST=HRT 计算伴随式 S
? 设
? 设
的行矢量。表示
其中
H
h
h
h
h
H
)0,,2,1(
0
2
1
?
?
?????
??
?
?
?
?
?
??
?
?
?
?
?
? ??
??
knkniikn
kn
1 2 0
11 1 1 1
2 2 2 2 2
0 0 0 0 0
S (,,,)
S H R
hRhh
hh hR
R
hh hR
n k n k
TT
T
nkn k n k n n k
T
n k n k n n k T nk
T
S S S
SR
SR
SR
? ? ? ?
??? ? ? ? ? ? ?
? ? ? ? ? ? ? ??
?
?
??? ? ? ? ? ? ? ?
??? ? ? ? ? ? ? ?
??? ? ? ? ? ? ? ?
? ? ?
??? ? ? ? ? ? ? ?
??? ? ? ? ? ? ? ?
??
? ? ? ? ? ? ? ? ??
,得 到 伴 随 式 各 分 量 的 表 示 式
? 这是前面介绍过的由接收矢量相应分量直接求和计
算伴随式的方法，对所有线性码都适用。
?
?
?
?
?
?
?
?
?
?
????
????
T
T
knkn
T
knkn
S
S
S
Rh
Rh
Rh
00
22
11
?
所以
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
??
??
???
??
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
???
0
1
2
3
045
156
3456
346
0
1
2
3
4
5
6
1000110
0100011
0010111
0001101
S
S
S
S
RRR
RRR
RRRR
RRR
R
R
R
R
R
R
R
TT
RHS
)11.2.6(11 nkkn ??? ? GmC
? ? )12.2.6(rkknk ?? ? QIG
? ? ? ?
kr
T
rk
T
krrk
rkrSrkkS
????
??
??
??
PQPQ
IPHQIG
)()( 或
(4) 接收字循环移位的伴随式与伴随式循环移位的关系
? 定理 6.3.7：设 S(x) 为接收矢量 R(x) 的伴随式，则
R(x) 的循环移位 xR(x) (mod (xn+1) ) 的伴随式 S(1)(x)
等于伴随式 S(x) 的循环移位 xS(x) (mod g(x) )，即
S(1)(x)≡ xS(x) (mod g(x) )
? 上式说明, 接收矢量的循环移位（ mod (xn+1) 运算下）
与伴随式在模 g(x) 运算下（即在除以 g(x) 的伴随式
计算电路中）的循环移位是一一对应的。
