通信原理第11章

1通信原理2通信原理第11章差错控制编码3第11章差错控制编码11.1概述信道分类：从差错控制角度看随机信道：错码的出现是随机的突发信道：错码是成串集中出现的混合信道：既存在随机错码又存在突发错码差错控制技术的种类检错重发前向纠错反馈校验检错删除4第11章差错控制编码差错控制编码：常称为纠错编码监督码元：上述4种技术中除第3种外，都是在接收端识别有无错码。所以在发送端需要在信息码元序列中增加一些差错控制码元，它们称为监督码元。不同的编码方法，有不同的检错或纠错能力。多余度：就是指增加的监督码元多少。例如，若编码序列中平均每两个信息码元就添加一个监督码元，则这种编码的多余度为1/3。编码效率(简称码率)：设编码序列中信息码元数量为k，总码元数量为n，则比值k/n就是码率。冗余度：监督码元数(n-k)和信息码元数k之比。理论上，差错控制以降低信息传输速率为代价换取提高传输可靠性。5第11章差错控制编码自动要求重发(ARQ)系统3种ARQ系统停止等待ARQ系统数据按分组发送。每发送一组数据后发送端等待接收端的确认(ACK)答复，然后再发送下一组数据。图中的第3组接收数据有误，接收端发回一个否认(NAK)答复。这时，发送端将重发第3组数据。系统是工作在半双工状态，时间没有得到充分利用，传输效率较低。接收码组ACKACKNAKACKACKNAKACKt1233455发送码组12334556t有错码组有错码组6第11章差错控制编码拉后ARQ系统发送端连续发送数据组，接收端对于每个接收到的数据组都发回确认(ACK)或否认(NAK)答复。例如，图中第5组接收数据有误，则在发送端收到第5组接收的否认答复后，从第5组开始重发数据组。在这种系统中需要对发送的数据组和答复进行编号，以便识别。显然，这种系统需要双工信道接收数据有错码组有错码组91011101112214365798576ACK1NAK5NAK9ACK5发送数据57695214367981011101112重发码组重发码组7第11章差错控制编码选择重发ARQ系统它只重发出错的数据组，因此进一步提高了传输效率。接收数据有错码组有错码组921436575981011131412发送数据995852143671011131412重发码组重发码组NAK9ACK1NAK5ACK5ACK98第11章差错控制编码ARQ的主要优点：和前向纠错方法相比监督码元较少即能使误码率降到很低，即码率较高；检错的计算复杂度较低；检错用的编码方法和加性干扰的统计特性基本无关，能适应不同特性的信道。ARQ的主要缺点：需要双向信道来重发，不能用于单向信道，也不能用于一点到多点的通信系统。因为重发而使ARQ系统的传输效率降低。在信道干扰严重时，可能发生因不断反复重发而造成事实上的通信中断。在要求实时通信的场合，例如电话通信，往往不允许使用ARQ法。9第11章差错控制编码ARQ系统的原理方框图在发送端，输入的信息码元在编码器中被分组编码（加入监督码元）后，除了立即发送外，还暂存于缓冲存储器中。若接收端解码器检出错码，则由解码器控制产生一个重发指令。此指令经过反向信道送到发送端。由发送端重发控制器控制缓冲存储器重发一次。接收端仅当解码器认为接收信息码元正确时，才将信息码元送给收信者，否则在输出缓冲存储器中删除接收码元。当解码器未发现错码时，经过反向信道发出不需重发指令。发送端收到此指令后，即继续发送后一码组，发送端的缓冲存储器中的内容也随之更新。10第11章差错控制编码11.2纠错编码的基本原理分组码基本原理：举例说明如下。设有一种由3位二进制数字构成的码组，它共有8种不同的可能组合。若将其全部用来表示天气，则可以表示8种不同天气，例如：“000”（晴），“001”（云），“010”（阴），“011”（雨），“100”（雪），“101”（霜），“110”（雾），“111”（雹）。其中任一码组在传输中若发生一个或多个错码，则将变成另一个信息码组。这时，接收端将无法发现错误。11第11章差错控制编码若在上述8种码组中只准许使用4种来传送天气，例如：“000”＝晴“011”＝云“101”＝阴“110”＝雨这时，虽然只能传送4种不同的天气，但是接收端却有可能发现码组中的一个错码。例如，若“000”（晴）中错了一位，则接收码组将变成“100”或“010”或“001”。这3种码组都是不准使用的，称为禁用码组。接收端在收到禁用码组时，就认为发现了错码。当发生3个错码时，“000”变成了“111”，它也是禁用码组，故这种编码也能检测3个错码。但是这种码不能发现一个码组中的两个错码，因为发生两个错码后产生的是许用码组。12第11章差错控制编码检错和纠错上面这种编码只能检测错码，不能纠正错码。例如，当接收码组为禁用码组“100”时，接收端将无法判断是哪一位码发生了错误，因为晴、阴、雨三者错了一位都可以变成“100”。要能够纠正错误，还要增加多余度。例如，若规定许用码组只有两个：“000”（晴），“111”（雨），其他都是禁用码组，则能够检测两个以下错码，或能够纠正一个错码。例如，当收到禁用码组“100”时，若当作仅有一个错码，则可以判断此错码发生在“1”位，从而纠正为“000”（晴）。因为“111”（雨）发生任何一位错码时都不会变成“100”这种形式。但是，这时若假定错码数不超过两个，则存在两种可能性：“000”错一位和“111”错两位都可能变成“100”，因而只能检测出存在错码而无法纠正错码。13第11章差错控制编码分组码的结构将信息码分组，为每组信息码附加若干监督码的编码称为分组码。在分组码中，监督码元仅监督本码组中的信息码元。信息位和监督位的关系：举例如下信息位监督位晴000云011阴101雨11014第11章差错控制编码分组码的一般结构分组码的符号：(n,k)N－码组的总位数，又称为码组的长度（码长），k－码组中信息码元的数目，n–k＝r－码组中的监督码元数目，或称监督位数目。15第11章差错控制编码分组码的码重和码距码重：把码组中“1”的个数目称为码组的重量，简称码重。码距：把两个码组中对应位上数字不同的位数称为码组的距离，简称码距。码距又称汉明距离。例如，“000”＝晴，“011”＝云，“101”＝阴，“110”＝雨，4个码组之间，任意两个的距离均为2。最小码距：把某种编码中各个码组之间距离的最小值称为最小码距(d0)。例如，上面的编码的最小码距d0=2。16第11章差错控制编码码距的几何意义对于3位的编码组，可以在3维空间中说明码距的几何意义。每个码组的3个码元的值(a1,a2,a3)就是此立方体各顶点的坐标。而上述码距概念在此图中就对应于各顶点之间沿立方体各边行走的几何距离。由此图可以直观看出，上例中4个准用码组之间的距离均为2。(0,0,0)(0,0,1)(1,0,1)(1,0,0)(1,1,0)(0,1,0)(0,1,1)(1,1,1)a2a0a117第11章差错控制编码码距和检纠错能力的关系一种编码的最小码距d0的大小直接关系着这种编码的检错和纠错能力为检测e个错码，要求最小码距d0e+1【证】设一个码组A位于O点。若码组A中发生一个错码，则我们可以认为A的位置将移动至以O点为圆心，以1为半径的圆上某点，但其位置不会超出此圆。若码组A中发生两位错码，则其位置不会超出以O点为圆心，以2为半径的圆。因此，只要最小码距不小于3，码组A发生两位以下错码时，不可能变成另一个准用码组，因而能检测错码的位数等于2。0123BA汉明距离ed018第11章差错控制编码同理，若一种编码的最小码距为d0，则将能检测(d0-1)个错码。反之，若要求检测e个错码，则最小码距d0至少应不小于(e+1)。为了纠正t个错码，要求最小码距d02t+1【证】图中画出码组A和B的距离为5。码组A或B若发生不多于两位错码，则其位置均不会超出半径为2以原位置为圆心的圆。这两个圆是不重叠的。判决规则为：若接收码组落于以A为圆心的圆上就判决收到的是码组A，若落于以B为圆心的圆上就判决为码组B。这样，就能够纠正两位错码。BtA汉明距离012345td019第11章差错控制编码若这种编码中除码组A和B外，还有许多种不同码组，但任两码组之间的码距均不小于5，则以各码组的位置为中心以2为半径画出之圆都不会互相重叠。这样，每种码组如果发生不超过两位错码都将能被纠正。因此，当最小码距d0＝5时，能够纠正2个错码，且最多能纠正2个。若错码达到3个，就将落入另一圆上，从而发生错判。故一般说来，为纠正t个错码，最小码距应不小于(2t+1)。20第11章差错控制编码为纠正t个错码，同时检测e个错码，要求最小码距在解释此式之前，先来分析下图所示的例子。图中码组A和B之间距离为5。按照检错能力公式，最多能检测4个错码，即e=d0–1=5–1=4，按照纠错能力公式纠错时，能纠正2个错码。但是，不能同时作到两者，因为当错码位数超过纠错能力时，该码组立即进入另一码组的圆内而被错误地“纠正”了。例如，码组A若错了3位，就会被误认为码组B错了2位造成的结果，从而被错“纠”为B。这就是说，检错和纠错公式不能同时成立或同时运用。)(10tetedBtA汉明距离012345td021第11章差错控制编码所以，为了在可以纠正t个错码的同时，能够检测e个错码，就需要像下图所示那样，使某一码组（譬如码组A）发生e个错误之后所处的位置，与其他码组（譬如码组B）的纠错圆圈至少距离等于1，不然将落在该纠错圆上从而发生错误地“纠正”。因此，由此图可以直观看出，要求最小码距这种纠错和检错结合的工作方式简称纠检结合。ABe1tt汉明距离)(10teted22第11章差错控制编码这种工作方式是自动在纠错和检错之间转换的。当错码数量少时，系统按前向纠错方式工作，以节省重发时间，提高传输效率；当错码数量多时，系统按反馈重发方式纠错，以降低系统的总误码率。所以，它适用于大多数时间中错码数量很少，少数时间中错码数量多的情况。23第11章差错控制编码11.3纠错编码的性能系统带宽和信噪比的矛盾：由上节所述的纠错编码原理可知，为了减少接收错误码元数量，需要在发送信息码元序列中加入监督码元。这样作的结果使发送序列增长，冗余度增大。若仍须保持发送信息码元速率不变，则传输速率必须增大，因而增大了系统带宽。系统带宽的增大将引起系统中噪声功率增大，使信噪比下降。信噪比的下降反而又使系统接收码元序列中的错码增多。一般说来，采用纠错编码后，误码率总是能够得到很大改善的。改善的程度和所用的编码有关。24第11章差错控制编码编码性能举例未采用纠错编码时，若接收信噪比等于7dB，编码前误码率约为810-4，图中A点，在采用纠错编码后，误码率降至约410-5，图中B点。这样，不增大发送功率就能降低误码率约一个半数量级。10-610-510-410-310-210-1编码后PeCDEAB信噪比(dB)25第11章差错控制编码由图还可以看出，若保持误码率在10-5，图中C点，未采用编码时，约需要信噪比Eb/n0=10.5dB。在采用这种编码时，约需要信噪比7.5dB，图中D点。可以节省功率2dB。通常称这2dB为编码增益。上面两种情况付出的代价是带宽增大。10-610-510-410-310-210-1编码后PeCDEAB信噪比(dB)26第11章差错控制编码传输速率和Eb/n0的关系对于给定的传输系统式中，RB为码元速率。若希望提高传输速率，由上式看出势必使信噪比下降，误码率增大。假设系统原来工作在图中C点，提高速率后由C点升到E点。但加用纠错编码后，仍可将误码率降到D点。这时付出的代价仍是带宽增大。BsssbRnPTnPnTPnE0000)/1(10-610-510-410-310-210-1编码后PeCDEAB信