1
第 9章 差错控制编码
9.1 引言
9.2 纠错编码的基本原理
9.3 常用的简单编码
9.4 线性分组码
9.5 循环码
9.6 卷积码
2
9.1 引言
? 差错控制编码的基本方法
在发送端被传输的信息序列上附加一些
监督码元,这些多余码元与信息码元之间
以某种确定的规则相互关联 (约束 ),接收端
按照既定的规则检验信息码元与监督码
元之间的关系,
3
常用差错控制方法
? 检错重发
? 前向纠错
发 收
检错码
应答信号
发 收纠错码
4
混合纠错
发 收
纠检错
应答信号
常用检错重发系统, 停发等候重发,返回
重发和选择重发
5
停发等候重发
1 2 3 3
1
TI
2 3
发
接收 ACK
NAK
发现错误
这是一种半双工的通信方式,原理简单,
效率低,
6
返回重发
1 2 3 4 5 6 2 3 4 5 6 7 8 9…
1 2 3 4 5 6 2 3 4 5 6 7 8 9…
发
接收
发现错误
NAK 从码组 2开始重发
(传输效率最高,需复杂的控制,收、发数据缓存 )选择重发
7 8 9 10 11 12
重发码组 2
7
9.2 纠错编码的基本原理
? 分类
按差错控制编码的 功能, 检错码、纠错
码、纠删码。
按信息码元和附加的监督码元之间的 检
验关系,线性码、非线性码。
按信息码元和监督码元之间的 约束方式：
分组码、卷积码。
8
例,3位二进制数构成的码组
表示天气
全用 用 4种 用 2种 全用 用 4种 用 2种
000 晴 晴 晴 100 雪
001 云 101 霜 阴
010 阴 110 雾 雨
011 雨 云 111 雹 雨
9
如不要检（纠）错，传输 4种不同的
信息，用两位码组就够了，这两位码
代表所传信息，称为 信息位,多增加
的称为 监督位 。
? 将信息码分组，为每组信码附加若干监督码的
编码，称为 分组码 。在分组码中，监督码元仅
监督本码组的中的信息码元。
? 分组码用（ n,k） 表示,n—码组长度,k —
信息位数,n – k = r 监督位数。
? 1的数目称为码组的重量，两个码组对应位上
数字不同的位数称为码组距离（汉明距离）。
各码组间距离的最小值为最小码距 d0
10
d0的大小直接关系着编码的检，纠错
能力。
? 为检测 e 个错码，要求 d0 ≥ e + 1
? 为纠正 t 个错码，要求 d0 ≥2 t + 1
? 为纠正 t 个错码，同时检测 e 个错码，要求
d0 ≥ e + t +1
B
d0
BA 1 2 BA 1 2 BB3 4 5
d0
11
A B1
t
e
若随机信道中，发送,0”和发送,1”时的
错误概率相等，为 P,且 P<<1,则码长为
n 的码组恰好发生 r个错码的概率为,
rrnrr
nn Prnr
nPPCrp
)!(!
!)1()(
????
?
12
当 n=7 P=10-3时
P(1) ≈7× 10-3 P(2) ≈2.1× 10-5
P(3) ≈3.5× 10-8
可见,采用差错控制编码,即使仅能纠
正这种码组中的 1 ~ 2个错误,也可以使
误码率下降几个数量级,
13
9.3 常用的简单编码
? 奇偶监督码
无论信息位有多少,监督位只有一位,使码
组中, 1” 的数目为偶 (或奇 )数,
接收端
?
?
?????
?? 奇数监督码
偶数监督码
1
0
021 aaa nn ?
这种码能够检测奇数个错码,适用
检测随机错误
14
二维奇偶监督码
? 把上述奇偶监督码的若干码组排列成矩
阵,每一码组写成一行,然后,再按列的方向
增加第二维监督位
10111 21 1 aaaa nn ???
20212 22 1 aaaa nn ???
mmmnmn aaaa 0121 ???
0121 cccc nn ???
15
恒比码
? 每个码组均含有相同数目的, 1” (和, 0” ).由
于, 1” 的数目与, 0” 的数目之比保持恒定,故
得此名,
正反码
? 是一种简单的能够纠正错码的编码,监督位数
目与信息位数目相同,监督位与信息位相同或相
反,由信息码中的, 1” 的个数而定,
16
9.4 线性分组码
? 线性分组码中信息码元和监督码元是用线性方
程联系起来的,线性码建立在代数学群论基础上,
线性码各许用码组的集合构成代数学中的群,因
此,又称群码,
? 主要性质
任意两许用码组之和 (模 2和 )仍为一许用码组,
(封闭性 )
码的最小距离等于非零码的最小重量
17
奇偶监督码是一种最简单的线性码,偶
校验时
? S称为校正子,又称伴随式, S=0无错,S=1 有
错,
? 一般,由 r个监督方程式计算得 r个校正子,
可以用来指示 2r-1种错误,对于一位误码来
说,就可以指示 2r-1个误码位置,对于 (n,k)码,
如果满足 2r-1≥n 则可能构造出纠正一位或
一位以上错误的线性码,
021 aaaS nn ???? ?? ?
18
设分组码 (n,k)中 k=4,为纠正一位错码,
要求 r≥3,则 n=k+r=7
S1S2S3 错码位置 S1S2S3 错码位置
001 a0 101 a4
010 a1 110 a5
100 a2 111 a6
011 a3 000 无错
19
024561 ????? aaaaS
013562 ????? aaaaS
003463 ????? aaaaS
4562 aaaa ???
3561 aaaa ???
3460 aaaa ???
计算监督
位判断
错码
位置
按上述方法构造的纠正单个错误的线性
分组码称为 汉明码 。
码长 n=2r – 1 信息位 k= 2r – 1 – r 监督位 r
（ 1）
（ 2）
20
编码速率 =
? （ 1）改写为
n
rrr
n
k
rr
r
??
?
??
?
??? 1
12
1
12
12
00010111 0123456 ?????????????? aaaaaaa
00101011 0123456 ?????????????? aaaaaaa
01001101 0123456 ?????????????? aaaaaaa
表示成矩阵形式
?
?
?
?
?
?
?
?
?
?
1001101
0101011
0010111
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
0
1
2
3
4
5
6
a
a
a
a
a
a
a
= ?
?
?
?
?
?
?
?
?
?
0
0
0
P Ir
21
简记为 或
? H称为监督矩阵,H确定，则编码时监督
位和信息位的关系就完全确定了。
P为 r × k 阶 Ir为 r × r 阶单位方阵
具有 [ P Ir ]形式的 H矩阵称为典型阵。
（ 2）改写为：
TTHA 0? 0?TAH
?
?
?
?
?
?
?
?
?
?
0
1
2
a
a
a
= ?
?
?
?
?
?
?
?
?
?
1101
1011
0111
?
?
?
?
?
?
?
?
?
?
?
?
3
4
5
6
a
a
a
a
22
或
? ?012 aaa ? ?3456 aaaa? ?
?
?
?
?
?
?
?
?
?
?
?
110
101
011
111
? ?3456 aaaa? Q
阶rkPQ T ?? ? ?QIG k? 生成矩阵
? ?0123456 aaaaaaa ? ?3456 aaaa? G
A ? ?3456 aaaa? G
23
具有 形式的生成矩阵称
为典型生成矩阵。
由典型生成矩阵得出的码组 A中，
信息位不变，监督位附加其后，
这种码称为系统码。
? ?QIG k?
24
发送码组 A在传输过程中可能发生误码，
设接收到的码组为 B=[bn-1 bn-2 … b0]
? 则 B – A = E
E= [en-1 en-2 … e0] 错误图样
也可写作 B=A+E
?
?
?
?
?
?
ii
ii
i ab
ab
e
当
当
1
0
25
接收端计算校正子为
错误图样与校正子之间有确定的关系
TTT
TT
EHEHAH
HEABHS
???
??? ）（
26
例 设 且有 3
个接收码组
? 验证 3个接收码组是否发生差错？
? 若在某码组中有错码，错码的校正子是什么？
然后再指出发生错码的码字中，哪位有错？
?
?
?
?
?
?
?
?
?
?
?
100101
010110
001011
H
? ?1011101 ?B
? ?1101012 ?B ? ?1100003 ?B
27
解,1）若无错，则错误图样为 0,S为 0 ? ?
00011 ?? THBS B1无错
? ?10122 ?? THBS B2错
? ?11033 ?? THBS B3错
2） ∵ S2=H 第 1列
∴ E=[1 0 0 0 0 0] 第 1位错
同理 S3=H 第 3列
∴ E=[0 0 1 0 0 0] 第 3位错
TEHS ?
28
线性码的重要性质
? 封闭性
任意许用两个码组之和仍为许用码组
? 两个码组之间的距离必是另一码组的重
量,故最小码距即码的最小重量 (除全 0码
外 )
29
9.5 循环码
9.5.1 循环码原理
? 循环码是一种重要的线性分组码,易于实
现,性能较好,
? 循环码除具有线性码的一般性质外,还具
有循环性,即循环码中任一码组循环一位
以后,仍为该码中的一个码组,
? 一长为 n的码组可表示成码多项式
01
2
2
1
1)( axaxaxaxT
n
n
n
n ?????
?
?
?
? ?
30
码多项式的按模运算
若 F(x) = N(x) Q(x) + R(x)
则 F(x) ≡ R(x) ( 模 N(x) )
例 )1(11 3224 ?????? xxxxx 模
x
xxx 11 243 ???
xx ?4
12 ?? xx
31
在循环码中,若 T(x)是一个长为 n
的许用码组,则 xi T(x)在按模 xn +1
运算下,也是一个许用码组,
即 若
则 T′(x)也是一个许用码组
)1()()( ???? ni xxTxTx 模
32
在循环码中，一个（ n,k） 码有 2k个
不同码组
? 假设用 g（ x） 表示一个前 k-1位皆为 0（第
k位不为 0）的码组
则
在循环码中，除全 0码外，再没有连续 k
位均为, 0” 的码组，即连, 0” 的长度
最多只能 k-1位。因此 g（ x） 必须是一个
常数项不为, 0” 的 n-k次多项式
012211)( axaxaxaxT nnnn ????? ???? ?
011)( axaxaxg knknknkn ???? ?????? ?
生成多项
式
33
g(x),xg(x),x2g(x),… xk-1g(x)都是码组,且线性
无关,故循环码的生成矩阵 G可写成
? 假如输入信息码元 mk-1 mk-2 … m0 则
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
)(
)(
)(
)(
)(
2
1
xg
xxg
xgx
xgx
xG
k
k
?
)()()( 021 xGmmmxT kk ????
)()( 02211 xgmxmxm kkkk ???? ???? ?
34
所有码多项式 T(x)都可被 g(x)整除,而且,
任一次数不大于 k-1的多项式乘 g(x)都
是码多项式,
? 生成多项式 g(X)的确定
∵ T(x) = h(x) g(x)
又 g(x)为一个码组,故 xkg(x)在模 xn+1运算下
也为一码组,故可写成
1
)()(
1
)(
???? nn
k
x
xTxQ
x
xgx
=1
35
? 故 g(x) 是 xn+1的一个 n – k次因式,此即寻
找 g(x) 的方法,
例
)(1)( xTxxgx nk ???
)]()[()()()(1 xhxxgxgxhxgxx kkn ?????
)1)(1)(1(1 3237 ??????? xxxxxx
都可作为 (7,3)循环码的生成多项式
36
9.5.2 循环码的编、解码方法
编码步骤
? 根据给定的（ n,k)选定生成多项式 g(x),即
从 xn+1的因子中选一 n-k次多项式作为
g(x).
? 所有码多项式 T(x)都可被 g(x)整除,据此
对给定的信息位 m(x)进行编码,
1,信息码后附加 n-k个 0
2.
3.
)( xmx kn ?
)(
)()(
)(
)(
xg
xrxQ
xg
xmx kn ???
)()()( xrxmxxT kn ?? ?
37
监督位信息位
例 (7,3)循环码 m(x)=x2+x,g(x)= x4 +x2+ x+1
? 解 5637 )( xxxmx ???
1)(
)(
24
56
???
???
xxx
xx
xg
xmx kn
1
11
24
2
2
???
?????
xxx
xxx r(x)
1 1 0 0 1 0 11)( 256 ????? xxxxT
38
a + b + c d +
输入 m
输出 f
e
S
（ 7,3）码编码器
m a b c d e f
0 0 0 0 0 0 0
1 1 1 1 0 1 1
1 1 0 0 1 1 1
0 1 0 1 0 1 0
0 0 1 0 1 0 0
0 0 0 1 0 1 1
0 0 0 0 1 0 0
0 0 0 0 0 1 1
f=m
f=e
39
循环码的解码
? 将接收码组 R(x)用 g(x)去除,若未发生错误,
R(x)能被 g(x)整除,发生错误则有余项,
40
9.6 卷积码
在编码器复杂性相同的情况下,卷积
码的性能优于分组码,
? 卷积码把 k个信息位编 n位,k和 n通常很小,
特别适宜于串行形式传输,延时小,
? n 个码元与当前段的 k个信息位有关,而且
与前 N-1段的信息有关,编码过程相互关联
的码元为 Nn个,
? N或 nN称为卷积码的约束长度,
? 常把卷积码记作 (n,k,N)
41
6 5 4 3 2 1
+
输入 bi
ci
输出
bici
卷积码编码器
k=1,n=2,N=6
42
b6 b5 b4 b3 b2 b1
+
一级
移存
+
S6 S5 S4 S3 S2 S1
+
门限电路
(2,1,6)卷积码门限译码器
输入
bi
ci
重算 ci
输出
校正子
,1”的个数 ≥3?
43
假定 b1以前各码元均未发生错误,则
)()( 111 cEbES ??
)()( 222 cEbES ??
)()( 333 cEbES ??
)()()( 1444 bEcEbES ???
)()()()( 21555 bEbEcEbES ????
)()()()()( 321666 bEbEbEcEbES ?????
?
?
??
错
无错
b
bbE
1
0)(
?
?
??
错
无错
c
ccE
1
0)(
(1)
44
(1)式经线性变换
? 这是一组正交于 E(b1)的正交校验方程,在
所考察的 12个码元 (b1~b6,c1~c6)中错误不多
于 2个的条件下,仅当 E(b1)=1,(2)式才有可
能有 3个或 3个以上方程等于 1,门限电路门
限设为 3,此时,门限电路输出, 1”,纠正 b1
错误,同时送到受 E(b1)影响的各级校正子
移存器纠正其中错误,
)()( 111 cEbES ?? )()()(
1444 bEcEbES ??? )()()()(
21555 bEbEcEbES ???? )()()()()(
6263162 cEcEbEbEbESS ??????
(2)
45
监督矩阵 H
假定 b1进入编码器之前，各级移存器
处于, 0” 状态
则 即11 bc ?
22 bc ?
33 bc ?
414 bbc ??
5215 bbbc ???
63216 bbbbc ????
74327 bbbbc ????
011 ?? bc
022 ?? bc
033 ?? bc
05215 ???? bbbc
0414 ??? bbc
063216 ???? bbbc
074327 ????? bbbbc
46
H1
用矩阵表示为
1 1
0 0 1 1
0 0 0 0 1 1
1 0 0 0 0 0 1 1
1 0 1 0 0 0 0 0 1 1
1 0 1 0 1 0 0 0 0 0 1 1
0 0 1 0 1 0 1 0 0 0 0 0 1 1
…
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
6
6
5
5
4
4
3
3
2
2
1
1
c
b
c
b
c
b
c
b
c
b
c
b
0?Nkn )( ?
n
n-k
47
H1,截短监督矩阵
自第 7行起，每行结构相同，只是每
行的起始比上一行多两个, 0” 。
? 一般，卷积码的截短监督矩阵形式为：
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
???
?
?
?
knNNN
kn
kn
kn
Ipppp
Ippp
Ipp
Ip
H
121
123
12
1
1
000
00
0
?
?
48
In-k — n-k阶单位方阵
Pi — （ n-k）× k矩阵
0 — n-k 阶全零方阵
? 基本监督矩阵
h=[ PN 0 PN-1 0 PN-2 0 … P1 In-k ]
只要给定 h,H1随之确定。
49
生成矩阵 G 基本生成矩阵 g
g=[ IK Q1 0 Q2 0 Q3 … 0 QN ]
? 截短生成矩阵
?1G
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
1
21
121
321
0
00
000
QI
QQI
QQQI
QQQQI
k
Nk
NK
Nk
?
?
Ik — k阶单位方阵
Qi =PiT —k × （ n-k） 矩阵
0 — k 阶全零方阵
50
卷积码的图解表示
（ 3,1,3）卷积码编码器
a 状态 m1m2为 00,b 状态 m1m2为 01，
c 状态 m1m2为 10,d 状态 m1m2为 11。
M3 M2 M1
+
+
输入序列
mj
mj
y1,j
Y2,j
51
（ 3,1,3）卷积码的树状图
000
000
111
000
111
001
110
000
111
001
110
011
100
010
101
a
a
b
a
b
c
d
a
bc
d
a
b
c
d
111
001
110
011
100
010
101
000
111
001
110
011
100
010
101
b
c
d
a
b
c
d
a
bc
d
a
b
c
d
a
52
（ 3,1,3）卷积码的网格图
a
b
c
d
000 000 000 000 000
111 111 111 111 111
011 011 011
001 001 001 001
110 110 110 110
010 010 010
101 101 101
100
53
（ 3,1,3）卷积码的状态图
a a
b b
c c
d a
111
110
101
000
011
100
001
010
a
b
c
d
111000 110 101
100 001
011 010
54
在前述编码器中，若起始状态为 a,输入序
列为 11010111，求输出序列和状态变化路径
a
b
c
d
000 000 000 000 000
111 111 111 111 111
011 011 011
001 001 001 001
110 110 110 110
010 010 010
101 101 101
100
55
对于（ n,k,N） 卷积码的一般情况，
有如下结论：
? 对应于每组 k个输入比特，编码后产生 n
个输出比特。
? 树状图每个节点引出 2k条支路。
? 网格图和状态图都有 2k(N-1)种可能的状态，
每个状态引出 2k条支路，同时也有 2k条支
路从其它状态或本状态引入。
第 9章 差错控制编码
9.1 引言
9.2 纠错编码的基本原理
9.3 常用的简单编码
9.4 线性分组码
9.5 循环码
9.6 卷积码
2
9.1 引言
? 差错控制编码的基本方法
在发送端被传输的信息序列上附加一些
监督码元,这些多余码元与信息码元之间
以某种确定的规则相互关联 (约束 ),接收端
按照既定的规则检验信息码元与监督码
元之间的关系,
3
常用差错控制方法
? 检错重发
? 前向纠错
发 收
检错码
应答信号
发 收纠错码
4
混合纠错
发 收
纠检错
应答信号
常用检错重发系统, 停发等候重发,返回
重发和选择重发
5
停发等候重发
1 2 3 3
1
TI
2 3
发
接收 ACK
NAK
发现错误
这是一种半双工的通信方式,原理简单,
效率低,
6
返回重发
1 2 3 4 5 6 2 3 4 5 6 7 8 9…
1 2 3 4 5 6 2 3 4 5 6 7 8 9…
发
接收
发现错误
NAK 从码组 2开始重发
(传输效率最高,需复杂的控制,收、发数据缓存 )选择重发
7 8 9 10 11 12
重发码组 2
7
9.2 纠错编码的基本原理
? 分类
按差错控制编码的 功能, 检错码、纠错
码、纠删码。
按信息码元和附加的监督码元之间的 检
验关系,线性码、非线性码。
按信息码元和监督码元之间的 约束方式：
分组码、卷积码。
8
例,3位二进制数构成的码组
表示天气
全用 用 4种 用 2种 全用 用 4种 用 2种
000 晴 晴 晴 100 雪
001 云 101 霜 阴
010 阴 110 雾 雨
011 雨 云 111 雹 雨
9
如不要检（纠）错，传输 4种不同的
信息，用两位码组就够了，这两位码
代表所传信息，称为 信息位,多增加
的称为 监督位 。
? 将信息码分组，为每组信码附加若干监督码的
编码，称为 分组码 。在分组码中，监督码元仅
监督本码组的中的信息码元。
? 分组码用（ n,k） 表示,n—码组长度,k —
信息位数,n – k = r 监督位数。
? 1的数目称为码组的重量，两个码组对应位上
数字不同的位数称为码组距离（汉明距离）。
各码组间距离的最小值为最小码距 d0
10
d0的大小直接关系着编码的检，纠错
能力。
? 为检测 e 个错码，要求 d0 ≥ e + 1
? 为纠正 t 个错码，要求 d0 ≥2 t + 1
? 为纠正 t 个错码，同时检测 e 个错码，要求
d0 ≥ e + t +1
B
d0
BA 1 2 BA 1 2 BB3 4 5
d0
11
A B1
t
e
若随机信道中，发送,0”和发送,1”时的
错误概率相等，为 P,且 P<<1,则码长为
n 的码组恰好发生 r个错码的概率为,
rrnrr
nn Prnr
nPPCrp
)!(!
!)1()(
????
?
12
当 n=7 P=10-3时
P(1) ≈7× 10-3 P(2) ≈2.1× 10-5
P(3) ≈3.5× 10-8
可见,采用差错控制编码,即使仅能纠
正这种码组中的 1 ~ 2个错误,也可以使
误码率下降几个数量级,
13
9.3 常用的简单编码
? 奇偶监督码
无论信息位有多少,监督位只有一位,使码
组中, 1” 的数目为偶 (或奇 )数,
接收端
?
?
?????
?? 奇数监督码
偶数监督码
1
0
021 aaa nn ?
这种码能够检测奇数个错码,适用
检测随机错误
14
二维奇偶监督码
? 把上述奇偶监督码的若干码组排列成矩
阵,每一码组写成一行,然后,再按列的方向
增加第二维监督位
10111 21 1 aaaa nn ???
20212 22 1 aaaa nn ???
mmmnmn aaaa 0121 ???
0121 cccc nn ???
15
恒比码
? 每个码组均含有相同数目的, 1” (和, 0” ).由
于, 1” 的数目与, 0” 的数目之比保持恒定,故
得此名,
正反码
? 是一种简单的能够纠正错码的编码,监督位数
目与信息位数目相同,监督位与信息位相同或相
反,由信息码中的, 1” 的个数而定,
16
9.4 线性分组码
? 线性分组码中信息码元和监督码元是用线性方
程联系起来的,线性码建立在代数学群论基础上,
线性码各许用码组的集合构成代数学中的群,因
此,又称群码,
? 主要性质
任意两许用码组之和 (模 2和 )仍为一许用码组,
(封闭性 )
码的最小距离等于非零码的最小重量
17
奇偶监督码是一种最简单的线性码,偶
校验时
? S称为校正子,又称伴随式, S=0无错,S=1 有
错,
? 一般,由 r个监督方程式计算得 r个校正子,
可以用来指示 2r-1种错误,对于一位误码来
说,就可以指示 2r-1个误码位置,对于 (n,k)码,
如果满足 2r-1≥n 则可能构造出纠正一位或
一位以上错误的线性码,
021 aaaS nn ???? ?? ?
18
设分组码 (n,k)中 k=4,为纠正一位错码,
要求 r≥3,则 n=k+r=7
S1S2S3 错码位置 S1S2S3 错码位置
001 a0 101 a4
010 a1 110 a5
100 a2 111 a6
011 a3 000 无错
19
024561 ????? aaaaS
013562 ????? aaaaS
003463 ????? aaaaS
4562 aaaa ???
3561 aaaa ???
3460 aaaa ???
计算监督
位判断
错码
位置
按上述方法构造的纠正单个错误的线性
分组码称为 汉明码 。
码长 n=2r – 1 信息位 k= 2r – 1 – r 监督位 r
（ 1）
（ 2）
20
编码速率 =
? （ 1）改写为
n
rrr
n
k
rr
r
??
?
??
?
??? 1
12
1
12
12
00010111 0123456 ?????????????? aaaaaaa
00101011 0123456 ?????????????? aaaaaaa
01001101 0123456 ?????????????? aaaaaaa
表示成矩阵形式
?
?
?
?
?
?
?
?
?
?
1001101
0101011
0010111
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
0
1
2
3
4
5
6
a
a
a
a
a
a
a
= ?
?
?
?
?
?
?
?
?
?
0
0
0
P Ir
21
简记为 或
? H称为监督矩阵,H确定，则编码时监督
位和信息位的关系就完全确定了。
P为 r × k 阶 Ir为 r × r 阶单位方阵
具有 [ P Ir ]形式的 H矩阵称为典型阵。
（ 2）改写为：
TTHA 0? 0?TAH
?
?
?
?
?
?
?
?
?
?
0
1
2
a
a
a
= ?
?
?
?
?
?
?
?
?
?
1101
1011
0111
?
?
?
?
?
?
?
?
?
?
?
?
3
4
5
6
a
a
a
a
22
或
? ?012 aaa ? ?3456 aaaa? ?
?
?
?
?
?
?
?
?
?
?
?
110
101
011
111
? ?3456 aaaa? Q
阶rkPQ T ?? ? ?QIG k? 生成矩阵
? ?0123456 aaaaaaa ? ?3456 aaaa? G
A ? ?3456 aaaa? G
23
具有 形式的生成矩阵称
为典型生成矩阵。
由典型生成矩阵得出的码组 A中，
信息位不变，监督位附加其后，
这种码称为系统码。
? ?QIG k?
24
发送码组 A在传输过程中可能发生误码，
设接收到的码组为 B=[bn-1 bn-2 … b0]
? 则 B – A = E
E= [en-1 en-2 … e0] 错误图样
也可写作 B=A+E
?
?
?
?
?
?
ii
ii
i ab
ab
e
当
当
1
0
25
接收端计算校正子为
错误图样与校正子之间有确定的关系
TTT
TT
EHEHAH
HEABHS
???
??? ）（
26
例 设 且有 3
个接收码组
? 验证 3个接收码组是否发生差错？
? 若在某码组中有错码，错码的校正子是什么？
然后再指出发生错码的码字中，哪位有错？
?
?
?
?
?
?
?
?
?
?
?
100101
010110
001011
H
? ?1011101 ?B
? ?1101012 ?B ? ?1100003 ?B
27
解,1）若无错，则错误图样为 0,S为 0 ? ?
00011 ?? THBS B1无错
? ?10122 ?? THBS B2错
? ?11033 ?? THBS B3错
2） ∵ S2=H 第 1列
∴ E=[1 0 0 0 0 0] 第 1位错
同理 S3=H 第 3列
∴ E=[0 0 1 0 0 0] 第 3位错
TEHS ?
28
线性码的重要性质
? 封闭性
任意许用两个码组之和仍为许用码组
? 两个码组之间的距离必是另一码组的重
量,故最小码距即码的最小重量 (除全 0码
外 )
29
9.5 循环码
9.5.1 循环码原理
? 循环码是一种重要的线性分组码,易于实
现,性能较好,
? 循环码除具有线性码的一般性质外,还具
有循环性,即循环码中任一码组循环一位
以后,仍为该码中的一个码组,
? 一长为 n的码组可表示成码多项式
01
2
2
1
1)( axaxaxaxT
n
n
n
n ?????
?
?
?
? ?
30
码多项式的按模运算
若 F(x) = N(x) Q(x) + R(x)
则 F(x) ≡ R(x) ( 模 N(x) )
例 )1(11 3224 ?????? xxxxx 模
x
xxx 11 243 ???
xx ?4
12 ?? xx
31
在循环码中,若 T(x)是一个长为 n
的许用码组,则 xi T(x)在按模 xn +1
运算下,也是一个许用码组,
即 若
则 T′(x)也是一个许用码组
)1()()( ???? ni xxTxTx 模
32
在循环码中，一个（ n,k） 码有 2k个
不同码组
? 假设用 g（ x） 表示一个前 k-1位皆为 0（第
k位不为 0）的码组
则
在循环码中，除全 0码外，再没有连续 k
位均为, 0” 的码组，即连, 0” 的长度
最多只能 k-1位。因此 g（ x） 必须是一个
常数项不为, 0” 的 n-k次多项式
012211)( axaxaxaxT nnnn ????? ???? ?
011)( axaxaxg knknknkn ???? ?????? ?
生成多项
式
33
g(x),xg(x),x2g(x),… xk-1g(x)都是码组,且线性
无关,故循环码的生成矩阵 G可写成
? 假如输入信息码元 mk-1 mk-2 … m0 则
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
)(
)(
)(
)(
)(
2
1
xg
xxg
xgx
xgx
xG
k
k
?
)()()( 021 xGmmmxT kk ????
)()( 02211 xgmxmxm kkkk ???? ???? ?
34
所有码多项式 T(x)都可被 g(x)整除,而且,
任一次数不大于 k-1的多项式乘 g(x)都
是码多项式,
? 生成多项式 g(X)的确定
∵ T(x) = h(x) g(x)
又 g(x)为一个码组,故 xkg(x)在模 xn+1运算下
也为一码组,故可写成
1
)()(
1
)(
???? nn
k
x
xTxQ
x
xgx
=1
35
? 故 g(x) 是 xn+1的一个 n – k次因式,此即寻
找 g(x) 的方法,
例
)(1)( xTxxgx nk ???
)]()[()()()(1 xhxxgxgxhxgxx kkn ?????
)1)(1)(1(1 3237 ??????? xxxxxx
都可作为 (7,3)循环码的生成多项式
36
9.5.2 循环码的编、解码方法
编码步骤
? 根据给定的（ n,k)选定生成多项式 g(x),即
从 xn+1的因子中选一 n-k次多项式作为
g(x).
? 所有码多项式 T(x)都可被 g(x)整除,据此
对给定的信息位 m(x)进行编码,
1,信息码后附加 n-k个 0
2.
3.
)( xmx kn ?
)(
)()(
)(
)(
xg
xrxQ
xg
xmx kn ???
)()()( xrxmxxT kn ?? ?
37
监督位信息位
例 (7,3)循环码 m(x)=x2+x,g(x)= x4 +x2+ x+1
? 解 5637 )( xxxmx ???
1)(
)(
24
56
???
???
xxx
xx
xg
xmx kn
1
11
24
2
2
???
?????
xxx
xxx r(x)
1 1 0 0 1 0 11)( 256 ????? xxxxT
38
a + b + c d +
输入 m
输出 f
e
S
（ 7,3）码编码器
m a b c d e f
0 0 0 0 0 0 0
1 1 1 1 0 1 1
1 1 0 0 1 1 1
0 1 0 1 0 1 0
0 0 1 0 1 0 0
0 0 0 1 0 1 1
0 0 0 0 1 0 0
0 0 0 0 0 1 1
f=m
f=e
39
循环码的解码
? 将接收码组 R(x)用 g(x)去除,若未发生错误,
R(x)能被 g(x)整除,发生错误则有余项,
40
9.6 卷积码
在编码器复杂性相同的情况下,卷积
码的性能优于分组码,
? 卷积码把 k个信息位编 n位,k和 n通常很小,
特别适宜于串行形式传输,延时小,
? n 个码元与当前段的 k个信息位有关,而且
与前 N-1段的信息有关,编码过程相互关联
的码元为 Nn个,
? N或 nN称为卷积码的约束长度,
? 常把卷积码记作 (n,k,N)
41
6 5 4 3 2 1
+
输入 bi
ci
输出
bici
卷积码编码器
k=1,n=2,N=6
42
b6 b5 b4 b3 b2 b1
+
一级
移存
+
S6 S5 S4 S3 S2 S1
+
门限电路
(2,1,6)卷积码门限译码器
输入
bi
ci
重算 ci
输出
校正子
,1”的个数 ≥3?
43
假定 b1以前各码元均未发生错误,则
)()( 111 cEbES ??
)()( 222 cEbES ??
)()( 333 cEbES ??
)()()( 1444 bEcEbES ???
)()()()( 21555 bEbEcEbES ????
)()()()()( 321666 bEbEbEcEbES ?????
?
?
??
错
无错
b
bbE
1
0)(
?
?
??
错
无错
c
ccE
1
0)(
(1)
44
(1)式经线性变换
? 这是一组正交于 E(b1)的正交校验方程,在
所考察的 12个码元 (b1~b6,c1~c6)中错误不多
于 2个的条件下,仅当 E(b1)=1,(2)式才有可
能有 3个或 3个以上方程等于 1,门限电路门
限设为 3,此时,门限电路输出, 1”,纠正 b1
错误,同时送到受 E(b1)影响的各级校正子
移存器纠正其中错误,
)()( 111 cEbES ?? )()()(
1444 bEcEbES ??? )()()()(
21555 bEbEcEbES ???? )()()()()(
6263162 cEcEbEbEbESS ??????
(2)
45
监督矩阵 H
假定 b1进入编码器之前，各级移存器
处于, 0” 状态
则 即11 bc ?
22 bc ?
33 bc ?
414 bbc ??
5215 bbbc ???
63216 bbbbc ????
74327 bbbbc ????
011 ?? bc
022 ?? bc
033 ?? bc
05215 ???? bbbc
0414 ??? bbc
063216 ???? bbbc
074327 ????? bbbbc
46
H1
用矩阵表示为
1 1
0 0 1 1
0 0 0 0 1 1
1 0 0 0 0 0 1 1
1 0 1 0 0 0 0 0 1 1
1 0 1 0 1 0 0 0 0 0 1 1
0 0 1 0 1 0 1 0 0 0 0 0 1 1
…
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
6
6
5
5
4
4
3
3
2
2
1
1
c
b
c
b
c
b
c
b
c
b
c
b
0?Nkn )( ?
n
n-k
47
H1,截短监督矩阵
自第 7行起，每行结构相同，只是每
行的起始比上一行多两个, 0” 。
? 一般，卷积码的截短监督矩阵形式为：
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
???
?
?
?
knNNN
kn
kn
kn
Ipppp
Ippp
Ipp
Ip
H
121
123
12
1
1
000
00
0
?
?
48
In-k — n-k阶单位方阵
Pi — （ n-k）× k矩阵
0 — n-k 阶全零方阵
? 基本监督矩阵
h=[ PN 0 PN-1 0 PN-2 0 … P1 In-k ]
只要给定 h,H1随之确定。
49
生成矩阵 G 基本生成矩阵 g
g=[ IK Q1 0 Q2 0 Q3 … 0 QN ]
? 截短生成矩阵
?1G
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
1
21
121
321
0
00
000
QI
QQI
QQQI
QQQQI
k
Nk
NK
Nk
?
?
Ik — k阶单位方阵
Qi =PiT —k × （ n-k） 矩阵
0 — k 阶全零方阵
50
卷积码的图解表示
（ 3,1,3）卷积码编码器
a 状态 m1m2为 00,b 状态 m1m2为 01，
c 状态 m1m2为 10,d 状态 m1m2为 11。
M3 M2 M1
+
+
输入序列
mj
mj
y1,j
Y2,j
51
（ 3,1,3）卷积码的树状图
000
000
111
000
111
001
110
000
111
001
110
011
100
010
101
a
a
b
a
b
c
d
a
bc
d
a
b
c
d
111
001
110
011
100
010
101
000
111
001
110
011
100
010
101
b
c
d
a
b
c
d
a
bc
d
a
b
c
d
a
52
（ 3,1,3）卷积码的网格图
a
b
c
d
000 000 000 000 000
111 111 111 111 111
011 011 011
001 001 001 001
110 110 110 110
010 010 010
101 101 101
100
53
（ 3,1,3）卷积码的状态图
a a
b b
c c
d a
111
110
101
000
011
100
001
010
a
b
c
d
111000 110 101
100 001
011 010
54
在前述编码器中，若起始状态为 a,输入序
列为 11010111，求输出序列和状态变化路径
a
b
c
d
000 000 000 000 000
111 111 111 111 111
011 011 011
001 001 001 001
110 110 110 110
010 010 010
101 101 101
100
55
对于（ n,k,N） 卷积码的一般情况，
有如下结论：
? 对应于每组 k个输入比特，编码后产生 n
个输出比特。
? 树状图每个节点引出 2k条支路。
? 网格图和状态图都有 2k(N-1)种可能的状态，
每个状态引出 2k条支路，同时也有 2k条支
路从其它状态或本状态引入。
