? 差错率,差错率是衡量传输质量的重要指
标之一，它有以下几种不同的定义。
? 码元差错率,指在传输的码元总数中发生差错的码
元数所占的比例（平均值），简称 误码率 。
? 比特差错率 /比特误码率,指在传输的比特总数中发
生差错的比特数所占的比例（平均值）。 在二进制
传输系统中，码元差错率就是比特差错率 。
? 码组差错率,指在传输的码组总数中发生差错的码
组数所占的比例（平均值）。
第五节 纠错编码的基本思想
? 根据不同的应用场合对差错率有不同的要求。
? 在电报传送时，允许的比特差错率约为 10－ 4～
10－ 5；
? 计算机数据传输，一般要求比特差错率小于 10－
8～ 10－ 9；
? 在遥控指令和武器系统的指令系统中，要求有更
小的误比特率或码组差错率。
采用信道编码的数字通信系统
? 在某些情况下，信道的改善可能较困难或者不经济，这
就要求采用信道编码，以便满足系统差错率的技术指标
要求。
? 信道编码为系统设计者提供了一个降低系统差错率的措
施。采用信道编码后的数字通信系统可用图 6.1.2所示。
信
源
编
码
解
调
器
信
源
图 6, 1, 2 有 信 道 编 码 的 数 字 通 信 系 统 框 图
调
制
器
传
输
媒
介
信
宿
信
源
译
码
信
道
译
码
信
道
编
码
C Rm m '
(1) 编码信道, 是研究纠错编码和译码的一种模型。 如
图 6.1.3所示。
? 编码信道
? 无线通信中的发射机、天线、自由空间、接收机等的全体；
? 有线通信中的如调制解调器、电缆等的全体；
? Internet 网的多个路由器、节点、电缆、底层协议等的全体；
? 计算机的存储器（如磁盘等）的全体。
信 道 译 码信 道 编 码 编 码 信 道
消 息 m 码 字 C
接 收 向 量 R
消 息 m ’
? 二进制编码信道模型,
R =C+E (mod 2)
? E：随机变量；
? 差错图案,随机序列 (Ei)；
? 称 E=(E0,E1,…,En-1)中 Ei=1为第 i
位上的一个随机错误；
? 第 i至第 j位之间有很多错误时，
称为一个 j－ i+1长的突发错误。
图 6, 1, 4 B S C 转 移 概 率
1 － p
b
0 0
11
1 － p
b
p
b
p
b
图 6, 1, 5 B S C 编 码 信 道
1
C
E
R
(2) 信道编码的基本思想
? 信道编码的对象,是信源编码器输出的信息序列 m。
通常是二元符号 1,0组成的序列。
? 信道编码的基本思想
? 按一定规则给数字序列 m增加一些多余的码元，使
不具有规律性的信息序列 m 变换为具有某种规律
性的数码序列 C；
? 码序列中的 信息序列码元 与 多余码元 之间是相关的；
? 信道译码器利用这种 预知的 编码规则译码。检验接
收到的数字序列 R 是否符合 既定的 规则，从而发
现 R 中是否有错，或者纠正其中的差错；
? 码元的组成及其它们之间的关系
? 信息码组, 数字序列 m 总是以 k 个码元为一组
传输，称这 k 个码元的码组为信息码组。例如遥控
系统中的每个指令字，计算机中的每个字节。
? 码组 /码字, 信道编码器按一定的规则对每个信息
码组附加一些多余的码元，构成了 n 个码元的码组。
? 监督码元 /监督元, 附加的 (n－ k) 个码元称为该
码组的监督码元或监督元。
? (3) 纠错编码的分类
? 分组码,编码的规则仅局限于本码组之内，本码组的监
督元仅和本码组的信息元相关。
信息码组由 k 个二进制码元组成，共有 2k 个不同的信息
码组；
附加 n－ k个码元，每个监督元取值与该信息码组的 k个码
元有关；
编码器输出长度 n；
这 2k 个码字的集合称为 (n,k) 分组码；
? 卷积码,本码组的监督元不仅和本码组的信息元相关，
而且还与本码组相邻的前 n－ 1 个码组的信息元相关。
? 是否可用线性方程组来表示
? 线性码,编码规则可以用线性方程表示；
? 非线性码,编码规则不能用线性方程表示；
? 按码字的结构分
? 系统码,前 k 个码元与信息码组一致；
? 非系统码,没有系统码的特性。
? 按纠正差错的类型可分为 纠正随机错误的码 和 纠正突
发错误的码 ；
? 按码字中每个码元的取值可分为 二进制码 和 多进制码 。
(1)偶（或奇）校验方法
? p 为偶校验位
m0+m1+m2+… +mk－ 1+p=0 (mod 2)
? 则 C =(m0,m1,m2,…,mk－ 1,p) 为一个偶校验码字。
? C 中一定有偶数个, 1”
? 当差错图案 E 中有奇数个, 1”，即 R 中有奇数个位有错
时，可以通过校验方程是否为 0判断有无可能传输差错。
? (2)多个奇偶校验位
? 一个校验位可以由信息位的部分或全部按校验方程产生；
? 例如 C 是一个对阵列消息进行垂直与水平校验以及总校验的
码字；
? 其码率为
? 当校验位数增加时，
可以检测到差错图案
种类数也增加，同时
码率减小。
0,0 0,1 0,
1,0 1,1 1,
,0,1,
1
,,
0
1
,,
0
11
,,,
00
1
C
1( 1 )
1
m od 2,0,1,,1
m od 2,0,1,,1
m od 2
tt
s s t s t
s s t s t
t
i t i j
j
s
s j i j
i
st
s t i t s j
ij
m m p
st
R
st m m pst s t
st p p p
p m i s
p m j t
p m m
?
? ? ? ?
?
?
?
?
?
??
??
??
??
??
? ? ?
?? ??? ? ?
?
??
??
? ? ?
? ? ?
??
?
?
??
(3) 重复消息位方法
? n重复码,码率为 1/n，仅有两个码字 C0和 C1，传送
1比特 (k=1)消息；
? C0=(00… 0),C1=(11… 1)
? n重复码可以检测出任意小于 n/2 个差错的错误图案
? BSC信道,pb≤1/2,n比特传输中发生差错数目越
少，概率越大 (1－ pb)n> pb(1－ pb)n － 1>… >
pbt(1－ pb)n － t>… > pbn
(4) 等重码 /定比码
? 设计码字中的非 0符号个数恒为常数，即 C 由全体重
量恒等于 m 的 n 重向量组成。
? 5中取 3等重码可以检测出全部奇数位差错，对某些码
字的传输则可以检测出部分偶数位差错。
(1) 差错控制的基本方式
? 前向纠错 (FEC),发送端的信道编码器将信息码组编成具有一
定纠错能力的码。接收端信道译码器对接收码字进行译码，若传
输中产生的差错数目在码的纠错能力之内时，译码器对差错进行
定位并加以纠正。
? 自动请求重发 (ARQ),用于检测的纠错码在译码器输出端只
给出当前码字传输是否可能出错的指示，当有错时按某种协议通
过一个反向信道请求发送端重传已发送的码字全部或部分。
? 混合纠错 (HEC),是 FEC与 ARQ方式的结合。发端发送同时具
有自动纠错和检测能力的码组，收端收到码组后，检查差错情况，
如果差错在码的纠错能力以内，则自动进行纠正。如果信道干扰
很严重，错误很多，超过了码的纠错能力，但能检测出来，则经
反馈信道请求发端重发这组数据。
? 编码增益
实际的通信系统，信号的传送需要一定的信噪比 Eb/N0，它直接影
响信道转移概率的大小，误码率 pbe与信噪比 Eb/N0 的关系如图 6.1.9所
示，当采用纠错码之后，达到同样的误码率需要的信噪比减小量称为编
码增益。
编 码 后
编 码 前
p
b e
E
b
/ N
0
0
编 码 增 益
? 线性分组码的编码,
? 线性分组码的编码过程分为两步,
? 把信息序列按一定长度分成若干信息码组，每组由 k
位组成；
? 编码器按照预定的 线性规则 (可由线性方程组规定 )，
把信息码组变换成 n 重 (n>k) 码字，其中 (n－ k) 个
附加码元是由信息码元的 线性运算 产生的。
? 信息码组长 k 位，有 2k 个不同的信息码组，则有 2k 个
码字与它们一一对应。
(1) 一致监督方程
? 编码就是给已知信息码组按预定规则添加监督码元，以构成码字。
? 在 k 个信息码元之后附加 r(r=n－ k) 个监督码元，使每个监督元是
其中某些信息元的模 2和。
? 举例,k=3,r=4，构成 (7,3) 线性分组码 。设码字为
? (C6,C5,C4,C3,C2,C1,C0)
? C6,C5,C4为信息元,C3,C2,C1,C0为监督元，每个码元取, 0”或
,1”
? 监督元可按下面方程组计算
3 6 4
2 6 5 4
1 6 5
0 5 4
( 6.2.1 )
C C C
C C C C
C C C
C C C
???
?
? ? ??
?
???
? ??
?
? 一致监督方程 /一致校验方程：确定信息元得到监督元
规则的一组方程称为监督方程 /校验方程。由于 所有码
字都按同一规则确定,又称为一致监督方程 /一致校验
方程。
? 由于一致监督方程是 线性 的，即监督元和新信源之间是
线性运算关系，所以由线性监督方程所确定的分组码是
线性分组码 。
(2) 举例
? 信息码组 (101)，即 C6=1,C5=0,C4=1
? 代入 监督方程 得,C3=0,C2=0,C1=1,
C0=1
? 由信息码组 (101) 编出的码字为
(1010011)。其它 7个码字如表 6.2.1。
表 6, 2, 1 ( 7,3 ) 分组码 编码表
信息组 对应 码字
0 0 0 0 0 0 0 0 0 0
0 0 1 0 0 1 1 1 0 1
0 1 0 0 1 0 0 1 1 1
0 1 1 0 1 1 1 0 1 0
1 0 0 1 0 0 1 1 1 0
1 0 1 1 0 1 0 0 1 1
1 1 0 1 1 0 1 0 0 1
1 1 1 1 1 1 0 1 0 0
?
?
?
?
?
?
?
???????
???????
???????
???????
00000
00000
0000
00000
045
156
2456
346
CCC
CCC
CCCC
CCC
(3) 一致监督矩阵
? 为了运算方便，将监
督方程写成矩阵形式，
得,
? 系数矩阵 H 的后四列组成一个 (4× 4) 阶单位子阵，用
I4 表示,H 的其余部分用 P 表示
? 推广到一般情况：对 (n,k) 线性分组码，每个码字中的
r(r=n－ k) 个监督元与信息元之间的关系可由下面的线性
方程组确定
? 令上式的系数矩阵为 H，码字行阵列为 C
(2) 线性分组码的生成矩阵
? 在由 (n,k) 线性码构成的线性空间 Vn 的 k 维子空间中，
一定存在 k 个线性独立的码字,g1,g2,…,gk,。码 CI
中其它任何码字 C都可以表为这 k 个码字的一种线性组
合，即
? G中每一行 gi=(gi1,gi2,…,gin ) 都是一个码字；
? 对每一个信息组 m，由矩阵 G都可以求得 (n,k) 线性码
对应的码字。
? (n,k) 线性码的每一个码字都是生成矩阵 G 的行矢量的
线性组合，所以它的 2k 个码字构成了由 G 的行张成的
n 维空间的一个 k 维子空间 Vk。
? 线性系统分组码
通过行初等变换，将 G 化为前 k 列是单位子阵的 标
准形式
? 线性系统分组码,用标准生成矩阵 Gk× n 编成的码
字，前面 k 位为信息数字，后面 r=n－ k 位为校验
字，这种信息数字在前校验数字在后的线性分组码
称为线性系统分组码。
? 当生成矩阵 G 确定之后,(n,k) 线性码也就完全被
确定了，只要找到码的生成矩阵，编码问题也同样
被解决了。
图 6, 2, 1 系 统 码 的 码 字 结 构
信 息 数 字 校 验 数 字
(3) 举例
(7,4) 线性码的生成矩阵为
(4) 生成矩阵与一致监督矩阵的关系
? 由于生成矩阵 G的每一行都是一个码字，所以 G 的每行都满足
Hr× nCTn× 1=0Tr× 1，则有
Hr× nGTn× k=0Tr× k 或 Gk× nHTn× r=0k× r
? 线性系统码的监督矩阵 H 和生成矩阵 G 之间可以直接互换 。
? 举例
已知 (7,4)线性系统码的监督矩阵为
(5) 对偶码
? 对偶码, 对一个 (n,k)线性码 CI，由于 Hr× nGTn× k=0Tr× k，如果
以 G 作监督矩阵，而以 H 作生成矩阵，可构造另一个码 CId，码
CId是一个 (n,n－ k)线性码，称码 CId为原码的对偶码。
? 例如, (7,4)线性码的对偶码是 (7,3)码,
? (7,3)码的监督矩阵 H(7,3)是 (7,4)码生成矩阵 G(7,4)
? (7,3) 码的生成矩阵 G(7,3) 是 (7,4) 码监督矩阵 H(7,4)
(1) 汉明重量和汉明球
? 汉明距离 /距离：在 (n,k)线性码中，两个码字 U,V 之
间对应码元位上符号取值不同的个数，称为码字 U、
V 之间的汉明距离。
? 例如, (7,3) 码的两个码字
U=0011101,V=0100111，它们之间第 2,3,4和 6
位不同。因此，码字 U 和 V 的距离为 4。
? 线性分组码的一个码字对应于 n 维线性空间中的一
点，码字间的距离即为空间中两 对应点的距离。
汉明重量和汉明球
? 汉明球,以码字 C为中心，半径为 t 的汉明球是与 C 的
汉明距离 ≤ t 的向量全体 SC(t)
线性分组码的最小距离、检错和纠错能力
t
V U
d
m i n
图 6, 2, 3 d
m i n
= 5,码 距 和 纠 错 能 力 关 系 示 意 图
? 汉明重量 /码字重量 /W：码字中非 0码元符号的个数，
称为该码字的汉明重量。
? 在二元线性码中，码字重量就是码字中含, 1”的个
数。
? 最小重量 /Wmin,线性分组码 CI中，非 0码字重量最
小值，叫做码 CI的最小重量,
Wmin =min{W(V),V∈ CI,V≠0}
? 最小距离 与 最小重量 的关系, 线性分组码的最小
距离等于它的最小重量。
(2) 最小距离与检、纠错能力
? 一般地说，线性码的最小距离越大，意味着任意码字
间的差别越大，则码的检、纠错能力越强。
? 检错能力,如果一个线性码能检出长度 ≤l 个码元的 任
何错误图样,称码的 检错能力为 l。
? 纠错能力,如果线性码能纠正长度 ≤t 个码元的 任意错
误图样,称码的 纠错能力为 t。
? 最小距离与纠错能力, (n,k) 线性码能纠 t 个错误的充要条
件是码的最小距离为
几何意义,
t
V U
d
m i n
图 6, 2, 3 d
m i n
= 5,码 距 和 纠 错 能 力 关 系 示 意 图
l
V U
d
m i n
图 6, 2, 4 d
m i n
= 4,码 距 和 检 错 能 力 关 系 示 意 图
? 最小距离与检错能力, (n,k) 线性码能够发现 l
个错误的充要条件是码的最小距离为
? dmin=l+1 或 l=dmin－ 1
? 最小距离与检、纠错能力, (n,k) 线性码能纠 t 个错误，
并能发现 l 个错误 (l>t) 的充要条件是码的最小距离为
dmin=t+l+1 或 t+l=dmin－ 1
l
d
m i n
图 6, 2, 5 d
m i n
= 5,t = 1,l = 3 时 码 距 和 检 错 能 力 关 系 示 意 图
t
V
U
d
m i n
l
d
m i n
t
d
m i n
t l
图 6, 2, 6 最 小 码 距 与 检 纠 错 能 力
(1) 伴随式和错误检测
① 用监督矩阵编码，也 用监督矩阵译码,接收到
一个接收字 R 后，校验 H?RT=0T 是否成立,
? 若关系成立，则认为 R 是一个码字；
? 否则判为码字在传输中发生了错误；
② 伴随式 /监督子 /校验子, S=R?HT或 ST=H?RT。
③ 如何纠错？
? 设发送码矢 C=(Cn－ 1,Cn－ 2,…,C0)
? 信道错误图样为 E=(En－ 1,En－ 2,…,E0),
?其中 Ei=0，表示第 i位无错；
?Ei=1，表示第 i位有错。 i=n－ 1,n－ 2,…,0。
? 接收字 R 为
R=(Rn－ 1,Rn－ 2,…,R0)=C+E
=(Cn－ 1+En－ 1,Cn－ 2+En－ 2,…,C0 +E0)
? 求接收字的伴随式（接收字用监督矩阵进行检验）
ST=H?RT=H?(C+E)T=H?CT+H?ET
? 由于 H?CT=0T，所以 ST=H?ET
⑤ 举例, (7,3)码接收矢量 R 的伴随式计算
? 设发送码矢 C=1010011，接收码字 R＝ 1010011，
R与 C相同。
? 若接收字中有一位错误
? 当码元错误多于 1个时
② 标准阵列
? 码矢参数
? 发送码矢：取自于 2k 个码字集合 {C}；
? 接收矢量：可以是 2n 个 n 重中任一个矢量。
? 译码方法
? 把 2n 个 n 重矢量划分为 2k 个互不相交的子
集,使得在每个子集中仅含一个
码矢；
? 根据码矢和子集间一一对应关系，若接收矢量 Rl 落
在子集 Dl中，就把 Rl 译为子集 Dl 含有的码字 Cl；
? 当接收矢量 R 与实际发送码矢在同一子集中时，译
码就是正确的。
? 标准阵列,是对给定的 (n,k) 线性码，将 2n 个 n 重划分
为 2k 个子集的一种方法。
? 标准阵列构造方法
? 先将 2k 个码矢排成一行，作为 标准阵列 的第一行，并
将全 0码矢 C1=(00… 0)放在最左面的位置上；
? 然后在剩下的 (2n－ 2k) 个 n 重中选取一个重量最轻的
n 重 E2 放在全 0码矢 C1 下面，再将 E2 分别和码矢
相加，放在对应码矢下面构成阵列第二行
? 在第二次剩下的 n 重中，选取重量最轻的 n 重 E3，
放在 E2 下面，并将 E3 分别加到第一行各码矢上，得
到第三行；
? …,继续这样做下去，直到全部 n 重用完为止。得到
(n,k) 线性码的标准阵列。
表 6,2,2
码字
C
1
( = 0)
( 陪集首 )
C
2
… C
i
…
E
2
C
2
+ E
2
… C
i
+ E
2
…
E
3
C
2
+ E
3
… C
i
+ E
3
…
… … … … …
禁
用
码
组
…
? 定理 6.2.6 (线性码纠错极限定理 ),二元
(n,k) 线性码能纠 2n－ k 个错误图样。 这 2n－ k
个可纠的错误图样，包括 0矢量在内，即把无
错的情况也看成一个可纠的错误图样。
? 陪集,标准阵列的每一行叫做码的一个陪集。
? 陪集首,每个陪集的第一个元素叫做陪集首。
? 每一列包含 2n－ k 个元素，最上面的是一个码矢，
其它元素是陪集首和该码矢之和，例如第 j 列为
? 若发送码矢为 Cj，信道干扰的错误图样是陪集
首，则接收矢量 R 必在 Dj 中；
? 若错误图样不是陪集首，则接收矢量 R不在 Dj
中，则译成其它码字，造成错误译码；
? 当且仅当错误图样为陪集首时，译码才是正确的。
? 可纠正的错误图样,这 2n－ k 个陪集首称为可纠
正的错误图样。
? 线性码纠错能力与监督元数目的关系, 一个
可纠 t 个错误的线性码必须满足
上式中等式成立时的线性码称为 完备码 。即
? 定义, (n,k) 线性码的所有 2n－ k 个伴随式，在译码过程
中若都用来纠正所有小于等于 个随
机错误，以及部分大于 t 的错误图样，则这种译码方法
称为 完备译码 。
? 限定距离译码,任一个 (n,k) 线性码，能纠正
个随机错误，如果在译码时仅纠正 t’ <t 个错误，而当
错误个数大于 t’时，译码器不进行纠错而仅指出发生了
错误，称这种方法为 限定距离译码 。
? 标准阵列译码 =最小距离译码法 =最佳译码法
? 陪集首是可纠正的错误图样，为了使译码错误概
率最小，应选取出现概率最大的错误图样作陪集
首；
? 重量较轻的错误图样出现概率较大，所以在构造
标准阵列时是选取重量最轻的 n 重作陪集首；
? 这样，当错误图样为陪集首时（可纠的错误图
样），接收矢量与原发送码矢间的距离（等于陪
集首）最小；
? 因此，选择重量最轻的元素作陪集首，按标准阵
列译码就是按最小距离译码；
? 所以标准阵列译码法也是最佳译码法。
? 定理 6.2.7：在标准阵列中，一个陪集的所有
2k 个 n 重有相同的伴随式，不同的陪集伴随
式互不相同。
(1)不可检错误概率 pud
? 令 Ai为码的重量分布，表示重量为 i的码字个
数，由于 仅当错误图样与码矢集合中的非 0
码矢相同时，才不能检出错误,所以
线性分组码的性能
(2) 译码错误概率 pwe
? 正确译码概率 pwc：纠正小于等于 t个差错的概率
? 译码错误概率 pwe为
? 汉明码是汉明于 1950年提出的纠一个错误的线性码，也
是第一个纠错码。由于它编码简单，因而是在通信系统
和数据存储系统中得到广泛应用的一类线性码。
? 汉明码的结构参数,
? 纠一个错误的线性码，其最小距离 dmin=3 ；监督矩
阵任意两列线性无关 / H 的任两列互不相同 ；没有全
0的列。
? 监督元个数 n－ k=r； H 阵中每列有 r 个元素，至多
可构成 2r－ 1种互不相同的非 0列。
汉明码
? 汉明码监督矩阵构成的两种方式
?构成 H 阵的标准形式,H=[Q Im]，其中 Im 为 m
阶单位子阵，子阵 Q 是构造 Im 后剩下的列任意排
列。用这种形式的 H 阵编出的汉明码是系统码。
?按 m重表示的二进制顺序排列。按这种形式 H 阵编
出的码是非系统码。当发生可纠的单个错误时，伴
随式为 H 阵中对应的列，所以伴随式的二进制数值
就是错误位置号，有时这种码译码比较方便。
(1) 研究码限的意义
? 研究码的纠错能力，也就是分析码的 n,k,d 之间的关系，
不仅能从理论上指出哪些码可以构造出，哪些码不能构
造出，而且也为工程实验提供了对各种码性能估计的理
论依据。
? 研究码的纠错能力始终是编码理论中一个重要的课题。
? 在纠错编码实现上总希望在尽可能小的 n 和 r 条件下获
得尽可能大的 k,d 或 t。
? 满足码限的码称为最佳码。
线性分组码的码限
(2) 三个码限
? 普罗特金 (Plotkin)限 (P限 )
对任意二元 (n,k,d) 码满足
? 汉明限 (H限 )
对任意二元 (n,k,2t+1) 码满足
? 瓦尔沙莫夫－吉尔伯特 (Varshamov-Gilbert)(V-G限 )
存在某个二元 (n,k,d)码满足
? 在 n 充分大时各个
码限的关系曲线如
图 6.2.33所示。图
中以 V-G 限为下限，
H 限和 P 限为上限
所围的区域 (兰色区
域 )是好码（满足所
有上述码限的
(n,k,d)码）。
标之一，它有以下几种不同的定义。
? 码元差错率,指在传输的码元总数中发生差错的码
元数所占的比例（平均值），简称 误码率 。
? 比特差错率 /比特误码率,指在传输的比特总数中发
生差错的比特数所占的比例（平均值）。 在二进制
传输系统中，码元差错率就是比特差错率 。
? 码组差错率,指在传输的码组总数中发生差错的码
组数所占的比例（平均值）。
第五节 纠错编码的基本思想
? 根据不同的应用场合对差错率有不同的要求。
? 在电报传送时，允许的比特差错率约为 10－ 4～
10－ 5；
? 计算机数据传输，一般要求比特差错率小于 10－
8～ 10－ 9；
? 在遥控指令和武器系统的指令系统中，要求有更
小的误比特率或码组差错率。
采用信道编码的数字通信系统
? 在某些情况下，信道的改善可能较困难或者不经济，这
就要求采用信道编码，以便满足系统差错率的技术指标
要求。
? 信道编码为系统设计者提供了一个降低系统差错率的措
施。采用信道编码后的数字通信系统可用图 6.1.2所示。
信
源
编
码
解
调
器
信
源
图 6, 1, 2 有 信 道 编 码 的 数 字 通 信 系 统 框 图
调
制
器
传
输
媒
介
信
宿
信
源
译
码
信
道
译
码
信
道
编
码
C Rm m '
(1) 编码信道, 是研究纠错编码和译码的一种模型。 如
图 6.1.3所示。
? 编码信道
? 无线通信中的发射机、天线、自由空间、接收机等的全体；
? 有线通信中的如调制解调器、电缆等的全体；
? Internet 网的多个路由器、节点、电缆、底层协议等的全体；
? 计算机的存储器（如磁盘等）的全体。
信 道 译 码信 道 编 码 编 码 信 道
消 息 m 码 字 C
接 收 向 量 R
消 息 m ’
? 二进制编码信道模型,
R =C+E (mod 2)
? E：随机变量；
? 差错图案,随机序列 (Ei)；
? 称 E=(E0,E1,…,En-1)中 Ei=1为第 i
位上的一个随机错误；
? 第 i至第 j位之间有很多错误时，
称为一个 j－ i+1长的突发错误。
图 6, 1, 4 B S C 转 移 概 率
1 － p
b
0 0
11
1 － p
b
p
b
p
b
图 6, 1, 5 B S C 编 码 信 道
1
C
E
R
(2) 信道编码的基本思想
? 信道编码的对象,是信源编码器输出的信息序列 m。
通常是二元符号 1,0组成的序列。
? 信道编码的基本思想
? 按一定规则给数字序列 m增加一些多余的码元，使
不具有规律性的信息序列 m 变换为具有某种规律
性的数码序列 C；
? 码序列中的 信息序列码元 与 多余码元 之间是相关的；
? 信道译码器利用这种 预知的 编码规则译码。检验接
收到的数字序列 R 是否符合 既定的 规则，从而发
现 R 中是否有错，或者纠正其中的差错；
? 码元的组成及其它们之间的关系
? 信息码组, 数字序列 m 总是以 k 个码元为一组
传输，称这 k 个码元的码组为信息码组。例如遥控
系统中的每个指令字，计算机中的每个字节。
? 码组 /码字, 信道编码器按一定的规则对每个信息
码组附加一些多余的码元，构成了 n 个码元的码组。
? 监督码元 /监督元, 附加的 (n－ k) 个码元称为该
码组的监督码元或监督元。
? (3) 纠错编码的分类
? 分组码,编码的规则仅局限于本码组之内，本码组的监
督元仅和本码组的信息元相关。
信息码组由 k 个二进制码元组成，共有 2k 个不同的信息
码组；
附加 n－ k个码元，每个监督元取值与该信息码组的 k个码
元有关；
编码器输出长度 n；
这 2k 个码字的集合称为 (n,k) 分组码；
? 卷积码,本码组的监督元不仅和本码组的信息元相关，
而且还与本码组相邻的前 n－ 1 个码组的信息元相关。
? 是否可用线性方程组来表示
? 线性码,编码规则可以用线性方程表示；
? 非线性码,编码规则不能用线性方程表示；
? 按码字的结构分
? 系统码,前 k 个码元与信息码组一致；
? 非系统码,没有系统码的特性。
? 按纠正差错的类型可分为 纠正随机错误的码 和 纠正突
发错误的码 ；
? 按码字中每个码元的取值可分为 二进制码 和 多进制码 。
(1)偶（或奇）校验方法
? p 为偶校验位
m0+m1+m2+… +mk－ 1+p=0 (mod 2)
? 则 C =(m0,m1,m2,…,mk－ 1,p) 为一个偶校验码字。
? C 中一定有偶数个, 1”
? 当差错图案 E 中有奇数个, 1”，即 R 中有奇数个位有错
时，可以通过校验方程是否为 0判断有无可能传输差错。
? (2)多个奇偶校验位
? 一个校验位可以由信息位的部分或全部按校验方程产生；
? 例如 C 是一个对阵列消息进行垂直与水平校验以及总校验的
码字；
? 其码率为
? 当校验位数增加时，
可以检测到差错图案
种类数也增加，同时
码率减小。
0,0 0,1 0,
1,0 1,1 1,
,0,1,
1
,,
0
1
,,
0
11
,,,
00
1
C
1( 1 )
1
m od 2,0,1,,1
m od 2,0,1,,1
m od 2
tt
s s t s t
s s t s t
t
i t i j
j
s
s j i j
i
st
s t i t s j
ij
m m p
st
R
st m m pst s t
st p p p
p m i s
p m j t
p m m
?
? ? ? ?
?
?
?
?
?
??
??
??
??
??
? ? ?
?? ??? ? ?
?
??
??
? ? ?
? ? ?
??
?
?
??
(3) 重复消息位方法
? n重复码,码率为 1/n，仅有两个码字 C0和 C1，传送
1比特 (k=1)消息；
? C0=(00… 0),C1=(11… 1)
? n重复码可以检测出任意小于 n/2 个差错的错误图案
? BSC信道,pb≤1/2,n比特传输中发生差错数目越
少，概率越大 (1－ pb)n> pb(1－ pb)n － 1>… >
pbt(1－ pb)n － t>… > pbn
(4) 等重码 /定比码
? 设计码字中的非 0符号个数恒为常数，即 C 由全体重
量恒等于 m 的 n 重向量组成。
? 5中取 3等重码可以检测出全部奇数位差错，对某些码
字的传输则可以检测出部分偶数位差错。
(1) 差错控制的基本方式
? 前向纠错 (FEC),发送端的信道编码器将信息码组编成具有一
定纠错能力的码。接收端信道译码器对接收码字进行译码，若传
输中产生的差错数目在码的纠错能力之内时，译码器对差错进行
定位并加以纠正。
? 自动请求重发 (ARQ),用于检测的纠错码在译码器输出端只
给出当前码字传输是否可能出错的指示，当有错时按某种协议通
过一个反向信道请求发送端重传已发送的码字全部或部分。
? 混合纠错 (HEC),是 FEC与 ARQ方式的结合。发端发送同时具
有自动纠错和检测能力的码组，收端收到码组后，检查差错情况，
如果差错在码的纠错能力以内，则自动进行纠正。如果信道干扰
很严重，错误很多，超过了码的纠错能力，但能检测出来，则经
反馈信道请求发端重发这组数据。
? 编码增益
实际的通信系统，信号的传送需要一定的信噪比 Eb/N0，它直接影
响信道转移概率的大小，误码率 pbe与信噪比 Eb/N0 的关系如图 6.1.9所
示，当采用纠错码之后，达到同样的误码率需要的信噪比减小量称为编
码增益。
编 码 后
编 码 前
p
b e
E
b
/ N
0
0
编 码 增 益
? 线性分组码的编码,
? 线性分组码的编码过程分为两步,
? 把信息序列按一定长度分成若干信息码组，每组由 k
位组成；
? 编码器按照预定的 线性规则 (可由线性方程组规定 )，
把信息码组变换成 n 重 (n>k) 码字，其中 (n－ k) 个
附加码元是由信息码元的 线性运算 产生的。
? 信息码组长 k 位，有 2k 个不同的信息码组，则有 2k 个
码字与它们一一对应。
(1) 一致监督方程
? 编码就是给已知信息码组按预定规则添加监督码元，以构成码字。
? 在 k 个信息码元之后附加 r(r=n－ k) 个监督码元，使每个监督元是
其中某些信息元的模 2和。
? 举例,k=3,r=4，构成 (7,3) 线性分组码 。设码字为
? (C6,C5,C4,C3,C2,C1,C0)
? C6,C5,C4为信息元,C3,C2,C1,C0为监督元，每个码元取, 0”或
,1”
? 监督元可按下面方程组计算
3 6 4
2 6 5 4
1 6 5
0 5 4
( 6.2.1 )
C C C
C C C C
C C C
C C C
???
?
? ? ??
?
???
? ??
?
? 一致监督方程 /一致校验方程：确定信息元得到监督元
规则的一组方程称为监督方程 /校验方程。由于 所有码
字都按同一规则确定,又称为一致监督方程 /一致校验
方程。
? 由于一致监督方程是 线性 的，即监督元和新信源之间是
线性运算关系，所以由线性监督方程所确定的分组码是
线性分组码 。
(2) 举例
? 信息码组 (101)，即 C6=1,C5=0,C4=1
? 代入 监督方程 得,C3=0,C2=0,C1=1,
C0=1
? 由信息码组 (101) 编出的码字为
(1010011)。其它 7个码字如表 6.2.1。
表 6, 2, 1 ( 7,3 ) 分组码 编码表
信息组 对应 码字
0 0 0 0 0 0 0 0 0 0
0 0 1 0 0 1 1 1 0 1
0 1 0 0 1 0 0 1 1 1
0 1 1 0 1 1 1 0 1 0
1 0 0 1 0 0 1 1 1 0
1 0 1 1 0 1 0 0 1 1
1 1 0 1 1 0 1 0 0 1
1 1 1 1 1 1 0 1 0 0
?
?
?
?
?
?
?
???????
???????
???????
???????
00000
00000
0000
00000
045
156
2456
346
CCC
CCC
CCCC
CCC
(3) 一致监督矩阵
? 为了运算方便，将监
督方程写成矩阵形式，
得,
? 系数矩阵 H 的后四列组成一个 (4× 4) 阶单位子阵，用
I4 表示,H 的其余部分用 P 表示
? 推广到一般情况：对 (n,k) 线性分组码，每个码字中的
r(r=n－ k) 个监督元与信息元之间的关系可由下面的线性
方程组确定
? 令上式的系数矩阵为 H，码字行阵列为 C
(2) 线性分组码的生成矩阵
? 在由 (n,k) 线性码构成的线性空间 Vn 的 k 维子空间中，
一定存在 k 个线性独立的码字,g1,g2,…,gk,。码 CI
中其它任何码字 C都可以表为这 k 个码字的一种线性组
合，即
? G中每一行 gi=(gi1,gi2,…,gin ) 都是一个码字；
? 对每一个信息组 m，由矩阵 G都可以求得 (n,k) 线性码
对应的码字。
? (n,k) 线性码的每一个码字都是生成矩阵 G 的行矢量的
线性组合，所以它的 2k 个码字构成了由 G 的行张成的
n 维空间的一个 k 维子空间 Vk。
? 线性系统分组码
通过行初等变换，将 G 化为前 k 列是单位子阵的 标
准形式
? 线性系统分组码,用标准生成矩阵 Gk× n 编成的码
字，前面 k 位为信息数字，后面 r=n－ k 位为校验
字，这种信息数字在前校验数字在后的线性分组码
称为线性系统分组码。
? 当生成矩阵 G 确定之后,(n,k) 线性码也就完全被
确定了，只要找到码的生成矩阵，编码问题也同样
被解决了。
图 6, 2, 1 系 统 码 的 码 字 结 构
信 息 数 字 校 验 数 字
(3) 举例
(7,4) 线性码的生成矩阵为
(4) 生成矩阵与一致监督矩阵的关系
? 由于生成矩阵 G的每一行都是一个码字，所以 G 的每行都满足
Hr× nCTn× 1=0Tr× 1，则有
Hr× nGTn× k=0Tr× k 或 Gk× nHTn× r=0k× r
? 线性系统码的监督矩阵 H 和生成矩阵 G 之间可以直接互换 。
? 举例
已知 (7,4)线性系统码的监督矩阵为
(5) 对偶码
? 对偶码, 对一个 (n,k)线性码 CI，由于 Hr× nGTn× k=0Tr× k，如果
以 G 作监督矩阵，而以 H 作生成矩阵，可构造另一个码 CId，码
CId是一个 (n,n－ k)线性码，称码 CId为原码的对偶码。
? 例如, (7,4)线性码的对偶码是 (7,3)码,
? (7,3)码的监督矩阵 H(7,3)是 (7,4)码生成矩阵 G(7,4)
? (7,3) 码的生成矩阵 G(7,3) 是 (7,4) 码监督矩阵 H(7,4)
(1) 汉明重量和汉明球
? 汉明距离 /距离：在 (n,k)线性码中，两个码字 U,V 之
间对应码元位上符号取值不同的个数，称为码字 U、
V 之间的汉明距离。
? 例如, (7,3) 码的两个码字
U=0011101,V=0100111，它们之间第 2,3,4和 6
位不同。因此，码字 U 和 V 的距离为 4。
? 线性分组码的一个码字对应于 n 维线性空间中的一
点，码字间的距离即为空间中两 对应点的距离。
汉明重量和汉明球
? 汉明球,以码字 C为中心，半径为 t 的汉明球是与 C 的
汉明距离 ≤ t 的向量全体 SC(t)
线性分组码的最小距离、检错和纠错能力
t
V U
d
m i n
图 6, 2, 3 d
m i n
= 5,码 距 和 纠 错 能 力 关 系 示 意 图
? 汉明重量 /码字重量 /W：码字中非 0码元符号的个数，
称为该码字的汉明重量。
? 在二元线性码中，码字重量就是码字中含, 1”的个
数。
? 最小重量 /Wmin,线性分组码 CI中，非 0码字重量最
小值，叫做码 CI的最小重量,
Wmin =min{W(V),V∈ CI,V≠0}
? 最小距离 与 最小重量 的关系, 线性分组码的最小
距离等于它的最小重量。
(2) 最小距离与检、纠错能力
? 一般地说，线性码的最小距离越大，意味着任意码字
间的差别越大，则码的检、纠错能力越强。
? 检错能力,如果一个线性码能检出长度 ≤l 个码元的 任
何错误图样,称码的 检错能力为 l。
? 纠错能力,如果线性码能纠正长度 ≤t 个码元的 任意错
误图样,称码的 纠错能力为 t。
? 最小距离与纠错能力, (n,k) 线性码能纠 t 个错误的充要条
件是码的最小距离为
几何意义,
t
V U
d
m i n
图 6, 2, 3 d
m i n
= 5,码 距 和 纠 错 能 力 关 系 示 意 图
l
V U
d
m i n
图 6, 2, 4 d
m i n
= 4,码 距 和 检 错 能 力 关 系 示 意 图
? 最小距离与检错能力, (n,k) 线性码能够发现 l
个错误的充要条件是码的最小距离为
? dmin=l+1 或 l=dmin－ 1
? 最小距离与检、纠错能力, (n,k) 线性码能纠 t 个错误，
并能发现 l 个错误 (l>t) 的充要条件是码的最小距离为
dmin=t+l+1 或 t+l=dmin－ 1
l
d
m i n
图 6, 2, 5 d
m i n
= 5,t = 1,l = 3 时 码 距 和 检 错 能 力 关 系 示 意 图
t
V
U
d
m i n
l
d
m i n
t
d
m i n
t l
图 6, 2, 6 最 小 码 距 与 检 纠 错 能 力
(1) 伴随式和错误检测
① 用监督矩阵编码，也 用监督矩阵译码,接收到
一个接收字 R 后，校验 H?RT=0T 是否成立,
? 若关系成立，则认为 R 是一个码字；
? 否则判为码字在传输中发生了错误；
② 伴随式 /监督子 /校验子, S=R?HT或 ST=H?RT。
③ 如何纠错？
? 设发送码矢 C=(Cn－ 1,Cn－ 2,…,C0)
? 信道错误图样为 E=(En－ 1,En－ 2,…,E0),
?其中 Ei=0，表示第 i位无错；
?Ei=1，表示第 i位有错。 i=n－ 1,n－ 2,…,0。
? 接收字 R 为
R=(Rn－ 1,Rn－ 2,…,R0)=C+E
=(Cn－ 1+En－ 1,Cn－ 2+En－ 2,…,C0 +E0)
? 求接收字的伴随式（接收字用监督矩阵进行检验）
ST=H?RT=H?(C+E)T=H?CT+H?ET
? 由于 H?CT=0T，所以 ST=H?ET
⑤ 举例, (7,3)码接收矢量 R 的伴随式计算
? 设发送码矢 C=1010011，接收码字 R＝ 1010011，
R与 C相同。
? 若接收字中有一位错误
? 当码元错误多于 1个时
② 标准阵列
? 码矢参数
? 发送码矢：取自于 2k 个码字集合 {C}；
? 接收矢量：可以是 2n 个 n 重中任一个矢量。
? 译码方法
? 把 2n 个 n 重矢量划分为 2k 个互不相交的子
集,使得在每个子集中仅含一个
码矢；
? 根据码矢和子集间一一对应关系，若接收矢量 Rl 落
在子集 Dl中，就把 Rl 译为子集 Dl 含有的码字 Cl；
? 当接收矢量 R 与实际发送码矢在同一子集中时，译
码就是正确的。
? 标准阵列,是对给定的 (n,k) 线性码，将 2n 个 n 重划分
为 2k 个子集的一种方法。
? 标准阵列构造方法
? 先将 2k 个码矢排成一行，作为 标准阵列 的第一行，并
将全 0码矢 C1=(00… 0)放在最左面的位置上；
? 然后在剩下的 (2n－ 2k) 个 n 重中选取一个重量最轻的
n 重 E2 放在全 0码矢 C1 下面，再将 E2 分别和码矢
相加，放在对应码矢下面构成阵列第二行
? 在第二次剩下的 n 重中，选取重量最轻的 n 重 E3，
放在 E2 下面，并将 E3 分别加到第一行各码矢上，得
到第三行；
? …,继续这样做下去，直到全部 n 重用完为止。得到
(n,k) 线性码的标准阵列。
表 6,2,2
码字
C
1
( = 0)
( 陪集首 )
C
2
… C
i
…
E
2
C
2
+ E
2
… C
i
+ E
2
…
E
3
C
2
+ E
3
… C
i
+ E
3
…
… … … … …
禁
用
码
组
…
? 定理 6.2.6 (线性码纠错极限定理 ),二元
(n,k) 线性码能纠 2n－ k 个错误图样。 这 2n－ k
个可纠的错误图样，包括 0矢量在内，即把无
错的情况也看成一个可纠的错误图样。
? 陪集,标准阵列的每一行叫做码的一个陪集。
? 陪集首,每个陪集的第一个元素叫做陪集首。
? 每一列包含 2n－ k 个元素，最上面的是一个码矢，
其它元素是陪集首和该码矢之和，例如第 j 列为
? 若发送码矢为 Cj，信道干扰的错误图样是陪集
首，则接收矢量 R 必在 Dj 中；
? 若错误图样不是陪集首，则接收矢量 R不在 Dj
中，则译成其它码字，造成错误译码；
? 当且仅当错误图样为陪集首时，译码才是正确的。
? 可纠正的错误图样,这 2n－ k 个陪集首称为可纠
正的错误图样。
? 线性码纠错能力与监督元数目的关系, 一个
可纠 t 个错误的线性码必须满足
上式中等式成立时的线性码称为 完备码 。即
? 定义, (n,k) 线性码的所有 2n－ k 个伴随式，在译码过程
中若都用来纠正所有小于等于 个随
机错误，以及部分大于 t 的错误图样，则这种译码方法
称为 完备译码 。
? 限定距离译码,任一个 (n,k) 线性码，能纠正
个随机错误，如果在译码时仅纠正 t’ <t 个错误，而当
错误个数大于 t’时，译码器不进行纠错而仅指出发生了
错误，称这种方法为 限定距离译码 。
? 标准阵列译码 =最小距离译码法 =最佳译码法
? 陪集首是可纠正的错误图样，为了使译码错误概
率最小，应选取出现概率最大的错误图样作陪集
首；
? 重量较轻的错误图样出现概率较大，所以在构造
标准阵列时是选取重量最轻的 n 重作陪集首；
? 这样，当错误图样为陪集首时（可纠的错误图
样），接收矢量与原发送码矢间的距离（等于陪
集首）最小；
? 因此，选择重量最轻的元素作陪集首，按标准阵
列译码就是按最小距离译码；
? 所以标准阵列译码法也是最佳译码法。
? 定理 6.2.7：在标准阵列中，一个陪集的所有
2k 个 n 重有相同的伴随式，不同的陪集伴随
式互不相同。
(1)不可检错误概率 pud
? 令 Ai为码的重量分布，表示重量为 i的码字个
数，由于 仅当错误图样与码矢集合中的非 0
码矢相同时，才不能检出错误,所以
线性分组码的性能
(2) 译码错误概率 pwe
? 正确译码概率 pwc：纠正小于等于 t个差错的概率
? 译码错误概率 pwe为
? 汉明码是汉明于 1950年提出的纠一个错误的线性码，也
是第一个纠错码。由于它编码简单，因而是在通信系统
和数据存储系统中得到广泛应用的一类线性码。
? 汉明码的结构参数,
? 纠一个错误的线性码，其最小距离 dmin=3 ；监督矩
阵任意两列线性无关 / H 的任两列互不相同 ；没有全
0的列。
? 监督元个数 n－ k=r； H 阵中每列有 r 个元素，至多
可构成 2r－ 1种互不相同的非 0列。
汉明码
? 汉明码监督矩阵构成的两种方式
?构成 H 阵的标准形式,H=[Q Im]，其中 Im 为 m
阶单位子阵，子阵 Q 是构造 Im 后剩下的列任意排
列。用这种形式的 H 阵编出的汉明码是系统码。
?按 m重表示的二进制顺序排列。按这种形式 H 阵编
出的码是非系统码。当发生可纠的单个错误时，伴
随式为 H 阵中对应的列，所以伴随式的二进制数值
就是错误位置号，有时这种码译码比较方便。
(1) 研究码限的意义
? 研究码的纠错能力，也就是分析码的 n,k,d 之间的关系，
不仅能从理论上指出哪些码可以构造出，哪些码不能构
造出，而且也为工程实验提供了对各种码性能估计的理
论依据。
? 研究码的纠错能力始终是编码理论中一个重要的课题。
? 在纠错编码实现上总希望在尽可能小的 n 和 r 条件下获
得尽可能大的 k,d 或 t。
? 满足码限的码称为最佳码。
线性分组码的码限
(2) 三个码限
? 普罗特金 (Plotkin)限 (P限 )
对任意二元 (n,k,d) 码满足
? 汉明限 (H限 )
对任意二元 (n,k,2t+1) 码满足
? 瓦尔沙莫夫－吉尔伯特 (Varshamov-Gilbert)(V-G限 )
存在某个二元 (n,k,d)码满足
? 在 n 充分大时各个
码限的关系曲线如
图 6.2.33所示。图
中以 V-G 限为下限，
H 限和 P 限为上限
所围的区域 (兰色区
域 )是好码（满足所
有上述码限的
(n,k,d)码）。
