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 aaa3456 aaaa
110
101
011
111
3456 aaaa? Q
阶rkPQ TQIG k? 生成矩阵
0123456 aaaaaaa3456 aaaa? G
A3456 aaaa? G
23
具有 形式的生成矩阵称为典型生成矩阵。
由典型生成矩阵得出的码组 A中，
信息位不变，监督位附加其后，
这种码称为系统码。
QIG k?
24
发送码组 A在传输过程中可能发生误码，
设接收到的码组为 B=[bn-1 bn-2 … b 0]
则 B – A = E
E= [en-1 en-2 … e 0] 错误图样也可写作 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?B1100003?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),…x k-1g(x)都是码组,且线性无关,故循环码的生成矩阵 G可写成
假如输入信息码元 mk-1 mk-2 … m 0 则
)(
)(
)(
)(
)(
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 … P 1 In-k ]
只要给定 h,H1随之确定。
49
生成矩阵 G 基本生成矩阵 g
g=[ IK Q1 0 Q2 0 Q3 … 0 Q N ]
截短生成矩阵
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 aaa3456 aaaa
110
101
011
111
3456 aaaa? Q
阶rkPQ TQIG k? 生成矩阵
0123456 aaaaaaa3456 aaaa? G
A3456 aaaa? G
23
具有 形式的生成矩阵称为典型生成矩阵。
由典型生成矩阵得出的码组 A中，
信息位不变，监督位附加其后，
这种码称为系统码。
QIG k?
24
发送码组 A在传输过程中可能发生误码，
设接收到的码组为 B=[bn-1 bn-2 … b 0]
则 B – A = E
E= [en-1 en-2 … e 0] 错误图样也可写作 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?B1100003?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),…x k-1g(x)都是码组,且线性无关,故循环码的生成矩阵 G可写成
假如输入信息码元 mk-1 mk-2 … m 0 则
)(
)(
)(
)(
)(
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 … P 1 In-k ]
只要给定 h,H1随之确定。
49
生成矩阵 G 基本生成矩阵 g
g=[ IK Q1 0 Q2 0 Q3 … 0 Q N ]
截短生成矩阵
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条支路从其它状态或本状态引入。
