第五章 信道编码
?信道编码的基本概念和基本原理
?线性分组码
?循环码、卷积码和秩距离码
?突发错误的纠正
?级连码、交织码及 TCM码
?纠错码的应用
信
源
检错、
纠错
编码器
编码
信道
检错、
纠错
译码器
信
宿
噪声源
数字通信系统简化模型
? ?M ??C ??R ? ??M
??E
编码信道：包括信道编码器、实际信道、信道译码器。
该模型是研究信道纠错编码和译码的模型，集中研究通信
可靠性。
通信可靠性问题,消息通过信道传输的时候，如何选择编
码方案来减少差错。首先与信道统计特性有关，其次与编
码方法、译码方法也有关系。
第一节 信道编码的基本概念和基本原理
信道是信号从信源传送到信宿的通路 。
1) 由于信道有干扰, 使得传送的数据流 (码流 )中产生误码 。
2) 误码的处理技术有纠错, 交织, 线性内插等 。
3) 信道编码的 目的 是提高信息传输或通信的可靠性 。
4) 信道编码的 任务 是降低误码率, 使系统具有一定的纠错
能力和抗干扰能力, 提高数据传输效率 。
5) 信道编码的 过程 是在 源数据码流 中加插一些码元, 达到
在接收端进行检错和纠错的目的 。
6) 在带宽固定的信道中, 总的传送码率是固定的, 由于信
道编码增加了数据量, 其结果只能是以降低传送有用信
息码率为代价了 。
一、信道编码概念
目的,降低错误译码概率 PE。
对象,信息序列 （ 设码元间彼此无关且等概出现 ） 。
方法,在传输的信息码之中按一定规律产生一些附加
数字，经信道传输，在传输中若码字出现错误，
收端能利用编码规律发现码的内在相关性受到破
坏，从而按一定的译码规则自动纠正或发现错误，
降低误码率。
一、信道编码概念
实质,在保持一定传输信息速率条件下，通过增
加一定的码元多余度，使输出的码字具有特定
的相关性，从而使收端易于发现或纠正由于信
道噪声而引起的传输错误。
q=rk个
k维矢量
禁用码组
许用码组
n重序列
rn个
信道
编码器
M C
校验元
rk个
C0
C1
Ci
┋
Cj
┋
C2k-1
收端
传输模式
PE～信道传输特征
PE～译码方法
C2k
┋
Ci’
┋
C2n-1
许
用
码
组
禁
用
码
组
C0
C1
┋
Ci
┋
C2k-1
许
用
码
组
发端
二、信道编码的基本原理（检错、纠错原理）
寻找一种编码方法，使所加的监督码元最少，而检错纠错能
力又高，且便于实现。
理论基础：香农第二定理
对于一个给定的有扰信道，如信道容量为 C，只要发送端
以低于 C的速率 R发送信息，则一定存在一种编码方法，
使编码错误概率 p随码长 n的增加，按指数下降到任意小的
值。也就是说，可以通过编码使通信过程实际上不发生错
误，或使错误控制在允许数值之下。即：
[]n E RPe ??
信息传输率
E(R)
码长
P?exp{-nE )}
※ E (R)意义,n给定，则最佳编码的 P上界既定。
１,适用于 DMC，有记忆信道及连续信道 ;
0RC ER C N P
RC ?
? ? ????
? ??
?
时, 足 够 长, 必 存 在 最 佳 编 码, 使
输 入 等 概, 时, 最 佳 编 码 也 存 在 （ 有 效 性, 可 靠 性 最 优 ）
()
()
2 2 ( 0)
2 2 ( 0)
N R N C
N R N C
R C M
R C M
?
?
?
?
?
?
?? ? ? ?
?? ? ? ?
?
等 价 于 存 在 最 佳
等 价 于 不 存 在 最 佳
２,PE→0,可靠编码条件：
有噪信道编码逆定理
设离散无记忆信道［ X,p(y|x),Y］的信道容
量为 C,R是信息传输率，当 R>C时，则无论码长 N
多长，总找不到一种编码，使译码的平均错误概率
任意小。
表述二,设某信道有 r个输入符号,s个输出符号，
信道容量为 C。只要码长 N足够长，总可以在输入
的 rN个符号的集合中找到 M（ M?2N(C-?),?为任意
小的正数）个码字，分别代表 M个等可能性的消
息，组成一个码以及相应的译码规则，使信道输
出端的平均错误译码概率 PE达到任意小。
1) 差错类型
1° 随机错误, 数据流中发生的错误彼此无关,表现为错
误之间的无相关性,
2° 突发错误, 数据流中一个错误的发生,带来一连串错
误的发生,表现为误错之间的相关性,
2) 差错控制的途径
1° 增加信道容量措施
扩展带宽、提高发送功率、降低噪声
2° 编码措施
减小码率,增加码长、交织器,纠错码
3° 传输方式措施
重复发送,反馈 重发,多进制信号
三、差错控制
? 需要双向信道，和前向信道有相同的通信容。
? 引入较大的停顿（不实时）。
? 可以纠正任何错误。
1° 反馈检验法 (IRQ)
分组 存储 发 收
收 发
kI?kI
3) 差错控制的分类
2° 检错重发法（ ARQ）
? 自动请求重发
? 也需要反向信道，但容量可以降低，也会引
入停顿
检错
编码 存储 发 收
收 发
kI?kI
检错
译码
3° 前向纠错（ FEC）
? 不需要双向信道
? 不会引入停顿
? 靠纠错编码
3° 混合纠错检错（ HEC）
4) 差错控制编码的基本原理
? 如用三位二进制编码来代表八个字母
? 000 A 100 E
? 001 B 101 F
? 010 C 110 G
? 011 D 111 H
? 不管哪一位发生错误，都会使传输字母错误
? 如用三位字母传四个字母
? 000 A 011 B 101 C 110
D
? 发生一位错误，准用码字将变成禁用码字，接收端就
能知道出错，但是不能纠错。
?如用三位字母传二个字母
000 A 111 B
? 检三个错误，纠正一个错误。大数法则纠错。
?结论
? 具有检错或纠错的码组，其所用的比特数必须
大于信息码组原来的比特数
－ >引入余度。
5）、检错、纠错能力
?码重 (weight)
一个码组中,1”的数目
?码距 (distance)
两个码组之间对应位置上 1,0不同的位数，又叫汉明
(Hamming)距。
10 1 1 0 码重,3
01 1 0 0 2 距离,3
? 为检查出 个错误，要求最小码距为
? 为纠正 个错误，要求最小码距为
? 为纠正 个错误，同时检查出 个错误，要求最小码
距为
? 纠正 个错误和 p个删除，要求最小码距为：t
m in 1dl??
m in 21dt??
m i n 1 ( )d l t l t? ? ? ?
检错、纠错能力
l
t
t
l
12m i n ??? ptd
? 按功能分
?检错码
?纠错码
?纠删码（发现不可纠正的错误时，可发出指示或删除）
? 按信息码元和监督码元之间的校验关系分
?线性码
?非线性码
? 按信息码元和监督码元之间的约束方式分
?分组码
?卷积码
6）、差错控制编码分类
卷积码
非线性码 线性码
纠错码
分组码
循环码 非循环码
纠随机
错误码
纠突发
错误码
纠随机和突
发错误码
纠同步
错误码
纠错码分类
第二节 线性分组码
? 表示,(n,k)
n, 帧（组）长 k/n, 编码效率
? 特点
? 监督码只用来监督本帧中的信息位
? 分类
? 线性码 － 信息码与监督码之间为线性关系
? 非线性码 － 不存在线性关系
01221 aaaaa nn L??
信息位 监督位
一、基本概念
? 分组码的监督方程
? 矩阵形式
? ?6 5 4 3 2 1 0
1 1 1 0 1 0 0 0
1 1 0 1 0 1 0 0
1 0 1 1 0 0 1 0
T
a a a a a a a
? ? ? ?
? ? ? ??
? ? ? ?
? ? ? ?? ? ? ?
监督方程( 校验方程)
ccc
ccc
cccc
ccc
为监督元c,c,c,c为信息元,,c,c,c
)c,c,c,c,c,c,(cc
450
561
4562
463
0123456
0123456
?
?
?
?
?
?
?
?
??
??
???
??
?
? 监督矩阵
? H矩阵称为典型形式，各行一定是线性无关的。
而一个非典型形式的经过初等变换运算可以化
成典型形式，通过监督矩阵可以知道监督码和
信息码的监督关系。
],[
1001101
0101011
0010111
rrkrnr IQH ??? ?
?
?
?
?
?
?
?
?
?
?
?
? 生成矩阵
，通过监督矩阵可以得到生成码组。
? 如果输入码组为 A=0011,编码器输出码字
为,C=AG
TQP?
? ? ? ? ? ?
1 0 0 0 1 1 1
0 1 0 0 1 1 0
0 0 1 1 0 0 1 1 0 0 1 1 1 1 0
0 0 1 0 1 0 1
0 0 0 1 0 1 1
AG
??
??
? ? ? ? ?
??
??
?
?
?
?
?
?
?
?
?
?
?
?
?
?
??
110
101
011
111
1000
0100
0010
0001
],[ PIG
k
? 由这种方式得到的生成矩阵称为 典型生成矩阵,
由它产生的分组码必定为 系统码，也就是信息码
字保持不变，监督位附加其后,每行一定是线性
无关的，每行都是一个生成码组。
0 0 1 1 0 0 1 1 1 1 0?
定理：设二元线性分组码 CI是由监督矩阵 H所定义的，若 X和
Y为其中的任意两个码字，则 X+Y也是 CI中的一个码字。 —
—线性码的封闭性
对偶码,以 G作监督矩阵，以 H为生成矩阵，得到另
一个码 CJ—— （ n,n-k）线性码。 CJ为原码 CI的对
偶码。它们的码矢彼此正交，两个子空间是互为零
化空间。
缩短码,将分组码最左边 i位为 0的消息和对应的码
字挑选出来，把最左边的 0删去，构成（ n-i,k-i）
线性分组码。纠错检错能力与原码相同。
缩短码的监督矩阵：（ n,k）一致监督矩阵删去最左边一列。
缩短码的生成矩阵,（ n,k）生成矩阵删去最左边一列和最上面的一行。
二、汉明码 ——能 纠正单个错误 的线性分组码
3:
:
)(
1
1
:
1
1
:
),,(:
m i n
?
??
??
?
?
?
?
?
?
?
?
d
knr
kn
m
m
k
m
m
n
dkn
kn
kn
最小距离
监督位数
信息位数
码长
表示
汉明码的监督矩阵 H的列为所有非零的 r维向量组成，一
旦 r给定，就可以构造出具体的（ n,k）汉明码。
例：构造一个二元的（ 7,4,3）汉明码。
分析,r=n-k=3,除 0以外的所有 2r个元素构成矩阵 H
的列。
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
1001011
0101101
0011110
H
][ Q IH
1010101
1100110
1111000
H
:监 督 矩 阵 为
r
即
?
?
?
?
?
?
?
?
?
?
?
?
??
?
?
?
?
?
?
?
?
?
?
?
111
011
101
110
1011
1101
1110
T
QP
Q
?
?
?
?
?
????
????
????
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
0cccc
0cccc
0cccc
0
c
c
c
c
c
c
c
1001011
0101101
0011110
0由H C
6310
5320
4321
6
5
4
3
2
1
0
T
MGC
1111000
0110100
1010010
1100001
]Q[IG Tk
?
?
?
?
?
?
?
?
?
?
?
?
?
??
消息 码字 消息 码字
0000 0000000 1000 1000011
0001 0001111 1001 1001100
0010 0010110 1010 1010101
0011 0011001 1011 1011010
0100 0100101 1100 1100110
0101 0101010 1101 1101001
0110 0110011 1110 1110000
0111 0111100 1111 1111111
截短汉明码
? (n,k) － > (n-x,k-x)
?如 (15,11)－ > (12,8)
监督矩阵 H’ 是将原 H 的前 3 列 去掉
?截短汉明码的最小码距至少和原来码的码
距相同，因为监督位没有变。
3d m i n:最小距离
knr:校验位数
1xr2k:信息位数
1x2n:码长
r
r
?
??
????
???
? 能纠 t 个错误的 (n,k)应满足
取等号时为完备码
? 不同结构的线性码其纠错能力不同，能力和
dmin 有关,dmin 越大越好。
12
0
2 2 1
t
r n k t i
n n n n
i
C C C C?
?
? ? ? ? ? ? ? ?
? 如果在汉明码基础上，再加上一位对所有码字
进行校验的监督位
? 监督码字由 r 位增加到 r+1 位
? 信息位不变
?码长 码结构
?纠 1 位错，检测 2 位错
?如 （ 8,4），（ 16,11）
rn 2? )12,2( ?? rrr
扩展汉明码
1 1 1 1
0
0
0
E
H H
??
??
??
???
??
??
??
??
扩展汉明码的监督矩阵
?
?
?
?
?
?
?
?
?
?
?
?
??
?
?
?
?
?
?
?
?
?
?
?
01010101
0110110
01111000
11111111
1010101
1100110
1111000
H
0
E
H
编码器的实现
上例 m=(m1 m2 m3 m4)
m1,m2,m3,m4 ∈ {0,1}
Ci = mG
Ci = (c1 c2 c3 c4 c5 c6 c7)
= (m1 m2 m3 m4 m1+m2 + m3 m2+m3+m4 m1+m2+m4)
m1 c1
m2 c2
m3 c3
m4 c4
c5
c6
c7
?
?
?
?
?
?
?
?
?
?
?
?
?
1101000
0110100
1110010
1010001
G
+
+
+
三、线性分组码的编码
根据线性码的监督矩阵或生成矩阵将长为 k的信
息组变换成长为 n（ n>k）的码字。
四、线性分组码的译码
? 当给定接收码字 R时，译码器的错误译码概率表示
经过译码后平均接受到一个码字所产生的错误大
小。
? 平均错误概率：
?? )|()( REpRpp E
1,最大似然译码
1) 编码译码过程
源数据码流划分为信息组 m,编码译码过程如下,
信息组 m 码字 Ci 接收字 R Ci的估值
干扰
2) 译码
发送码字 Ci,接收字 R ; 译码器根据编码规则和信道特性,
对接收码字 R 作出判决,此过程称为 译码,
译码器的基本任务就是根据一套译码规则或算法,由接
收字 R 给出与发送信息组 m 的最好估计值, 由于 m 与 C 之
间是一一对应的,这就等价于译码器根据 R 对 C 的估计,
编码器 译码器信道
3) 最佳译码
在已知接收字 R 的条件下,找出可能性最大的发送码字 Ci
作为译码的估值,令
这种 译码方法叫做最佳译码或最大后验译码 (MAP)
根据 Bayes公式
式中 p( Ci ) 发送码字 Ci 的概率
p(R) 接收字 R的概率
p(R|Ci ) 先验概率
)|(m a x? RCpC i?
C?
kii
i qiRp
CRpCpRCp,,2,1
)(
)|()()|( L??
如果以下条件成立
码 C中的 q k 个码字以等概率发送,p( Ci ) = 1/ q k
p(R) 对于任何 R 都有相同的值,p(R) = 1/ q n
则后验概率 p(Ci|R) 最大,等同于先验概率 p(R|Ci )最大,
4) 最大似然译码
在已知接收字 R 的条件下,使得先验概率最大的译码方
法称为 最大似然译码
对于无记忆信道,若
Ci = ( ci 1,ci 2,…,ci n ),R = ( r 1,r 2,…,r n )
则最大似然函数
)|(m a x? ii CRpC ?
?
?
?
n
j
ijji crpCRp
1
)|(m ax)|(m ax
对数似然函数
5) 最小距离译码
对于 BSC信道,最大似然译码可以简化为最小距
离译码,
码 C 中任一码字 Ci 与 R的距离为 d,则 d 表示 Ci
在 BSC信道传输过程中码元传错的个数,
因此此时的似然函数
?
?
?
n
j
jiji crpCRp
1
)|(l o gm a x)|(l o gm a x
?
?
?
??
??
)(1
)()|(
jij
jij
ijj rcp
rcpcrp
nddnd
n
j
ijji pp
pppcrpCRp )1()
1()1()|()|( 1 ??????
?
?
?
结论
(1-p)n 是常数,而 p/(1-p) < 1,d 越大则 p(R | Ci ) 越小
反之,d 越小则 p(R | Ci ) 越大,
因此求最大似然函数的问题就转化为求 Hamming最小
距离的问题,
5.4 线性分组码
5.4.1 线性分组码的基本概念
1) 模运算 (对于整数 )
1° 同余
a = b (mod m), a 除以 m 与 b 除以 m(m>1) 的余数相同 ;
或称为 a 和 b 对于 模 m 同余,
最小非负剩余, a = r (mod m) ; 0 ≤ r < m ;
r 为 模 m最小非负剩余
模 m运算, a,b ∈ { 0,1,2,…,m-1} ; r为最小非负剩余
将 a + b=r (mod m),a × b =r (mod m) 记为
这种求 a + b 和 a × b 的 模 m
最小非负剩余称为模 m的加法 运算和 模 m的乘法 运算,
为了简单起见,以后将运算符号 简记为 +和 ×,
rbarba ????
??,
2° 模 2 运算 (二进制 ) 3° 模 q 运算 (q进制 )
例, 模 3 运算
1+1+1=1,1+1+1+1=0,…
0-1=1,1-0=1,1-1=0
2) 线性分组码
定义 1 设 Ci = ( ci 1,ci 2,…,ci n ),Cj= ( cj 1,cj 2,…,cj n )是
二元码 C 的两个码字,则 Ci 与 Cj 的和 为 Ci 与 Cj
对应码元的模 2 运算 ; 若 Cs = ( cs 1,cs 2,…,cs n )
且 Cs =Ci + Cj 即 cs r = ci r + cj r (r =1,2,…,n )
+ 0 1 2
0 0 1 2
1 1 2 0
2 2 0 1
× 0 1 2
0 0 0 0
1 0 1 2
2 0 2 1
+ 0 1
0 0 1
1 1 0
× 0 1
0 0 0
1 0 1
定义 2 设 ( n,k )分组码 C 中的任意两个码字
1° C 中有全 0 码元的码字 ;
2° C 中的任意两个码字的和仍为码 C 的码字 ;
则分组码 C 称为 ( n,k )线性分组码,
推论 线性分组码 任意两个以上码字的和 仍为码 C 的码字,
根据分组码的定义,信息组 m 的 k 个码元 (信息位 )应包
含在线性分组码的码字中,
定义 3 若信息组 m的 k 个码元以整体不变的形式,放在码字
的任意位置中,该码为 系统码, 否则,称为 非系统码,
系统码通常如下图将信息组放在码字的最左边或最右边,
k 位信息位 n- k位校验位 n- k 位校验位 k位信息位
例 试构造 (5,2) 线性分组码,且 d min = 3
信息组 m 00 01 10 11
00000 00001 00010 00011 00100 00101 00110 00111
01000 01001 01010 01011 01100 01101 01110 01111
10000 10001 10010 10011 10100 10101 10110 10111
11000 11001 11010 11011 11100 11101 11110 11111
1组 2组 3组 4组 5组 6组 7组 8组 9组
00000 00000 00000 00000 00000 00000 00000 00000 00000
01011 01011 01011 01101 01101 01101 01110 01110 01110
10101 10110 10111 10011 10110 10111 10011 10101 10111
11110 11101 11100 11110 11011 11010 11101 11001 11001
3) 码字的重量
定义 4 ( n,k )码 C 的一个码字 C i中非零码元的个数称为码
字 C i 的 Hamming重量,简称 码重,记为 W(C i),
定义 5 ( n,k )码 C中所有非零码字的 Hamming重量的最小
值称为码 C 的最小 Hamming重量,或码 C最小重量
记为 Wmin,
推论 设 Ci,Cj 为 二元 分组码 C的任意两个码字,则
W(Ci + Cj ) = d (Ci,Cj ).
证明 Ci,Cj 的对应码元相同时,则 Ci + Cj 对应的码元为 0 ;
Ci,Cj 的对应码元不同时,则 Ci + Cj 对应的码元为 1 ;
则 W(Ci + Cj ) 为 Ci,Cj 的对应码元不同的个数,而
d (Ci,Cj )为 Ci,Cj 的对应码元不同的个数,故推论成立,
定理 二元 ( n,k )线性分组码 C的 最小距离 等于其
最小重量,
证明 设 C 中的任意两个码字 Ci,Cj,且 Ci≠ Cj 则
Cs= Ci + Cj 是非零码字,同时是码 C 的码字
又因为 W(Ci + Cj ) = W (Cs ) =d (Ci,Cj ),
因此 Wmin =d min
结论, 二元线性分组码 C 的最小重量,即非零码字
,1”的个数
最少的码字决定了码 C 的检错或纠错能力,
如何获得二元线性分组码
5.4.2 近世代数学初步
1) 群的概念
定义 1 G是一个非空集合,*是 G中的一个代数运算，若
1° a,b∈ G,有 a * b ∈ G (封闭性 )
2° a,b,c∈ G,有 (a * b) * c = a * ( b * c ) (结合律 )
3° 存在单位元素 e∈ G,a∈ G,有 e * a = a * e = a
4° a∈ G,存在逆元素 a -1∈ G,有 a-1 *a = a-1 *a = e
5° a,b∈ G,有 a * b = b * a (交换律 )
如果这种运算 *满足：
条件 1°,2°,3°,4° 则 G 称对代数运算为一个群,或称
G为一个非交换群,
条件 1°,2°,3°,4°,5° 则称 G为一个 交换群 或 Abel群,
?
?
?
?
?
若运算 * 是普通的加法, +”,则群称为 加群,
若运算 * 是普通的乘法, ×,,则群称为 乘群,
定义 2 若群 G 仅有有限个原素则称为 有限群 ;否则为 无限群,
1° 无限群的例子
例 1 整数集对加法构成 Abel群,对乘法不是群,
例 2 有理数,实 数,复 数集对加法构成 Abel群,
不含数 0 的有理数,实 数,复 数集对乘法构成 Abel群,
例 3 n 维方阵的集合加法构成 Abel群,对乘法不是群,
例 4 n 维非奇异方阵对乘法构成非 Abel群,
2° 有限群的例子
例 1 数 0 对加法构成群,数 1 对乘法构成群,
例 2 集合 { 0,1,2,…,m-1}对模 m加法运算构成 Abel群,
对乘法不是群,
例 3 当 m 为素数时,集合 { 1,2,…,m-1}对模 m 乘法运
算构成 Abel群,
例 4 方程 x n - 1= 0的本原根 e j 2kπ/n,k=0,1,… n-1对乘法
构成 Abel群,
例 5 线性分组码构成 Abel群,所以线性分组码又称为 群码,
2) 域的概念
定义 1 F 是一个非空集合,对于 F 的任意两个元素
a 和 b,
定义集合元素的加法运算,记作 a＋ b ; 乘法
运算,
记作 a b ; 且有如下规则,
加法运算
1° a,b ∈ F,有 a＋ b ∈ F ;
2° a,b ∈ F,有 a＋ b = b＋ a ;
3° a,b,c ∈ F,有 (a＋ b)＋ c = a＋ ( b＋
c) ;
4° 存在 0 ∈ F,a ∈ F,有 a＋ 0 = a ；
5° a ∈ F,存在 - a ∈ F,有 a＋ (- a) = 0 ;
?
?
?
?
?
乘法运算
1° a,b ∈ F,有 a b ∈ F ;
2° a,b ∈ F,有 a b = b a ;
3° a,b,c ∈ F,有 (a b) c = a ( b c) ;
4° 存在 e ∈ F,a ∈ F,有 a e = a ；
5° a ∈ F,且 a≠0,存在 a -1 ∈ F,有 a a -1= e ;
乘法对加法的分配律
a,b,c ∈ F,有 a (b＋ c) = a b＋ a c
以上运算规则都成立, 则称 F 对于所规定的加法运算
和乘法运算是一个域,
定义 2 设 F 是一个域,如果 F 中的元素个数无限,则 F 称为
无限域, 如果 F 中的元素个数有限,则 F 称为有限
域, 有限域亦称为 Galois域,
?
?
?
?
?
1° 无限域的例子
例 1 有理数,实 数,复 数集对加法,乘法构成域,
例 2 形如 的数对加法,乘法构成域,
2° 有限域的例子
例 1 集合 { 0,1,2,…,m-1}对模 m加法,乘法运算构成域,
Rbaba ??,2
5.4.3 生成矩阵和校验矩阵
1) 生成矩阵
例 1 试构造 (5,2) 线性分组码,且 d min = 3
m=(m1 m2 ) = (00),(01),(10),(11)
Ci=( m1 m2 m1 m2 m1+m2 )
(00) → ( 0 0 0 0 0) (01) → ( 0 1 0 1 1)
(10) → ( 1 0 1 0 1) (11) → ( 1 1 1 1 0)
1° (n,k) 线性分组码的生成矩阵 G 是一个 k× n 维矩阵,
为了获得系统线性分组码,生成矩阵由两个分块矩阵组成,
G = [I k P k× (n-k)] I k, k维单位矩阵,以获得信息位 ;
P k× (n-k),k× (n-k)矩阵,以获得校验位,
??
?
??
????
11010
10101)()(
2154321 mmmGcccccC iiiiii
2° 线性分组码生成矩阵的特点
生成矩阵不是唯一的 ;
生成矩阵的行矢量均为线性分组码的码字 ;
生成矩阵的行矢量是模 2 运算下线性无关 ;
线性分组码任一码字是行矢量模 2 运算下的线性组合,
3° 如何获得生成矩阵?
例 2 试构造 (7,4) 线性分组码,且 d min = 3
生成矩阵生成的线性分组码要有尽可能大的 d min,即生
成矩阵的行矢量中的, 1”的个数 ≥ d min,且生成矩阵各行矢
量 (码字 )的对应元素不相同的个数 ≥ d min,
?
?
?
?
?
?
?
?
?
?
?
?
?
1101000
0110100
1110010
1010001
G
?
?
?
?
?
?
?
?
?
?
?
?
?
1101000
0110100
1100010
1010001
G
2) 一致校验矩阵
(n,k) 线性分组码为一系统码,则码字有
(c1 c2 … ck ck+1 … cn) = (m1 m2 … mk ck+1 … cn)
由生成矩阵 G 生成的码字
(c1 c2 … ck ck+1 … cn) = (m1 m2 … mk ) G
= (m1 m2 … mk ) [I k P k× (n-k)]
码字的校验位
( ck+1 … cn) = (m1 m2 … mk ) P k× (n-k)=(c1 c2 … ck ) P k× (n-k)
(c1 c2 … ck ) P k× (n-k)- ( ck+1 … cn) = 0 1× (n-k)
(c1 c2 … ck ) P k× (n-k)+ ( ck+1 … cn) I (n-k) = 0 1× (n-k)
)(1
)(
)(
121 0)( kn
kn
knk
nkk I
Pccccc
??
?
??
? ???
?
??
?LL
一致校验矩阵 H (简称校验矩阵 )
H = [P T I (n-k) ] (n-k) × n
当系统码生成矩阵 G 确定后,校验矩阵 H由生成矩阵中的
分块矩阵 P k× (n-k)确定,
由生成矩阵 G 生成的任一码字 Ci 均满足下式,不是 G生成
码字则不满足下式
Ci H T= 0 1× (n-k) 或 H Ci T = 0 (n-k)× 1
因此,校验矩阵 H 可以判断是否为码字,
3) 极大最小距离码
(n,k)线性分组码要有尽可能大的 d min,其的上限是什么?
如何达到上限,
)()(
)(
knnkn
knkT
I
P
H
???
??
?
?
?
?
?
??
令 H=[h1 h2 … hn],h1 h2 … hn 为 (n-k)维列矢量
(n,k)线性分组码的任一非零码字 Ci = (ci 1 ci 2 … ci n)
因为 H Ci T = 0 所以 ci 1 h1 + ci 2 h2 + … + ci n hn= 0,因此,
矢量 h1 h2 … hn 是线性相关的,
(n,k)线性分组码的 d min = W min,设 Cs 为码重最小的码
字,则 Cs 中码元为, 1” 的个数 = d min,因为 H Cs T = 0,所
以
H 的列矢量至少要有 d min 才线性相关, 而 H 的 d min -1个列矢
量是线性无关的,否则就至少有一个码重为 d min –1 的码字,
这与 d min 相矛盾,
由于 H 是 n × (n-k) 矩阵,其秩最多为 (n-k),最多有 (n-k)个
列矢量线性无关,因此 d min -1 ≤ (n-k),即 d min ≤ n - k+1,
当 d min = n - k+1 时的码称为 极大最小距离码,
?信道编码的基本概念和基本原理
?线性分组码
?循环码、卷积码和秩距离码
?突发错误的纠正
?级连码、交织码及 TCM码
?纠错码的应用
信
源
检错、
纠错
编码器
编码
信道
检错、
纠错
译码器
信
宿
噪声源
数字通信系统简化模型
? ?M ??C ??R ? ??M
??E
编码信道：包括信道编码器、实际信道、信道译码器。
该模型是研究信道纠错编码和译码的模型，集中研究通信
可靠性。
通信可靠性问题,消息通过信道传输的时候，如何选择编
码方案来减少差错。首先与信道统计特性有关，其次与编
码方法、译码方法也有关系。
第一节 信道编码的基本概念和基本原理
信道是信号从信源传送到信宿的通路 。
1) 由于信道有干扰, 使得传送的数据流 (码流 )中产生误码 。
2) 误码的处理技术有纠错, 交织, 线性内插等 。
3) 信道编码的 目的 是提高信息传输或通信的可靠性 。
4) 信道编码的 任务 是降低误码率, 使系统具有一定的纠错
能力和抗干扰能力, 提高数据传输效率 。
5) 信道编码的 过程 是在 源数据码流 中加插一些码元, 达到
在接收端进行检错和纠错的目的 。
6) 在带宽固定的信道中, 总的传送码率是固定的, 由于信
道编码增加了数据量, 其结果只能是以降低传送有用信
息码率为代价了 。
一、信道编码概念
目的,降低错误译码概率 PE。
对象,信息序列 （ 设码元间彼此无关且等概出现 ） 。
方法,在传输的信息码之中按一定规律产生一些附加
数字，经信道传输，在传输中若码字出现错误，
收端能利用编码规律发现码的内在相关性受到破
坏，从而按一定的译码规则自动纠正或发现错误，
降低误码率。
一、信道编码概念
实质,在保持一定传输信息速率条件下，通过增
加一定的码元多余度，使输出的码字具有特定
的相关性，从而使收端易于发现或纠正由于信
道噪声而引起的传输错误。
q=rk个
k维矢量
禁用码组
许用码组
n重序列
rn个
信道
编码器
M C
校验元
rk个
C0
C1
Ci
┋
Cj
┋
C2k-1
收端
传输模式
PE～信道传输特征
PE～译码方法
C2k
┋
Ci’
┋
C2n-1
许
用
码
组
禁
用
码
组
C0
C1
┋
Ci
┋
C2k-1
许
用
码
组
发端
二、信道编码的基本原理（检错、纠错原理）
寻找一种编码方法，使所加的监督码元最少，而检错纠错能
力又高，且便于实现。
理论基础：香农第二定理
对于一个给定的有扰信道，如信道容量为 C，只要发送端
以低于 C的速率 R发送信息，则一定存在一种编码方法，
使编码错误概率 p随码长 n的增加，按指数下降到任意小的
值。也就是说，可以通过编码使通信过程实际上不发生错
误，或使错误控制在允许数值之下。即：
[]n E RPe ??
信息传输率
E(R)
码长
P?exp{-nE )}
※ E (R)意义,n给定，则最佳编码的 P上界既定。
１,适用于 DMC，有记忆信道及连续信道 ;
0RC ER C N P
RC ?
? ? ????
? ??
?
时, 足 够 长, 必 存 在 最 佳 编 码, 使
输 入 等 概, 时, 最 佳 编 码 也 存 在 （ 有 效 性, 可 靠 性 最 优 ）
()
()
2 2 ( 0)
2 2 ( 0)
N R N C
N R N C
R C M
R C M
?
?
?
?
?
?
?? ? ? ?
?? ? ? ?
?
等 价 于 存 在 最 佳
等 价 于 不 存 在 最 佳
２,PE→0,可靠编码条件：
有噪信道编码逆定理
设离散无记忆信道［ X,p(y|x),Y］的信道容
量为 C,R是信息传输率，当 R>C时，则无论码长 N
多长，总找不到一种编码，使译码的平均错误概率
任意小。
表述二,设某信道有 r个输入符号,s个输出符号，
信道容量为 C。只要码长 N足够长，总可以在输入
的 rN个符号的集合中找到 M（ M?2N(C-?),?为任意
小的正数）个码字，分别代表 M个等可能性的消
息，组成一个码以及相应的译码规则，使信道输
出端的平均错误译码概率 PE达到任意小。
1) 差错类型
1° 随机错误, 数据流中发生的错误彼此无关,表现为错
误之间的无相关性,
2° 突发错误, 数据流中一个错误的发生,带来一连串错
误的发生,表现为误错之间的相关性,
2) 差错控制的途径
1° 增加信道容量措施
扩展带宽、提高发送功率、降低噪声
2° 编码措施
减小码率,增加码长、交织器,纠错码
3° 传输方式措施
重复发送,反馈 重发,多进制信号
三、差错控制
? 需要双向信道，和前向信道有相同的通信容。
? 引入较大的停顿（不实时）。
? 可以纠正任何错误。
1° 反馈检验法 (IRQ)
分组 存储 发 收
收 发
kI?kI
3) 差错控制的分类
2° 检错重发法（ ARQ）
? 自动请求重发
? 也需要反向信道，但容量可以降低，也会引
入停顿
检错
编码 存储 发 收
收 发
kI?kI
检错
译码
3° 前向纠错（ FEC）
? 不需要双向信道
? 不会引入停顿
? 靠纠错编码
3° 混合纠错检错（ HEC）
4) 差错控制编码的基本原理
? 如用三位二进制编码来代表八个字母
? 000 A 100 E
? 001 B 101 F
? 010 C 110 G
? 011 D 111 H
? 不管哪一位发生错误，都会使传输字母错误
? 如用三位字母传四个字母
? 000 A 011 B 101 C 110
D
? 发生一位错误，准用码字将变成禁用码字，接收端就
能知道出错，但是不能纠错。
?如用三位字母传二个字母
000 A 111 B
? 检三个错误，纠正一个错误。大数法则纠错。
?结论
? 具有检错或纠错的码组，其所用的比特数必须
大于信息码组原来的比特数
－ >引入余度。
5）、检错、纠错能力
?码重 (weight)
一个码组中,1”的数目
?码距 (distance)
两个码组之间对应位置上 1,0不同的位数，又叫汉明
(Hamming)距。
10 1 1 0 码重,3
01 1 0 0 2 距离,3
? 为检查出 个错误，要求最小码距为
? 为纠正 个错误，要求最小码距为
? 为纠正 个错误，同时检查出 个错误，要求最小码
距为
? 纠正 个错误和 p个删除，要求最小码距为：t
m in 1dl??
m in 21dt??
m i n 1 ( )d l t l t? ? ? ?
检错、纠错能力
l
t
t
l
12m i n ??? ptd
? 按功能分
?检错码
?纠错码
?纠删码（发现不可纠正的错误时，可发出指示或删除）
? 按信息码元和监督码元之间的校验关系分
?线性码
?非线性码
? 按信息码元和监督码元之间的约束方式分
?分组码
?卷积码
6）、差错控制编码分类
卷积码
非线性码 线性码
纠错码
分组码
循环码 非循环码
纠随机
错误码
纠突发
错误码
纠随机和突
发错误码
纠同步
错误码
纠错码分类
第二节 线性分组码
? 表示,(n,k)
n, 帧（组）长 k/n, 编码效率
? 特点
? 监督码只用来监督本帧中的信息位
? 分类
? 线性码 － 信息码与监督码之间为线性关系
? 非线性码 － 不存在线性关系
01221 aaaaa nn L??
信息位 监督位
一、基本概念
? 分组码的监督方程
? 矩阵形式
? ?6 5 4 3 2 1 0
1 1 1 0 1 0 0 0
1 1 0 1 0 1 0 0
1 0 1 1 0 0 1 0
T
a a a a a a a
? ? ? ?
? ? ? ??
? ? ? ?
? ? ? ?? ? ? ?
监督方程( 校验方程)
ccc
ccc
cccc
ccc
为监督元c,c,c,c为信息元,,c,c,c
)c,c,c,c,c,c,(cc
450
561
4562
463
0123456
0123456
?
?
?
?
?
?
?
?
??
??
???
??
?
? 监督矩阵
? H矩阵称为典型形式，各行一定是线性无关的。
而一个非典型形式的经过初等变换运算可以化
成典型形式，通过监督矩阵可以知道监督码和
信息码的监督关系。
],[
1001101
0101011
0010111
rrkrnr IQH ??? ?
?
?
?
?
?
?
?
?
?
?
?
? 生成矩阵
，通过监督矩阵可以得到生成码组。
? 如果输入码组为 A=0011,编码器输出码字
为,C=AG
TQP?
? ? ? ? ? ?
1 0 0 0 1 1 1
0 1 0 0 1 1 0
0 0 1 1 0 0 1 1 0 0 1 1 1 1 0
0 0 1 0 1 0 1
0 0 0 1 0 1 1
AG
??
??
? ? ? ? ?
??
??
?
?
?
?
?
?
?
?
?
?
?
?
?
?
??
110
101
011
111
1000
0100
0010
0001
],[ PIG
k
? 由这种方式得到的生成矩阵称为 典型生成矩阵,
由它产生的分组码必定为 系统码，也就是信息码
字保持不变，监督位附加其后,每行一定是线性
无关的，每行都是一个生成码组。
0 0 1 1 0 0 1 1 1 1 0?
定理：设二元线性分组码 CI是由监督矩阵 H所定义的，若 X和
Y为其中的任意两个码字，则 X+Y也是 CI中的一个码字。 —
—线性码的封闭性
对偶码,以 G作监督矩阵，以 H为生成矩阵，得到另
一个码 CJ—— （ n,n-k）线性码。 CJ为原码 CI的对
偶码。它们的码矢彼此正交，两个子空间是互为零
化空间。
缩短码,将分组码最左边 i位为 0的消息和对应的码
字挑选出来，把最左边的 0删去，构成（ n-i,k-i）
线性分组码。纠错检错能力与原码相同。
缩短码的监督矩阵：（ n,k）一致监督矩阵删去最左边一列。
缩短码的生成矩阵,（ n,k）生成矩阵删去最左边一列和最上面的一行。
二、汉明码 ——能 纠正单个错误 的线性分组码
3:
:
)(
1
1
:
1
1
:
),,(:
m i n
?
??
??
?
?
?
?
?
?
?
?
d
knr
kn
m
m
k
m
m
n
dkn
kn
kn
最小距离
监督位数
信息位数
码长
表示
汉明码的监督矩阵 H的列为所有非零的 r维向量组成，一
旦 r给定，就可以构造出具体的（ n,k）汉明码。
例：构造一个二元的（ 7,4,3）汉明码。
分析,r=n-k=3,除 0以外的所有 2r个元素构成矩阵 H
的列。
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
1001011
0101101
0011110
H
][ Q IH
1010101
1100110
1111000
H
:监 督 矩 阵 为
r
即
?
?
?
?
?
?
?
?
?
?
?
?
??
?
?
?
?
?
?
?
?
?
?
?
111
011
101
110
1011
1101
1110
T
QP
Q
?
?
?
?
?
????
????
????
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
0cccc
0cccc
0cccc
0
c
c
c
c
c
c
c
1001011
0101101
0011110
0由H C
6310
5320
4321
6
5
4
3
2
1
0
T
MGC
1111000
0110100
1010010
1100001
]Q[IG Tk
?
?
?
?
?
?
?
?
?
?
?
?
?
??
消息 码字 消息 码字
0000 0000000 1000 1000011
0001 0001111 1001 1001100
0010 0010110 1010 1010101
0011 0011001 1011 1011010
0100 0100101 1100 1100110
0101 0101010 1101 1101001
0110 0110011 1110 1110000
0111 0111100 1111 1111111
截短汉明码
? (n,k) － > (n-x,k-x)
?如 (15,11)－ > (12,8)
监督矩阵 H’ 是将原 H 的前 3 列 去掉
?截短汉明码的最小码距至少和原来码的码
距相同，因为监督位没有变。
3d m i n:最小距离
knr:校验位数
1xr2k:信息位数
1x2n:码长
r
r
?
??
????
???
? 能纠 t 个错误的 (n,k)应满足
取等号时为完备码
? 不同结构的线性码其纠错能力不同，能力和
dmin 有关,dmin 越大越好。
12
0
2 2 1
t
r n k t i
n n n n
i
C C C C?
?
? ? ? ? ? ? ? ?
? 如果在汉明码基础上，再加上一位对所有码字
进行校验的监督位
? 监督码字由 r 位增加到 r+1 位
? 信息位不变
?码长 码结构
?纠 1 位错，检测 2 位错
?如 （ 8,4），（ 16,11）
rn 2? )12,2( ?? rrr
扩展汉明码
1 1 1 1
0
0
0
E
H H
??
??
??
???
??
??
??
??
扩展汉明码的监督矩阵
?
?
?
?
?
?
?
?
?
?
?
?
??
?
?
?
?
?
?
?
?
?
?
?
01010101
0110110
01111000
11111111
1010101
1100110
1111000
H
0
E
H
编码器的实现
上例 m=(m1 m2 m3 m4)
m1,m2,m3,m4 ∈ {0,1}
Ci = mG
Ci = (c1 c2 c3 c4 c5 c6 c7)
= (m1 m2 m3 m4 m1+m2 + m3 m2+m3+m4 m1+m2+m4)
m1 c1
m2 c2
m3 c3
m4 c4
c5
c6
c7
?
?
?
?
?
?
?
?
?
?
?
?
?
1101000
0110100
1110010
1010001
G
+
+
+
三、线性分组码的编码
根据线性码的监督矩阵或生成矩阵将长为 k的信
息组变换成长为 n（ n>k）的码字。
四、线性分组码的译码
? 当给定接收码字 R时，译码器的错误译码概率表示
经过译码后平均接受到一个码字所产生的错误大
小。
? 平均错误概率：
?? )|()( REpRpp E
1,最大似然译码
1) 编码译码过程
源数据码流划分为信息组 m,编码译码过程如下,
信息组 m 码字 Ci 接收字 R Ci的估值
干扰
2) 译码
发送码字 Ci,接收字 R ; 译码器根据编码规则和信道特性,
对接收码字 R 作出判决,此过程称为 译码,
译码器的基本任务就是根据一套译码规则或算法,由接
收字 R 给出与发送信息组 m 的最好估计值, 由于 m 与 C 之
间是一一对应的,这就等价于译码器根据 R 对 C 的估计,
编码器 译码器信道
3) 最佳译码
在已知接收字 R 的条件下,找出可能性最大的发送码字 Ci
作为译码的估值,令
这种 译码方法叫做最佳译码或最大后验译码 (MAP)
根据 Bayes公式
式中 p( Ci ) 发送码字 Ci 的概率
p(R) 接收字 R的概率
p(R|Ci ) 先验概率
)|(m a x? RCpC i?
C?
kii
i qiRp
CRpCpRCp,,2,1
)(
)|()()|( L??
如果以下条件成立
码 C中的 q k 个码字以等概率发送,p( Ci ) = 1/ q k
p(R) 对于任何 R 都有相同的值,p(R) = 1/ q n
则后验概率 p(Ci|R) 最大,等同于先验概率 p(R|Ci )最大,
4) 最大似然译码
在已知接收字 R 的条件下,使得先验概率最大的译码方
法称为 最大似然译码
对于无记忆信道,若
Ci = ( ci 1,ci 2,…,ci n ),R = ( r 1,r 2,…,r n )
则最大似然函数
)|(m a x? ii CRpC ?
?
?
?
n
j
ijji crpCRp
1
)|(m ax)|(m ax
对数似然函数
5) 最小距离译码
对于 BSC信道,最大似然译码可以简化为最小距
离译码,
码 C 中任一码字 Ci 与 R的距离为 d,则 d 表示 Ci
在 BSC信道传输过程中码元传错的个数,
因此此时的似然函数
?
?
?
n
j
jiji crpCRp
1
)|(l o gm a x)|(l o gm a x
?
?
?
??
??
)(1
)()|(
jij
jij
ijj rcp
rcpcrp
nddnd
n
j
ijji pp
pppcrpCRp )1()
1()1()|()|( 1 ??????
?
?
?
结论
(1-p)n 是常数,而 p/(1-p) < 1,d 越大则 p(R | Ci ) 越小
反之,d 越小则 p(R | Ci ) 越大,
因此求最大似然函数的问题就转化为求 Hamming最小
距离的问题,
5.4 线性分组码
5.4.1 线性分组码的基本概念
1) 模运算 (对于整数 )
1° 同余
a = b (mod m), a 除以 m 与 b 除以 m(m>1) 的余数相同 ;
或称为 a 和 b 对于 模 m 同余,
最小非负剩余, a = r (mod m) ; 0 ≤ r < m ;
r 为 模 m最小非负剩余
模 m运算, a,b ∈ { 0,1,2,…,m-1} ; r为最小非负剩余
将 a + b=r (mod m),a × b =r (mod m) 记为
这种求 a + b 和 a × b 的 模 m
最小非负剩余称为模 m的加法 运算和 模 m的乘法 运算,
为了简单起见,以后将运算符号 简记为 +和 ×,
rbarba ????
??,
2° 模 2 运算 (二进制 ) 3° 模 q 运算 (q进制 )
例, 模 3 运算
1+1+1=1,1+1+1+1=0,…
0-1=1,1-0=1,1-1=0
2) 线性分组码
定义 1 设 Ci = ( ci 1,ci 2,…,ci n ),Cj= ( cj 1,cj 2,…,cj n )是
二元码 C 的两个码字,则 Ci 与 Cj 的和 为 Ci 与 Cj
对应码元的模 2 运算 ; 若 Cs = ( cs 1,cs 2,…,cs n )
且 Cs =Ci + Cj 即 cs r = ci r + cj r (r =1,2,…,n )
+ 0 1 2
0 0 1 2
1 1 2 0
2 2 0 1
× 0 1 2
0 0 0 0
1 0 1 2
2 0 2 1
+ 0 1
0 0 1
1 1 0
× 0 1
0 0 0
1 0 1
定义 2 设 ( n,k )分组码 C 中的任意两个码字
1° C 中有全 0 码元的码字 ;
2° C 中的任意两个码字的和仍为码 C 的码字 ;
则分组码 C 称为 ( n,k )线性分组码,
推论 线性分组码 任意两个以上码字的和 仍为码 C 的码字,
根据分组码的定义,信息组 m 的 k 个码元 (信息位 )应包
含在线性分组码的码字中,
定义 3 若信息组 m的 k 个码元以整体不变的形式,放在码字
的任意位置中,该码为 系统码, 否则,称为 非系统码,
系统码通常如下图将信息组放在码字的最左边或最右边,
k 位信息位 n- k位校验位 n- k 位校验位 k位信息位
例 试构造 (5,2) 线性分组码,且 d min = 3
信息组 m 00 01 10 11
00000 00001 00010 00011 00100 00101 00110 00111
01000 01001 01010 01011 01100 01101 01110 01111
10000 10001 10010 10011 10100 10101 10110 10111
11000 11001 11010 11011 11100 11101 11110 11111
1组 2组 3组 4组 5组 6组 7组 8组 9组
00000 00000 00000 00000 00000 00000 00000 00000 00000
01011 01011 01011 01101 01101 01101 01110 01110 01110
10101 10110 10111 10011 10110 10111 10011 10101 10111
11110 11101 11100 11110 11011 11010 11101 11001 11001
3) 码字的重量
定义 4 ( n,k )码 C 的一个码字 C i中非零码元的个数称为码
字 C i 的 Hamming重量,简称 码重,记为 W(C i),
定义 5 ( n,k )码 C中所有非零码字的 Hamming重量的最小
值称为码 C 的最小 Hamming重量,或码 C最小重量
记为 Wmin,
推论 设 Ci,Cj 为 二元 分组码 C的任意两个码字,则
W(Ci + Cj ) = d (Ci,Cj ).
证明 Ci,Cj 的对应码元相同时,则 Ci + Cj 对应的码元为 0 ;
Ci,Cj 的对应码元不同时,则 Ci + Cj 对应的码元为 1 ;
则 W(Ci + Cj ) 为 Ci,Cj 的对应码元不同的个数,而
d (Ci,Cj )为 Ci,Cj 的对应码元不同的个数,故推论成立,
定理 二元 ( n,k )线性分组码 C的 最小距离 等于其
最小重量,
证明 设 C 中的任意两个码字 Ci,Cj,且 Ci≠ Cj 则
Cs= Ci + Cj 是非零码字,同时是码 C 的码字
又因为 W(Ci + Cj ) = W (Cs ) =d (Ci,Cj ),
因此 Wmin =d min
结论, 二元线性分组码 C 的最小重量,即非零码字
,1”的个数
最少的码字决定了码 C 的检错或纠错能力,
如何获得二元线性分组码
5.4.2 近世代数学初步
1) 群的概念
定义 1 G是一个非空集合,*是 G中的一个代数运算，若
1° a,b∈ G,有 a * b ∈ G (封闭性 )
2° a,b,c∈ G,有 (a * b) * c = a * ( b * c ) (结合律 )
3° 存在单位元素 e∈ G,a∈ G,有 e * a = a * e = a
4° a∈ G,存在逆元素 a -1∈ G,有 a-1 *a = a-1 *a = e
5° a,b∈ G,有 a * b = b * a (交换律 )
如果这种运算 *满足：
条件 1°,2°,3°,4° 则 G 称对代数运算为一个群,或称
G为一个非交换群,
条件 1°,2°,3°,4°,5° 则称 G为一个 交换群 或 Abel群,
?
?
?
?
?
若运算 * 是普通的加法, +”,则群称为 加群,
若运算 * 是普通的乘法, ×,,则群称为 乘群,
定义 2 若群 G 仅有有限个原素则称为 有限群 ;否则为 无限群,
1° 无限群的例子
例 1 整数集对加法构成 Abel群,对乘法不是群,
例 2 有理数,实 数,复 数集对加法构成 Abel群,
不含数 0 的有理数,实 数,复 数集对乘法构成 Abel群,
例 3 n 维方阵的集合加法构成 Abel群,对乘法不是群,
例 4 n 维非奇异方阵对乘法构成非 Abel群,
2° 有限群的例子
例 1 数 0 对加法构成群,数 1 对乘法构成群,
例 2 集合 { 0,1,2,…,m-1}对模 m加法运算构成 Abel群,
对乘法不是群,
例 3 当 m 为素数时,集合 { 1,2,…,m-1}对模 m 乘法运
算构成 Abel群,
例 4 方程 x n - 1= 0的本原根 e j 2kπ/n,k=0,1,… n-1对乘法
构成 Abel群,
例 5 线性分组码构成 Abel群,所以线性分组码又称为 群码,
2) 域的概念
定义 1 F 是一个非空集合,对于 F 的任意两个元素
a 和 b,
定义集合元素的加法运算,记作 a＋ b ; 乘法
运算,
记作 a b ; 且有如下规则,
加法运算
1° a,b ∈ F,有 a＋ b ∈ F ;
2° a,b ∈ F,有 a＋ b = b＋ a ;
3° a,b,c ∈ F,有 (a＋ b)＋ c = a＋ ( b＋
c) ;
4° 存在 0 ∈ F,a ∈ F,有 a＋ 0 = a ；
5° a ∈ F,存在 - a ∈ F,有 a＋ (- a) = 0 ;
?
?
?
?
?
乘法运算
1° a,b ∈ F,有 a b ∈ F ;
2° a,b ∈ F,有 a b = b a ;
3° a,b,c ∈ F,有 (a b) c = a ( b c) ;
4° 存在 e ∈ F,a ∈ F,有 a e = a ；
5° a ∈ F,且 a≠0,存在 a -1 ∈ F,有 a a -1= e ;
乘法对加法的分配律
a,b,c ∈ F,有 a (b＋ c) = a b＋ a c
以上运算规则都成立, 则称 F 对于所规定的加法运算
和乘法运算是一个域,
定义 2 设 F 是一个域,如果 F 中的元素个数无限,则 F 称为
无限域, 如果 F 中的元素个数有限,则 F 称为有限
域, 有限域亦称为 Galois域,
?
?
?
?
?
1° 无限域的例子
例 1 有理数,实 数,复 数集对加法,乘法构成域,
例 2 形如 的数对加法,乘法构成域,
2° 有限域的例子
例 1 集合 { 0,1,2,…,m-1}对模 m加法,乘法运算构成域,
Rbaba ??,2
5.4.3 生成矩阵和校验矩阵
1) 生成矩阵
例 1 试构造 (5,2) 线性分组码,且 d min = 3
m=(m1 m2 ) = (00),(01),(10),(11)
Ci=( m1 m2 m1 m2 m1+m2 )
(00) → ( 0 0 0 0 0) (01) → ( 0 1 0 1 1)
(10) → ( 1 0 1 0 1) (11) → ( 1 1 1 1 0)
1° (n,k) 线性分组码的生成矩阵 G 是一个 k× n 维矩阵,
为了获得系统线性分组码,生成矩阵由两个分块矩阵组成,
G = [I k P k× (n-k)] I k, k维单位矩阵,以获得信息位 ;
P k× (n-k),k× (n-k)矩阵,以获得校验位,
??
?
??
????
11010
10101)()(
2154321 mmmGcccccC iiiiii
2° 线性分组码生成矩阵的特点
生成矩阵不是唯一的 ;
生成矩阵的行矢量均为线性分组码的码字 ;
生成矩阵的行矢量是模 2 运算下线性无关 ;
线性分组码任一码字是行矢量模 2 运算下的线性组合,
3° 如何获得生成矩阵?
例 2 试构造 (7,4) 线性分组码,且 d min = 3
生成矩阵生成的线性分组码要有尽可能大的 d min,即生
成矩阵的行矢量中的, 1”的个数 ≥ d min,且生成矩阵各行矢
量 (码字 )的对应元素不相同的个数 ≥ d min,
?
?
?
?
?
?
?
?
?
?
?
?
?
1101000
0110100
1110010
1010001
G
?
?
?
?
?
?
?
?
?
?
?
?
?
1101000
0110100
1100010
1010001
G
2) 一致校验矩阵
(n,k) 线性分组码为一系统码,则码字有
(c1 c2 … ck ck+1 … cn) = (m1 m2 … mk ck+1 … cn)
由生成矩阵 G 生成的码字
(c1 c2 … ck ck+1 … cn) = (m1 m2 … mk ) G
= (m1 m2 … mk ) [I k P k× (n-k)]
码字的校验位
( ck+1 … cn) = (m1 m2 … mk ) P k× (n-k)=(c1 c2 … ck ) P k× (n-k)
(c1 c2 … ck ) P k× (n-k)- ( ck+1 … cn) = 0 1× (n-k)
(c1 c2 … ck ) P k× (n-k)+ ( ck+1 … cn) I (n-k) = 0 1× (n-k)
)(1
)(
)(
121 0)( kn
kn
knk
nkk I
Pccccc
??
?
??
? ???
?
??
?LL
一致校验矩阵 H (简称校验矩阵 )
H = [P T I (n-k) ] (n-k) × n
当系统码生成矩阵 G 确定后,校验矩阵 H由生成矩阵中的
分块矩阵 P k× (n-k)确定,
由生成矩阵 G 生成的任一码字 Ci 均满足下式,不是 G生成
码字则不满足下式
Ci H T= 0 1× (n-k) 或 H Ci T = 0 (n-k)× 1
因此,校验矩阵 H 可以判断是否为码字,
3) 极大最小距离码
(n,k)线性分组码要有尽可能大的 d min,其的上限是什么?
如何达到上限,
)()(
)(
knnkn
knkT
I
P
H
???
??
?
?
?
?
?
??
令 H=[h1 h2 … hn],h1 h2 … hn 为 (n-k)维列矢量
(n,k)线性分组码的任一非零码字 Ci = (ci 1 ci 2 … ci n)
因为 H Ci T = 0 所以 ci 1 h1 + ci 2 h2 + … + ci n hn= 0,因此,
矢量 h1 h2 … hn 是线性相关的,
(n,k)线性分组码的 d min = W min,设 Cs 为码重最小的码
字,则 Cs 中码元为, 1” 的个数 = d min,因为 H Cs T = 0,所
以
H 的列矢量至少要有 d min 才线性相关, 而 H 的 d min -1个列矢
量是线性无关的,否则就至少有一个码重为 d min –1 的码字,
这与 d min 相矛盾,
由于 H 是 n × (n-k) 矩阵,其秩最多为 (n-k),最多有 (n-k)个
列矢量线性无关,因此 d min -1 ≤ (n-k),即 d min ≤ n - k+1,
当 d min = n - k+1 时的码称为 极大最小距离码,
