1
第十章 信道编码和差错控制
10.1概述
信道编码：
目的：提高信号传输的可靠性。
方法：增加多余比特，以发现或纠正错误。
差错控制：包括信道编码在内的一切纠正错误手段。
产生错码的原因：
乘性干扰引起的码间串扰
加性干扰引起的信噪比降低
信道分类：按照加性干扰造成错码的统计特性不同划分
随机信道：错码随机出现，例如由白噪声引起的错码
突发信道：错码相对集中出现，例如由脉冲干扰引起的错码。
混合信道
2
差错控制技术的种类：
检错重发：
能发现错码，但是不能确定错码的位置。
通信系统需要有双向信道。
前向纠错 (FEC)：利用加入的差错控制码元，不但能够发现错码，还能纠正错码。
反馈校验：
将收到的码元转发回发送端，将它和原发送码元比较。
缺点：需要双向信道，传输效率也较低。
检错删除：
在接收端发现错码后，立即将其删除。
适用在发送码元中有大量多余度，删除部分接收码元不影响应用之处。
3
编码序列的参数
n － 编码序列中总码元数量
k － 编码序列中信息码元数量
r － 编码序列中差错控制码元数量
（差错控制码元，以后称为监督码元或监督位 ）
k/n － 码率
(n - k) / k = r / k － 冗余度
4
自动要求重发 (ARQ)系统
停止等待 ARQ系统
拉后 ARQ系统停止等待 ARQ系统接收数据
ACK ACK NAK ACK ACK NAK ACK
1 2 3 3 4 5 5
t
发送数据
1 2 3 3 4 5 5 6
t
有错码组 有错码组拉后 ARQ系统
21 43 65 7 98接收数据有错码组 有错码组
910 11 10 11 125 76
ACK1 NAK5 NAK9ACK5
5 76 9521 43 6 7 98发送数据 10 11 10 11 12
重发码组 重发码组
5
选择重发 ARQ系统
ARQ和前向纠错比较：
优点
监督码元较少，即码率较高
检错的计算复杂度较低
能适应不同特性的信道
缺点
需要双向信道。
不适用于一点到多点的通信系统或广播系统。
传输效率降低，可能因反复重发而造成事实上的通信中断。
选择重发 ARQ系统
9接收数据有错码组 有错码组
21 43 65 7 5 98 10 11 13 1412
发送数据 9 95 8521 43 6 7 10 11 13 1412
重发码组 重发码组
NAK9ACK1 NAK5 ACK5 ACK9
6
10.2 纠错编码的基本原理
分组码举例
设：有一种由 3个二进制码元构成的编码，它共有 23 = 8种不同的可能码组：
000 – 晴 001 – 云 010 – 阴 011 – 雨
100 – 雪 101 – 霜 110 – 雾 111 – 雹这时，若一个码组中发生错码，则将收到错误信息。
若在此 8种码组中仅允许使用 4种来传送天气，例如：令
000 – 晴 011 – 云 101 – 阴 110 – 雨为 许用码组,其他 4种不允许使用，称为 禁用码组 。
这时，接收端有可能发现（检测到）码组中的一个错码。
这种编码只能检测错码，不能纠正错码。
若规定只许用两个码组：例如
000 – 晴 111 – 雨就能检测两个以下错码，或纠正一个错码。
7
分组码概念
分组码 ＝ 信息位 ＋ 监督位
分组码符号,(n,k)
其中,n － 码组总长度，
k － 信息码元数目。
r = n – k － 监督码元数目。
右表中的码组为 (3,2)码。
分组码的一般结构：
分组码的参数：
码重：码组内,1”的个数
码距：两码组中对应位取值不同的位数，又称汉明距离
最小码距 (d0),各码组间的最小距离信息位 监督位晴 00 0
云 01 1
阴 10 1
雨 11 0
k个信息位 r个监督位
an-1 an-2,.,ar ar-1 an-2,.,a0 t
码长 n = k + r
分组码的结构
8
码距的几何意义：以 n = 3的编码为例
一般而言，码距是 n 维空间中单位正多面体顶点之间的汉明距离。
(0,0,0)
(0,0,1) (1,0,1)
(1,0,0)
(1,1,0)(0,1,0)
(0,1,1) (1,1,1)
a2
a0
a1
9
一种编码的纠检错能力：决定于最小码距 d0的值。
为了能检测 e个错码，要求最小码距
为了能纠正 t 个错码，要求最小码距
10 ed
0 1 2 3
BA 汉明距离e
d0
码距等于 3的两个码组
120 td
B tA 汉明距离
0 1 2 3 4 5t
d0
码距等于 5的两个码组
10
为了能纠正 t个错码，同时检测 e个错码，要求最小码距纠检结合工作方式：
当错码数量少时，系统按前向纠错方式工作，以节省重发时间，提高传输效率；
当错码数量多时，系统按反馈重发的纠错方式工作，
以降低系统的总误码率。
A B
1
tt 汉明距离
e
码距等于 (e+t+1)的两个码组
)(10 teted
11
10.3 纠错编码系统的性能
10.3.1 误码率性能和带宽的关系采用编码降低误码率所付出的代价是带宽的增大。
10-6
10-5
10-4
10-3
10-2
10-1
编码后
Eb/n0 (dB)
编码和误码率关系
Pe
C
D
E
A?
B
2PSK
12
10.3.2 功率和带宽的关系采用编码以节省功率，并保持误码率不变，付出的代价也是带宽增大。
10-6
10-5
10-4
10-3
10-2
10-1
编码后
Eb/n0 (dB)
编码和误码率关系
Pe
C
D
E
A?
B
2PSK
13
10.3.3 传输速率和带宽的关系对于给定的传输系统，其传输速率和 Eb/n0的关系：
式中,RB － 码元速率。
提高传输速率，采用编码以保持误码率不变；付出的代价仍是带宽增大。
B
sssb
Rn
P
Tn
P
n
TP
n
E
0000 )/1(
10-6
10-5
10-4
10-3
10-2
10-1
编码后
Eb/n0 (dB)
编码和误码率关系
Pe
C
D
E
A?
B
2PSK
14
10.3.4 编码增益定义：在保持误码率恒定条件下，采用纠错编码所节省的信噪比 Eb/n0称为编码增益：
式中,(Eb/n0)u － 未编码时的信噪比 (dB)；
(Eb/n0)c － 编码后所需的信噪比 (dB)。
)(// 00 dBnEnEG cbubdB
15
10.4 奇偶监督码
10.4.1 一维奇偶监督码
奇偶监督码 － 分为奇数监督码和偶数监督码两类。
在奇偶监督码中，监督位只有 1位，故码率等于 k/(k+1)。
偶数监督码中，此监督位使码组中,1”的个数为偶数：
式中,a0为监督位，其他位为信息位。
奇数监督码中，此监督位使码组中,1”的个数为奇数：
0021 aaa nn?
1021 aaa nn?
16
检错能力 － 能够检测奇数个错码。
设：码组长度为 n，
码组中各个错码的发生是独立的和等概率的，
则在一个码组中出现 j 个错码的概率为式中，
—为在 n个码元中有 j个错码的组合数。
奇偶监督码不能检测码组中出现的偶数个错码，所以在一个码组中有错码而不能检测的概率等于,
－ 当 n为偶数时
－ 当 n为奇数时
jnjnj ppCnjP )1(),(
)!(!
!
jnj
nC n
j
2/
1
22
2 )1(
n
j
jnjn
ju ppCP
2/)1(
1
22
2 )1(
n
j
jnjn
ju ppCP
17
[例 ] 右表中的编码是偶数监督码。
设信道的误码率为 10-4，错码的出现是独立的。试计算其不能检测的误码率。
将给定条件代入式计算得出由计算结果可见，此编码可以将误码率从 10-4降低到 10-8量级。效果非常明显。
信息位 监督位晴 00 0
云 01 1
阴 10 1
雨 11 0?
2/
1
22
2 )1(
n
j
jnjn
ju ppCP
824432422
044
4
224
2
2
1
2424
2
10666126)1(6
)1()1()1(
pppppppp
ppCppCppCP
j
jj
ju
18
1 1?na 1 2?na 11a 10a
2 1?na 2 2?na 21a 20a
mna 1? mna 2? ma1 ma0
1?nc 2?nc 1c 0c
10.4.2 二维奇偶监督码
码率等于
有可能检测偶数个错码
适合检测突发错码
能够纠正部分错码
…
…
… … … … …
…
…
nm
nm
n
k
)1(
)1(
19
10.5 线性分组码
基本概念
代数码 － 利用代数关系式产生监督位的编码
线性分组码 － 代数码的一种，其监督位和信息位的关系由线性代数方程决定
汉明码 － 一种能够纠正一个错码的线性分组码
校正子：
在偶数监督码中，计算实际上就是计算并检验 S是否等于 0。
S称为校正子。
监督关系式：
0021 aaa nn?
021 aaaS nn
021 aaaS nn
20
纠错基本原理
中,S只有两种取值，故只能表示有错和无错，而不能进一步指明错码的位置。
若此码组长度增加一位，则能增加一个监督关系式。这样，
就能得到两个校正子。两个校正子的可能取值有 4种组合，
即 00,01,10,11，故能表示 4种不同的信息。若用其中一种组合表示无错码，则还有其他 3种组合可以用于指明一个错码的 3种不同位置。 从而可以有纠错能力。
一般而言，若有 r 个监督关系式，则 r 个校正子可以指明一个错码的 (2r– 1) 个不同位置。
当校正子可以指明的错码位置数目等于或大于码组长度 n
时，才能够纠正码组中任何一个位置上的错码，即要求
021 aaaS nn
1212 rkn rr 或
21
汉明码
例：要求设计一个能够纠正 1个错码的分组码 (n,k)，给定的码组中有 4个信息位，即 k = 4。
由这时要求监督位数 r? 3。若取 r = 3，则 n = k + r = 7。现在用 a6 a5 a4 a3 a2 a1 a0表示这 7个码元，用 S1 S2 S3表示校正子，则这 3个校正子恰好能够指明 23– 1 = 7个错码的位置。
若规定校正子和错码位置的关系如下表，则仅当在 a6 a5
a4 a2位置上有错码时，校正子 S1的值才等于 1；否则 S1
的值为零。这就意味着 a6 a5 a4 a2四个码元构成偶数监督关系：
同理，有
S1 S2 S3 错码位置
S1 S2 S3 错码位置
001 a0 101 a4
010 a1 110 a5
100 a2 111 a6
011 a3 000 无错码
1212 rkn rr 或
24561 aaaaS
13562 aaaaS
03463 aaaaS
22
在编码时，信息位 a6 a5 a4 a3的值决定于输入信号，它们是随机的。监督位 a2 a1 a0是按监督关系确定的，应该保证上列 3式中的校正子等于 0，即有给定信息位后，为了计算监督位，上式可以改写为按照上式计算结果为
0
0
0
0346
1356
2456
aaaa
aaaa
aaaa
3460
3561
4562
aaaa
aaaa
aaaa
信息位
a6 a5 a4
a3
监督位
a2 a1 a0
信息位
a6 a5 a4
a3
监督位
a2 a1 a0
0000 000 1000 111
0001 011 1001 100
0010 101 1010 010
0011 110 1011 001
0100 110 1100 001
0101 101 1101 010
0110 011 1110 100
0111 000 1111 111
23
在接收端解码时，对于每个接收码组，先按式计算出校正子 S1,S2和 S3，然后按照表判断错码的位置。
例：若接收码组为 0000011，则按上三式计算得到,S1
= 0,S2 = 1,S3 = 1。这样，由上表可知，错码位置在
a3。
24561 aaaaS
13562 aaaaS
03463 aaaaS
S1 S2 S3 错码位置
S1 S2 S3 错码位置
001 a0 101 a4
010 a1 110 a5
100 a2 111 a6
011 a3 000 无错码
24
上例中的汉明码是 (7,4)码，其最小码距 d0 = 3。
由式
可知，此码能够检测 2个错码，或纠正 1个错码。
汉明码的码率：
当 r (或 n)很大时，上式趋近于 1。所以汉明码是一种高效编码。
10 ed
120 td
12
12
r
r r
n
k
25
分组码的一般原理
线性分组码的监督位和信息位的关系可以改写为上式中，已经将,?”简写成,+”。
0
0
0
0346
1356
2456
aaaa
aaaa
aaaa
01001101
00101011
00010111
0123456
0123456
0123456
aaaaaaa
aaaaaaa
aaaaaaa
26
监督矩阵上式可以写成矩阵形式：
（模 2）
将上式简写为
HAT = 0T 或 AHT = 0
01001101
00101011
00010111
0123456
0123456
0123456
aaaaaaa
aaaaaaa
aaaaaaa
0
0
0
1 0 1 1 0 0 1
1 1 0 1 0 1 0
1 1 1 0 1 0 0
0
1
2
3
4
5
6
a
a
a
a
a
a
a
27
HAT = 0T
式中，
－ 称为监督矩阵
监督矩阵的性质
监督矩阵 H确定码组中的信息位和监督位的关系。
H 的行数就是监督关系式的数目，即监督位数 r 。
H 的每行中,1”的位置表示相应的码元参与监督关系。
H 可以分成两部分，例如
－典型监督矩阵式中,P 为 r? k阶矩阵,Ir为 r? r 阶单位方阵。
1 0 1 1 0 0 1
1 1 0 1 0 1 0
1 1 1 0 1 0 0
H
rPIH?
0011011
0101101
1001110
A = [a6 a5 a4 a3 a2 a1 a0]
0 = [000]
28
H 矩阵的各行应该是线性无关的，否则将得不到 r 个线性无关的监督关系式。
若一个矩阵能写成典型阵形式 [P Ir]，则其各行一定是线性无关的。
生成矩阵
例：
可以写为上式两端分别转置后，可以变成式中,Q为 k? r 阶矩阵，是 P的转置，即 Q = PT
3
4
5
6
0
1
2
1011
1101
1110
a
a
a
a
a
a
a
3460
3561
4562
aaaa
aaaa
aaaa
Q34563456012
0 1 1
1 0 1
1 1 0
1 1 1
aaaaaaaaaaa?
29
将 Q的左边加上一个 k阶单位方阵，称为生成矩阵：
－ 生成矩阵
G称为生成矩阵，因为可以用它产生整个码组 A，即有
生成矩阵的性质
具有 [IkQ]形式的生成矩阵称为 典型生成矩阵 。
由典型生成矩阵得出的码组 A中，信息位的位置不变，监督位附加于其后。这种形式的码组称为 系统码 。
矩阵 G的各行也必须是线性无关的。
如果已有 k个线性无关的码组，则可以将其用来作为生成矩阵 G，并由它生成其余码组。
0110001
1010010
1100100
1111000
QG kI
G34560123456 aaaaaaaaaaaA
30
错误图样设：发送码组 A是一个 n列的行矩阵：
接收码组是一个 n列的行矩阵 B：
令接收码组和发送码组之差为
E就是错码的行矩阵
－称为错误图样式中，
(i = 0,1,…,n-1)
若 ei = 0，表示该码元未错；若 ei = 1，表示该码元为错码。
0121 aaaaA nn
0121 bbbbB nn
B – A = E (模 2)
0121 eeeeE nn
ii
ii
i ab
abe
当当
,1
,0
31
校正子矩阵
B – A = E 可以改写成 B = A + E
上式表示发送码组 A与错码矩阵 E之和等于接收码组 B。
例如,若发送码组 A = [1 0 0 0 1 1 1]，
错码矩阵 E = [0 0 0 0 1 0 0]，
则 接收码组 B = [1 0 0 0 0 1 1]。
在接收端解码时，将接收码组 B代入式
AHT = 0
中 A的位置进行计算。若接收码组中无错码，则 B = A。代入后，该式仍成立，即有
BH T = 0
只有当错码未超出检测能力时，上式才不成立。
假设，这时该式的右端等于 S，即有
BH T = S
将 B = A + E 代入上式，得到,S = (A + E) H T = AH T + EH T
32
S = (A + E) H T = AH T + EH T
上式右端第一项等于 0，所以
S = EH T － 校正子矩阵当 H 确定后，上式中 S只与 E 有关，而与 A 无关。
这意味着,S 和错码 E 之间有确定的线性变换关系。
若 S 和 E 有一一对应关系，则 S 将能代表错码位置。
线性码的封闭性：若 A1和 A2是一种线性码中的两个码组，
则 (A1+A2)仍是其中一个码组。
『 证 』 若 A1和 A2是两个码组，则有,A1HT = 0,A2HT = 0
将上两式相加，得出
A1HT + A2HT = (A1 + A2 ) HT = 0
所以 (A1 + A2)也是一个码组。
由于线性码具有封闭性，所以两个码组 (A1和 A2)之间的距离（即对应位不同的数目）必定是另一个码组 (A1 + A2)
的重量（即,1”的数目）。因此，码的最小距离就是码的最小重量（除全,0”码组外）。
33
10.6 循环码
10.6.1 循环码的概念：
循环性是指任一码组循环一位后仍然是该编码中的一个码组。
例：一种 (7,3)循环码的全部码组如下表中第 2码组向右移一位即得到第 5码组；第 5码组向右移一位即得到第 7码组。
码组编号信息位 监督位 码组编号信息位 监督位
A6a5a4 a3a2a1a0 a6a5a4 A3a2a1a0
1 000 0000 5 100 1011
2 001 0111 6 101 1100
3 010 1110 7 110 0101
4 011 1001 8 111 0010
34
一般情况若 (an-1 an-2 … a0)是循环码的一个码组，则循环移位后的码组,(an-2 an-3 … a0 an-1)
(an-3 an-4 … an-1 an-2)
… …
(a0 an-1 … a2 a1)
仍然是该编码中的码组。
多项式表示法一个长度为 n的码组 (an-1 an-2 … a0)可以表示成上式中 x 的值没有任何意义，仅用它的幂代表码元的位置。
例：码组 1 1 0 0 1 0 1可以表示为
012211)( axaxaxaxT nnnn
1
1010011)(
256
23456
xxx
xxxxxxxT
35
10.6.2 循环码的运算
整数的按模运算在整数运算中，有模 n运算。例如，在模 2运算中，有
1 + 1 = 2? 0 (模 2),1 + 2 = 3? 1 (模 2),2? 3 = 6? 0 (模 2)
等等。
一般说来，若一个整数 m可以表示为式中,Q为整数，则在模 n运算下，有
m? p (模 n)
所以，在模 n运算下，一个整数 m等于它被 n除得的余数。
npnpQnm,
36
码多项式的按模运算若任意一个多项式 F(x)被一个 n次多项式 N(x)除，得到商式 Q(x)和一个次数小于 n的余式 R(x)，即则在按模 N(x)运算下，有这时，码多项式系数仍按模 2运算。
例 1,x3被 (x3 + 1)除，得到余项 1，即例 2：
因为
x
x3 + 1 x4 +x2 + 1
x4 + x
x2 +x +1
在模 2运算中加法和减法一样。
)()()()( xRxQxNxF
）（模 )()()( xNxRxF?
）（模 )1(1 33 xx
）（模 )1(11 3224 xxxxx
37
循环码的数学表示法在循环码中，设 T(x)是一个长度为 n的码组，若则 T?(x)也是该编码中的一个码组。
[证 ] 设一循环码为则有上式中的 T?(x) 正是码组 T (x)向左循环移位 i 次的结果。
例,一循环码为 1100101，即若给定 i = 3，则有上式对应的码组为 0101110，它正是 T(x)向左移 3位的结果。
结论：一个长为 n的循环码必定为按模 (xn + 1)运算的一个余式。
）（模 )1()()( ni xxTxTx
012211)( axaxaxaxT nnnn
)(
)(
1
10
2
2
1
1
0
1
1
1
1
2
2
1
1
xTaxaxaxaxa
xaxaxaxaxaxTx
in
i
n
in
in
n
in
iin
in
in
n
in
n
i
1)( 256 xxxxT
）（模 )1()( 723535893 xxxxxxxxxxTx
38
循环码的生成
有了生成矩阵 G，就可以由 k个信息位得出整个码组：
例：
式中，
生成矩阵 G的每一行都是一个码组。
因此，若能找到 k 个已知的码组，就能构成矩阵 G。如前所述，这 k个已知码组必须是线性不相关的。
在循环码中，一个 (n,k)码有 2k个不同的码组。若用 g(x)表示其中前 (k-1)位皆为,0”的码组，则 g(x),x g(x),x2 g(x)，
,xk-1 g(x)都是码组，而且这 k个码组是线性无关的。因此它们可以用来构成此循环码的生成矩阵 G。
G34560123456 aaaaaaaaaaaA
0110001
1010010
1100100
1111000
QG kI
39
在循环码中除全,0”码组外，再没有连续 k位均为,0”的码组。否则，在经过若干次循环移位后将得到 k位信息位全为
,0”，但监督位不全为,0”的一个码组。这在线性码中显然是不可能的。
因此,g(x)必须是一个常数项不为,0”的 (n - k)次多项式，
而且这个 g(x)还是这种 (n,k)码中次数为 (n– k)的唯一一个多项式。因为如果有两个，则由码的封闭性，把这两个相加也应该是一个码组，且此码组多项式的次数将小于 (n–
k)，即连续,0”的个数多于 (k– 1)。显然，这是与前面的结论矛盾的。
我们称这唯一的 (n– k)次多项式 g(x)为码的生成多项式。一旦确定了 g(x)，则整个 (n,k)循环码就被确定了。
40
因此，循环码的生成矩阵 G可以写成
例：
上表中的编码为 (7,3)循环码,n = 7,k = 3,n – k = 4，
其中唯一的一个 (n– k) = 4次码多项式代表的码组是第二码组 0010111，与它对应的码多项式，即生成多项式，为
g(x) = x4 + x2 + x + 1。
)(
)(
)(
)(
)(
2
1
xg
xxg
xgx
xgx
x
k
k
G
码组编号 信息位 监督位 码组编号 信息位 监督位
A6a5a4 a3a2a1a0 a6a5a4 A3a2a1a0
1 000 0000 5 100 1011
2 001 0111 6 101 1100
3 010 1110 7 110 0101
4 011 1001 8 111 0010
41
g(x) = x4 + x2 + x + 1 即,1 0 1 1 1”
将此 g(x)代入上矩阵，得到或上式不符合 G = [IkQ]形式，所以它不是典型生成矩阵。但它经过线性变换后，不难化成典型阵。
此循环码组的多项式表示式 T(x)：
上式表明，所有码多项式 T(x)都能够被 g(x)整除，而且任意一个次数不大于 (k– 1)的多项式乘 g(x)都是码多项式。
)(
)(
)(
)(
2
xg
xxg
xgx
xG
0 0 1 0 1 1 1
0 1 0 1 1 1 0
1 0 1 1 1 0 0
)( xG
)()(
)()()(
)(
)(
)(
][)(][)(
45
2
6
45
2
6
2
456456
xgaxaxa
xgaxxgaxgxa
xg
xxg
xgx
aaaxaaaxT
G
42
寻求码生成多项式因为任意一个循环码 T(x)都是 g(x)的倍式，故它可以写成
T(x) = h(x)?g(x)
而生成多项式 g(x)本身也是一个码组，即有
T?(x) = g(x)
由于码组 T?(x)是一个 (n– k)次多项式，故 xk T?(x)是一个 n次多项式。由可知,xkT?(x)在模 (xn + 1)运算下也是一个码组，所以有上式左端分子和分母都是 n次多项式，故相除的商式 Q(x) = 1。
因此，上式可以写成
）（模 )1()()( ni xxTxTx
1
)()(
1
)(
nn
k
x
xTxQ
x
xTx
)()1()( xTxxTx nk
43
将 T(x) = h(x)?g(x) 和 T?(x) = g(x) 代入化简后，得到上式表明，生成多项式 g(x)应该是 (xn + 1)的一个因子。
例,(x7 + 1)可以分解为为了求出 (7,3)循环码的生成多项式 g(x)，需要从上式中找到一个 (n – k) = 4次的因子。这样的因子有两个，即以上两式都可以作为生成多项式。
选用的生成多项式不同，产生出的循环码码组也不同。
)()1()( xTxxTx nk
)]()[(1 xhxxgx kn
)1)(1)(1(1 3237 xxxxxx
1)1)(1( 2423 xxxxxx
1)1)(1( 2343 xxxxxx
44
10.6.3 循环码的编码方法
用 xn-k乘 m(x)。这一运算实际上是在信息码后附加上 (n– k)个
,0”。例如，信息码为 110，它写成多项式为 m(x) = x2 + x。
当 n– k = 7 – 3 =4时,xn-k m(x) = x4 (x2 +x) = x6 +x5，它表示码组 1100000。
用 g(x)除 xn-k m(x)，得到商 Q(x)和余式 r(x)，即有例：若选定 g(x) = x4 + x2 + x + 1，则有上式是用码多项式表示的运算。它和下式等效：
编出的码组 T(x)为,T(x) = xn-k m(x) +r(x)
在上例中,T(x) = 1100000 + 101 = 1100101
)(
)()(
)(
)(
xg
xrxQ
xg
xmx kn
1
1)1(
1)(
)(
24
2
2
24
56
xxx
xxx
xxx
xx
xg
xmx kn
1 0 1 1 1
1 0 11 1 1
1 0 1 1 1
1 1 0 0 0 0 0
45
10.6.4 循环码的解码方法
在检错时：当接收码组没有错码时，接收码组 R(x)必定能被
g(x)整除，即下式中余项 r(x)应为零；否则，有误码。
当接收码组中的错码数量过多，超出了编码的检错能力时，有错码的接收码组也可能被 g(x)整除。这时，错码就不能检出了。
在纠错时：
用生成多项式 g(x)除接收码组 R(x)，得出余式 r(x)。
按照余式 r(x)，用查表的方法或计算方法得出错误图样
E(x)。
从 R(x)中减去 E(x)，便得到已经纠正错码的原发送码组
T(x)。
)(/)()()(/)( xgxrxQxgxR
)(/)()()(/)( xgxrxQxgxR
46
10.6.5 截短循环码
截短目的：
在设计时，通常信息位数 k、码长 n和纠错能力都是预先给定的。但是，并不一定有恰好满足这些条件的循环码存在。
故采用截短码长截短，得出满足要求的编码。
截短方法：
设给定一个 (n,k)循环码，它共有 2k种码组，现使其前 i (0
< i < k)个信息位全为,0”，于是它变成仅有 2k-i种码组。然后从中删去这 i 位全,0”的信息位，最终得到一个 (n – i,k
– i)的线性码。将这种码称为截短循环码。
截短循环码与截短前的循环码至少具有相同的纠错能力，并且截短循环码的编解码方法仍和截短前的方法一样。
例：要求构造一个能够纠正 1位错码的 (13,9)码。
这时可以由 (15,11)循环码的 11种码组中选出前两信息位均为,0”的码组，构成一个新的码组集合。然后在发送时不发送这两位,0”。于是发送码组成为 (13,9)截短循环码。
47
10.6.6 BCH码
BCH码是能够纠正多个随机错码的循环码。
BCH码分为两类：本原 BCH码和非本原 BCH码。
本原 BCH码：码长 n = 2m – 1 (m? 3，任意正整数 )，它的生成多项式 g(x)中含有最高次数为 m次的本原多项式；
非本原 BCH码：码长 n是 (2m– 1)的一个因子，它的生成多项式 g(x)中不含有最高次数为 m的本原多项式。
BCH码的工程设计：可以用查表法找到所需的生成多项式。
例：二进制非本原 BCH码的生成多项式系数表中 g(x)是用 8进制数字表示的； t 为纠错能力。
n k t g(x) n k t g(x)
17
21
23
33
41
9
12
12
22
21
2
2
3
2
4
727
1663
5343
5145
6647133
47
65
65
73
24
53
40
46
5
2
4
4
43073357
10761
354300067
1717773537
48
常用 BCH码：
戈莱 (Golay)码,(23,12)非本原 BCH码，它能纠正 3个随机错码，并且容易解码 。
扩展 BCH码 (n + 1,k),
BCH码的长度为奇数。在应用中，为了得到偶数长度的码，并增大检错能力，可以在 BCH码生成多项式中乘上一个因式 (x + 1)，从而得到扩展 BCH码 (n + 1,k)。
扩展 BCH码已经不再具有循环性。
扩展戈莱码 (24,12)：其最小码距为 8，码率为 1/2，能够纠正 3个错码和检测 4个错码。
49
几种二进制分组码的性能比较
2PSK
汉明码 (7,4)
t=1
汉明码 (31,26) t=1
扩展戈莱码 (24,12)
t=3
BCH 码 (127,64)
t=10
Eb / n0 (dB)
Pe
50
10.6.7 RS码
RS码：是 q进制 BCH码的一个特殊子类，并且具有很强的纠错能力。
RS码的参数：码长 n = q – 1，监督位数目 r = 2t，其中 t是能够纠正的错码数目；其生成多项式为
g(x) = (x +?)(x +?2) … ( x +?2t)
式中,?为伽罗华域 GF(2m)中的本原元。
RS码的主要优点：
它是多进制纠错编码，所以特别适合用于多进制调制的场合；
它能够纠正 t个 q位二进制错码，即能够纠正不超过 q个连续的二进制错码，所以适合在衰落信道中纠正突发性错码。
51
10.7 卷积码
卷积码的特点：
监督码元不仅和当前的 k比特信息段有关，而且还同前面 m
= (N – 1)个信息段有关。
将 N称为码组的约束度。
将卷积码记作 (n,k,m)，其码率为 k/n。
52
卷积码的编码
一般原理方框图编码输出每次输入
k比特 1 k… 1 k… 1 k… 1 k…… … …
1 … k … 2k 3k Nk… … … … …
… … … …1 2 n
Nk级移存器
n个模 2
加法器每输入 k比特旋转 1周
53
卷积码编码器的实例方框图,(n,k,m) =（ 3,1,2）
每当输入 1比特时，此编码器输出 3比特 c1c2 c3：
编码器的工作状态
1 2 3
b3b1输入 b2
编码输出c2
c1
c3
3213
312
11
bbbc
bbc
bc
b1 1 1 0 1 0 0 0
b3b2 00 01 11 10 01 10 00
c1c2
c3
111 110 010 100 001 011 000
状态 a b d c b c a
54
10.7.2 卷积码的解码
码树搜索法,(3,1,2)卷积码的码树图此法不实用：因为随信息位增多，分支数目按指数规律增长
000
111
001
110
011
100
010
101
000
111
001
110
011
100
010
101
c1c2c3000
100
111
011
001
101
110
010
c1c2c3
111
000
001
110
c1c2c3
信息位 1 1 0 1
b
a
起点信息位
000
111
c1c2c3
a
b
c
da
b
c
da
b
c
da
b
c
d
上半部下半部
1
0
a
状态 b3b2
a 0 0
b 0 1
c 1 0
d 1 1
a
b
c
d
a
b
c
d
c
d
a
b↑0
↓1
↓1
↑0
↑0
↓1
55
状态图和网格图
移存器状态和输入输出码元的关系
状态图前一状态
b3 b2
当前输入
b1
输出
c1c2c3
下一状态
b3 b2
a (00) 0
1
000
111
a (00)
b (01)
b (01) 0
1
001
110
c (10)
d (11)
c (10) 0
1
011
100
a (00)
b (01)
d (11) 0
1
010
101
c (10)
d (11)
3213
312
11
bbbc
bbc
bc
1 2 3
b3b1输入 b2
编码输出c2
c1
c3
a
b
c
d
000 111 101110
010011
100 001
56
(3,1,2)卷积码网格图
网格图中的编码路径举例
输入信息位为 1101时
输出编码序列是：
111 110 010 100 011…
110 110 110 110
011 011 011
010 010 010
101 101 101
001 001 001 001
a
b
c
d
a
b
c
d
000 000 000 000 000
111 111 111 111 111
100100100
a
b
c
d
000 111 101110
010011
100 001
a
b
c
d
a
b
c
d
110 010
001
111
100
57
维特比算法
基本原理：将接收到的序列和所有可能的发送序列作比较，
选择其中汉明距离最小的序列当作是现在的发送序列
例：设卷积码为 (n,k,m) = (3,1,2)码
现在的发送信息位为 1101
为了使移存器中的信息位全部移出，在信息位后面加入了 3个,0”，即 1101000
编码后的发送序列,111 110 010 100 001 011 000
接收序列,111 010 010 110 001 011 000 (红色为错码 )
由于这是一个 (3,1,2)卷积码，发送序列的约束度为 N = m
+ 1 ＝ 3，所以首先需考察 3个信息段，即考察 3n ＝ 9比特，
即接收序列前 9位,111 010 010”。
58
解码第 1步
由网格图可见，沿路径每一级有 4种状态 a,b,c和 d。每种状态只有两条路径可以到达。故 4种状态共有 8条到达路径。
比较网格图中的这 8条路径和接收序列之间的汉明距离。
例如，由出发点状态 a经过 3级路径后到达状态 a的两条路径中上面一条为,000 000 000”。它和接收序列,111
010 010”的汉明距离等于 5；下面一条为,111 001 011”,
它和接收序列的汉明距离等于 3。
110 110 110 110
011 011 011
010 010 010
101 101 101
001 001 001 001
a
b
c
d
a
b
c
d
000 000 000 000 000
111 111 111 111 111
100100100
59
将这 8个比较结果列表如下：
比较到达每个状态的两条路径的汉明距离，将距离小的一条路径保留，称为幸存路径。这样，就剩下 4条路径了，即表中第 2,4,6和 8条路径。
序号路径 对应序列 汉明距离 幸存否？
1 aaaa 000 000 000 5 否
2 abca 111 001 011 3 是
3 aaab 000 000 111 6 否
4 abcb 111 001 100 4 是
5 aabc 000 111 001 7 否
6 abdc 111 110 010 1 是
7 aabd 000 111 110 6 否
8 abdd 111 110 101 4 是
60
解码第 2步：继续考察接收序列中的后继 3个比特,110”
计算 4条幸存路径上增加 1级后的 8条可能路径的汉明距离。计算结果列于下表中。
表中总距离最小为 2，其路径是 abdc+b，相应序列为
111 110 010 100。它和发送序列相同，故对应发送信息位 1101。
序号 路径 原幸存路径的距离新增路径段新增距离 总距离 幸存否？
1 abca+a 3 aa 2 5 否
2 abdc+a 1 ca 2 3 是
3 abca+b 3 ab 1 4 否
4 abdc+b 1 cb 1 2 是
5 abcb+c 4 bc 3 7 否
6 abdd+c 4 dc 1 5 是
7 abcb+d 4 bd 0 4 是
8 abdd+d 4 dd 2 6 否
61
按照上表中的幸存路径画出的网格图示于下图中。
图中粗线路径是距汉明离最小（等于 2）的路径。
a
b
c
d
011
010 010
101
001
a
b
c
d
111
100100
110
110
62
在编码时，信息位后面加了 3个,0”。若把这 3个,0”仍然看作是信息位，则可以按照上述算法继续解码。这样得到的幸存路径网格图示于下图中。图中的粗线仍然是汉明距离最小的路径。
110
011
010 010
101 101
001 001
a
b
c
d
a
b
c
d
000
111
100100
000
011 011
001
101
63
若已知这 3个码元是（为结尾而补充的）,0”，则在解码时就预先知道在接收这 3个,0”码元后，路径必然应该回到状态 a。而由图可见，
只有两条路径可以回到 a状态。所以，这时上图可以简化成：
110
011
010 010
101 101
001 001
a
b
c
d
a
b
c
d
000
111
100100
000
011 011
001
110
011
010 010
101 101
001 001
a
b
c
d
a
b
c
d
000
111
100100
000
011 011
001
101
64
在上例中卷积码的约束度为 N = 3，需要存储和计算 8条路径的参量。
由此可见，维特比算法的复杂度随约束度 N按指数形式 2N
增长。故维特比算法适合约束度较小（ N? 10）的编码。
对于约束度大的卷积码，可以采用其他解码算法，
65
10.8 Turbo码和 LDPC码
Turbo码基本原理：
复合编码：将两种或多种简单的编码组合成复合编码。
链接码：链接码是复合编码的一种，它包括一个内（部）
码和一个外（部）码，如下图所示：
内码是二进制分组码或卷积码，而典型的外码则是多进制的 RS码。
Turbo码：是一种特殊的链接码。它在两个并联或串联的编码器之间增加一个交织器，使之具有很大的码组长度和在低信噪比条件下得到接近理想的性能。
内编码器
(n,k)
调制器信道解制器内解码器
(n,k)
外解码器
(N,K)
外编码器
(N,K)输入输出
66
Turbo码的基本结构
编码器：由一对递归系统卷积码（ RSCC） 编码器和一个交织器组成。
输入信息位是 bi，
输出是 bic1ic2i，
故码率等于 1/3。
RSCC编码器：和前面讨论的卷积码编码器之间的主要区别是从移存器输出到信息位输入端之间有反馈路径：
上图为码率等于 1/2的 RSCC编码器
RSCC
交织器 RSCC
bi
bi
c1i
c2i
D Dbi
bi
ci
67
交织器：基本形式是矩阵交织器。
交织目的：将集中出现的突发错码分散，变成随机错码
交织原理：
交织器由容量为 (n-1)m比特的存储器构成。
码元按行的方向输入存储器，再按列的方向输出。
a11 a12 a1m
a21 a22 a2m
an1 an2 anm
68
卷积交织器举例
x
x
x 12
3
4
x
x x
1
2
3
4
x x x 1
x
x x
1 x x x x x x
(a) 第 1~4比特输入时的状态
x
x
2 56
7
8
3
4 x
5
6
7
8
x x 2 5
x
2 x
5 1 x x x x x
(b) 第 5~8比特输入时的状态
x
3
6 9
3
6 2
9 5 1 x x x x9 10
11
12
10
11
12
7
8 4
x 3 6 9
(c) 第 9~12比特输入时的状态
10
13
7
6
9 5 4 3 2 114
15
16
11
12 8
1314
15
16
4
7
1013
4 7 10 13
(d) 第 13~16比特输入时的状态交织器 解交织器
69
卷积交织法优点：
延迟时间短和需要的存储容量小。
端到端的总延迟时间和两端所需的总存储容量均为
k(N+1)N个码元，是矩阵交织法的一半。
Turbo码的性能：
由此曲线可以看到，
交织器容量大时误码率低，这是因为交织范围大可以使交织器输入码元得到更好的随机化。
信噪比 (dB)
20
解码后的误码率交织器容量 100
10-1
10-2
10-3
10-4
10-5
10-6
10-7
70
LDPC码
LDPC码的全称：低密度奇偶校验 (Low-Density Parity-
Check)码。
LDPC码的特点：
是线性分组码；
它和 Turbo码都是复合码，两者的性能也接近；
两者的解码延迟时间都相当长；
比 Turbo码的解码简单，更容易实现。
71
LDPC码的基本原理：
LDPC码和普通的奇偶监督码一样，可以由 n列 m行的奇偶监督矩阵 H确定。 n是码长,m是校正子个数。
LDPC码的 H矩阵和普通奇偶监督码的 H矩阵不同：
首先，它是一个稀疏矩阵，即其中,1”的个数很少，
或者说密度很低。设 H矩阵每列有 j个,1”，每行有
k个,1”，则应有 j << m,k << n，且 j? 3。
其次,LDPC码的 H矩阵的任意两行的元素不能在相同位置上为,1”，即 H矩阵中没有四角由,1”构成的矩形。
在编码时设计好 H矩阵后，由 H矩阵可以导出生成矩阵 G。这样，对于给定的信息位不难算出码组。
72
LDPC码的解码方法：
和一般的奇偶监督码的解码方法不同。基本的解码算法称为置信传播算法 (Belief Propagation Algorithm)，通常简称 BP算法。这种算法实质上是求最大后验概率，但是需要进行多次迭代运算，逐步逼近最优的解码值。
73
10.9 小结
第十章 信道编码和差错控制
10.1概述
信道编码：
目的：提高信号传输的可靠性。
方法：增加多余比特，以发现或纠正错误。
差错控制：包括信道编码在内的一切纠正错误手段。
产生错码的原因：
乘性干扰引起的码间串扰
加性干扰引起的信噪比降低
信道分类：按照加性干扰造成错码的统计特性不同划分
随机信道：错码随机出现，例如由白噪声引起的错码
突发信道：错码相对集中出现，例如由脉冲干扰引起的错码。
混合信道
2
差错控制技术的种类：
检错重发：
能发现错码，但是不能确定错码的位置。
通信系统需要有双向信道。
前向纠错 (FEC)：利用加入的差错控制码元，不但能够发现错码，还能纠正错码。
反馈校验：
将收到的码元转发回发送端，将它和原发送码元比较。
缺点：需要双向信道，传输效率也较低。
检错删除：
在接收端发现错码后，立即将其删除。
适用在发送码元中有大量多余度，删除部分接收码元不影响应用之处。
3
编码序列的参数
n － 编码序列中总码元数量
k － 编码序列中信息码元数量
r － 编码序列中差错控制码元数量
（差错控制码元，以后称为监督码元或监督位 ）
k/n － 码率
(n - k) / k = r / k － 冗余度
4
自动要求重发 (ARQ)系统
停止等待 ARQ系统
拉后 ARQ系统停止等待 ARQ系统接收数据
ACK ACK NAK ACK ACK NAK ACK
1 2 3 3 4 5 5
t
发送数据
1 2 3 3 4 5 5 6
t
有错码组 有错码组拉后 ARQ系统
21 43 65 7 98接收数据有错码组 有错码组
910 11 10 11 125 76
ACK1 NAK5 NAK9ACK5
5 76 9521 43 6 7 98发送数据 10 11 10 11 12
重发码组 重发码组
5
选择重发 ARQ系统
ARQ和前向纠错比较：
优点
监督码元较少，即码率较高
检错的计算复杂度较低
能适应不同特性的信道
缺点
需要双向信道。
不适用于一点到多点的通信系统或广播系统。
传输效率降低，可能因反复重发而造成事实上的通信中断。
选择重发 ARQ系统
9接收数据有错码组 有错码组
21 43 65 7 5 98 10 11 13 1412
发送数据 9 95 8521 43 6 7 10 11 13 1412
重发码组 重发码组
NAK9ACK1 NAK5 ACK5 ACK9
6
10.2 纠错编码的基本原理
分组码举例
设：有一种由 3个二进制码元构成的编码，它共有 23 = 8种不同的可能码组：
000 – 晴 001 – 云 010 – 阴 011 – 雨
100 – 雪 101 – 霜 110 – 雾 111 – 雹这时，若一个码组中发生错码，则将收到错误信息。
若在此 8种码组中仅允许使用 4种来传送天气，例如：令
000 – 晴 011 – 云 101 – 阴 110 – 雨为 许用码组,其他 4种不允许使用，称为 禁用码组 。
这时，接收端有可能发现（检测到）码组中的一个错码。
这种编码只能检测错码，不能纠正错码。
若规定只许用两个码组：例如
000 – 晴 111 – 雨就能检测两个以下错码，或纠正一个错码。
7
分组码概念
分组码 ＝ 信息位 ＋ 监督位
分组码符号,(n,k)
其中,n － 码组总长度，
k － 信息码元数目。
r = n – k － 监督码元数目。
右表中的码组为 (3,2)码。
分组码的一般结构：
分组码的参数：
码重：码组内,1”的个数
码距：两码组中对应位取值不同的位数，又称汉明距离
最小码距 (d0),各码组间的最小距离信息位 监督位晴 00 0
云 01 1
阴 10 1
雨 11 0
k个信息位 r个监督位
an-1 an-2,.,ar ar-1 an-2,.,a0 t
码长 n = k + r
分组码的结构
8
码距的几何意义：以 n = 3的编码为例
一般而言，码距是 n 维空间中单位正多面体顶点之间的汉明距离。
(0,0,0)
(0,0,1) (1,0,1)
(1,0,0)
(1,1,0)(0,1,0)
(0,1,1) (1,1,1)
a2
a0
a1
9
一种编码的纠检错能力：决定于最小码距 d0的值。
为了能检测 e个错码，要求最小码距
为了能纠正 t 个错码，要求最小码距
10 ed
0 1 2 3
BA 汉明距离e
d0
码距等于 3的两个码组
120 td
B tA 汉明距离
0 1 2 3 4 5t
d0
码距等于 5的两个码组
10
为了能纠正 t个错码，同时检测 e个错码，要求最小码距纠检结合工作方式：
当错码数量少时，系统按前向纠错方式工作，以节省重发时间，提高传输效率；
当错码数量多时，系统按反馈重发的纠错方式工作，
以降低系统的总误码率。
A B
1
tt 汉明距离
e
码距等于 (e+t+1)的两个码组
)(10 teted
11
10.3 纠错编码系统的性能
10.3.1 误码率性能和带宽的关系采用编码降低误码率所付出的代价是带宽的增大。
10-6
10-5
10-4
10-3
10-2
10-1
编码后
Eb/n0 (dB)
编码和误码率关系
Pe
C
D
E
A?
B
2PSK
12
10.3.2 功率和带宽的关系采用编码以节省功率，并保持误码率不变，付出的代价也是带宽增大。
10-6
10-5
10-4
10-3
10-2
10-1
编码后
Eb/n0 (dB)
编码和误码率关系
Pe
C
D
E
A?
B
2PSK
13
10.3.3 传输速率和带宽的关系对于给定的传输系统，其传输速率和 Eb/n0的关系：
式中,RB － 码元速率。
提高传输速率，采用编码以保持误码率不变；付出的代价仍是带宽增大。
B
sssb
Rn
P
Tn
P
n
TP
n
E
0000 )/1(
10-6
10-5
10-4
10-3
10-2
10-1
编码后
Eb/n0 (dB)
编码和误码率关系
Pe
C
D
E
A?
B
2PSK
14
10.3.4 编码增益定义：在保持误码率恒定条件下，采用纠错编码所节省的信噪比 Eb/n0称为编码增益：
式中,(Eb/n0)u － 未编码时的信噪比 (dB)；
(Eb/n0)c － 编码后所需的信噪比 (dB)。
)(// 00 dBnEnEG cbubdB
15
10.4 奇偶监督码
10.4.1 一维奇偶监督码
奇偶监督码 － 分为奇数监督码和偶数监督码两类。
在奇偶监督码中，监督位只有 1位，故码率等于 k/(k+1)。
偶数监督码中，此监督位使码组中,1”的个数为偶数：
式中,a0为监督位，其他位为信息位。
奇数监督码中，此监督位使码组中,1”的个数为奇数：
0021 aaa nn?
1021 aaa nn?
16
检错能力 － 能够检测奇数个错码。
设：码组长度为 n，
码组中各个错码的发生是独立的和等概率的，
则在一个码组中出现 j 个错码的概率为式中，
—为在 n个码元中有 j个错码的组合数。
奇偶监督码不能检测码组中出现的偶数个错码，所以在一个码组中有错码而不能检测的概率等于,
－ 当 n为偶数时
－ 当 n为奇数时
jnjnj ppCnjP )1(),(
)!(!
!
jnj
nC n
j
2/
1
22
2 )1(
n
j
jnjn
ju ppCP
2/)1(
1
22
2 )1(
n
j
jnjn
ju ppCP
17
[例 ] 右表中的编码是偶数监督码。
设信道的误码率为 10-4，错码的出现是独立的。试计算其不能检测的误码率。
将给定条件代入式计算得出由计算结果可见，此编码可以将误码率从 10-4降低到 10-8量级。效果非常明显。
信息位 监督位晴 00 0
云 01 1
阴 10 1
雨 11 0?
2/
1
22
2 )1(
n
j
jnjn
ju ppCP
824432422
044
4
224
2
2
1
2424
2
10666126)1(6
)1()1()1(
pppppppp
ppCppCppCP
j
jj
ju
18
1 1?na 1 2?na 11a 10a
2 1?na 2 2?na 21a 20a
mna 1? mna 2? ma1 ma0
1?nc 2?nc 1c 0c
10.4.2 二维奇偶监督码
码率等于
有可能检测偶数个错码
适合检测突发错码
能够纠正部分错码
…
…
… … … … …
…
…
nm
nm
n
k
)1(
)1(
19
10.5 线性分组码
基本概念
代数码 － 利用代数关系式产生监督位的编码
线性分组码 － 代数码的一种，其监督位和信息位的关系由线性代数方程决定
汉明码 － 一种能够纠正一个错码的线性分组码
校正子：
在偶数监督码中，计算实际上就是计算并检验 S是否等于 0。
S称为校正子。
监督关系式：
0021 aaa nn?
021 aaaS nn
021 aaaS nn
20
纠错基本原理
中,S只有两种取值，故只能表示有错和无错，而不能进一步指明错码的位置。
若此码组长度增加一位，则能增加一个监督关系式。这样，
就能得到两个校正子。两个校正子的可能取值有 4种组合，
即 00,01,10,11，故能表示 4种不同的信息。若用其中一种组合表示无错码，则还有其他 3种组合可以用于指明一个错码的 3种不同位置。 从而可以有纠错能力。
一般而言，若有 r 个监督关系式，则 r 个校正子可以指明一个错码的 (2r– 1) 个不同位置。
当校正子可以指明的错码位置数目等于或大于码组长度 n
时，才能够纠正码组中任何一个位置上的错码，即要求
021 aaaS nn
1212 rkn rr 或
21
汉明码
例：要求设计一个能够纠正 1个错码的分组码 (n,k)，给定的码组中有 4个信息位，即 k = 4。
由这时要求监督位数 r? 3。若取 r = 3，则 n = k + r = 7。现在用 a6 a5 a4 a3 a2 a1 a0表示这 7个码元，用 S1 S2 S3表示校正子，则这 3个校正子恰好能够指明 23– 1 = 7个错码的位置。
若规定校正子和错码位置的关系如下表，则仅当在 a6 a5
a4 a2位置上有错码时，校正子 S1的值才等于 1；否则 S1
的值为零。这就意味着 a6 a5 a4 a2四个码元构成偶数监督关系：
同理，有
S1 S2 S3 错码位置
S1 S2 S3 错码位置
001 a0 101 a4
010 a1 110 a5
100 a2 111 a6
011 a3 000 无错码
1212 rkn rr 或
24561 aaaaS
13562 aaaaS
03463 aaaaS
22
在编码时，信息位 a6 a5 a4 a3的值决定于输入信号，它们是随机的。监督位 a2 a1 a0是按监督关系确定的，应该保证上列 3式中的校正子等于 0，即有给定信息位后，为了计算监督位，上式可以改写为按照上式计算结果为
0
0
0
0346
1356
2456
aaaa
aaaa
aaaa
3460
3561
4562
aaaa
aaaa
aaaa
信息位
a6 a5 a4
a3
监督位
a2 a1 a0
信息位
a6 a5 a4
a3
监督位
a2 a1 a0
0000 000 1000 111
0001 011 1001 100
0010 101 1010 010
0011 110 1011 001
0100 110 1100 001
0101 101 1101 010
0110 011 1110 100
0111 000 1111 111
23
在接收端解码时，对于每个接收码组，先按式计算出校正子 S1,S2和 S3，然后按照表判断错码的位置。
例：若接收码组为 0000011，则按上三式计算得到,S1
= 0,S2 = 1,S3 = 1。这样，由上表可知，错码位置在
a3。
24561 aaaaS
13562 aaaaS
03463 aaaaS
S1 S2 S3 错码位置
S1 S2 S3 错码位置
001 a0 101 a4
010 a1 110 a5
100 a2 111 a6
011 a3 000 无错码
24
上例中的汉明码是 (7,4)码，其最小码距 d0 = 3。
由式
可知，此码能够检测 2个错码，或纠正 1个错码。
汉明码的码率：
当 r (或 n)很大时，上式趋近于 1。所以汉明码是一种高效编码。
10 ed
120 td
12
12
r
r r
n
k
25
分组码的一般原理
线性分组码的监督位和信息位的关系可以改写为上式中，已经将,?”简写成,+”。
0
0
0
0346
1356
2456
aaaa
aaaa
aaaa
01001101
00101011
00010111
0123456
0123456
0123456
aaaaaaa
aaaaaaa
aaaaaaa
26
监督矩阵上式可以写成矩阵形式：
（模 2）
将上式简写为
HAT = 0T 或 AHT = 0
01001101
00101011
00010111
0123456
0123456
0123456
aaaaaaa
aaaaaaa
aaaaaaa
0
0
0
1 0 1 1 0 0 1
1 1 0 1 0 1 0
1 1 1 0 1 0 0
0
1
2
3
4
5
6
a
a
a
a
a
a
a
27
HAT = 0T
式中，
－ 称为监督矩阵
监督矩阵的性质
监督矩阵 H确定码组中的信息位和监督位的关系。
H 的行数就是监督关系式的数目，即监督位数 r 。
H 的每行中,1”的位置表示相应的码元参与监督关系。
H 可以分成两部分，例如
－典型监督矩阵式中,P 为 r? k阶矩阵,Ir为 r? r 阶单位方阵。
1 0 1 1 0 0 1
1 1 0 1 0 1 0
1 1 1 0 1 0 0
H
rPIH?
0011011
0101101
1001110
A = [a6 a5 a4 a3 a2 a1 a0]
0 = [000]
28
H 矩阵的各行应该是线性无关的，否则将得不到 r 个线性无关的监督关系式。
若一个矩阵能写成典型阵形式 [P Ir]，则其各行一定是线性无关的。
生成矩阵
例：
可以写为上式两端分别转置后，可以变成式中,Q为 k? r 阶矩阵，是 P的转置，即 Q = PT
3
4
5
6
0
1
2
1011
1101
1110
a
a
a
a
a
a
a
3460
3561
4562
aaaa
aaaa
aaaa
Q34563456012
0 1 1
1 0 1
1 1 0
1 1 1
aaaaaaaaaaa?
29
将 Q的左边加上一个 k阶单位方阵，称为生成矩阵：
－ 生成矩阵
G称为生成矩阵，因为可以用它产生整个码组 A，即有
生成矩阵的性质
具有 [IkQ]形式的生成矩阵称为 典型生成矩阵 。
由典型生成矩阵得出的码组 A中，信息位的位置不变，监督位附加于其后。这种形式的码组称为 系统码 。
矩阵 G的各行也必须是线性无关的。
如果已有 k个线性无关的码组，则可以将其用来作为生成矩阵 G，并由它生成其余码组。
0110001
1010010
1100100
1111000
QG kI
G34560123456 aaaaaaaaaaaA
30
错误图样设：发送码组 A是一个 n列的行矩阵：
接收码组是一个 n列的行矩阵 B：
令接收码组和发送码组之差为
E就是错码的行矩阵
－称为错误图样式中，
(i = 0,1,…,n-1)
若 ei = 0，表示该码元未错；若 ei = 1，表示该码元为错码。
0121 aaaaA nn
0121 bbbbB nn
B – A = E (模 2)
0121 eeeeE nn
ii
ii
i ab
abe
当当
,1
,0
31
校正子矩阵
B – A = E 可以改写成 B = A + E
上式表示发送码组 A与错码矩阵 E之和等于接收码组 B。
例如,若发送码组 A = [1 0 0 0 1 1 1]，
错码矩阵 E = [0 0 0 0 1 0 0]，
则 接收码组 B = [1 0 0 0 0 1 1]。
在接收端解码时，将接收码组 B代入式
AHT = 0
中 A的位置进行计算。若接收码组中无错码，则 B = A。代入后，该式仍成立，即有
BH T = 0
只有当错码未超出检测能力时，上式才不成立。
假设，这时该式的右端等于 S，即有
BH T = S
将 B = A + E 代入上式，得到,S = (A + E) H T = AH T + EH T
32
S = (A + E) H T = AH T + EH T
上式右端第一项等于 0，所以
S = EH T － 校正子矩阵当 H 确定后，上式中 S只与 E 有关，而与 A 无关。
这意味着,S 和错码 E 之间有确定的线性变换关系。
若 S 和 E 有一一对应关系，则 S 将能代表错码位置。
线性码的封闭性：若 A1和 A2是一种线性码中的两个码组，
则 (A1+A2)仍是其中一个码组。
『 证 』 若 A1和 A2是两个码组，则有,A1HT = 0,A2HT = 0
将上两式相加，得出
A1HT + A2HT = (A1 + A2 ) HT = 0
所以 (A1 + A2)也是一个码组。
由于线性码具有封闭性，所以两个码组 (A1和 A2)之间的距离（即对应位不同的数目）必定是另一个码组 (A1 + A2)
的重量（即,1”的数目）。因此，码的最小距离就是码的最小重量（除全,0”码组外）。
33
10.6 循环码
10.6.1 循环码的概念：
循环性是指任一码组循环一位后仍然是该编码中的一个码组。
例：一种 (7,3)循环码的全部码组如下表中第 2码组向右移一位即得到第 5码组；第 5码组向右移一位即得到第 7码组。
码组编号信息位 监督位 码组编号信息位 监督位
A6a5a4 a3a2a1a0 a6a5a4 A3a2a1a0
1 000 0000 5 100 1011
2 001 0111 6 101 1100
3 010 1110 7 110 0101
4 011 1001 8 111 0010
34
一般情况若 (an-1 an-2 … a0)是循环码的一个码组，则循环移位后的码组,(an-2 an-3 … a0 an-1)
(an-3 an-4 … an-1 an-2)
… …
(a0 an-1 … a2 a1)
仍然是该编码中的码组。
多项式表示法一个长度为 n的码组 (an-1 an-2 … a0)可以表示成上式中 x 的值没有任何意义，仅用它的幂代表码元的位置。
例：码组 1 1 0 0 1 0 1可以表示为
012211)( axaxaxaxT nnnn
1
1010011)(
256
23456
xxx
xxxxxxxT
35
10.6.2 循环码的运算
整数的按模运算在整数运算中，有模 n运算。例如，在模 2运算中，有
1 + 1 = 2? 0 (模 2),1 + 2 = 3? 1 (模 2),2? 3 = 6? 0 (模 2)
等等。
一般说来，若一个整数 m可以表示为式中,Q为整数，则在模 n运算下，有
m? p (模 n)
所以，在模 n运算下，一个整数 m等于它被 n除得的余数。
npnpQnm,
36
码多项式的按模运算若任意一个多项式 F(x)被一个 n次多项式 N(x)除，得到商式 Q(x)和一个次数小于 n的余式 R(x)，即则在按模 N(x)运算下，有这时，码多项式系数仍按模 2运算。
例 1,x3被 (x3 + 1)除，得到余项 1，即例 2：
因为
x
x3 + 1 x4 +x2 + 1
x4 + x
x2 +x +1
在模 2运算中加法和减法一样。
)()()()( xRxQxNxF
）（模 )()()( xNxRxF?
）（模 )1(1 33 xx
）（模 )1(11 3224 xxxxx
37
循环码的数学表示法在循环码中，设 T(x)是一个长度为 n的码组，若则 T?(x)也是该编码中的一个码组。
[证 ] 设一循环码为则有上式中的 T?(x) 正是码组 T (x)向左循环移位 i 次的结果。
例,一循环码为 1100101，即若给定 i = 3，则有上式对应的码组为 0101110，它正是 T(x)向左移 3位的结果。
结论：一个长为 n的循环码必定为按模 (xn + 1)运算的一个余式。
）（模 )1()()( ni xxTxTx
012211)( axaxaxaxT nnnn
)(
)(
1
10
2
2
1
1
0
1
1
1
1
2
2
1
1
xTaxaxaxaxa
xaxaxaxaxaxTx
in
i
n
in
in
n
in
iin
in
in
n
in
n
i
1)( 256 xxxxT
）（模 )1()( 723535893 xxxxxxxxxxTx
38
循环码的生成
有了生成矩阵 G，就可以由 k个信息位得出整个码组：
例：
式中，
生成矩阵 G的每一行都是一个码组。
因此，若能找到 k 个已知的码组，就能构成矩阵 G。如前所述，这 k个已知码组必须是线性不相关的。
在循环码中，一个 (n,k)码有 2k个不同的码组。若用 g(x)表示其中前 (k-1)位皆为,0”的码组，则 g(x),x g(x),x2 g(x)，
,xk-1 g(x)都是码组，而且这 k个码组是线性无关的。因此它们可以用来构成此循环码的生成矩阵 G。
G34560123456 aaaaaaaaaaaA
0110001
1010010
1100100
1111000
QG kI
39
在循环码中除全,0”码组外，再没有连续 k位均为,0”的码组。否则，在经过若干次循环移位后将得到 k位信息位全为
,0”，但监督位不全为,0”的一个码组。这在线性码中显然是不可能的。
因此,g(x)必须是一个常数项不为,0”的 (n - k)次多项式，
而且这个 g(x)还是这种 (n,k)码中次数为 (n– k)的唯一一个多项式。因为如果有两个，则由码的封闭性，把这两个相加也应该是一个码组，且此码组多项式的次数将小于 (n–
k)，即连续,0”的个数多于 (k– 1)。显然，这是与前面的结论矛盾的。
我们称这唯一的 (n– k)次多项式 g(x)为码的生成多项式。一旦确定了 g(x)，则整个 (n,k)循环码就被确定了。
40
因此，循环码的生成矩阵 G可以写成
例：
上表中的编码为 (7,3)循环码,n = 7,k = 3,n – k = 4，
其中唯一的一个 (n– k) = 4次码多项式代表的码组是第二码组 0010111，与它对应的码多项式，即生成多项式，为
g(x) = x4 + x2 + x + 1。
)(
)(
)(
)(
)(
2
1
xg
xxg
xgx
xgx
x
k
k
G
码组编号 信息位 监督位 码组编号 信息位 监督位
A6a5a4 a3a2a1a0 a6a5a4 A3a2a1a0
1 000 0000 5 100 1011
2 001 0111 6 101 1100
3 010 1110 7 110 0101
4 011 1001 8 111 0010
41
g(x) = x4 + x2 + x + 1 即,1 0 1 1 1”
将此 g(x)代入上矩阵，得到或上式不符合 G = [IkQ]形式，所以它不是典型生成矩阵。但它经过线性变换后，不难化成典型阵。
此循环码组的多项式表示式 T(x)：
上式表明，所有码多项式 T(x)都能够被 g(x)整除，而且任意一个次数不大于 (k– 1)的多项式乘 g(x)都是码多项式。
)(
)(
)(
)(
2
xg
xxg
xgx
xG
0 0 1 0 1 1 1
0 1 0 1 1 1 0
1 0 1 1 1 0 0
)( xG
)()(
)()()(
)(
)(
)(
][)(][)(
45
2
6
45
2
6
2
456456
xgaxaxa
xgaxxgaxgxa
xg
xxg
xgx
aaaxaaaxT
G
42
寻求码生成多项式因为任意一个循环码 T(x)都是 g(x)的倍式，故它可以写成
T(x) = h(x)?g(x)
而生成多项式 g(x)本身也是一个码组，即有
T?(x) = g(x)
由于码组 T?(x)是一个 (n– k)次多项式，故 xk T?(x)是一个 n次多项式。由可知,xkT?(x)在模 (xn + 1)运算下也是一个码组，所以有上式左端分子和分母都是 n次多项式，故相除的商式 Q(x) = 1。
因此，上式可以写成
）（模 )1()()( ni xxTxTx
1
)()(
1
)(
nn
k
x
xTxQ
x
xTx
)()1()( xTxxTx nk
43
将 T(x) = h(x)?g(x) 和 T?(x) = g(x) 代入化简后，得到上式表明，生成多项式 g(x)应该是 (xn + 1)的一个因子。
例,(x7 + 1)可以分解为为了求出 (7,3)循环码的生成多项式 g(x)，需要从上式中找到一个 (n – k) = 4次的因子。这样的因子有两个，即以上两式都可以作为生成多项式。
选用的生成多项式不同，产生出的循环码码组也不同。
)()1()( xTxxTx nk
)]()[(1 xhxxgx kn
)1)(1)(1(1 3237 xxxxxx
1)1)(1( 2423 xxxxxx
1)1)(1( 2343 xxxxxx
44
10.6.3 循环码的编码方法
用 xn-k乘 m(x)。这一运算实际上是在信息码后附加上 (n– k)个
,0”。例如，信息码为 110，它写成多项式为 m(x) = x2 + x。
当 n– k = 7 – 3 =4时,xn-k m(x) = x4 (x2 +x) = x6 +x5，它表示码组 1100000。
用 g(x)除 xn-k m(x)，得到商 Q(x)和余式 r(x)，即有例：若选定 g(x) = x4 + x2 + x + 1，则有上式是用码多项式表示的运算。它和下式等效：
编出的码组 T(x)为,T(x) = xn-k m(x) +r(x)
在上例中,T(x) = 1100000 + 101 = 1100101
)(
)()(
)(
)(
xg
xrxQ
xg
xmx kn
1
1)1(
1)(
)(
24
2
2
24
56
xxx
xxx
xxx
xx
xg
xmx kn
1 0 1 1 1
1 0 11 1 1
1 0 1 1 1
1 1 0 0 0 0 0
45
10.6.4 循环码的解码方法
在检错时：当接收码组没有错码时，接收码组 R(x)必定能被
g(x)整除，即下式中余项 r(x)应为零；否则，有误码。
当接收码组中的错码数量过多，超出了编码的检错能力时，有错码的接收码组也可能被 g(x)整除。这时，错码就不能检出了。
在纠错时：
用生成多项式 g(x)除接收码组 R(x)，得出余式 r(x)。
按照余式 r(x)，用查表的方法或计算方法得出错误图样
E(x)。
从 R(x)中减去 E(x)，便得到已经纠正错码的原发送码组
T(x)。
)(/)()()(/)( xgxrxQxgxR
)(/)()()(/)( xgxrxQxgxR
46
10.6.5 截短循环码
截短目的：
在设计时，通常信息位数 k、码长 n和纠错能力都是预先给定的。但是，并不一定有恰好满足这些条件的循环码存在。
故采用截短码长截短，得出满足要求的编码。
截短方法：
设给定一个 (n,k)循环码，它共有 2k种码组，现使其前 i (0
< i < k)个信息位全为,0”，于是它变成仅有 2k-i种码组。然后从中删去这 i 位全,0”的信息位，最终得到一个 (n – i,k
– i)的线性码。将这种码称为截短循环码。
截短循环码与截短前的循环码至少具有相同的纠错能力，并且截短循环码的编解码方法仍和截短前的方法一样。
例：要求构造一个能够纠正 1位错码的 (13,9)码。
这时可以由 (15,11)循环码的 11种码组中选出前两信息位均为,0”的码组，构成一个新的码组集合。然后在发送时不发送这两位,0”。于是发送码组成为 (13,9)截短循环码。
47
10.6.6 BCH码
BCH码是能够纠正多个随机错码的循环码。
BCH码分为两类：本原 BCH码和非本原 BCH码。
本原 BCH码：码长 n = 2m – 1 (m? 3，任意正整数 )，它的生成多项式 g(x)中含有最高次数为 m次的本原多项式；
非本原 BCH码：码长 n是 (2m– 1)的一个因子，它的生成多项式 g(x)中不含有最高次数为 m的本原多项式。
BCH码的工程设计：可以用查表法找到所需的生成多项式。
例：二进制非本原 BCH码的生成多项式系数表中 g(x)是用 8进制数字表示的； t 为纠错能力。
n k t g(x) n k t g(x)
17
21
23
33
41
9
12
12
22
21
2
2
3
2
4
727
1663
5343
5145
6647133
47
65
65
73
24
53
40
46
5
2
4
4
43073357
10761
354300067
1717773537
48
常用 BCH码：
戈莱 (Golay)码,(23,12)非本原 BCH码，它能纠正 3个随机错码，并且容易解码 。
扩展 BCH码 (n + 1,k),
BCH码的长度为奇数。在应用中，为了得到偶数长度的码，并增大检错能力，可以在 BCH码生成多项式中乘上一个因式 (x + 1)，从而得到扩展 BCH码 (n + 1,k)。
扩展 BCH码已经不再具有循环性。
扩展戈莱码 (24,12)：其最小码距为 8，码率为 1/2，能够纠正 3个错码和检测 4个错码。
49
几种二进制分组码的性能比较
2PSK
汉明码 (7,4)
t=1
汉明码 (31,26) t=1
扩展戈莱码 (24,12)
t=3
BCH 码 (127,64)
t=10
Eb / n0 (dB)
Pe
50
10.6.7 RS码
RS码：是 q进制 BCH码的一个特殊子类，并且具有很强的纠错能力。
RS码的参数：码长 n = q – 1，监督位数目 r = 2t，其中 t是能够纠正的错码数目；其生成多项式为
g(x) = (x +?)(x +?2) … ( x +?2t)
式中,?为伽罗华域 GF(2m)中的本原元。
RS码的主要优点：
它是多进制纠错编码，所以特别适合用于多进制调制的场合；
它能够纠正 t个 q位二进制错码，即能够纠正不超过 q个连续的二进制错码，所以适合在衰落信道中纠正突发性错码。
51
10.7 卷积码
卷积码的特点：
监督码元不仅和当前的 k比特信息段有关，而且还同前面 m
= (N – 1)个信息段有关。
将 N称为码组的约束度。
将卷积码记作 (n,k,m)，其码率为 k/n。
52
卷积码的编码
一般原理方框图编码输出每次输入
k比特 1 k… 1 k… 1 k… 1 k…… … …
1 … k … 2k 3k Nk… … … … …
… … … …1 2 n
Nk级移存器
n个模 2
加法器每输入 k比特旋转 1周
53
卷积码编码器的实例方框图,(n,k,m) =（ 3,1,2）
每当输入 1比特时，此编码器输出 3比特 c1c2 c3：
编码器的工作状态
1 2 3
b3b1输入 b2
编码输出c2
c1
c3
3213
312
11
bbbc
bbc
bc
b1 1 1 0 1 0 0 0
b3b2 00 01 11 10 01 10 00
c1c2
c3
111 110 010 100 001 011 000
状态 a b d c b c a
54
10.7.2 卷积码的解码
码树搜索法,(3,1,2)卷积码的码树图此法不实用：因为随信息位增多，分支数目按指数规律增长
000
111
001
110
011
100
010
101
000
111
001
110
011
100
010
101
c1c2c3000
100
111
011
001
101
110
010
c1c2c3
111
000
001
110
c1c2c3
信息位 1 1 0 1
b
a
起点信息位
000
111
c1c2c3
a
b
c
da
b
c
da
b
c
da
b
c
d
上半部下半部
1
0
a
状态 b3b2
a 0 0
b 0 1
c 1 0
d 1 1
a
b
c
d
a
b
c
d
c
d
a
b↑0
↓1
↓1
↑0
↑0
↓1
55
状态图和网格图
移存器状态和输入输出码元的关系
状态图前一状态
b3 b2
当前输入
b1
输出
c1c2c3
下一状态
b3 b2
a (00) 0
1
000
111
a (00)
b (01)
b (01) 0
1
001
110
c (10)
d (11)
c (10) 0
1
011
100
a (00)
b (01)
d (11) 0
1
010
101
c (10)
d (11)
3213
312
11
bbbc
bbc
bc
1 2 3
b3b1输入 b2
编码输出c2
c1
c3
a
b
c
d
000 111 101110
010011
100 001
56
(3,1,2)卷积码网格图
网格图中的编码路径举例
输入信息位为 1101时
输出编码序列是：
111 110 010 100 011…
110 110 110 110
011 011 011
010 010 010
101 101 101
001 001 001 001
a
b
c
d
a
b
c
d
000 000 000 000 000
111 111 111 111 111
100100100
a
b
c
d
000 111 101110
010011
100 001
a
b
c
d
a
b
c
d
110 010
001
111
100
57
维特比算法
基本原理：将接收到的序列和所有可能的发送序列作比较，
选择其中汉明距离最小的序列当作是现在的发送序列
例：设卷积码为 (n,k,m) = (3,1,2)码
现在的发送信息位为 1101
为了使移存器中的信息位全部移出，在信息位后面加入了 3个,0”，即 1101000
编码后的发送序列,111 110 010 100 001 011 000
接收序列,111 010 010 110 001 011 000 (红色为错码 )
由于这是一个 (3,1,2)卷积码，发送序列的约束度为 N = m
+ 1 ＝ 3，所以首先需考察 3个信息段，即考察 3n ＝ 9比特，
即接收序列前 9位,111 010 010”。
58
解码第 1步
由网格图可见，沿路径每一级有 4种状态 a,b,c和 d。每种状态只有两条路径可以到达。故 4种状态共有 8条到达路径。
比较网格图中的这 8条路径和接收序列之间的汉明距离。
例如，由出发点状态 a经过 3级路径后到达状态 a的两条路径中上面一条为,000 000 000”。它和接收序列,111
010 010”的汉明距离等于 5；下面一条为,111 001 011”,
它和接收序列的汉明距离等于 3。
110 110 110 110
011 011 011
010 010 010
101 101 101
001 001 001 001
a
b
c
d
a
b
c
d
000 000 000 000 000
111 111 111 111 111
100100100
59
将这 8个比较结果列表如下：
比较到达每个状态的两条路径的汉明距离，将距离小的一条路径保留，称为幸存路径。这样，就剩下 4条路径了，即表中第 2,4,6和 8条路径。
序号路径 对应序列 汉明距离 幸存否？
1 aaaa 000 000 000 5 否
2 abca 111 001 011 3 是
3 aaab 000 000 111 6 否
4 abcb 111 001 100 4 是
5 aabc 000 111 001 7 否
6 abdc 111 110 010 1 是
7 aabd 000 111 110 6 否
8 abdd 111 110 101 4 是
60
解码第 2步：继续考察接收序列中的后继 3个比特,110”
计算 4条幸存路径上增加 1级后的 8条可能路径的汉明距离。计算结果列于下表中。
表中总距离最小为 2，其路径是 abdc+b，相应序列为
111 110 010 100。它和发送序列相同，故对应发送信息位 1101。
序号 路径 原幸存路径的距离新增路径段新增距离 总距离 幸存否？
1 abca+a 3 aa 2 5 否
2 abdc+a 1 ca 2 3 是
3 abca+b 3 ab 1 4 否
4 abdc+b 1 cb 1 2 是
5 abcb+c 4 bc 3 7 否
6 abdd+c 4 dc 1 5 是
7 abcb+d 4 bd 0 4 是
8 abdd+d 4 dd 2 6 否
61
按照上表中的幸存路径画出的网格图示于下图中。
图中粗线路径是距汉明离最小（等于 2）的路径。
a
b
c
d
011
010 010
101
001
a
b
c
d
111
100100
110
110
62
在编码时，信息位后面加了 3个,0”。若把这 3个,0”仍然看作是信息位，则可以按照上述算法继续解码。这样得到的幸存路径网格图示于下图中。图中的粗线仍然是汉明距离最小的路径。
110
011
010 010
101 101
001 001
a
b
c
d
a
b
c
d
000
111
100100
000
011 011
001
101
63
若已知这 3个码元是（为结尾而补充的）,0”，则在解码时就预先知道在接收这 3个,0”码元后，路径必然应该回到状态 a。而由图可见，
只有两条路径可以回到 a状态。所以，这时上图可以简化成：
110
011
010 010
101 101
001 001
a
b
c
d
a
b
c
d
000
111
100100
000
011 011
001
110
011
010 010
101 101
001 001
a
b
c
d
a
b
c
d
000
111
100100
000
011 011
001
101
64
在上例中卷积码的约束度为 N = 3，需要存储和计算 8条路径的参量。
由此可见，维特比算法的复杂度随约束度 N按指数形式 2N
增长。故维特比算法适合约束度较小（ N? 10）的编码。
对于约束度大的卷积码，可以采用其他解码算法，
65
10.8 Turbo码和 LDPC码
Turbo码基本原理：
复合编码：将两种或多种简单的编码组合成复合编码。
链接码：链接码是复合编码的一种，它包括一个内（部）
码和一个外（部）码，如下图所示：
内码是二进制分组码或卷积码，而典型的外码则是多进制的 RS码。
Turbo码：是一种特殊的链接码。它在两个并联或串联的编码器之间增加一个交织器，使之具有很大的码组长度和在低信噪比条件下得到接近理想的性能。
内编码器
(n,k)
调制器信道解制器内解码器
(n,k)
外解码器
(N,K)
外编码器
(N,K)输入输出
66
Turbo码的基本结构
编码器：由一对递归系统卷积码（ RSCC） 编码器和一个交织器组成。
输入信息位是 bi，
输出是 bic1ic2i，
故码率等于 1/3。
RSCC编码器：和前面讨论的卷积码编码器之间的主要区别是从移存器输出到信息位输入端之间有反馈路径：
上图为码率等于 1/2的 RSCC编码器
RSCC
交织器 RSCC
bi
bi
c1i
c2i
D Dbi
bi
ci
67
交织器：基本形式是矩阵交织器。
交织目的：将集中出现的突发错码分散，变成随机错码
交织原理：
交织器由容量为 (n-1)m比特的存储器构成。
码元按行的方向输入存储器，再按列的方向输出。
a11 a12 a1m
a21 a22 a2m
an1 an2 anm
68
卷积交织器举例
x
x
x 12
3
4
x
x x
1
2
3
4
x x x 1
x
x x
1 x x x x x x
(a) 第 1~4比特输入时的状态
x
x
2 56
7
8
3
4 x
5
6
7
8
x x 2 5
x
2 x
5 1 x x x x x
(b) 第 5~8比特输入时的状态
x
3
6 9
3
6 2
9 5 1 x x x x9 10
11
12
10
11
12
7
8 4
x 3 6 9
(c) 第 9~12比特输入时的状态
10
13
7
6
9 5 4 3 2 114
15
16
11
12 8
1314
15
16
4
7
1013
4 7 10 13
(d) 第 13~16比特输入时的状态交织器 解交织器
69
卷积交织法优点：
延迟时间短和需要的存储容量小。
端到端的总延迟时间和两端所需的总存储容量均为
k(N+1)N个码元，是矩阵交织法的一半。
Turbo码的性能：
由此曲线可以看到，
交织器容量大时误码率低，这是因为交织范围大可以使交织器输入码元得到更好的随机化。
信噪比 (dB)
20
解码后的误码率交织器容量 100
10-1
10-2
10-3
10-4
10-5
10-6
10-7
70
LDPC码
LDPC码的全称：低密度奇偶校验 (Low-Density Parity-
Check)码。
LDPC码的特点：
是线性分组码；
它和 Turbo码都是复合码，两者的性能也接近；
两者的解码延迟时间都相当长；
比 Turbo码的解码简单，更容易实现。
71
LDPC码的基本原理：
LDPC码和普通的奇偶监督码一样，可以由 n列 m行的奇偶监督矩阵 H确定。 n是码长,m是校正子个数。
LDPC码的 H矩阵和普通奇偶监督码的 H矩阵不同：
首先，它是一个稀疏矩阵，即其中,1”的个数很少，
或者说密度很低。设 H矩阵每列有 j个,1”，每行有
k个,1”，则应有 j << m,k << n，且 j? 3。
其次,LDPC码的 H矩阵的任意两行的元素不能在相同位置上为,1”，即 H矩阵中没有四角由,1”构成的矩形。
在编码时设计好 H矩阵后，由 H矩阵可以导出生成矩阵 G。这样，对于给定的信息位不难算出码组。
72
LDPC码的解码方法：
和一般的奇偶监督码的解码方法不同。基本的解码算法称为置信传播算法 (Belief Propagation Algorithm)，通常简称 BP算法。这种算法实质上是求最大后验概率，但是需要进行多次迭代运算，逐步逼近最优的解码值。
73
10.9 小结
