数字通信第41章纠错码

2023/1/101第4章差错控制编码2023/1/102内容4.1引言4.2纠错编码的基本原理4.3常用的简单编码4.4线性分组码4.5卷积码4.6Turbo码和LDPC码4.7编码调制2023/1/1034.1引言信道分类：从差错控制角度看随机信道：错码的出现是随机的，噪声引起突发信道：错码成串集中出现，干扰、快衰落引起混合信道：既存在随机错码又存在突发错码差错控制技术的种类反馈校验前向纠错检错重发检错删除2023/1/104差错控制技术1.反馈检验法需要双向信道，和前向信道有相同的通信容量。引入较大的延时可以纠正任何错误BA2023/1/1052.前向纠错（FEC）不需要双向信道实时性好靠纠错编码2023/1/106

3.检错重发法（ARQ）自动请求重发需要反向信道，但容量降低，会引入停顿BA2023/1/107三种自动请求重发(ARQ)系统停止等待ARQ系统系统工作在半双工状态，时间没有得到充分利用，传输效率较低。接收码组ACKACKNAKACKACKNAKACKt1233455发送码组12334556t有错码组有错码组AB2023/1/108拉后ARQ系统需要对发送的数据组和答复进行编号，以便识别。系统需要双工信道接收数据有错码组有错码组91011101112214365798576ACK1NAK5NAK9ACK5发送数据57695214367981011101112重发码组重发码组2023/1/109选择重发ARQ系统它只重发出错的数据组，因此进一步提高了传输效率。接收数据有错码组有错码组921436575981011131412发送数据995852143671011131412重发码组重发码组NAK9ACK1NAK5ACK5ACK92023/1/1010ARQ的主要优点：和前向纠错方法相比监督码元较少(码率较高)能使误码率降到很低；检错的计算复杂度较低；检错用的编码方法和加性噪声的统计特性基本无关，能适应不同特性的信道。ARQ技术的优缺点2023/1/1011ARQ的主要缺点：重发而使ARQ系统的传输效率降低。在要求实时通信的场合，例如电话通信，往往不允许使用ARQ法。信道干扰严重时，可能发生因不断重发造成事实上的通信中断。需要双向信道来重发，不能用于单向信道，也不能用于一点到多点的通信系统。ARQ技术的优缺点2023/1/10124.2差错控制编码的基本原理如用三位二进制编码来代表八个字母 000 A 100 E 001 B 101 F 010 C 110 G 011 D 111 H不管哪一位发生错误，都会使传输字母错误如用三位二进制编码传四个字母 000 A 011 B 101 C 110 D发生一位错误，许用码字将变成禁用码字，接收端就能知道出错，但是不能纠错。2023/1/1013如用三位二进制编码传二个字母 000 A 111 B

检二个错误，纠正一个错误。具有检错或纠错的码组，其所用的比特数必须大于信息码组原来的比特数－>引入冗余度。结论2023/1/1014分组码的符号：(n,k)n－码组的总位数，又称为码组的长度（码长），k－码组中信息码元的数目，n–k＝r－码组中的监督码元数目，或称监督位数目。将信息码分组，为每组信息码附加若干监督码的编码称为分组码。分组码的结构

2023/1/1015监督码元：在发送端需要在信息码元序列中增加一些差错控制码元，它们称为监督码元。在分组码中，监督码元仅监督本码组中的信息码元。信息位和监督位的关系：举例如下信息位监督位晴000云011阴101雨1102023/1/1016码率编码效率(码率)：设编码序列中信息码元数量为k，总码元数量为n，则比值k/n就是码率。冗余度：指增加的监督码元多少。例如，若编码序列中平均每两个信息码元就添加一个监督码元，则这种编码的多余度为1/3。理论上，差错控制以降低信息传输速率为代价换取提高传输可靠性。2023/1/1017码重、码距码重(weight)一个码字中“1”的数目码距(distance)两个码字之间对应位置上1、0不同的个数，又叫汉明(Hamming)距。 10110码重：3 01100码重：2最小码距：把某种编码中各个码组之间距离的最小值称为最小码距(d0)。例如，上面的编码的最小码距d0=2。码距：32023/1/1018图9-1码距的几何意义(0,0,0)(0,0,1)(1,0,1)(1,0,0)(1,1,0)(0,1,0)(0,1,1)(1,1,1)a2a0a12023/1/1019为检测e个错码，要求最小码距d0e+1

0123BA汉明距离ed0最小汉明距与检错、纠错能力2023/1/1020为了纠正t个错码，要求最小码距d02t+1BtA汉明距离012345td02023/1/1021为纠正t个错码，同时检测e个错码，要求最小码距先分析下图所示例子。按照检错能力公式，最多能检测4个错码，按照纠错能力公式纠错时，能纠正2个错码。但是，不能同时作到两者，因为当错码位数超过纠错能力时，该码组进入另一码组的圆内而被错误地“纠正”了。BtA汉明距离012345td02023/1/1022 所以，为了在可以纠正t个错码的同时，能够检测e个错码，就需要像下图那样，使某一码组（A）发生e个错误之后所处的位置，与其他码组（B）的纠错圆圈至少距离等于1，不然将落在该纠错圆上从而发生错误地“纠正”。因此，要求最小码距

这种纠错和检错结合的工作方式简称纠检结合。ABe1tt汉明距离2023/1/1023 这种工作方式是自动在纠错和检错之间转换的。当错码数量少时，系统按前向纠错方式工作，以提高传输效率；当错码数量多时，系统按反馈重发方式纠错，以降低系统的总误码率。它适用于大多数时间中错码数量很少，少数时间中错码数量多的情况。2023/1/1024汉明距与检错、纠错能力为检查出e个错误，要求最小码距为为纠正t个错误，要求最小码距为为纠正t个错误，同时检查出e个错误，要求最小码距为2023/1/1025香农信道编码理论香农信道编码定理存在噪声干扰的信道，若离散信道容量为C，只要发送端以低于C的速率R发送信息，则一定存在一种编码方式，使译码的错误概率随着码长N的增加将按指数下降到任意小的值，即E[R]为正实函数，称为误差指数，与R、C的关系如图：RC1C2C1>C2E(R)2023/1/1026香农信道编码理论结论在有扰信道中，只要信息传输速率(码率)小于信道容量，采用信道编码有可能实现任意可靠的信息传输。存在性证明。如码长及信息速率一定，可以通过增大信道容量，使Pe减小。如信道容量及信息速率一定，可以通过增加码长，使错误概率下降。2023/1/1027系统带宽和信噪比的矛盾：为了纠错需要在发送信息码元序列中加入监督码元。这样使发送序列增长，冗余度增大。若仍须保持发送信息码元速率不变，则传输速率必须增大，因而增大了系统带宽。系统带宽的增大将引起系统中噪声功率增大，使信噪比下降。信噪比的下降反而又使系统接收码元序列中的错码增多。一般说来，采用纠错编码后，误码率总是能够得到很大改善的。改善的程度和所用的编码有关。纠错码的作用2023/1/1028未采用纠错编码时， 若接收信噪比等于 7dB，编码前误码率 约为810-4，图中A 点，在采用纠错编码 后，误码率降至约4 10-5，图中B点。 不增大发送功率就能 降低误码率约一个半 数量级。10-610-510-410-310-210-1编码后PeCDEAB信噪比(dB)编码性能举例2023/1/1029若保持误码率在10-5， 图中C点，未采用编 码时，约需要信噪比 Eb/n0=9.5dB。在 采用这种编码时，约 需要信噪比7.5dB，图 中D点。可以节省功率 2dB。通常称这2dB为 编码增益。上面两种情况付出的代 价是带宽增大。10-610-510-410-310-210-1编码后PeCDEAB信噪比(dB)2023/1/1030传输速率和Eb/n0的关系 对于给定的传输系统 若希望提高传输速率， 由上式看出必使信 噪比下降，误码率增 大。假设系统原来工作 在图中C点，提高速率后 由C点升到E点。但加用纠错编码后，仍可将误码率降到D点。这时付出的代价仍是带宽增大。10-610-510-410-310-210-1编码后PeCDEAB信噪比(dB)2023/1/10314.3常用的简单编码奇偶校验码二维奇偶校验码恒比码正反码2023/1/1032奇偶校验码特点：偶校验奇校验编码检错能力：如果以上关系被破坏，则出现错误，因此能检查出奇数个错误，但不能检测偶数个错误。 讨论：这种码检错能力不高(最小码距为dmin=2)，采用什么方法提高呢？2023/1/1033二维奇偶校验码特点：检码字按行排成方阵，不仅对行进行奇偶校验，而且也对列进行奇偶校验。编码：检错能力：有可能检测偶数个错误，但对构成矩形的4个错码检测不出；适于检测突发错误。列监督位，行监督位，/0/1/0/1对称出现4个错码也检不出来2023/1/1034等比码编码规则：电传机传输十位阿拉伯数字时，用5位代码表示，每个码组的长度为5，其中恒有3个“1”，称为“5中取3”恒比码。共有种许用码组。检错能力：能够检测码组中所有奇数个错误和部分偶数个错误，但不能检测码组中1变为0与0变为1的错码数目相同的那些偶数个错误。2023/1/1035正反码编码规则：信息位段有奇数个1：1100111001（监督位与信息位重复）信息位段有偶数个1：1000101110（监督位是信息位反码）。检错能力：能够纠正一位错码，并能检测全部两位以下的错码和大部分两位以上的错码。信息位监督位信息位监督位2023/1/1036正反码的解码在上例中，先将接收码组中信息位和监督位按模2相加，得到一个5位的合成码组。然后，由此合成码组产生一个校验码组。若接收码组的信息位中有奇数个“1”，则合成码组就是校验码组；若接收码组的信息位中有偶数个“1”，则取合成码组的反码作为校验码组。最后，观察校验码组中“1”的个数，按下表进行判决及纠正可能发现的错码。2023/1/1037校验码组和错码的关系

例如，若发送码组为1100111001，接收码组中无错码，则合成码组应为1100111001=00000。由于接收码组信息位中有奇数个“1”，所以校验码组就是00000。按上表判决，结论是无错码。校验码组的组成错码情况1全为“0”无错码2有4个“1”和1个“0”信息码中有1位错码，其位置对应校验码组中“0”的位置3有4个“0”和1个“1”监督码中有1位错码，其位置对应校验码组中“1”的位置4其他组成错码多于1个2023/1/10384.4线性分组码内容：一、分组码基本概念二、汉明码的构造三、线性分组码的编码及译码2023/1/1039差错控制编码分类按功能分检错码纠错码纠删码（发现不可纠正的错误时，可发出指示或删除）按信息码元和监督码元之间的校验关系分线性码非线性码按信息码元和监督码元之间的约束方式分分组码卷积码2023/1/1040代数码：建立在代数学基础上的编码。线性码：按照一组线性方程构成的代数码。在线性码中信息位和监督位是由一些线性代数方程联系着的。线性分组码：按照一组线性方程构成的分组码。本节将以汉明码为例引入线性分组码的一般原理。基本概念2023/1/1041定义：可用线性方程组（代数关系）表述码的规律性的分组码称为线性分组码。例如偶校验码的编程原理利用了代数关系：称奇偶校验码为线性分组码。码参数：分组码一般用表示，其中：n是码长，k/n是编码效率2023/1/1042图9-3分组码结构2023/1/1043汉明码（Hamming）提出：为了纠正一位错误码，在分组码中最少要几位监督码位？编码效率能否提高？从这种思想出发，便导致了汉明码的诞生。特点：汉明码是能够纠正一位错码且编码效率较高的一种线性分组码。2023/1/1044汉明码的构造下面介绍汉明码的构造原理。内容：校正子（伴随式）个数与纠错能力的关系举例：（7，4）汉明码校验方程编译码方法2023/1/1045校正子的个数与纠错能力的关系一位校正子的情况先回顾偶校验码,在接收端实际上计算监督关系式：，若，认为码字无错，有错由于s（校正子）只有两种形式“0”或“1”，只能代表有错或无错，因而不找出错码的位置。2023/1/1046校正子的个数与纠错能力的关系二位校正子的情况两个监督式就有两个校正子，其可能值有4种组合：00，01，10，11，这4种组合代表不同信息。若用1种组合表示无错，其余3种组合就可以用来表示一位错码的3种不同位置。2023/1/1047校正子的个数与纠错能力的关系位校正子的情况个监督式能指示一位错码的个可能位置。一般来说，若，则监督位，一般线性码要纠正一位以上的错误应满足：汉明码满足：2023/1/10482.举例：（7，4）汉明码如何构造这些监督关系式（校验方程）：设码字（7，4）～校正子（3个监督关系式中的校正子），可建立三个互为独立的监督关系式。校验位信息位2023/1/1049校验方程的推导的值与错码位置的对应关系可以规定如下表：错码位置错码位置001101010110100111011000无错2023/1/1050可写成偶监督关系式：

2023/1/1051校验方程校验方程2023/1/1052编码方法上面的校验方程可写成监督码元在左边的形式：信息位确定后，可直接按上式计算出监督位。2023/1/1053信息位a6a5a4a3监督位a2a1a0信息位a6a5a4a3监督位a2a1a000000001000111000101110011000010101101001000111101011001010011011000010101101110101001100111110100011100011111112023/1/1054译码方法译码：接收端收到每个码字后，先计算出，再按表判断错码情况。如果不全零，可判出在哪一位出错。2023/1/1055按照上述方法构造的码称为汉明码。表中所列的(7,4)汉明码的最小码距d0=3。因此，这种码能够纠正1个错码或检测2个错码。由于码率k/n=(n-r)/n=1–r/n，故当n很大和r很小时，码率接近1。可见，汉明码是一种高效码。2023/1/1056三、线性分组码的一般原理内容：(1)校验矩阵和生成矩阵(2)校正子S（伴随式）译码2023/1/1057校验矩阵（7，4）汉明码的监督方程矩阵形式上式还可以简记为HAT=0T或AHT=0 2023/1/1058校验矩阵校验矩阵H矩阵称为典型形式，各行一定是线性无关的。而一个非典型形式的经过运算可以化成典型形式，通过校验矩阵可以知道监督码和信息码的监督关系。2023/1/1059生成矩阵若把监督关系式改写为：2023/1/1060生成矩阵改写为矩阵形式：即：其中：2023/1/1061生成矩阵和编码生成矩阵

，通过校验矩阵可以得到生成码组。编码：如果输入码组为00112023/1/1062生成矩阵和编码由这种方式得到的生成矩阵称为典型生成矩阵，由它产生的分组码必定为系统码，也就是信息码字保持不变，监督位附加其后，每行一定是线性无关的，每行都是一个生成码组。2023/1/1063伴随式译码原理发送码组