第五章 信道编码
?信道编码的基本概念和基本原理
?线性分组码
?循环码、卷积码 和秩距离码
?突发错误的纠正
?级连码、交织码及 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??
信息位 监督位
一、基本概念
? 分组码的监督方程
? 矩阵形式
监督方程( 校验方程)
ccc
ccc
cccc
ccc
为监督元c,c,c,c为信息元,,c,c,c
)c,c,c,c,c,c,(cc
450
561
4562
463
0123456
0123456
?
?
?
?
?
?
?
?
??
??
???
??
?
? ?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
0
0
0
1001101
0101011
0010111
0123456 ccccccc
? 监督矩阵
? 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）汉明码 。
例 1：构造一个二元的（ 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最小
距离的问题,
2,伴随式和错误检测
1）伴随式
S=RHT或 ST=HRT—— 接收码字 R的伴随式（监督子，或校验子）
设，发送码字 C=（ cn-1,cn-2,…,c 0）
接收码字 R=（ rn-1,rn-2,…,r 0）,
则，差错码组（错误图样） E=R-C=（ en-1,en-2,…,e 0）
如果 ei=0，表示 ri = ci
ei=1，表示 ri ≠ci
R=C+E
伴随式,ST=HRT=H（ C+E） T=HCT+HET
=HET（因为 HCT=0T）
=h1en-1+h2en-2+…+h ne0
即,S=EHT
结论：
?伴随式只与错误图样有关，与发送的具体码
字无关。
? S=0，表示没有出错,S≠0，判有错。
?不同的错误图样具有不用的伴随式，它们是
一一对应的，二元码伴随式是 H阵中与错误
码元对应列之和。
例 2：计算（ 7,3）码接收码字 R的伴随式
设（ 7,3）码的监督矩阵为：
?
?
?
?
?
?
?
?
?
?
?
?
?
1000110
0100011
0010111
0001101
H
发送码字 C=（ 1010011）
接收码字 R=（ 1010011）
T
TT
0
1
1
0
0
1
0
1
1000110
0100011
0010111
0001101
HRS
伴随式为：
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
1
1
1
0
1
1
0
0
1
1
1
1000110
0100011
0010111
0001101
HRS
TT
接收码字 R=（ 1110011）
接收字无错
ST≠0，接收字有错。
ST等于 H的第二列，所以码字
R的第二位是错的。
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） 定义：设 C是一个 （ n,k） 线性码, 如果 C中一个码字
经任意循环移位后仍然是 C中的一个码字, 则此码称为
循环码 。
+ 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维矢量 C=（ cn-1,cn-2,….,c1,c0 ），可以用一
个次数不超过 n-1的多项式唯一确定。
012211)( cxcxcxcxC nnnn ????? ???? L
C循环 1次：
102312)1( )( ????? ????? nnnnn cxcxcxcxC L
C循环 i次：
ininininnini cxcxcxcxcxC ????????? ??????? LL 1102211)( )(
)1m od ()()()1( ?? nxxxCxC
表示为：
码字的 1次循环多项式是
原码多项式乘 x再除以
（ xn+1）的余式。
码字的 i次循环多项式是原码多项式乘 xi再除以
（ xn+1）的余式。
)1m o d ()()()( ?? nii xxCxxC
例 3：码字 0011101经过循环移位，可得到其他 6个非 0码字。
原码字对应码多项式为 x4+x3+x2+1，乘以 xi (i=1…6)
再模 x7+1。
3 循环码的生成矩阵和监督矩阵
1）生成多项式 g(x)的确定, g(x)是一个能除尽 xn+1的 n-k阶
多项式。
0111)( gxgxcxgxg knknknkn ????? ?????? L
阶数低于 n并能被 g(x)除尽的一组多项式构成一个（ n,k）
循环码。 C (x) = M (x) g (x)
2) 生成矩阵,
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
)(
)(
)(
)(
)(
2
1
xg
xxg
xgx
xgx
xG
k
k
?
3）生成多项式 g(x)的性质,
? 在（ n,k）循环系统中存在一个（ n-k）次码多项式。
? 在（ n,k）循环码中,n-k次码多项式是最低次码多项
式。
? 在（ n,k）循环码中,g(x)是唯一的 n-k次多项式。
? 在（ n,k）循环码中，每个多项式 C(X)都是 g(x)的倍
数；每个为 g(x)倍式且次数小于或等于 n-1的多项式，
必是一个码多项式。
? 任意（ n,k）循环码的生成多项式 g(x)一定整除 1+xn
4) 求解方法,
求解（ n,k）循环码时，只要分解多项式 xn+1，从中
取出（ n-k）次因式作生成多项式即可求解。
例 4：设（ 7,4）循环码的生成多项式 g(x)=x3+x+1，求生成矩阵 G(x)及生
成码字。
?
?
?
?
?
?
?
?
?
?
?
?
?
?
??
??
??
??
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
1)(
)(
)(
)(
)(
3
24
235
346
2
3
xx
xxx
xxx
xxx
xg
xgx
xgx
xgx
xG
?
?
?
?
?
?
?
?
?
?
?
?
?
1101000
0110100
0011010
0001101
G
C=MG
例 5：求（ 7,3）循环码的生成多项式。
分解多项式 x7+1
)1)(1)(1(
)1)(1(1:
))((:
323
234567
122321
??????
?????????
???????? ?????
xxxxx
xxxxxxxx
babbabaababa nnnnnnn
得
由 L
n-k=7-3=4,∴ g（ x）为 4次多项式
1)1)(1()(
1)1)(1()(
243
23423
????????
????????
xxxxxxxg
xxxxxxxg
或
5） 监督矩阵
?循环码的生成多项式必须能除尽 xn+1
)()(1 xhxgx n ??
h(x)是监督多项式（校验多项式）
0111)( hxhxhxhxh kkkk ????? ?? L
h ( x ) 的反多项式( x )*h
001hh1
01hh10
1hh100
( x )*hx
( x )*xh
( x )*h
监督矩阵：H
21
21
21
1kn
??
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
??
L
???????
L
L
?
例 6：（ 7,3）循环码为例说明监督矩阵的确定。
01
2
2
3
3
4
4
23423 1)1)(1()(
gxgxgxgxg
xxxxxxxg
?????
????????生成多项式：
)1)(1)(1(
)1)(1(1
323
234567
??????
?????????
xxxxx
xxxxxxxx分解：
0122333 1)( hxhxhxhxxxh ???????? 监督多项式：
001001
2
201102
3
30211203
4
31221304
5
322314
6
3324
7
34
7
)()(
)()(
)()(
)()(1
hgxhghgxhghghg
xhghghghgxhghghghg
xhghghgxhghgxhg
xgxhx
??????
????????
??????
??
x3的系数：
x4的系数：
x5的系数：
x6的系数：
030211203 ???? hghghghg
031221304 ???? hghghghg
两端同次项系数相等
0322314 ??? hghghg
03324 ?? hghg
写成矩阵：
0
0
0
000
000
000
000
0
1
2
3
4
3210
3210
3210
3210
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
g
g
g
g
g
hhhh
hhhh
hhhh
hhhh
第一行元素为 h(x)系数反序排列。
1)(* 23 ??? xxxh 第二、三、四行元素为第一行移位。
监督矩阵：
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
0001011
0010110
0101100
1011000
)(*
)(*
)(*
)(*
)3,7(
3
2
xhx
xhx
xxh
xh
H
4 循环码的检错能力
1） 能检出全部单个错误码
2） 能检出全部离散的二位错
3）能检出全部的奇数个错码
4）能检测所有长度不超过（ n-k）的突发错误
5）在突发长度 b大于（ n-k）的错误中，
若 b=n-k+1，则（ n-k）循环码不能检测概率为 2-（ n-k-1） （能检
测的概率为 [1- 2-（ n-k-1） ]）
若 b>n-k+1，则（ n-k）循环码不能检测概率为 2-（ n-k） （能检测
的概率为 [1- 2-（ n-k） ]）
5 循环码的 伴随多项式,
假设发送的 码多项式 C(x)和 错误图样多项式 e(x)以及 接
收的码多项式 R(x)分别为：
?
?
??
n
i
in
i xCxC
1
)( ?
?
??
n
i
in
i xexe
1
)( ?
?
??
n
i
in
i xrxR
1
)(
则对于加性信道有,R(x)=C(x)+e(x)
设 g(x)为码的生成多项式，由于码字多项式 C(x)能被 g(x)
除尽，故有：
R(x) modg(x)=e(x)modg(x)
)(
)()(
)(
)()(
)(
)(
xg
xexp
xg
xexC
xg
xR ????即：
定义伴随多项式为：
S(x)=e(x) modg(x)
?根据伴随式的定义，若无错误传输，则
S(x)=0，否则 S(x) ≠0,由此可实现循环码
的检错。
?因为 g(x)的次数为 n-k,e(x)的次数为 n-1，
所以伴随式的最高次数为 n-k-1，那么 S(x)共
有 n-k项，故有 2n-k种可能的伴随式。
若满足 2n-k≧n+1,则循环码具有纠错能力。
例 7：前例中的（ 7,3）循环码，若接收到的码字
为 1100100，判断是否为许用码字。
解：接收码字 1100100码多项式为,R (x)=x6+x5+x2，
g(x)=x4+x2+x+1
由伴随式 S(x)=R(x) modg(x)=e(x)modg(x)，
有 S(x)= x6+x5+x2 mod(x4+x2+x+1)=1
∵S(x) ≠0, ∴ 该码字不是（ 7,3）循环码的许用
码字。
6 循环码的编码器
? 步骤：
① 用 xn-k乘以信息多项式 M(x) 。
② 用 g(x)除以 xn-k M(x) 得到余式 b(x)。
③ 作码字 b(x)+ xn-k M(x) 多项式。
(7,4)系统循环码为例,u=(1001) 即
D1 D2 + D3 +
输入
校验位
码字输出
)(
)()(
)(
)(
xg
xbxq
xg
xMx kn ???? )()()( xbkxxMxC
n ???
)1()()( 33 xxxgxg ????
31)( xxu ??
? ?1001110?? C
7 循环码的译码器
? 译码三步
? 伴随式 S的计算
? 由 S得到错误图样
? 纠正
? 生成多项式 g(x)去
除接收码字 R(x)
校正子 S的计算
)(m od)()( xgxRxS ?
5.5 卷积码 (连环码 )
?在分组码中,任何特定的时间单位内编码器所
产生的 n个码元的码组,仅取决于该时间单位
内 k个消息位,
?存在着另一种码,由编码器在特定的时间内所
产生的码元不但取决于这个特定时间段内进
入的信息组,而且也与前面的时间段内的信息
组有关,这种码称为 卷积码,
?卷积码的编码可用移位寄存器来完成
?卷积码有多种描述方法，分为两类
?解析描述法：生成矩阵法，离散卷积法，生
成多项式法。解析法多用于编码。
?图形描述法：包括状态图、数图、网格图等。
译码采用图形法，尤其是网格图。
一、定义：对于任一给定时刻，编码器的一个
输出码字不仅与该时刻的当前输入码字有关，
还与编码器的移位寄存器中存储的前面 m个
输入信息码字有关。因此卷积码记为
(n0,k0,m0)卷积码 。
? n0为输出的每个码字的位数；
? k0为输入的每个信息码字的位数；
? m0为移位寄存器中存储的信息码字个数（级连的移
位寄存器个数）
定义,m0为卷积码的 记忆长度 。
(m0+1)为卷积码的 码字约束长度,相应的 比特
（码元）约束长度 为 (m0+1)n0。
卷积码的码率为 R=k0/n0，它也表示卷积码的 编
码效率 。
卷积码可以是线性码，但不是分组码，卷积码是有
记忆的编码
例 8：给出一个（ 3,2,1）卷积码编码器的原理图
该编码器由 2个移位寄存器构成。
编码器每个并行输入一个 2位信息码字：
则并行输出一个 3位卷积码字：
Pi为监督元，有：
可见，卷积码当前码字的监督元不仅与当前输入的信
息元有关，还与前次输入的 2个信息码元有关。
][ )2()1( iii mmm ?
][][ )2()1()3()2()1( iiiiiii pmmCCCC ??
)2(1)1(1)2()1( ?? ???? iiiii mmmmp
二、卷积码的生成序列
? 卷积码的生成序列
设卷积码编码器输入码序列 （ 待编码的信息序列 ） 为
U＝ ［ u0(1)u0(2)…u0（ k0） u1(1)u1(2)
…u1(k0)…us(1)us(2)…us(k0)…］
C＝ ［ c0(1)c0(2)…c0(n0)c1(1)c1(2)
…c1(n0)…cs(1)cs(2)…cs(n0)…］
则编码器输出码序列中任一子码可以由如下卷积
关系给出：
00
0
11
( ) ( ) (,),1,2,,
km
s s t t
it
C j u i g i j j n?
??
????
gt(i,j)为非系统卷
积码的生成序列
? 系统码的生成矩阵
系统卷积码序列中, 对应于前 k0位, 生成序列 g(i,j)
中有 k0× k0个生成序列是固定的, 即,
1
(,)
0
ij
g i j
ij
???
? ?
???
（ i,j≦ k0）
对应后 (n0-k0)个监督位,k0× (n0-k0)个生成序列需要给定,
以便确定每个子码中 n0-k0个监督元,则码字,
00
0
00
10
( ) ( ) 1,2,,
( ) ( ) (,),1,,
ss
km
s s t
it
c j u i j k
c j u i g i j j k n?
??
? ? ? ?
?
?
? ? ? ?
?
??
g(i,j)为系统卷积
码的生成序列
例 9：（ 3,1,2）系统卷积码的生成序列为：
]101[])3,1()3,1()3,1([)3,1(
]001[])2,1()2,1()2,1([)2,1(
]001[)1,1(
210
210
??
??
?
gggg
gggg
g
则其任一码字为：
)3,1()1()3,1()1()3,1()1(
)3,1()1()3(
)2,1()1()2,1()1()2,1()1(
)2,1()1()2(
)1()1(
22110
0
22110
0
0
0
gugugu
guc
gugugu
guc
uc
sss
m
t
ttss
sss
m
t
ttss
ss
??
?
?
??
?
?
???
?
???
?
?
?
?
三、卷积码的生成矩阵和监督矩阵
? 卷积码的生成矩阵
上例中
)3,1()1()3,1()1()3,1()1(
)1()1()3,1()1()3(
)2,1()1()2,1()1()2,1()1(
)1()2,1()1()2(
)1()1(
22110
2
0
22110
0
0
0
gugugu
uuguc
gugugu
uguc
uc
sss
ss
m
t
ttss
sss
s
m
t
ttss
ss
??
?
?
?
??
?
?
???
???
???
??
?
?
?
假设输入为,U=(u1,u2,u3,…)
则输出为,C=(u1 u1 u1,u2 u2 u2,u3 u3 u3+u1,u4 u4 u4+u2…)
写成矩阵形式,C=UG
? ?
])()([
1 1 1
0 0 01 1 1
0 0 10 0 01 1 1
0 0 00 0 10 0 01 1 1
0 0 00 0 00 0 10 0 01 1 1
24441333222111
4321
L
??????
L
L
L
L
L
L
uuuuuuuuuuuuuu
uuuuUGC
???
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
??
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
L
L
L
???
L
LL
0
10
21
01010
0210
G
GG
GG
GGGG
GGGG
G
mm
m卷积码的基本生
成矩阵。
生成矩阵可以改写为：
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
L
L
L
L
??
L
L
00
10100
02100
00
000
pI
pppI
ppppI
G
k
mk
mk
Ik0为 k0× k0阶单位矩阵
0为 k0× k0阶全 0方阵
pl为 k0× (n0-k0)阶矩阵。
考虑一个约束长度内的码序列：
U=[u0 u1 u2…u m0]
得到卷积码的初始截短码组 C：
C=[c0 c1 c2…c m0]
?
?
?
?
?
?
?
?
?
?
?
?
?
?
00
10100
02100
00
000
pI
pppI
ppppI
G
k
mk
mk
??
L
L
?
?
?
?
?
?
?
?
?
?
?
?
??
??
??
?
),()2,()1,(
),2()2,2()1,2(
),1()2,1()1,1(
00000
000
000
nkgkkgkkg
ngkgkg
ngkgkg
p
lll
lll
lll
l
L
???
L
L
截短码组的生成矩阵,
g=[Ik0p0 0p1 … 0p m0]
]101[])3,1()3,1()3,1([)3,1(
]011[])2,1()2,1()2,1([)2,1(
]001[)1,1(
210
210
??
??
?
gggg
gggg
g
例 10：（ 3,1,2）系统卷积码的生成序列为：
? ?
? ?
? ?10])3,1()2,1([
01])3,1()2,1([
11])3,1()2,1([
21
222
111
000
??
??
??
?
ggp
ggp
ggp
p l 阶矩阵为
]001010111[
]000[ 02100
?
? mk ppppIg L
?
?
?
?
?
?
?
?
?
?
?
1 1 1
0 1 01 1 1
0 0 10 1 01 1 1
G
]1 1 00 1 01 1 1[
1 1 1
0 1 01 1 1
0 0 10 1 01 1 1
]1 0 1[
]1 0 1[
?
?
?
?
?
?
?
?
?
?
?
??
?
UGC
U
则
若
? 卷积码的监督矩阵
(n0,k0,m0)码的基本监督矩阵为：
00 1 1 00 0 0
T T T T
m m rh p p p p I???? ??
式中,h——(n0-k0)× n0N阶矩阵 。
(n0,k0,m0)码的监督矩阵为
0
11
1 2 1 0
1 2 1 1
00
0 0 0
0 0 0 0
T
r
TT
T T T T
m m r
T T T T T
m m r
PI
PP
H
P P P P I
P P P P P I
??
?
??
??
???
??
??
式中,Ｈ —— (n0-k0)N× n0N
(n0,k0,m0)码的监督矩阵为
【 例 5― 12】 设 (3,1,2)系统码的生成序
列为
g(1,1)＝ 1
g(1,2) ＝ ［ g0(1,2),g1(1,2),g2(1,2) ］
g(1,3)＝ ［ g0(1,3),g1(1,3),g2(1,3)］
求该码的监督矩阵 。
由公式式得 (3,1,2)码的监督矩阵为
02
0 0 2
0 0 0 2
0
00
T
TT
T T T
PI
H P P I
P P P I
??
??
?
??
??
其中,H——6× 9阶矩阵 (N(n0-k0)＝ 6,Nn0＝ 9)
I2——2
0—— 2阶全 0方阵。
而 pT0,pT1,pT2,分别为
0 12
0 1 2
0 1 2
( 1,2) ( 1,2) ( 1,2)
,,
( 1,3 ) ( 1,3 ) ( 1,3 )
T T Tg ggp p p
g g g
?? ? ? ? ?
? ? ??? ? ? ? ?
? ? ? ???
其矩阵方程如下：
02
1 0 2
2 1 1 2
00
00
T
T T T T
T T T
pI
p p I C
p p p I
??
??
?
??
??
其中,CT——初始截短码组的转置，
C＝［ c0(1)c0(2)c0(3)c1(1)c1(2)c1(3)c2(1)c2(2)c2(3)
0T——6× 1阶全 0阵 。
它的基本监督阵是一个 2× 9阶阵, 即：
2 1 0 200TTTh P P P I??? ??
四 卷积码编码器：
us(1) Us-1(1) Us-2(1)
cs(1)
g0(1,2) g1(1,2) g2(1,2)
g0(1,3) g1(1,3) g2(1,3)
cs(2)
cs(3)
串行编码电路
us(1)
例 9：
us(1)
cs(1)
cs(2)
cs(3)
g2(1,2) g1(1,2) g0(1,2)
g2(1,3) g2(1,3) g0(1,3)
)3,1()1( 22 gu s? )3,1()1( 11 gu s?
)2,1()1( 22 gu s? )2,1()1( 11 gu s ?
Ⅰ 型编码电路
需要 n0-k0组寄存器，每组为 m0个，一共需要 (n0-k0)m0个寄存器
us(1)
cs(1)
g0(1,2) g1(1,2) g2(1,2)
cs(2)
g0(1,3) g1(1,3) g2(1,3)
cs(2)
ⅠⅠ 型编码电路
需要 k0组寄存器，每组为 m0个，一共需要 k0× m0个寄存器
?卷积码经典的译码方法有大数逻辑译码和维
特比译码
小结
?线性分组码的基本概念
?线性分组码的定义、系统码的概念
?生成矩阵、校验矩阵及其相互关系
?线性分组码的编码：利用生成矩阵
?译码：利用伴随式
?线性分组码的检纠错能力及最小码距的确定
?汉明码、循环码及卷积码
习题
? P175[5-5]
? P176
[5-13,5-15,5-16,5-17,5-18,5-20,5-21]
? P177[5-29]
?信道编码的基本概念和基本原理
?线性分组码
?循环码、卷积码 和秩距离码
?突发错误的纠正
?级连码、交织码及 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??
信息位 监督位
一、基本概念
? 分组码的监督方程
? 矩阵形式
监督方程( 校验方程)
ccc
ccc
cccc
ccc
为监督元c,c,c,c为信息元,,c,c,c
)c,c,c,c,c,c,(cc
450
561
4562
463
0123456
0123456
?
?
?
?
?
?
?
?
??
??
???
??
?
? ?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
0
0
0
1001101
0101011
0010111
0123456 ccccccc
? 监督矩阵
? 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）汉明码 。
例 1：构造一个二元的（ 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最小
距离的问题,
2,伴随式和错误检测
1）伴随式
S=RHT或 ST=HRT—— 接收码字 R的伴随式（监督子，或校验子）
设，发送码字 C=（ cn-1,cn-2,…,c 0）
接收码字 R=（ rn-1,rn-2,…,r 0）,
则，差错码组（错误图样） E=R-C=（ en-1,en-2,…,e 0）
如果 ei=0，表示 ri = ci
ei=1，表示 ri ≠ci
R=C+E
伴随式,ST=HRT=H（ C+E） T=HCT+HET
=HET（因为 HCT=0T）
=h1en-1+h2en-2+…+h ne0
即,S=EHT
结论：
?伴随式只与错误图样有关，与发送的具体码
字无关。
? S=0，表示没有出错,S≠0，判有错。
?不同的错误图样具有不用的伴随式，它们是
一一对应的，二元码伴随式是 H阵中与错误
码元对应列之和。
例 2：计算（ 7,3）码接收码字 R的伴随式
设（ 7,3）码的监督矩阵为：
?
?
?
?
?
?
?
?
?
?
?
?
?
1000110
0100011
0010111
0001101
H
发送码字 C=（ 1010011）
接收码字 R=（ 1010011）
T
TT
0
1
1
0
0
1
0
1
1000110
0100011
0010111
0001101
HRS
伴随式为：
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
1
1
1
0
1
1
0
0
1
1
1
1000110
0100011
0010111
0001101
HRS
TT
接收码字 R=（ 1110011）
接收字无错
ST≠0，接收字有错。
ST等于 H的第二列，所以码字
R的第二位是错的。
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） 定义：设 C是一个 （ n,k） 线性码, 如果 C中一个码字
经任意循环移位后仍然是 C中的一个码字, 则此码称为
循环码 。
+ 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维矢量 C=（ cn-1,cn-2,….,c1,c0 ），可以用一
个次数不超过 n-1的多项式唯一确定。
012211)( cxcxcxcxC nnnn ????? ???? L
C循环 1次：
102312)1( )( ????? ????? nnnnn cxcxcxcxC L
C循环 i次：
ininininnini cxcxcxcxcxC ????????? ??????? LL 1102211)( )(
)1m od ()()()1( ?? nxxxCxC
表示为：
码字的 1次循环多项式是
原码多项式乘 x再除以
（ xn+1）的余式。
码字的 i次循环多项式是原码多项式乘 xi再除以
（ xn+1）的余式。
)1m o d ()()()( ?? nii xxCxxC
例 3：码字 0011101经过循环移位，可得到其他 6个非 0码字。
原码字对应码多项式为 x4+x3+x2+1，乘以 xi (i=1…6)
再模 x7+1。
3 循环码的生成矩阵和监督矩阵
1）生成多项式 g(x)的确定, g(x)是一个能除尽 xn+1的 n-k阶
多项式。
0111)( gxgxcxgxg knknknkn ????? ?????? L
阶数低于 n并能被 g(x)除尽的一组多项式构成一个（ n,k）
循环码。 C (x) = M (x) g (x)
2) 生成矩阵,
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
)(
)(
)(
)(
)(
2
1
xg
xxg
xgx
xgx
xG
k
k
?
3）生成多项式 g(x)的性质,
? 在（ n,k）循环系统中存在一个（ n-k）次码多项式。
? 在（ n,k）循环码中,n-k次码多项式是最低次码多项
式。
? 在（ n,k）循环码中,g(x)是唯一的 n-k次多项式。
? 在（ n,k）循环码中，每个多项式 C(X)都是 g(x)的倍
数；每个为 g(x)倍式且次数小于或等于 n-1的多项式，
必是一个码多项式。
? 任意（ n,k）循环码的生成多项式 g(x)一定整除 1+xn
4) 求解方法,
求解（ n,k）循环码时，只要分解多项式 xn+1，从中
取出（ n-k）次因式作生成多项式即可求解。
例 4：设（ 7,4）循环码的生成多项式 g(x)=x3+x+1，求生成矩阵 G(x)及生
成码字。
?
?
?
?
?
?
?
?
?
?
?
?
?
?
??
??
??
??
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
1)(
)(
)(
)(
)(
3
24
235
346
2
3
xx
xxx
xxx
xxx
xg
xgx
xgx
xgx
xG
?
?
?
?
?
?
?
?
?
?
?
?
?
1101000
0110100
0011010
0001101
G
C=MG
例 5：求（ 7,3）循环码的生成多项式。
分解多项式 x7+1
)1)(1)(1(
)1)(1(1:
))((:
323
234567
122321
??????
?????????
???????? ?????
xxxxx
xxxxxxxx
babbabaababa nnnnnnn
得
由 L
n-k=7-3=4,∴ g（ x）为 4次多项式
1)1)(1()(
1)1)(1()(
243
23423
????????
????????
xxxxxxxg
xxxxxxxg
或
5） 监督矩阵
?循环码的生成多项式必须能除尽 xn+1
)()(1 xhxgx n ??
h(x)是监督多项式（校验多项式）
0111)( hxhxhxhxh kkkk ????? ?? L
h ( x ) 的反多项式( x )*h
001hh1
01hh10
1hh100
( x )*hx
( x )*xh
( x )*h
监督矩阵：H
21
21
21
1kn
??
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
??
L
???????
L
L
?
例 6：（ 7,3）循环码为例说明监督矩阵的确定。
01
2
2
3
3
4
4
23423 1)1)(1()(
gxgxgxgxg
xxxxxxxg
?????
????????生成多项式：
)1)(1)(1(
)1)(1(1
323
234567
??????
?????????
xxxxx
xxxxxxxx分解：
0122333 1)( hxhxhxhxxxh ???????? 监督多项式：
001001
2
201102
3
30211203
4
31221304
5
322314
6
3324
7
34
7
)()(
)()(
)()(
)()(1
hgxhghgxhghghg
xhghghghgxhghghghg
xhghghgxhghgxhg
xgxhx
??????
????????
??????
??
x3的系数：
x4的系数：
x5的系数：
x6的系数：
030211203 ???? hghghghg
031221304 ???? hghghghg
两端同次项系数相等
0322314 ??? hghghg
03324 ?? hghg
写成矩阵：
0
0
0
000
000
000
000
0
1
2
3
4
3210
3210
3210
3210
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
g
g
g
g
g
hhhh
hhhh
hhhh
hhhh
第一行元素为 h(x)系数反序排列。
1)(* 23 ??? xxxh 第二、三、四行元素为第一行移位。
监督矩阵：
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
0001011
0010110
0101100
1011000
)(*
)(*
)(*
)(*
)3,7(
3
2
xhx
xhx
xxh
xh
H
4 循环码的检错能力
1） 能检出全部单个错误码
2） 能检出全部离散的二位错
3）能检出全部的奇数个错码
4）能检测所有长度不超过（ n-k）的突发错误
5）在突发长度 b大于（ n-k）的错误中，
若 b=n-k+1，则（ n-k）循环码不能检测概率为 2-（ n-k-1） （能检
测的概率为 [1- 2-（ n-k-1） ]）
若 b>n-k+1，则（ n-k）循环码不能检测概率为 2-（ n-k） （能检测
的概率为 [1- 2-（ n-k） ]）
5 循环码的 伴随多项式,
假设发送的 码多项式 C(x)和 错误图样多项式 e(x)以及 接
收的码多项式 R(x)分别为：
?
?
??
n
i
in
i xCxC
1
)( ?
?
??
n
i
in
i xexe
1
)( ?
?
??
n
i
in
i xrxR
1
)(
则对于加性信道有,R(x)=C(x)+e(x)
设 g(x)为码的生成多项式，由于码字多项式 C(x)能被 g(x)
除尽，故有：
R(x) modg(x)=e(x)modg(x)
)(
)()(
)(
)()(
)(
)(
xg
xexp
xg
xexC
xg
xR ????即：
定义伴随多项式为：
S(x)=e(x) modg(x)
?根据伴随式的定义，若无错误传输，则
S(x)=0，否则 S(x) ≠0,由此可实现循环码
的检错。
?因为 g(x)的次数为 n-k,e(x)的次数为 n-1，
所以伴随式的最高次数为 n-k-1，那么 S(x)共
有 n-k项，故有 2n-k种可能的伴随式。
若满足 2n-k≧n+1,则循环码具有纠错能力。
例 7：前例中的（ 7,3）循环码，若接收到的码字
为 1100100，判断是否为许用码字。
解：接收码字 1100100码多项式为,R (x)=x6+x5+x2，
g(x)=x4+x2+x+1
由伴随式 S(x)=R(x) modg(x)=e(x)modg(x)，
有 S(x)= x6+x5+x2 mod(x4+x2+x+1)=1
∵S(x) ≠0, ∴ 该码字不是（ 7,3）循环码的许用
码字。
6 循环码的编码器
? 步骤：
① 用 xn-k乘以信息多项式 M(x) 。
② 用 g(x)除以 xn-k M(x) 得到余式 b(x)。
③ 作码字 b(x)+ xn-k M(x) 多项式。
(7,4)系统循环码为例,u=(1001) 即
D1 D2 + D3 +
输入
校验位
码字输出
)(
)()(
)(
)(
xg
xbxq
xg
xMx kn ???? )()()( xbkxxMxC
n ???
)1()()( 33 xxxgxg ????
31)( xxu ??
? ?1001110?? C
7 循环码的译码器
? 译码三步
? 伴随式 S的计算
? 由 S得到错误图样
? 纠正
? 生成多项式 g(x)去
除接收码字 R(x)
校正子 S的计算
)(m od)()( xgxRxS ?
5.5 卷积码 (连环码 )
?在分组码中,任何特定的时间单位内编码器所
产生的 n个码元的码组,仅取决于该时间单位
内 k个消息位,
?存在着另一种码,由编码器在特定的时间内所
产生的码元不但取决于这个特定时间段内进
入的信息组,而且也与前面的时间段内的信息
组有关,这种码称为 卷积码,
?卷积码的编码可用移位寄存器来完成
?卷积码有多种描述方法，分为两类
?解析描述法：生成矩阵法，离散卷积法，生
成多项式法。解析法多用于编码。
?图形描述法：包括状态图、数图、网格图等。
译码采用图形法，尤其是网格图。
一、定义：对于任一给定时刻，编码器的一个
输出码字不仅与该时刻的当前输入码字有关，
还与编码器的移位寄存器中存储的前面 m个
输入信息码字有关。因此卷积码记为
(n0,k0,m0)卷积码 。
? n0为输出的每个码字的位数；
? k0为输入的每个信息码字的位数；
? m0为移位寄存器中存储的信息码字个数（级连的移
位寄存器个数）
定义,m0为卷积码的 记忆长度 。
(m0+1)为卷积码的 码字约束长度,相应的 比特
（码元）约束长度 为 (m0+1)n0。
卷积码的码率为 R=k0/n0，它也表示卷积码的 编
码效率 。
卷积码可以是线性码，但不是分组码，卷积码是有
记忆的编码
例 8：给出一个（ 3,2,1）卷积码编码器的原理图
该编码器由 2个移位寄存器构成。
编码器每个并行输入一个 2位信息码字：
则并行输出一个 3位卷积码字：
Pi为监督元，有：
可见，卷积码当前码字的监督元不仅与当前输入的信
息元有关，还与前次输入的 2个信息码元有关。
][ )2()1( iii mmm ?
][][ )2()1()3()2()1( iiiiiii pmmCCCC ??
)2(1)1(1)2()1( ?? ???? iiiii mmmmp
二、卷积码的生成序列
? 卷积码的生成序列
设卷积码编码器输入码序列 （ 待编码的信息序列 ） 为
U＝ ［ u0(1)u0(2)…u0（ k0） u1(1)u1(2)
…u1(k0)…us(1)us(2)…us(k0)…］
C＝ ［ c0(1)c0(2)…c0(n0)c1(1)c1(2)
…c1(n0)…cs(1)cs(2)…cs(n0)…］
则编码器输出码序列中任一子码可以由如下卷积
关系给出：
00
0
11
( ) ( ) (,),1,2,,
km
s s t t
it
C j u i g i j j n?
??
????
gt(i,j)为非系统卷
积码的生成序列
? 系统码的生成矩阵
系统卷积码序列中, 对应于前 k0位, 生成序列 g(i,j)
中有 k0× k0个生成序列是固定的, 即,
1
(,)
0
ij
g i j
ij
???
? ?
???
（ i,j≦ k0）
对应后 (n0-k0)个监督位,k0× (n0-k0)个生成序列需要给定,
以便确定每个子码中 n0-k0个监督元,则码字,
00
0
00
10
( ) ( ) 1,2,,
( ) ( ) (,),1,,
ss
km
s s t
it
c j u i j k
c j u i g i j j k n?
??
? ? ? ?
?
?
? ? ? ?
?
??
g(i,j)为系统卷积
码的生成序列
例 9：（ 3,1,2）系统卷积码的生成序列为：
]101[])3,1()3,1()3,1([)3,1(
]001[])2,1()2,1()2,1([)2,1(
]001[)1,1(
210
210
??
??
?
gggg
gggg
g
则其任一码字为：
)3,1()1()3,1()1()3,1()1(
)3,1()1()3(
)2,1()1()2,1()1()2,1()1(
)2,1()1()2(
)1()1(
22110
0
22110
0
0
0
gugugu
guc
gugugu
guc
uc
sss
m
t
ttss
sss
m
t
ttss
ss
??
?
?
??
?
?
???
?
???
?
?
?
?
三、卷积码的生成矩阵和监督矩阵
? 卷积码的生成矩阵
上例中
)3,1()1()3,1()1()3,1()1(
)1()1()3,1()1()3(
)2,1()1()2,1()1()2,1()1(
)1()2,1()1()2(
)1()1(
22110
2
0
22110
0
0
0
gugugu
uuguc
gugugu
uguc
uc
sss
ss
m
t
ttss
sss
s
m
t
ttss
ss
??
?
?
?
??
?
?
???
???
???
??
?
?
?
假设输入为,U=(u1,u2,u3,…)
则输出为,C=(u1 u1 u1,u2 u2 u2,u3 u3 u3+u1,u4 u4 u4+u2…)
写成矩阵形式,C=UG
? ?
])()([
1 1 1
0 0 01 1 1
0 0 10 0 01 1 1
0 0 00 0 10 0 01 1 1
0 0 00 0 00 0 10 0 01 1 1
24441333222111
4321
L
??????
L
L
L
L
L
L
uuuuuuuuuuuuuu
uuuuUGC
???
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
??
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
L
L
L
???
L
LL
0
10
21
01010
0210
G
GG
GG
GGGG
GGGG
G
mm
m卷积码的基本生
成矩阵。
生成矩阵可以改写为：
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
L
L
L
L
??
L
L
00
10100
02100
00
000
pI
pppI
ppppI
G
k
mk
mk
Ik0为 k0× k0阶单位矩阵
0为 k0× k0阶全 0方阵
pl为 k0× (n0-k0)阶矩阵。
考虑一个约束长度内的码序列：
U=[u0 u1 u2…u m0]
得到卷积码的初始截短码组 C：
C=[c0 c1 c2…c m0]
?
?
?
?
?
?
?
?
?
?
?
?
?
?
00
10100
02100
00
000
pI
pppI
ppppI
G
k
mk
mk
??
L
L
?
?
?
?
?
?
?
?
?
?
?
?
??
??
??
?
),()2,()1,(
),2()2,2()1,2(
),1()2,1()1,1(
00000
000
000
nkgkkgkkg
ngkgkg
ngkgkg
p
lll
lll
lll
l
L
???
L
L
截短码组的生成矩阵,
g=[Ik0p0 0p1 … 0p m0]
]101[])3,1()3,1()3,1([)3,1(
]011[])2,1()2,1()2,1([)2,1(
]001[)1,1(
210
210
??
??
?
gggg
gggg
g
例 10：（ 3,1,2）系统卷积码的生成序列为：
? ?
? ?
? ?10])3,1()2,1([
01])3,1()2,1([
11])3,1()2,1([
21
222
111
000
??
??
??
?
ggp
ggp
ggp
p l 阶矩阵为
]001010111[
]000[ 02100
?
? mk ppppIg L
?
?
?
?
?
?
?
?
?
?
?
1 1 1
0 1 01 1 1
0 0 10 1 01 1 1
G
]1 1 00 1 01 1 1[
1 1 1
0 1 01 1 1
0 0 10 1 01 1 1
]1 0 1[
]1 0 1[
?
?
?
?
?
?
?
?
?
?
?
??
?
UGC
U
则
若
? 卷积码的监督矩阵
(n0,k0,m0)码的基本监督矩阵为：
00 1 1 00 0 0
T T T T
m m rh p p p p I???? ??
式中,h——(n0-k0)× n0N阶矩阵 。
(n0,k0,m0)码的监督矩阵为
0
11
1 2 1 0
1 2 1 1
00
0 0 0
0 0 0 0
T
r
TT
T T T T
m m r
T T T T T
m m r
PI
PP
H
P P P P I
P P P P P I
??
?
??
??
???
??
??
式中,Ｈ —— (n0-k0)N× n0N
(n0,k0,m0)码的监督矩阵为
【 例 5― 12】 设 (3,1,2)系统码的生成序
列为
g(1,1)＝ 1
g(1,2) ＝ ［ g0(1,2),g1(1,2),g2(1,2) ］
g(1,3)＝ ［ g0(1,3),g1(1,3),g2(1,3)］
求该码的监督矩阵 。
由公式式得 (3,1,2)码的监督矩阵为
02
0 0 2
0 0 0 2
0
00
T
TT
T T T
PI
H P P I
P P P I
??
??
?
??
??
其中,H——6× 9阶矩阵 (N(n0-k0)＝ 6,Nn0＝ 9)
I2——2
0—— 2阶全 0方阵。
而 pT0,pT1,pT2,分别为
0 12
0 1 2
0 1 2
( 1,2) ( 1,2) ( 1,2)
,,
( 1,3 ) ( 1,3 ) ( 1,3 )
T T Tg ggp p p
g g g
?? ? ? ? ?
? ? ??? ? ? ? ?
? ? ? ???
其矩阵方程如下：
02
1 0 2
2 1 1 2
00
00
T
T T T T
T T T
pI
p p I C
p p p I
??
??
?
??
??
其中,CT——初始截短码组的转置，
C＝［ c0(1)c0(2)c0(3)c1(1)c1(2)c1(3)c2(1)c2(2)c2(3)
0T——6× 1阶全 0阵 。
它的基本监督阵是一个 2× 9阶阵, 即：
2 1 0 200TTTh P P P I??? ??
四 卷积码编码器：
us(1) Us-1(1) Us-2(1)
cs(1)
g0(1,2) g1(1,2) g2(1,2)
g0(1,3) g1(1,3) g2(1,3)
cs(2)
cs(3)
串行编码电路
us(1)
例 9：
us(1)
cs(1)
cs(2)
cs(3)
g2(1,2) g1(1,2) g0(1,2)
g2(1,3) g2(1,3) g0(1,3)
)3,1()1( 22 gu s? )3,1()1( 11 gu s?
)2,1()1( 22 gu s? )2,1()1( 11 gu s ?
Ⅰ 型编码电路
需要 n0-k0组寄存器，每组为 m0个，一共需要 (n0-k0)m0个寄存器
us(1)
cs(1)
g0(1,2) g1(1,2) g2(1,2)
cs(2)
g0(1,3) g1(1,3) g2(1,3)
cs(2)
ⅠⅠ 型编码电路
需要 k0组寄存器，每组为 m0个，一共需要 k0× m0个寄存器
?卷积码经典的译码方法有大数逻辑译码和维
特比译码
小结
?线性分组码的基本概念
?线性分组码的定义、系统码的概念
?生成矩阵、校验矩阵及其相互关系
?线性分组码的编码：利用生成矩阵
?译码：利用伴随式
?线性分组码的检纠错能力及最小码距的确定
?汉明码、循环码及卷积码
习题
? P175[5-5]
? P176
[5-13,5-15,5-16,5-17,5-18,5-20,5-21]
? P177[5-29]
