2001 Copyright SCUT DT&P Labs 1
数字通信原理
（ 9）
2001 Copyright SCUT DT&P Labs 2
第十一章 差错控制编码
2001 Copyright SCUT DT&P Labs 3
11.1 差错控制编码的基本概念
1.差错控制的主要方式
（ 1） 检错重发（ ARQ,Automatic Request for Repetition）；
（ 2） 前向纠错（ FEC,Forward Error Control）；
（ 3） 混合纠错（ HEC,Hybrid Error Control）。
2.差错控制的基本实现方法在信息上附加一定位数的监督码元，使其与信息位按某种规则相互关联，若数据在传输过程中发生差错，关联关系被破坏，
从而可检出和 /或纠正错误。
2001 Copyright SCUT DT&P Labs 4
11.1 差错控制编码的基本概念
3.差错控制编码的分类
（ 1） 线性码,信息码与监督码之间的关系为线性关系；
非线性码：信息码与监督码之间的关系为非线性关系。
（ 2） 分组码：信息码与监督码以组为单位建立关系 ；
卷积码：监督码与本组和前面码组中的信息码有关。
（ 3） 系统码,编码后码组中信息码保持原图样顺序不变；
非系统码：编码后码组中原信息码原图样发生变化。
（ 4）数学方法：
代数码；
几何码；
算术码。
2001 Copyright SCUT DT&P Labs 5
11.1 差错控制编码的基本概念
4.误码的主要形式
（ 1） 随机错误：误码的位置随机（误码间无关联），随机误码主要由白噪声引起。
（ 2） 突发错误：误码成串出现，主要由强脉冲及雷电等突发的强干扰引起。
（ 3） 混合错误：以上两种误码及产生原因的组合。
2001 Copyright SCUT DT&P Labs 6
11.1 差错控制编码的基本概念
5.有扰离散信道的编码定理（香农信道编码定理）
若有扰信道容量为 C,信息传输速率为 R,如果 R<C,则存在编码方法，使错误概率
P? e-nE(R)
其中 E(R) 称为误差指数,n 为码组长度 。
信道容量 C作为曲线的的参变量，包含有关
S/N的因素。
E
C
(R)
R
C
1
0 C
2
C
2001 Copyright SCUT DT&P Labs 7
11.1 差错控制编码的基本概念
5.检错与纠错的基本概念
（ 1） 例，三位二进制码的三种编码方法。三位二进码共有 8种可能的组合,000,001,010,011,100,101,110,111。
a,若 8个码组均用于表示不同的信息，任一位或一位以上的错误都会变成另一码组，所以无法检错和纠错。
b,若将 8个码组分成许用和禁用两类：
许用码组,000,011,101,110
禁用码组,111,100,010,001
因任何一位误码，都会变成禁用码组，所以可检出一位误码。
c,若只用 000,111两个码组，其余为禁用码组，则可发现两位及以下的误码，并纠正一位误码。
2001 Copyright SCUT DT&P Labs 8
11.1 差错控制编码的基本概念
5.检错与纠错的基本概念（续前）
直观地，冗余度越大，许（准）用码组间的区别越大，检错和纠错能力越强。
（ 2）,基本术语
a,码重 W,码组中非零码元的数目；
b,码距 d（ Hamming距）,两码组中对应码元位置上取值不同的个数；
c,最小码距 dmin,准用码组中任两码组间的最小码距。
2001 Copyright SCUT DT&P Labs 9
5.检错与纠错的基本概念 11.1 差错控制编码的基本概念
（ 3） 线性分组码的基本结论
a,要在一个码组中检出 e个误码，要求
dmin? e＋ 1
即任一码组产生小于等于 e个误码时，都不会变成另一准用码组 。
C
i
C
j
e 1
d
min
2001 Copyright SCUT DT&P Labs 10
（ 3） 线性分组码的基本结论 11.1 差错控制编码的基本概念
b,要在一个码组中能纠正 t个误码，要求
dmin? 2t＋ 1
将以 t为半径的,球,内所有的禁用码组均判为球心中的准用码组，可纠正 t个以内的错误 。 C i C j
t 1 t
d
min
2001 Copyright SCUT DT&P Labs 11
（ 3） 线性分组码的基本结论 11.1 差错控制编码的基本概念
c,要在一个码组中能纠正 t个误码，同时检出 e (e? t) 个误码
dmin? e＋ t＋ 1
当误码数小于等于 t时，可纠正；
当误码数大于 t小于等于 e时，不会落入另一码组的纠错范围内 。C
i C
j
t
1t
d
min
e
2001 Copyright SCUT DT&P Labs 12
（ 3） 线性分组码的基本结论 11.1 差错控制编码的基本概念
d,编码效率设码组长为 n,信息位为 k,监督位为 r,编码效率定义为
n
k
2001 Copyright SCUT DT&P Labs 13
11.1 差错控制编码的基本概念
6.几种简单的检错码
（ 1）奇偶效验码在信息码组 an-1,an-2,…,a1中加入监督位 a0,使编码后码组中
,1” 的个数为奇数（ 奇效验 ）或偶数（ 偶效验 ）。
偶效验,取 a0,使下式成立
an-1?an-2?…?a1?a0 ＝ 0
a0 = an-1?an-2?…?a1
奇效验,取 a0,使下式成立
an-1?an-2?…?a1?a0 ＝ 1
a0 = an-1?an-2?…?a1?1
2001 Copyright SCUT DT&P Labs 14
6.几种简单的检错码 11.1 差错控制编码的基本概念
（ 1）奇偶效验码（续前）
奇偶效验码码组间最小距离 dmin＝ 2
证明（以偶效验为例）：因为
an-1?an-2?…?a1?a0 ＝ 0
所以当码组中任一位 aj发生错误时 aj?/aj;
an-1?an-2?…/aj…?a1?a0 ＝ 1
至少可检出一位误码，故 dmin大于或等于 2。
当有两位 ai,aj发生误码时
an-1?an-2?…/aj…/sj…?a1?a0 ＝ 0
所以不能检出两位误码,故 dmin小于或等于 2。
综上,dmin＝ 2。
2001 Copyright SCUT DT&P Labs 15
6.几种简单的检错码 11.1 差错控制编码的基本概念
（ 2）水平奇偶效验码
m个码组分别以各自码组为单位作奇效验或偶效验，然后以各码组的最高位、次高位,… 依次发送：
an-1 an-2 …… a1 a0
an-1 an-2 …… a1 a0
…… … … …… … …
an-1 an-2 …… a1 a0
an-1 an-2 …… a1 a0
当突发的错误数小于 m个时，每个码组中的误码个数小于 2个，通过奇偶效验可以检出。
2001 Copyright SCUT DT&P Labs 16
6.几种简单的检错码 11.1 差错控制编码的基本概念
（ 2）水平奇偶效验码（续前）
在上面的分析中，整个方阵作为一个,码组,,长度为原来的 m
倍，
可检出不大于 m个的突发错误，在未增加监督位的条件下，检错能力为原来的 m倍，这是 香农信道编码定理 应用的一个例子。
该编解码所付的 代价,缓存空间和延时增大。
2001 Copyright SCUT DT&P Labs 17
6.几种简单的检错码 11.1 差错控制编码的基本概念
（ 3） 水平垂直奇偶效验码在水平奇偶监督码的基础上增加列的奇偶效验。
可检出任一行和任一列的所有奇数个错误，及长度不大于行数（按列发）或不大于列数（按行发）的突发错误。
（ 4） 群计数码计算码组中信息位,1” 的个数，将计算值作为监督位，可检出除
,0” 变,1”,,1” 变,0” 成对出现之外的所有错误。
2001 Copyright SCUT DT&P Labs 18
6.几种简单的检错码 11.1 差错控制编码的基本概念
（ 5） 恒比码从某确定长度的码组中挑选出那些,1” 和,0” 的比例为恒定值的码组作为许用码组，当收到违反恒比特性的码组即可判为误码。
（ 6） ISBN国际统一图书编号
ISBN A BBB CCCCC X
国家代号 出版公司 书名编号 效验码效验码的选择使进行,两列,的累加后其和 模 11 为零。
2001 Copyright SCUT DT&P Labs 19
6.几种简单的检错码 11.1 差错控制编码的基本概念
（ 6） ISBN国际统一图书编号 （续前）
例：
《现代通信原理》书代号为
ISBN 7 3 0 2 0 1 0 0 2 1
7 10 10 12 12 13 13 13 15 16
7 17 27 39 51 64 77 90 105 121
121 ＝ 0 mod 11
2001 Copyright SCUT DT&P Labs 20
11.2 线性分组码
1.基本概念
（ 1） 线性分组码：码组中的信息位和监督位之间的关系由线性方程确定；
线性分组码的特点：
两许用码组之和（逐位模 2和）仍为一许用码组（封闭性）；
码组间的最小距离等于非零码的最小重量。
2001 Copyright SCUT DT&P Labs 21
11.2 线性分组码
2.例,具有纠正 一位 误码的分组码
C6C5C4C3 C2C1C0 n = 7,k = 4,
信息位 监督位 r = n－ k＝ 3
定义一组确定误码位置的参量,S1S2S3
误码位置 S1S2S3 误码位置 S1S2S3
无误码 000 C3 011
C0 001 C4 101
C1 010 C5 110
C2 100 C6 111
由上表可得,S1＝ C6?C5?C4?C2 S2＝ C6?C5?C3?C1
S3＝ C6?C5?C3?C0
2001 Copyright SCUT DT&P Labs 22
2.例（续前） 11.2 线性分组码容易验证，当出现 一位 误码时，校正子能够确定误码的位置。
当无误码时，应有
S1＝ C6?C5?C4?C2＝ 0 S2＝ C6?C5?C3?C1＝ 0
S3＝ C6?C5?C3?C0＝ 0
上述方程亦称为 监督方程 。
由此可得编码时监督位的取值：
C2＝ C6?C5?C4
C1＝ C6?C5?C3
C0 ＝ C6?C4?C3
给出一组信息码 C6C5C4C3,可计算出监督位 C2C1C0。
信息位于监督位间的关系为 线性关系 。
2001 Copyright SCUT DT&P Labs 23
2.例（续前）,11.2 线性分组码设信息码组 C6C5C4C3＝ 0101
C2＝ C6?C5?C4 ＝ 0?1?0＝ 1
C1＝ C6?C5?C3 ＝ 0?1?1＝ 0
C0 ＝ C6?C5?C4 = 0?0?1＝ 1
发送,C6C5C4C3 C2C1C0＝ 0101101
若接收时有一位,C5,位出错,C6C5C4C3 C2C1C0＝ 0001101
S1＝ C6?C5?C4?C2＝ 0?0?0?1=1
S2＝ C6?C5?C3?C1＝ 0?0?1?0=1
S3＝ C6?C5?C3?C0＝ 0?0?0?0=0
根据效验子 S1 S2 S3＝ 110,可判断误码发生在 C5。
2001 Copyright SCUT DT&P Labs 24
11.2 线性分组码
3.监督矩阵前述的监督方程可用矩阵形式表示矩阵 H称为 监督矩阵 。
对上例，有：
0
...
0
0
...
0
1
2
1
C
C
C
C
H
n
n
0
0
0
1001101
0101011
0010111
0123456
TCCCCCCC
2001 Copyright SCUT DT&P Labs 25
3.监督矩阵（续前） 11.2 线性分组码在上例中，监督矩阵 H为：
监督矩阵的性质,
（ 1） H由码元间的监督关系唯一确定；
（ 2） H的行向量相互独立，当采用系统码结构时，具有形式其中 Ir是 r× r单位阵。
（ 3）若发 [C],收到 [R],则有误码。
1001101
0101011
0010111
H
rIPH,?
0?TRH
2001 Copyright SCUT DT&P Labs 26
11.2 线性分组码
3.校正 [S]与 H及误码的关系设发送码组为 [A],接收码组为 [B]
误码为,[B]-[A]=[E]=[en-1en-2……e1e0]
由 [B]=[A]+[E]：
得 [S]=[B]HT={[A]+[E]}HT＝ [A]HT+[E]HT = 0 + [E]HT =[E]HT
[S]仅与 [E]和 HT有关。
ii
ii
i ab
ab
e
,1
,0
2001 Copyright SCUT DT&P Labs 27
11.2 线性分组码
4.生成矩阵在上例中，监督为的产生可表示为一般地，上述关系可表示为其转置形式：
3
4
5
6
0
1
2
1101
1011
0111
C
C
C
C
C
C
C
r
n
n
r
r
C
C
C
P
C
C
C
......
2
1
0
2
1
QCCC
PCCCCCC
rnn
T
rnnrr
...
......
21
21021
2001 Copyright SCUT DT&P Labs 28
11.2 线性分组码
4.生成矩阵（续前）
上式中定义生成矩阵,
其中 Ik是 k× k的单位阵。
系统码形式的发送码组可按下式产生：
TPQ?
QIPIG kTk,,
GCCCCCC rnnnn,,,.,,21021
2001 Copyright SCUT DT&P Labs 29
11.2 线性分组码
5.汉明码具有下列特点的线性分组码称之为 汉明码,
码长,n＝ 2r－ 1,信息位,k＝ 2r－ 1－ r,监督位,r＝ n－ k
最小码距 dmin＝ 3,纠错能力 t＝ 1
记为：
（ n,k）＝（ 2r－ 1,2r－ 1－ r ）
汉明码的 编码效率,
12112
12
rr
r rr
n
k?
n
2001 Copyright SCUT DT&P Labs 30
11.2 线性分组码
5.汉明码（续前）
因为 汉明码有 r位监督位，效验子 S共有 2r种组合（图样）
而码长,n＝ 2r－ 1
对一位误码，有 n个可能的出错的位置，相应地可用 S中 2r－ 1种不同的图样分别表示，剩下一种全,0” 的图样表示无误码。
所以,汉明码可纠正一位误码，最小码距 dmin＝ 3。
汉明码的编译码器的一个实例（参见 图 11－ 8）
2001 Copyright SCUT DT&P Labs 31
11.2 线性分组码
6.扩展汉明码在汉明码中增加一位效验码 （ n,k）? （ n＋ 1,k）,对所有的位作偶监督。
例：设原汉明码（ 7,4）：
C6C5C4C3 C2C1C0? C7C6C5C4 C3 C2C1 C0
信息位 监督位 信息位 原监督位 偶效验位监督矩阵,H? He 效验方程
1...11
0
0
0
0
HH
e
1
0
...
0
0
1...
0
0
0
0
0
1
1
1
1.,,11
rn
C
C
C
C
H
n
n
n
2001 Copyright SCUT DT&P Labs 32
6.扩展汉明码 11.2 线性分组码效验子 的确定方法与原汉明码效验子 的确定方法相同相同。而新增效验子作偶效验。
（ 1）当接收的码组仅发生一位误码时,误码的位置 i由效验子 [S]图样对应的 He中相应的第 i列确定。
（ 2）当发生两位误码时，如第 i,j位。则效验子 [S]为 He中第 i位误码对应的图样与第 j位误码对应的图样按位模 2和。前 r个元素对应原 H矩阵中的某一列，但
1
1
...
S
S
S
r
r
0
2
1
...
S
S
S
r
r
0S?
0110,.,CCCCS nn
10S
10S
2001 Copyright SCUT DT&P Labs 33
6.扩展汉明码 11.2 线性分组码所以 [S]不是 He中的任一列，因而可判断有两位误码，即
t＝ 1,e＝ 2,dmin >= t+e+1 = 1+2+1=4
但因为只增加了一位效验位，最小的码重不可能增加 2
所以改进后的扩展汉明码 dmin＝ 4
数字通信原理
（ 9）
2001 Copyright SCUT DT&P Labs 2
第十一章 差错控制编码
2001 Copyright SCUT DT&P Labs 3
11.1 差错控制编码的基本概念
1.差错控制的主要方式
（ 1） 检错重发（ ARQ,Automatic Request for Repetition）；
（ 2） 前向纠错（ FEC,Forward Error Control）；
（ 3） 混合纠错（ HEC,Hybrid Error Control）。
2.差错控制的基本实现方法在信息上附加一定位数的监督码元，使其与信息位按某种规则相互关联，若数据在传输过程中发生差错，关联关系被破坏，
从而可检出和 /或纠正错误。
2001 Copyright SCUT DT&P Labs 4
11.1 差错控制编码的基本概念
3.差错控制编码的分类
（ 1） 线性码,信息码与监督码之间的关系为线性关系；
非线性码：信息码与监督码之间的关系为非线性关系。
（ 2） 分组码：信息码与监督码以组为单位建立关系 ；
卷积码：监督码与本组和前面码组中的信息码有关。
（ 3） 系统码,编码后码组中信息码保持原图样顺序不变；
非系统码：编码后码组中原信息码原图样发生变化。
（ 4）数学方法：
代数码；
几何码；
算术码。
2001 Copyright SCUT DT&P Labs 5
11.1 差错控制编码的基本概念
4.误码的主要形式
（ 1） 随机错误：误码的位置随机（误码间无关联），随机误码主要由白噪声引起。
（ 2） 突发错误：误码成串出现，主要由强脉冲及雷电等突发的强干扰引起。
（ 3） 混合错误：以上两种误码及产生原因的组合。
2001 Copyright SCUT DT&P Labs 6
11.1 差错控制编码的基本概念
5.有扰离散信道的编码定理（香农信道编码定理）
若有扰信道容量为 C,信息传输速率为 R,如果 R<C,则存在编码方法，使错误概率
P? e-nE(R)
其中 E(R) 称为误差指数,n 为码组长度 。
信道容量 C作为曲线的的参变量，包含有关
S/N的因素。
E
C
(R)
R
C
1
0 C
2
C
2001 Copyright SCUT DT&P Labs 7
11.1 差错控制编码的基本概念
5.检错与纠错的基本概念
（ 1） 例，三位二进制码的三种编码方法。三位二进码共有 8种可能的组合,000,001,010,011,100,101,110,111。
a,若 8个码组均用于表示不同的信息，任一位或一位以上的错误都会变成另一码组，所以无法检错和纠错。
b,若将 8个码组分成许用和禁用两类：
许用码组,000,011,101,110
禁用码组,111,100,010,001
因任何一位误码，都会变成禁用码组，所以可检出一位误码。
c,若只用 000,111两个码组，其余为禁用码组，则可发现两位及以下的误码，并纠正一位误码。
2001 Copyright SCUT DT&P Labs 8
11.1 差错控制编码的基本概念
5.检错与纠错的基本概念（续前）
直观地，冗余度越大，许（准）用码组间的区别越大，检错和纠错能力越强。
（ 2）,基本术语
a,码重 W,码组中非零码元的数目；
b,码距 d（ Hamming距）,两码组中对应码元位置上取值不同的个数；
c,最小码距 dmin,准用码组中任两码组间的最小码距。
2001 Copyright SCUT DT&P Labs 9
5.检错与纠错的基本概念 11.1 差错控制编码的基本概念
（ 3） 线性分组码的基本结论
a,要在一个码组中检出 e个误码，要求
dmin? e＋ 1
即任一码组产生小于等于 e个误码时，都不会变成另一准用码组 。
C
i
C
j
e 1
d
min
2001 Copyright SCUT DT&P Labs 10
（ 3） 线性分组码的基本结论 11.1 差错控制编码的基本概念
b,要在一个码组中能纠正 t个误码，要求
dmin? 2t＋ 1
将以 t为半径的,球,内所有的禁用码组均判为球心中的准用码组，可纠正 t个以内的错误 。 C i C j
t 1 t
d
min
2001 Copyright SCUT DT&P Labs 11
（ 3） 线性分组码的基本结论 11.1 差错控制编码的基本概念
c,要在一个码组中能纠正 t个误码，同时检出 e (e? t) 个误码
dmin? e＋ t＋ 1
当误码数小于等于 t时，可纠正；
当误码数大于 t小于等于 e时，不会落入另一码组的纠错范围内 。C
i C
j
t
1t
d
min
e
2001 Copyright SCUT DT&P Labs 12
（ 3） 线性分组码的基本结论 11.1 差错控制编码的基本概念
d,编码效率设码组长为 n,信息位为 k,监督位为 r,编码效率定义为
n
k
2001 Copyright SCUT DT&P Labs 13
11.1 差错控制编码的基本概念
6.几种简单的检错码
（ 1）奇偶效验码在信息码组 an-1,an-2,…,a1中加入监督位 a0,使编码后码组中
,1” 的个数为奇数（ 奇效验 ）或偶数（ 偶效验 ）。
偶效验,取 a0,使下式成立
an-1?an-2?…?a1?a0 ＝ 0
a0 = an-1?an-2?…?a1
奇效验,取 a0,使下式成立
an-1?an-2?…?a1?a0 ＝ 1
a0 = an-1?an-2?…?a1?1
2001 Copyright SCUT DT&P Labs 14
6.几种简单的检错码 11.1 差错控制编码的基本概念
（ 1）奇偶效验码（续前）
奇偶效验码码组间最小距离 dmin＝ 2
证明（以偶效验为例）：因为
an-1?an-2?…?a1?a0 ＝ 0
所以当码组中任一位 aj发生错误时 aj?/aj;
an-1?an-2?…/aj…?a1?a0 ＝ 1
至少可检出一位误码，故 dmin大于或等于 2。
当有两位 ai,aj发生误码时
an-1?an-2?…/aj…/sj…?a1?a0 ＝ 0
所以不能检出两位误码,故 dmin小于或等于 2。
综上,dmin＝ 2。
2001 Copyright SCUT DT&P Labs 15
6.几种简单的检错码 11.1 差错控制编码的基本概念
（ 2）水平奇偶效验码
m个码组分别以各自码组为单位作奇效验或偶效验，然后以各码组的最高位、次高位,… 依次发送：
an-1 an-2 …… a1 a0
an-1 an-2 …… a1 a0
…… … … …… … …
an-1 an-2 …… a1 a0
an-1 an-2 …… a1 a0
当突发的错误数小于 m个时，每个码组中的误码个数小于 2个，通过奇偶效验可以检出。
2001 Copyright SCUT DT&P Labs 16
6.几种简单的检错码 11.1 差错控制编码的基本概念
（ 2）水平奇偶效验码（续前）
在上面的分析中，整个方阵作为一个,码组,,长度为原来的 m
倍，
可检出不大于 m个的突发错误，在未增加监督位的条件下，检错能力为原来的 m倍，这是 香农信道编码定理 应用的一个例子。
该编解码所付的 代价,缓存空间和延时增大。
2001 Copyright SCUT DT&P Labs 17
6.几种简单的检错码 11.1 差错控制编码的基本概念
（ 3） 水平垂直奇偶效验码在水平奇偶监督码的基础上增加列的奇偶效验。
可检出任一行和任一列的所有奇数个错误，及长度不大于行数（按列发）或不大于列数（按行发）的突发错误。
（ 4） 群计数码计算码组中信息位,1” 的个数，将计算值作为监督位，可检出除
,0” 变,1”,,1” 变,0” 成对出现之外的所有错误。
2001 Copyright SCUT DT&P Labs 18
6.几种简单的检错码 11.1 差错控制编码的基本概念
（ 5） 恒比码从某确定长度的码组中挑选出那些,1” 和,0” 的比例为恒定值的码组作为许用码组，当收到违反恒比特性的码组即可判为误码。
（ 6） ISBN国际统一图书编号
ISBN A BBB CCCCC X
国家代号 出版公司 书名编号 效验码效验码的选择使进行,两列,的累加后其和 模 11 为零。
2001 Copyright SCUT DT&P Labs 19
6.几种简单的检错码 11.1 差错控制编码的基本概念
（ 6） ISBN国际统一图书编号 （续前）
例：
《现代通信原理》书代号为
ISBN 7 3 0 2 0 1 0 0 2 1
7 10 10 12 12 13 13 13 15 16
7 17 27 39 51 64 77 90 105 121
121 ＝ 0 mod 11
2001 Copyright SCUT DT&P Labs 20
11.2 线性分组码
1.基本概念
（ 1） 线性分组码：码组中的信息位和监督位之间的关系由线性方程确定；
线性分组码的特点：
两许用码组之和（逐位模 2和）仍为一许用码组（封闭性）；
码组间的最小距离等于非零码的最小重量。
2001 Copyright SCUT DT&P Labs 21
11.2 线性分组码
2.例,具有纠正 一位 误码的分组码
C6C5C4C3 C2C1C0 n = 7,k = 4,
信息位 监督位 r = n－ k＝ 3
定义一组确定误码位置的参量,S1S2S3
误码位置 S1S2S3 误码位置 S1S2S3
无误码 000 C3 011
C0 001 C4 101
C1 010 C5 110
C2 100 C6 111
由上表可得,S1＝ C6?C5?C4?C2 S2＝ C6?C5?C3?C1
S3＝ C6?C5?C3?C0
2001 Copyright SCUT DT&P Labs 22
2.例（续前） 11.2 线性分组码容易验证，当出现 一位 误码时，校正子能够确定误码的位置。
当无误码时，应有
S1＝ C6?C5?C4?C2＝ 0 S2＝ C6?C5?C3?C1＝ 0
S3＝ C6?C5?C3?C0＝ 0
上述方程亦称为 监督方程 。
由此可得编码时监督位的取值：
C2＝ C6?C5?C4
C1＝ C6?C5?C3
C0 ＝ C6?C4?C3
给出一组信息码 C6C5C4C3,可计算出监督位 C2C1C0。
信息位于监督位间的关系为 线性关系 。
2001 Copyright SCUT DT&P Labs 23
2.例（续前）,11.2 线性分组码设信息码组 C6C5C4C3＝ 0101
C2＝ C6?C5?C4 ＝ 0?1?0＝ 1
C1＝ C6?C5?C3 ＝ 0?1?1＝ 0
C0 ＝ C6?C5?C4 = 0?0?1＝ 1
发送,C6C5C4C3 C2C1C0＝ 0101101
若接收时有一位,C5,位出错,C6C5C4C3 C2C1C0＝ 0001101
S1＝ C6?C5?C4?C2＝ 0?0?0?1=1
S2＝ C6?C5?C3?C1＝ 0?0?1?0=1
S3＝ C6?C5?C3?C0＝ 0?0?0?0=0
根据效验子 S1 S2 S3＝ 110,可判断误码发生在 C5。
2001 Copyright SCUT DT&P Labs 24
11.2 线性分组码
3.监督矩阵前述的监督方程可用矩阵形式表示矩阵 H称为 监督矩阵 。
对上例，有：
0
...
0
0
...
0
1
2
1
C
C
C
C
H
n
n
0
0
0
1001101
0101011
0010111
0123456
TCCCCCCC
2001 Copyright SCUT DT&P Labs 25
3.监督矩阵（续前） 11.2 线性分组码在上例中，监督矩阵 H为：
监督矩阵的性质,
（ 1） H由码元间的监督关系唯一确定；
（ 2） H的行向量相互独立，当采用系统码结构时，具有形式其中 Ir是 r× r单位阵。
（ 3）若发 [C],收到 [R],则有误码。
1001101
0101011
0010111
H
rIPH,?
0?TRH
2001 Copyright SCUT DT&P Labs 26
11.2 线性分组码
3.校正 [S]与 H及误码的关系设发送码组为 [A],接收码组为 [B]
误码为,[B]-[A]=[E]=[en-1en-2……e1e0]
由 [B]=[A]+[E]：
得 [S]=[B]HT={[A]+[E]}HT＝ [A]HT+[E]HT = 0 + [E]HT =[E]HT
[S]仅与 [E]和 HT有关。
ii
ii
i ab
ab
e
,1
,0
2001 Copyright SCUT DT&P Labs 27
11.2 线性分组码
4.生成矩阵在上例中，监督为的产生可表示为一般地，上述关系可表示为其转置形式：
3
4
5
6
0
1
2
1101
1011
0111
C
C
C
C
C
C
C
r
n
n
r
r
C
C
C
P
C
C
C
......
2
1
0
2
1
QCCC
PCCCCCC
rnn
T
rnnrr
...
......
21
21021
2001 Copyright SCUT DT&P Labs 28
11.2 线性分组码
4.生成矩阵（续前）
上式中定义生成矩阵,
其中 Ik是 k× k的单位阵。
系统码形式的发送码组可按下式产生：
TPQ?
QIPIG kTk,,
GCCCCCC rnnnn,,,.,,21021
2001 Copyright SCUT DT&P Labs 29
11.2 线性分组码
5.汉明码具有下列特点的线性分组码称之为 汉明码,
码长,n＝ 2r－ 1,信息位,k＝ 2r－ 1－ r,监督位,r＝ n－ k
最小码距 dmin＝ 3,纠错能力 t＝ 1
记为：
（ n,k）＝（ 2r－ 1,2r－ 1－ r ）
汉明码的 编码效率,
12112
12
rr
r rr
n
k?
n
2001 Copyright SCUT DT&P Labs 30
11.2 线性分组码
5.汉明码（续前）
因为 汉明码有 r位监督位，效验子 S共有 2r种组合（图样）
而码长,n＝ 2r－ 1
对一位误码，有 n个可能的出错的位置，相应地可用 S中 2r－ 1种不同的图样分别表示，剩下一种全,0” 的图样表示无误码。
所以,汉明码可纠正一位误码，最小码距 dmin＝ 3。
汉明码的编译码器的一个实例（参见 图 11－ 8）
2001 Copyright SCUT DT&P Labs 31
11.2 线性分组码
6.扩展汉明码在汉明码中增加一位效验码 （ n,k）? （ n＋ 1,k）,对所有的位作偶监督。
例：设原汉明码（ 7,4）：
C6C5C4C3 C2C1C0? C7C6C5C4 C3 C2C1 C0
信息位 监督位 信息位 原监督位 偶效验位监督矩阵,H? He 效验方程
1...11
0
0
0
0
HH
e
1
0
...
0
0
1...
0
0
0
0
0
1
1
1
1.,,11
rn
C
C
C
C
H
n
n
n
2001 Copyright SCUT DT&P Labs 32
6.扩展汉明码 11.2 线性分组码效验子 的确定方法与原汉明码效验子 的确定方法相同相同。而新增效验子作偶效验。
（ 1）当接收的码组仅发生一位误码时,误码的位置 i由效验子 [S]图样对应的 He中相应的第 i列确定。
（ 2）当发生两位误码时，如第 i,j位。则效验子 [S]为 He中第 i位误码对应的图样与第 j位误码对应的图样按位模 2和。前 r个元素对应原 H矩阵中的某一列，但
1
1
...
S
S
S
r
r
0
2
1
...
S
S
S
r
r
0S?
0110,.,CCCCS nn
10S
10S
2001 Copyright SCUT DT&P Labs 33
6.扩展汉明码 11.2 线性分组码所以 [S]不是 He中的任一列，因而可判断有两位误码，即
t＝ 1,e＝ 2,dmin >= t+e+1 = 1+2+1=4
但因为只增加了一位效验位，最小的码重不可能增加 2
所以改进后的扩展汉明码 dmin＝ 4
