1、第六章：有噪信道编码一、信道编码的相关概念二、有噪信道编码定理三、纠错编码基本概念基本概念l信源编码的目的是压缩冗余度，提高信息的传输速率。l信道编码的目的是提高信息传输时的抗干扰能力以增加信息传输的可靠性。香农第二定理指出，当信息传输速率低于信道容量时，通过某种编译码方法，就能使错误概率为任意小。目前已有了许多有效的编译码方法，并形成了一门新的技术纠错编码技术。这里所讲的纠错编码即信道编码，与信源编码一样都是一种编码，但两者的作用是完全不同的。本章内容 有扰离散信道的编码定理 纠错编译码的基本原理与分析方法 线性分组码 卷积码 编码与调制的结合TCM码 运用级联、分集与信息迭代概念的纠错码6
2、.1 信道编码的基本概念 一、差错图样（error pattern）定量地描述信号的差错，收、发码之“差”：差错图样E发码C 收码R（模M）差错类型 差错符号：由符号发生差错引起，也叫信号差错，信号差错概率用误码元率表示 差错比特：由信息比特发生差错引起，也叫信息差错，信息差错概率用误比特率表示 对于二进制传输系统，符号差错等效于比特差错；对于多进制系统，一个符号差错到底对应多少比特差错却难以确定。因为一个符号由多个比特组成。差错图样类型 随机差错：若差错图样上各码位的取值既与前后位置无关又与时间无关，即差错始终以相等的概率独立发生于各码字、各码元、各比特；突发差错：前后相关、成堆出现。突发差
3、错总是以差错码元开头、以差错码元结尾，头尾之间并不是每个码元都错，而是码元差错概率超过了某个额定值。二、纠错码分类 从功能角度：检错码、纠错码 码元与原始信息位的关系：线性码、非线性码 对信息序列的处理方法：分组码、卷积码 差错类型：纠随机差错码、纠突发差错码、介于中间的纠随机/突发差错码。构码理论：代数码、几何码、算术码、组合码等 三、差错控制系统分类 前向纠错（FEC）：发端信息经纠错编码后传送，收端通过纠错译码自动纠正传递过程中的差错 反馈重发（ARQ）：收端通过检测接收码是否符合编码规律来判断，如判定码组有错，则通过反向信道通知发端重发该码 混合纠错（HEC）：前向纠错和反馈重发的结合
4、，发端发送的码兼有检错和纠错两种能力 6.1.2矢量空间与码空间 F表示码元所在的数域，对于二进制码，F代表二元域0,1，设n重有序元素的集合V=Vi,若满足条件：1、V中矢量元素在矢量加运算下构成加群；2、V中矢量元素与数域F元素的标乘封闭在V中；3、分配律、结合律成立，则称集合V是数域F上的n维矢量空间，或称n维线性空间，n维矢量又称n重(n-tuples)。01(1)(,),iiiiji nijVVVVVVF 矢量空间与基底注意：1、n维矢量空间一定包含0矢量2、n维矢量空间中的各矢量可能线性无关，也可能线性相关矢量空间中矢量的关系 对于域F上的若干矢量 线性组合：线性相关：其中任一矢量
5、可表示为其它矢量的线性组合 线性无关或线性独立：一组矢量中的任意一个都不可能用其它矢量的线性组合来代替。12,ikVVVV及及1122,()kiiiVaVa VaVaF11220,(iiiaVa VaVaF且且不不全全是是零零)矢量空间与基底3、一组线性无关的矢量 ，线性组合的集合就构成了一个矢量空间V，这组矢量 就是这个矢量空间的基底。n维矢量空间应包含n个基底 基底不唯一12,nV VV二元域GF(2)上三重矢量空间 以（100）为基底可张成一维三重子空间V1，含21=2 个元素，即 以(010)(001)为基底可张成二维三重子空间V2，含 22=4个元素，即 以(100)(010)(00
6、1)为基底可张成三维三重空间V,含 23=8个元素，V1和V2都是V的子空间。)100(),000(1V)011(),010(),001(),000(2V矢量空间 两个矢量正交：V1V2 0 两个矢量空间正交：某矢量空间中的任意元素与另一矢量空间中的任意元素正交 两个矢量空间的基底正交，则两个矢量空间正交 正交的两个子空间V1、V2互为对偶空间(Dual Space)，其中一个空间是另一个空间的零空间（null space，也称零化空间）。码空间 消息消息k长长 (n,k)码字码字n长长 qk 种种 分组编码器分组编码器 qn种种 k维维k重矢量重矢量 n维维n重矢量重矢量 通常通常qn qk
7、，分组编码的任务是，分组编码的任务是要在要在n维维n重矢量空间的重矢量空间的qn种可能组种可能组合中选择其中的合中选择其中的qk个构成一个个构成一个码空间码空间，其元素就是许用码的其元素就是许用码的码集码集。分组编码的任务 选择一个维n重子空间作为码空间。确定由k维k重信息空间到维n重码空间的映射方法。码空间的不同选择方法，以及信息组与码组的不同映射算法，就构成了不同的分组码。6.1.3随机编码 运用概率统计方法在特定信道条件下对编码信号的性能作出统计分析，求出差错概率的上下限边界，其中最优码所能达到的差错概率上界称作随机码界。用这种方法不能得知最优码是如何具体编出来的，却能得知最优码可以好到
8、什么程度，并进而推导出有扰离散信道的编码定理，对指导编码技术具有特别重要的理论价值。Shannon method for proving one baby weighs less than 10 kg 在(N,K)分组编码器中随机选定的码集有qNM种 第m个码集(记作cm)被随机选中的概率是 设与这种选择相对应的条件差错概率是Pe(cm)全部码集的平均差错概率是()(c)NMmPq 11(c)(c)(c)NMNMqqNMeemmemmmPPPqP 必定存在某些码集 某些码集 若 ，就必然存在一批码集 即差错概率趋于零的好码一定存在 11(c)(c)(c)NMNMqqNMeemmemmmPPPq
9、P(c)emePP(c)emePP 0eP 0)(mePc 码集点数M=qK占N维矢量空间总点数qN的比例是F=qK/qN =q-(N-K)当K和N的差值拉大即冗余的空间点数增加时，平均而言码字的分布将变得稀疏，码字间的平均距离将变大，平均差错概率将变小。当F0 即(N-K)时，能否让平均差错概率？Gallager在1965年推导了 的上边界，并证明这个上边界是按指数规律收敛的。0eP eP E(R)为可靠性函数，也叫误差指数 码率：R=(lbM)/N M是可能的信息组合数，M=qK N是每码字的码元数，R表示每码元携带的信息量，单位是每符号比特（bit/symbol）)(RNEeeP R在0
10、,R0区间时E(R)R曲线是斜率为-1（-45）的直线，E(R)反比于R；而 当 R=C 时E(R)=0即可靠性为零。E(R)C R 0 R0 -45 E(R)和和R的关系曲线的关系曲线6.1.4信道编码定理 正定理：只要传信率R小于信道容量C，总存在一种信道码（及解码器），可以以所要求的任意小的差错概率实现可靠的通信。逆定理：信道容量C是可靠通信系统传信率R的上边界，如果R C，就不可能有任何一种编码能使差错概率任意小。l信道编码的目标目标：提高通信的可靠性。l信道编码信道编码，就是按照一定的规则给信源编码后的码符号序列增加一些冗余信息，使其变成具有一定数学规律的码符号序列。l信道译码信道译
11、码，就是按与信道编码器相同的数学规律去掉接收到的码符号序列中的冗余符号。l通常来说，增加的冗余符号越多，检错和纠错能力就越强。但是，增加的冗余符号越多，传输效率就越低。信道编码的相关概念信道编码的相关概念 信道编码器：将信源编码后的符号加上冗余符号，提高传输的可靠性。信道编码的相关概念信道编码的相关概念信道编码的相关概念信道编码的相关概念图1 编码信道模型信道编码器信道译码器信道MXY例例1 1：二进制对称信道二进制对称信道 pppp0101信道编码的相关概念信道编码的相关概念0.90.10.10.9ppppPXYppppP(0)(1)P YppP Ypp(1,0)(1|0)(0)(0|1)P
12、 XYpP XYP YpppP XYpp(0)(1|0)(1)(0|1)EPP YP XYP YP XYppppppppppp译码规则1：信道译码器收到符号“0”译为“0”信道译码器收到符号“1”译为“1”正确译码概率0.1，错误译码概率0.9EP 信道编码的相关概念信道编码的相关概念pppp01010.10.90.90.1ppppP译码规则2：信道译码器收到符号“0”译为“1”信道译码器收到符号“1”译为“0”信道编码的相关概念信道编码的相关概念(0)(0|0)(1)(1|1)EPP YP XYP YP XYppppppppppp0.1EP 正确译码概率0.9，错误译码概率1p010.5 二
13、元对称信道的信道容量C定义6.1 设信道的输入符号集为 ，输出符号集为 。若对每一个输出符号都有一个确定的函数 ，使对应于唯一的一个输入符号 ，则称这样的一个函数为译码规则译码规则，记为12,rXx xx12,sYy yyjy()jF yix()1,2,1,2,jiF yxirjs（）XYx1x2xry1y2ysp(yj|xi)信道编码的相关概念信道编码的相关概念信道12,rXx xx12,sYy yy共有rs 种译码规则121()rxxF yx12()srxxF yx信道编码的相关概念信道编码的相关概念0)1(0)0(FF1)1(0)0(FF0)1(1)0(FF1)1(1)0(FF224sr
14、 译码规则例：pppp0101信道编码的相关概念信道编码的相关概念4.03.03.05.03.02.02.03.05.0P例2：设一个信道的信道矩阵为 ，根据此信道矩阵，设计译码规则。解：11()F yx33()F yx22()F yx译码规则A4.03.03.05.03.02.02.03.05.0P4.03.03.05.03.02.02.03.05.0P11()F yx32()F yx23()F yx译码规则B信道编码的相关概念信道编码的相关概念 对于有r个输入符号，s个输出符号的信道，总共可以设计出 种译码规则，到底哪一种译码规则最好哪一种译码规则最好？依据什么标准什么标准来选择译码规则？
15、问题：sr信道编码的相关概念信道编码的相关概念l设译码规则为 ()jiF yx当输入符号是xi时，译码正确当输入符号为除xi以外的(r-1)种符号时，译码错误正确译码的概率：()|(|)jjijp F yyp xy 错误译码的概率：|)(1)|(1)|(jjjijyyFpyxpyep信道编码的相关概念信道编码的相关概念l 平均正确译码概率：sjjjjEyyFpypP1|)()(l 平均错误译码概率：11()(|)()1()|ssEjjjjjjjPp yp e yp yp F yy信道编码的相关概念信道编码的相关概念 为提高规则通信的可靠性，所采用的译码应当使平均错误译码概率最小。-最大后验概率
16、译码规则最大后验概率译码规则 最常用的译码规则，包括：极大似然译码规则极大似然译码规则 最大后验概率译码规则最大后验概率译码规则信道编码的相关概念信道编码的相关概念(1 1)最大后验概率译码规则最大后验概率译码规则1()1()|sEjjjjPp yp F yy 已知：()0jp y 当求和项中的每一项都达到最小值时，就最小。EP1()|jjp F yy要最小。()|jjp F yy要最大。信道编码的相关概念信道编码的相关概念定义6.2 令 ，而 应满足条件 riyxpyxpjij,.,2,1)|()|(*()jF yx*x*xX称满足上述条件的译码函数对应的译码规则为最大后验最大后验概率译码规
17、则概率译码规则。minEEPP 信道编码的相关概念信道编码的相关概念11121121222212(|)(|)(|)(|)(|)(|)(|)(|)(|)ssrrrsrp xyp xyp xyxp xyp xyp xyxp xyp xyp xyxQsjijijsjjjEyxpypyxpypP1*1*min)|()()|(1)(信道编码的相关概念信道编码的相关概念1y2ysy11121121222212()()()()()()()()()ssXYrrrsrp x yp x yp x yxp x yp x yp x yxp x yp x yp x yxP1y2ysy信道编码的相关概念信道编码的相关概念
18、*min11*()1(|)()(|)ssEjjjijjjiPp yp xyp yp xy1*()sijjip x y问题：最大后验概率 通常是未知的，使用不方便。我们能否推导出更便于使用的译码规则?(|)ijp xy信道编码的相关概念信道编码的相关概念riyxpyxpjij,.,2,1)|()|()()|()()()|()(jijijjypxypxpypxypxp)|()()|()(ijijxypxpxypxp当输入符号等概分布时当输入符号等概分布时(2 2)极大似然译码规则极大似然译码规则)|()|(ijjxypxyp信道编码的相关概念信道编码的相关概念 1)当输入符号等概分布时，采用极大似
19、然译码准则等价于最大后验概率准则。2)当输入符号不等概分布或先验概率未知时，采用极大似然译码准则不一定使 最小。l 关于极大似然译码准则极大似然译码准则：EP信道编码的相关概念信道编码的相关概念当输入符号等概分布时当输入符号等概分布时)|()|()|()|()|()|()|()|()|(21222211121121rsrrssrxypxypxypxypxypxypxypxypxypxxxP1y2ysy(1)rs 项信道编码的相关概念信道编码的相关概念*min11*()1(|)()(|)ssEjjjijjjiPp yp xyp yp xy1*1*()()(|)ssijijijijip x yp
20、x p yx1*1(|)sjijip yxr例3：设信道矩阵为 ，且输入符号等概分布，即 ，求译码规则和平均错误译码概率。0.50.30.20.30.30.40.20.30.5P1231()()()3p xp xp x信道编码的相关概念信道编码的相关概念解：因为输入符号为等概分布，所以由最大似然译码规则可得0.50.30.20.30.30.40.20.30.5P11()F yx33()F yx22()F yx译码规则1(0.30.2)(0.30.3)(0.20.4)0.573EP 信道编码的相关概念信道编码的相关概念min1*1(|)sEjijiPp yxr4.03.03.05.03.02.0
21、2.03.05.0P4.03.03.05.03.02.02.03.05.0P11()F yx33()F yx22()F yx译码规则A4.03.03.05.03.02.02.03.05.0P译码规则B233211)()()(xyFxyFxyF例 6.3 假设输入等概，求以下两种译码规则的平均错误译码概率。信道编码的相关概念信道编码的相关概念4.03.03.05.03.02.02.03.05.0P4.03.03.05.03.02.02.03.05.0P信道编码的相关概念信道编码的相关概念1(0.20.3)(0.30.3)(0.20.5)0.63EP 1(0.20.3)(0.30.3)(0.20.
22、4)0.5673EP 4.03.03.05.03.02.02.03.05.0P4.03.03.05.03.02.02.03.05.0P信道编码的相关概念信道编码的相关概念111(0.30.2)(0.20.5)(0.30.3)0.6442EP 12311()(),()42p xp xp x如果111(0.30.2)(0.20.3)(0.30.4)0.6442EP 1*1*()()(|)ssEijijijijiPp x yp x p yx4.03.03.05.03.02.02.03.05.0P0.1250.0750.050.050.0750.1250.150.150.2XYP信道编码的相关概念信道
23、编码的相关概念1*()(0.1250.05)(0.0750.075)(0.050.125)0.5sEijjiPp x y12311()(),()42p xp xp x如果l 定理定理6.1 平均错误概率与信道疑义度H(X|Y)满足不等式：(|)()log(1)EEH X YH PPr信道编码的相关概念信道编码的相关概念010199.0p01.0pppppp1010P1)1(0)0(FF*1(|)EjiYXxPp yxr)(21pp210信道编码的相关概念信道编码的相关概念000000001010011100101110111二元对称信道的三次扩展信道1113222222332222223000
24、111pp pp pppp pppppppppppp pppp pp ppP000001 010011 100 101110 111pp823NrM=2328Ns信道编码的相关概念信道编码的相关概念322222233222222321ppppppppppppppppppppppppppppxxP12(000)(001)(010)(100)000(011)(101)(110)(111)111FFFFFFFFxx由最大似然译码规则，可得自动纠正一位错233 ppp 4103 sjiijEpMP1*min)|(1xy1y2y8y3y4y5y6y7y信道编码的相关概念信道编码的相关概念l 在输入符号集
25、（M个符号）等概的条件下，每个符号平均携带的最大信息量是 。l 当用n个码元符号来传输M个信源符号时，每个码符号携带的平均信息量，即信道信息传输率为：logMlog/MRn比特 码元符号l 不重复编码时(n=1)，l 重复编码时(n=3)，1/R（比特 码元符号）1/3R （比特 码元符号）信道编码的相关概念信道编码的相关概念 n=1,R=1,n=3,R=1/3,n=5,R=1/5,n=7,R=1/7,n=9,R=1/9,n=11,R=1/11,增加重复次数n，可使 减小很多，但信息传输率R也减少很多。210EP43 10EP51 10EP 74 10EP81 10EP 105 10EPEP信
26、道编码的相关概念信道编码的相关概念3222222323222232000001pp pp pppp ppppppp ppppp pppp ppppP12(000)(010)(100)(110)000(001)(011)(101)(111)001FFFFFFFFxx000001 010011 100 101110 1112*1(|)1.01 10EjiYXxPpM yx信道编码的相关概念信道编码的相关概念l 如果在扩展信源的如果在扩展信源的 个码符号序列中任意选择个码符号序列中任意选择M个序个序列作为列作为信道的输入，以代表信道的输入，以代表M个信源消息个信源消息。Nr(000,001)(000
27、,111)EEPPl 因此若选择因此若选择“000”000”和和“001”001”代表消息代表消息“0”0”和和“1”1”，则，则 信道编码的相关概念信道编码的相关概念l 有没有一种很简便的方法，帮我们选择平均错误概有没有一种很简便的方法，帮我们选择平均错误概率最小的率最小的M个序列？个序列？信道编码的相关概念信道编码的相关概念1）汉明距离2）码的最小距离3）汉明距离与极大似然译码准则信道编码的相关概念信道编码的相关概念定义6.4 设 和 表示两个长度为n的码符号序列，定义12niiiix xxx12njjjjy yyy1(,)kknijijkDxyx y称 为码字 和 之间的汉明距离。ixj
28、y1）汉明距离）汉明距离(,)ijD x y信道编码的相关概念信道编码的相关概念例4：求下面两个码字之间的汉明距离。解：00010101111010011000jiyx7),(jiDyx信道编码的相关概念信道编码的相关概念定义6.5 在二元码C中，任意两个码字之间的汉明距离的最小值，被称为码C的最小距离：minmin(,)ijDD w w(,)ijijwww wC2）码的最小距离）码的最小距离信道编码的相关概念信道编码的相关概念例5：设有n=3的两组码，分别求它们的最小汉明距离。0000111011100000010101001C2Cmin2D解：码 的最小汉明距离为1Cmin1D码 的最小汉
29、明距离为2C信道编码的相关概念信道编码的相关概念 码1码2码3码4码5码600011100000100001110111000000110001000000011011011111010000001010011100101110111信道编码的相关概念信道编码的相关概念 码1码2码3码4码5码字00011100001110111000000110001000000011011011111010000001010011100101110111消 息 数M24448 信 息 传输率R1/32/32/32/51码的最小距离32131平 均错 误概率（最大似然译码）43 10mindEP22 1022
30、.28 1047.8 1023 10结论：码的最小距离越大，平均译码错误概率越小。信道编码的相关概念信道编码的相关概念 设 和 表示两个长度为n的码符号序列，为信道的输入，为信道的输出。和 的汉明距离为D。3)汉明距离与极大似然译码准则汉明距离与极大似然译码准则对于离散平稳无记忆二元对称信道，有12121(|)(|)(|)nnkknDn Djijjjiiijikpp y yyx xxp yxp pyx12niiiix xxx12njjjjy yyyixjyixjy信道编码的相关概念信道编码的相关概念 通常情况下，D越小，就越大。0.5p 0.5p(|)jip yx 根据极大似然译码准则，*(|
31、)(|)jjippiyxyx极大似然译码准则就等价于，当接收到一个长为n的码符号序列 时，在输入码字集中寻找一个 ，使jy*x信道编码的相关概念信道编码的相关概念*)(xyjF),(),(*jijDDyxyx最小距离译码准则最小距离译码准则定理6.2（香农第二定理）设有一离散无记忆平稳信道，其信道容量为C，只要待传送的信息传输率RC，即 ，则无论码长 n 取多大，也不可能使译码错误概率任意小。2nCM 有噪信道编码定理有噪信道编码定理 信道容量是在信道中可靠传输信息的最大信息传信道容量是在信道中可靠传输信息的最大信息传输率。输率。结论：结论：有噪信道编码定理有噪信道编码定理)(expRnEPr
32、E有噪信道编码定理有噪信道编码定理纠错编码纠错编码1 1 纠错码的分类纠错码的分类2 2 纠错码的基本概念纠错码的基本概念 3 3 线性分组码线性分组码 4 4 汉明码汉明码 5 5 循环码循环码 *6 6 卷积码卷积码概述概述l 香农第二定理证明，当香农第二定理证明，当 时时 的码存在。的码存在。l 证明过程采用的是随机编码的方法：证明过程采用的是随机编码的方法：随机编码所得的码集很大，通过搜索得到好码的方法在实随机编码所得的码集很大，通过搜索得到好码的方法在实际上很难实现；际上很难实现；即使找到了好码，这种码的码字也没有规律，不便于译码。即使找到了好码，这种码的码字也没有规律，不便于译码。
33、l 真正实用的信道编码方法还需要通过各种数学工具真正实用的信道编码方法还需要通过各种数学工具来构造，使码具有好的结构性以便于译码。来构造，使码具有好的结构性以便于译码。RC0EP l 近世代数是信道编码理论用到的最重要的数学工具，近世代数是信道编码理论用到的最重要的数学工具，它包括群论、环论、域论、格论、线性代数等许多分支。它包括群论、环论、域论、格论、线性代数等许多分支。l 广义信道编码广义信道编码包括：调制、成形滤波、扩频、上下包括：调制、成形滤波、扩频、上下变频等。变频等。l 纠错编码是提高传输可靠性的最主要的措施之一。纠错编码是提高传输可靠性的最主要的措施之一。概述概述l 纠错编码的纠
34、错编码的基本思路基本思路：根据一定的规律在待发送的信息码元中人为的加根据一定的规律在待发送的信息码元中人为的加入一些入一些冗余码元，冗余码元，这些冗余码元与信息码元之间以某这些冗余码元与信息码元之间以某种确定的规则相互关联（约束）。种确定的规则相互关联（约束）。在接收端按照既定的规则检验信息码元与监督码在接收端按照既定的规则检验信息码元与监督码元之间的关系。如果传输过程出错，则信息码元与监元之间的关系。如果传输过程出错，则信息码元与监督码元之间的关系将受到破坏，从而可以发现错误乃督码元之间的关系将受到破坏，从而可以发现错误乃至纠正错误。至纠正错误。概述概述CE概述概述 mmsgC codeR
35、noisycodenewmsg干扰一般分为两种形式：干扰一般分为两种形式：一是随机噪声，它主要来源于设备的热噪声和散弹一是随机噪声，它主要来源于设备的热噪声和散弹噪声以及传播媒介的热噪声，它是通信系统中的主噪声以及传播媒介的热噪声，它是通信系统中的主要噪声；要噪声；二是脉冲干扰和信道衰落，它的特点是突发出现，二是脉冲干扰和信道衰落，它的特点是突发出现，主要来源于雷电、通电开关、负荷突变或设备故障主要来源于雷电、通电开关、负荷突变或设备故障等。等。概述概述信道可分为三类：信道可分为三类：1.只产生随机错误的信道称为随机信道。比如卫星信道、只产生随机错误的信道称为随机信道。比如卫星信道、同轴电缆、
36、光缆信道以及大多数微波中继信道。同轴电缆、光缆信道以及大多数微波中继信道。2.产生突发错误的信道称为突发信道。实际的短波信道、产生突发错误的信道称为突发信道。实际的短波信道、移动通信信道、由于擦伤造成成串差错的光盘和磁盘，均移动通信信道、由于擦伤造成成串差错的光盘和磁盘，均为这一类信道。为这一类信道。3.有些实际信道既有随机错误又有突发错误，称为混合有些实际信道既有随机错误又有突发错误，称为混合信道。信道。根据不同的信道类型设计的信道编码分为纠随机错误根据不同的信道类型设计的信道编码分为纠随机错误码、纠突发错误码和纠混合错误码。码、纠突发错误码和纠混合错误码。概述概述在通信系统中，纠检错的工作
37、方式有：在通信系统中，纠检错的工作方式有：(1)反馈重传反馈重传(ARQ)(2)前向纠错前向纠错(FEC)(3)混合纠错混合纠错概述概述 发送端经编码后发出能够发现错误的码，接收端收到后经发送端经编码后发出能够发现错误的码，接收端收到后经检验，如果发现传输中有错误，则通过反馈系统把这一判断结检验，如果发现传输中有错误，则通过反馈系统把这一判断结果反馈回发端，然后发送端把前面发出的信息重新传送一次，果反馈回发端，然后发送端把前面发出的信息重新传送一次，直到接收端认为正确地收到信息为止。直到接收端认为正确地收到信息为止。(1)反馈重传反馈重传(ARQ)mCR m检错检错编码编码信道信道检错检错译码
38、译码反馈反馈概述概述(2)前向纠错前向纠错(FEC)mCR m纠错纠错编码编码信道信道纠错纠错译码译码 发送端发出的是具有纠错能力的纠错码，接收端根据译发送端发出的是具有纠错能力的纠错码，接收端根据译码规则进行译码。当误码个数在码的纠错能力范围内时，译码规则进行译码。当误码个数在码的纠错能力范围内时，译码器可以自动纠正错误。码器可以自动纠正错误。概述概述特点：特点：1 1）前向纠错方式不需要反馈信道，特别适合于只能）前向纠错方式不需要反馈信道，特别适合于只能 提供单向信道的场合。提供单向信道的场合。2 2）由于能自动纠错，不要求检错重发，因而延时小，）由于能自动纠错，不要求检错重发，因而延时小
39、，实时性好。实时性好。3 3）随着纠错能力的增强，译码设备也变得复杂。）随着纠错能力的增强，译码设备也变得复杂。概述概述(3)混合纠错混合纠错 对发送端进行适当的编码。当对发送端进行适当的编码。当错误不严重错误不严重，在码的，在码的纠错能力范围之内时，采用自动纠错；当产生的纠错能力范围之内时，采用自动纠错；当产生的差错超差错超出码的纠错能力范围出码的纠错能力范围时，通过反馈系统要求发端重发。时，通过反馈系统要求发端重发。概述概述(1)按按功能功能分：分：检错码：仅能检测误码检错码：仅能检测误码 纠错码：可纠正误码纠错码：可纠正误码 纠删码：兼纠错和检错能力纠删码：兼纠错和检错能力(2)按信息码
40、元与监督码元之间的按信息码元与监督码元之间的检验关系检验关系分：分：线性码：满足线性关系线性码：满足线性关系 非线性码：不存在线性关系非线性码：不存在线性关系 纠错码纠错码1 1 纠错码的分类纠错码的分类(3)按信息码元与监督码元之间的按信息码元与监督码元之间的约束方式约束方式不同分：不同分：分组码：本码组的监督码元仅和本码组的信息元相关。分组码：本码组的监督码元仅和本码组的信息元相关。树码：本码组的监督码元不仅和本码组的信息元相关树码：本码组的监督码元不仅和本码组的信息元相关，而且与前面码组的信息码元有关。如果是线性关系则，而且与前面码组的信息码元有关。如果是线性关系则称为卷积码。称为卷积码
41、。(4)按信息码元在编码后是否保持原形式不变：按信息码元在编码后是否保持原形式不变：系统码：信息码元与监督码元在分组内有确定位置，系统码：信息码元与监督码元在分组内有确定位置，编码后的信息码元保持不变；编码后的信息码元保持不变；非系统码：信息位打乱，与编码前不同。非系统码：信息位打乱，与编码前不同。1 1 纠错码的分类纠错码的分类(5)(5)按纠正差错的类型可分为：按纠正差错的类型可分为：纠纠随机错误随机错误码码 纠纠突发错误突发错误码码 纠纠随机和突发错误随机和突发错误码码1 1 纠错码的分类纠错码的分类非线性卷积码线性树码非线性非循环码循环码线性分组码纠错码纠错码按结构分类如下：纠错码按结
42、构分类如下：1 1 纠错码的分类纠错码的分类l 分组码的表示方法：分组码的表示方法：（二元分组码）（二元分组码）信息码组由信息码组由 k 个信息码元（个信息码元（信息位信息位）组成，共有）组成，共有 2k 个不同的信息码组；个不同的信息码组；附加附加 个校验码元（个校验码元（校验位或监督位校验位或监督位），每），每个校验码元是该信息码组的某些信息码元模个校验码元是该信息码组的某些信息码元模2和；和；编码器输出长度为编码器输出长度为n的码字；的码字；码字的数目共有码字的数目共有 2k；这这2k 个码字的集合称为个码字的集合称为(n,k)分组码；分组码；rnk2 2 纠错码的基本概念纠错码的基本概
43、念 对 二进制(n,k)线性分组码，合法码字数为2k，可用编码空间的序列数为2n个。许用序列，禁用序列 任一种2k信息集合到二进制序列集合(2n)的映射都是一种(n,k)码，因此总共可能的编码方案有 种。22knC2 2 纠错码的基本概念纠错码的基本概念l 信息传输率（码率）信息传输率（码率）l 编码效率编码效率loglog2kMkRnnnkn 发现或构造好码是信道编码研究的主要问题。线性分组码是最具实用价值的一类码，比如汉明码、循环码、BCH码、RS码等。2 2 纠错码的基本概念纠错码的基本概念2 2 纠错码的基本概念纠错码的基本概念对信道编码的一般要求是：对信道编码的一般要求是：纠错检错能
44、力强；纠错检错能力强；信息传输率高；信息传输率高；编码规律简单，实现设备简单且费用合理；编码规律简单，实现设备简单且费用合理；与信道的差错统计特性相匹配。与信道的差错统计特性相匹配。汉明距离汉明距离niiiiccc21cnjjjjccc21cnkjijikkccd1),(cc汉明距离满足距离公理汉明距离满足距离公理(1)非负性非负性(2)对称性对称性(3)三角不等式三角不等式 0),(jidcc),(),(ijjiddcccc),(),(),(jllijidddcccccc2 2 纠错码的基本概念纠错码的基本概念汉明重量汉明重量 1()kniikWcc12niiiic ccc码码C 的最小距离
45、的最小距离 jiddjiji,:),(minminCcccc),()()(),(10cccccclljijnkijidWWccdkk线性分组码的最小距离等于非零码字的最小重量。线性分组码的最小距离等于非零码字的最小重量。2 2 纠错码的基本概念纠错码的基本概念 码1码2码3码4码5码6000111000001000011101110000001100010000000110110111110100000010100111001011101112 2 纠错码的基本概念纠错码的基本概念3 3 线性分组码线性分组码3272163215314CCCCCCCCCCCCC00007326215321431
46、CCCCCCCCCCCCC3.1 校验矩阵与生成矩阵校验矩阵与生成矩阵 7654321CCCCCCCC(1)校验矩阵校验矩阵000010001100100011001011100011017654321CCCCCCCTT0HC0CH TIQH 3 3 线性分组码线性分组码00007326215321431CCCCCCCCCCCCCl 被称为被称为校验矩阵校验矩阵。l 对对 线性分组码，校验矩阵为线性分组码，校验矩阵为 维矩阵。维矩阵。l对于系统码，校验矩阵可以表示为对于系统码，校验矩阵可以表示为H,)n k（()nknH=QI其中 为 维矩阵，为 维单位矩阵。Q()nkk()()nknkI3
47、3 线性分组码线性分组码3272163215314332211CCCCCCCCCCCCCCCCCCC3272163215314CCCCCCCCCCCCC由校验方程，得到由校验方程，得到(2)生成矩阵生成矩阵3 3 线性分组码线性分组码101110011100100111001321CCCC令令123,c c cmGIPC=mG3 3 线性分组码线性分组码3272163215314332211CCCCCCCCCCCCCCCCCCC其中其中 为为 维矩阵，维矩阵，为为 维单位矩阵。维单位矩阵。l 被称为被称为生成矩阵生成矩阵。l 对对 线性分组码，生成矩阵为线性分组码，生成矩阵为 维矩阵。维矩阵。
48、l对于系统码，生成矩阵可以表示为对于系统码，生成矩阵可以表示为G,)n k（knP()knkkkG=IPI3 3 线性分组码线性分组码l把生成矩阵的每一行用一个行向量把生成矩阵的每一行用一个行向量 来来表示，则生成矩阵可以表示为表示，则生成矩阵可以表示为12kmmmm12kGGGG1kiimiC=mGG,1,2,iikG Gl令令 ，则，则3 3 线性分组码线性分组码l由于生成矩阵由于生成矩阵GG的每一行都是一个码字，所以的每一行都是一个码字，所以G G 的每的每行都满足行都满足 ，则有，则有l对于标准形式的校验矩阵和监督矩阵，有对于标准形式的校验矩阵和监督矩阵，有TTi iH HG G0 0
49、TH HG G0 0TTT+Q QI II IP PQ QP P0 0HGTQ QP P(3)校验矩阵和生成矩阵的关系校验矩阵和生成矩阵的关系3 3 线性分组码线性分组码l线性分组码的封闭性线性分组码的封闭性：线性分组码中任意两个码字之：线性分组码中任意两个码字之和仍然是该码的码字。和仍然是该码的码字。证明：设证明：设 和和 分别是码分别是码 中的两个码字，因此有中的两个码字，因此有即即 满足监督方程，所以是码满足监督方程，所以是码 中的一个码字。中的一个码字。TT1TTTT1212TT2(+)H HC C0 0H H C CC CH HC CH HC C0 0H HC C0 01C CC C
50、C C2C C12+C CC C3 3 线性分组码线性分组码例例1：3重复码是一个（重复码是一个（3,1）线性分组码。其生成矩阵为）线性分组码。其生成矩阵为111G1111111321mmmmCCCC3 3 线性分组码线性分组码例例2：（：（4,3）偶校验码是一个（）偶校验码是一个（4,3）线性分组码，其生）线性分组码，其生成矩阵为成矩阵为 110010101001G1100101010013213213214321mmmmmmmmmCCCCC3 3 线性分组码线性分组码例例3：已知生成矩阵为已知生成矩阵为 求生成的线性分组码及由求生成的线性分组码及由H 生成的线性生成的线性分组码。分组码。1
