《差错控制编码》PPT课件.ppt

《《差错控制编码》PPT课件.ppt》由会员分享，可在线阅读，更多相关《《差错控制编码》PPT课件.ppt（59页珍藏版）》请在三一办公上搜索。

1、通信原理,主讲教师：高 渤,含弘光大 继往开来,电路与通信教研室 高渤,2,通信原理【第十一章 差错控制编码】,学习内容,概 述,1,2,3,4,纠错编码的性能,纠错编码的基本原理,5,第十一章 差错控制编码,简单的实用编码,5,线性分组码,卷积码,7,7,5,5,9,低密度奇偶检验码,6,循环码,8,Turbo码,10,网格编码调制,电路与通信教研室 高渤,3,通信原理【第十一章 差错控制编码】,学习目标,学习要点1、差错控制方式和编码分类；2、最小码距与纠检错能力；3、几种常用的简单编码；4、线性分组码的生成（G）、监督（H）和纠错（S）；5、循环码的生成多项式、生成矩阵、编码和译码；6、

2、卷积码的矩阵、多项式和图形描述方法。,电路与通信教研室 高渤,4,通信原理【第十一章 差错控制编码】,学习目标,重点1、概念：差错控制的基本原理；码重、汉明距离、最小距离的概念和确定；纠检能力与之间的关系；汉明码的概念及其有关参数；卷积码的描述方法和约束度N的含义。2、计算：码率的计算；线性分组码的、编码、校正子和纠错；循环码编码和译码过程；给出卷积码编码器，能写出其输入和输出的关系；给定输入信码，得到输出卷积码序列。,电路与通信教研室 高渤,5,通信原理【第十一章 差错控制编码】,学习目标,难点1、编码效率。2、汉明码。3、校验接收码组B是否出错的方法。4、多项式运算规则。,电路与通信教研室

3、 高渤,6,通信原理【第十一章 差错控制编码】,学习内容,概 述,1,2,3,4,纠错编码的性能,纠错编码的基本原理,5,第十一章 差错控制编码,简单的实用编码,5,线性分组码,卷积码,7,7,5,5,9,低密度奇偶检验码,6,循环码,8,Turbo码,10,网格编码调制,电路与通信教研室 高渤,7,通信原理【第十一章 差错控制编码】,一、信道分类 从差错控制角度看，按加性干扰引起的错码分布规律的不同，信道可以分为三类：1、随机信道：错码的出现是随机的。2、突发信道：错码是成串集中出现的。3、混合信道：既存在随机错码又存在突发错码。,第一节 概 述,二、差错控制技术 1、差错控制技术 一般分为

4、：检错重发、前向纠错、反馈校验、检错删除。,电路与通信教研室 高渤,8,通信原理【第十一章 差错控制编码】,2、差错控制编码：常称为纠错编码。,第一节 概 述,2）多余度：指增加的监督码元多少。例如，若编码序列中平均每两个信息码元就添加一个监督码元，则这种编码的多余度为1/3。,1）监督码元：除反馈校验外，都是在接收端识别有无错码。所以在发送端需要在信息码元序列中增加一些差错控制码元，称为监督码元。不同的编码方法，有不同的检错或纠错能力。,电路与通信教研室 高渤,9,通信原理【第十一章 差错控制编码】,4）冗余度：监督码元数（n-k）和信息码元数 k 之比（n-k）/k。,第一节 概 述,理论

5、上，差错控制以降低信息传输速率为代价换取提高传输可靠性。,3）编码效率（简称码率）：设编码序列中信息码元数量为k，总码元数量为n，则比值k/n 就是码率。,电路与通信教研室 高渤,10,通信原理【第十一章 差错控制编码】,三、差错控制原理举例自动要求重发（ARQ）系统,第一节 概 述,发送一组数据后发端等待收端的确认（ACK）答复，再发送下一组数据；若收到否认（NAK）答复，则重发。系统工作在半双工状态，时间没有得到充分利用，传输效率较低。,1、停止等待ARQ系统,电路与通信教研室 高渤,11,通信原理【第十一章 差错控制编码】,2、拉后ARQ系统,第一节 概 述,发送端连续发送数据组，接收端

6、对于每个接收到的数据组都发回确认（ACK）或否认（NAK）答复。,在这种系统中需要对发送的数据组和答复进行编号，以便识别。显然，这种系统需要双工信道。,电路与通信教研室 高渤,12,通信原理【第十一章 差错控制编码】,3、选择重发ARQ系统,第一节 概 述,只选择重发出错的数据组，因此进一步提高了传输效率。,电路与通信教研室 高渤,13,通信原理【第十一章 差错控制编码】,4、ARQ的主要优点（和前向纠错方法相比）：,第一节 概 述,5、ARQ的主要缺点：,3）检错用的编码方法和加性干扰的统计特性基本无关，能适应 不同特性的信道。,2）检错的计算复杂度较低；,1）监督码元较少即能使误码率降到很

7、低，即码率较高；,2）因为重发而使ARQ系统的传输效率降低。,1）需要双向信道来重发，也不能用于一点到多点的通信系统。,3）在信道干扰严重时，可能反复重发造成事实上的通信中断。,4）在要求实时通信的场合，往往不允许使用ARQ法。,电路与通信教研室 高渤,14,通信原理【第十一章 差错控制编码】,6、ARQ系统的原理方框图,第一节 概 述,电路与通信教研室 高渤,15,通信原理【第十一章 差错控制编码】,学习内容,概 述,1,2,3,4,纠错编码的性能,纠错编码的基本原理,5,第十一章 差错控制编码,简单的实用编码,5,线性分组码,卷积码,7,7,5,5,9,低密度奇偶检验码,6,循环码,8,T

8、urbo码,10,网格编码调制,电路与通信教研室 高渤,16,通信原理【第十一章 差错控制编码】,一、纠错编码的基本原理 1、相关知识回顾（1）纠错编码的概念 在信息码元序列中加入监督码元，称为差错控制编码。（2）实现纠错编码的基本思想（原理）1）利用冗余度 冗余比特与信息比特之间存在着特定的相关性。2）使噪声均化(随机化)噪声均化是将差错均匀分摊给各码字，达到提高总体差 错控制能力的目的。,第二节 纠错编码的基本原理,电路与通信教研室 高渤,17,通信原理【第十一章 差错控制编码】,2、纠错编码的分类1）按对信息序列的处理方法：分组码和卷积码。2）按照校验位与信息位的关系：线性码与非线性码。

9、3）按照适用的差错类型：纠随机差错码和纠突发差错码。4）按照构码理论：代数码、几何码、算术码、组合码等。,有多少观察问题的角度，就有多少分类方法。不同的分类方法只是从不同的角度抓住码的某一特性加以归类，并不能说明某个码的全部特性。分类可以进一步细化，把大类分割成小类。,第二节 纠错编码的基本原理,电路与通信教研室 高渤,18,通信原理【第十一章 差错控制编码】,3、纠错编码举例,分组码例子（3,2）,既不能检错也不能纠错,能检错，但不能纠错,许用码组,禁用码组,合法码组,许用码组000、111,其余码组禁用,既可检错，也能纠错,第二节 纠错编码的基本原理,电路与通信教研室 高渤,19,通信原理

10、【第十一章 差错控制编码】,4、分组码的概念（1）定义 将信息码分组，对每个信息码组附加若干监督码元的编码。（2）表示法 用符号（N，K）表示，其中K是每组二进制信息码元的个数，N是编码组的总位数，又称码长，NK=r 为每码组中监督码元的数目。,第二节 纠错编码的基本原理,电路与通信教研室 高渤,20,通信原理【第十一章 差错控制编码】,1）码重：码组中“1”的个数，称为码组的重量（简称码重）。,第二节 纠错编码的基本原理,3）最小码距：把某种编码中各个码组之间距离的最小值称为最 小码距（d0）。如上面的编码的最小码距d0=2。,“000”晴，“011”云，“101”阴，“110”雨，4个码组

11、之间，任意两个的距离均为2。,2）码距：把两个码组中对应位上数字不同的位数，称为码组的 距离，简称码距，又称汉明距离。例如：,（3）分组码的码重和码距,电路与通信教研室 高渤,21,通信原理【第十一章 差错控制编码】,码距的几何意义,（4）码距（汉明距）的几何意义 两个码组对应位上数字不同的位数，称为码组的距离。,最大码距,最小码距d0,编码的最小码距决定了该编码的检错和纠错能力：d0=1 时，没有检、纠错能力；d0=2 时，具有检查一个差错的能力；d0=3 时，用于检错时具有检查两个差错的能力；用于纠错时具有纠正一个差错的能力。,第二节 纠错编码的基本原理,电路与通信教研室 高渤,22,通信

12、原理【第十一章 差错控制编码】,最小码距 的大小与编码的检错和纠错能力的关系：1）为检测 个错码，则要求：2）为纠正 个错码，则要求：3）为纠正 个错码，同时检测 个错码，则要求：,第二节 纠错编码的基本原理,电路与通信教研室 高渤,23,通信原理【第十一章 差错控制编码】,纠正 t 个错码，同时检测 e 个错码,5、码距与检、纠错能力的关系,检测 e 个错码,纠正 t 个错码,第二节 纠错编码的基本原理,电路与通信教研室 高渤,24,通信原理【第十一章 差错控制编码】,第二节 纠错编码的基本原理,如何理解（证明）：为纠正 t 个错码，同时检测 e 个错码，要求最小码距 d0 t+e+1（e

13、t）。,设码组A和B之间距离为5，则,最多能检测4个错码，最多能纠正2个错码。,但是，不能同时满足。,当错码位数超过纠错能力时，该码组会立即进入另一码组的圆内而被错误地“纠正”了。,因此，检错和纠错公式不能同时成立或同时运用。,电路与通信教研室 高渤,25,通信原理【第十一章 差错控制编码】,为了可以在纠正 t 个错码的同时，能够检测 e 个错码，需要如下图所示。使某一码组（譬如码组A）发生e个错误之后所处位置，与其他码组（譬如码组B）的纠错圆圈至少距离等于 1，以避免落在该纠错圆上从而发生错误地“纠正”。因此，由此图可以直观看出，要求最小码距,第二节 纠错编码的基本原理,这种纠检结合的工作方

14、式是自动转换的。它适用于大多数时间里错码数量很少，少数时间里错码数量多的情况。,电路与通信教研室 高渤,26,通信原理【第十一章 差错控制编码】,学习内容,概 述,1,2,3,4,纠错编码的性能,纠错编码的基本原理,5,第十一章 错控制编码,简单的实用编码,5,线性分组码,卷积码,7,7,5,5,9,低密度奇偶检验码,6,循环码,8,Turbo码,10,网格编码调制,电路与通信教研室 高渤,27,通信原理【第十一章 差错控制编码】,一、系统带宽和信噪比的矛盾,第三节 纠错编码的性能,在发送码元序列中加入监督码元，使得发送序列增长，冗余度增大，若仍保持发送信息码元速率不变，则传输速率必须增大，因

15、而增大了系统带宽。系统带宽的增大将引起系统中噪声功率增大，使信噪比下降。信噪比的下降反而又使系统接收码元序列中的错码增多。一般说来，采用纠错编码后，误码率总是能够得到很大改善的。改善的程度和所用的编码有关。,电路与通信教研室 高渤,28,通信原理【第十一章 差错控制编码】,二、编码性能举例,第三节 纠错编码的性能,未采用纠错编码时，若接收信噪比等于7dB，编码前误码率约为810-3，图中A点；在采用纠错编码后，误码率降至约410-4.5，图中B点。这样，不增大发送功率就能降低误码率约一个半数量级。,电路与通信教研室 高渤,29,通信原理【第十一章 差错控制编码】,由图还可以看出，若保持误码率在

16、10-5，图中C点，未采用编码时，约需要信噪比Eb/n0=10.5 dB。采用编码时，约需要信噪比7.5 dB，图中D点。可以节省功率2dB，通常把这2dB称为编码增益。,第三节 纠错编码的性能,上面两种情况付出的代价是带宽增大。,电路与通信教研室 高渤,30,通信原理【第十一章 差错控制编码】,传输速率和Eb/n0的关系,第三节 纠错编码的性能,式中，RB为码元速率。若希望提高传输速率，由上式看出势必使信噪比下降，误码率增大。,对于给定的传输系统,电路与通信教研室 高渤,31,通信原理【第十一章 差错控制编码】,第三节 纠错编码的性能,假设系统原来工作在图中C点，提高速率后由C点升到E点。但

17、加用纠错编码后，仍可将误码率降到D点。这时付出的代价仍是带宽增大。,电路与通信教研室 高渤,32,通信原理【第十一章 差错控制编码】,学习内容,概 述,1,2,3,4,纠错编码的性能,纠错编码的基本原理,5,第十一章 差错控制编码,简单的实用编码,5,线性分组码,卷积码,7,7,5,5,9,低密度奇偶检验码,6,循环码,8,Turbo码,10,网格编码调制,电路与通信教研室 高渤,33,通信原理【第十一章 差错控制编码】,1、偶数监督码 无论信息位多少，监督位只有1位，它使码组中“1”的数目为偶数，即满足下式条件：。,一、奇偶监督码（适用于检测随机错码）,第四节 简单的实用编码,能检测奇数个错

18、码。在接收端，按照上式求“模2和”，若计算结果为“1”就说明存在错码，结果为“0”就认为无错码。,奇偶监督码分为奇数监督码和偶数监督码两种。,2、奇数监督码 码组中“1”的数目为奇数，即满足下式条件：,电路与通信教研室 高渤,34,通信原理【第十一章 差错控制编码】,二、二维奇偶监督码（方阵码，适用于检测突发错码）,第四节 简单的实用编码,1、二维奇偶监督码的构成 先把上述奇偶监督码的若干码组排成矩阵，每一码组写成一行，然后再按列的方向增加第二维监督位。,2、二维奇偶监督码的性能 可能检测偶数个错码，也有一些偶数错码不能被检测出来。,由于方阵码只对构成矩形四角的错码无法检测，故其检错能力较强。

19、此外，二维奇偶监督码不仅可用来检错，还可以用来纠正一些错码，例如：仅在一行中有奇数个错码时。,电路与通信教研室 高渤,35,通信原理【第十一章 差错控制编码】,三、恒比码,第四节 简单的实用编码,恒比码的主要优点是：简单和适于用来传输电传机或其他键盘设备产生的字母和符号。,检测时只要计算接收码组中“1”的数目是否对，就知道有无错码。,每个码组均含有相同数目的“1”（和“0”）。由于“1”的数目与“0”的数目之比保持恒定，因此称为恒比码。,电路与通信教研室 高渤,36,通信原理【第十一章 差错控制编码】,例如：若码长 n=10，其中信息位 k=5，监督位 r=5。编码规则：信息位中有奇数个“1”

20、时，监督位是信息位的简单重复；信息位有偶数个“1”时，监督位是信息位的反码。,四、正反码,第四节 简单的实用编码,1、正反码的编码 是一种简单的纠错码编码。监督码元与信息位数目相同或者相反，是由信息码中“1”的个数而定。,例如：若信息位为11001，则码组为 11001 11001；若信息位为10001，则码组为 10001 01110。,2、正反码的解码（略）,电路与通信教研室 高渤,37,通信原理【第十一章 差错控制编码】,学习内容,概 述,1,2,3,4,纠错编码的性能,纠错编码的基本原理,5,第十一章 差错控制编码,简单的实用编码,5,线性分组码,卷积码,7,7,5,5,9,低密度奇偶

21、检验码,6,循环码,8,Turbo码,10,网格编码调制,电路与通信教研室 高渤,38,通信原理【第十一章 差错控制编码】,一、线性分组码的基本概念,第五节 线性分组码,3、线性分组码：按照一组线性方程构成的分组码。,2、线性码：按照一组线性方程构成的代数码。在线性码中信息位和监 督位是由一些线性代数方程联系着的。,1、代数码：建立在代数学基础上的编码。,4、汉明码：是能够纠正1位错码且编码效率较高的一种线性分组码。,电路与通信教研室 高渤,39,通信原理【第十一章 差错控制编码】,若S=0，就认为无错码；若S=1，就认为有错码。上式就称为监督关系式，S 称为校正子。由于校正子S只有两种取值，

22、故它只能代表有错和无错这两种信息，而不能指出错码的位置。,在偶数监督码中，由于使用了一位监督位a0，它和信息位an-1 a1一起构成一个代数式：,二、汉明码的构造原理,第五节 线性分组码,在接收端解码时，实际上就是在计算,1、监督关系式的概念,电路与通信教研室 高渤,40,通信原理【第十一章 差错控制编码】,第五节 线性分组码,若监督位增加一位，即变成两位，则能增加一个类似的监督关系式。由于两个校正子的可能值为：00、01、10、11，故能表示4种不同的信息。若用其中1种组合表示无错，则其余3种组合就有可能用来指示一个错码的3种不同位置。同理，r 个监督关系式能指示1位错码的（2r 1）个可能

23、位置。,若码长为 n，信息位数为 k，则监督位数 rnk。如果用 r 个监督位构造出 r 个监督关系式来指示1位错码的 n 种可能位置，则要求,电路与通信教研室 高渤,41,通信原理【第十一章 差错控制编码】,第五节 线性分组码,2、如何构造监督关系式,例：设分组码（n,k）中k=4，为纠正1位错码，则要求监督位数 r 3。若取 r=3，则n=k+r=7。用a6 a5 a0表示7个码元，用S1、S2和S3表示3个监督关系式中的校正子，则S1、S2和S3的值与错码位置的对应关系，可以规定如下表所列：,电路与通信教研室 高渤,42,通信原理【第十一章 差错控制编码】,由表中可见，仅当一位错码的位置

24、在a2、a4、a5或a6时，校正子S1为1；否则S1为零。即：a2、a4、a5和a6四个码元构成偶数监督关系：,第五节 线性分组码,以及a0、a3、a4 和a6构成偶数监督关系：,同理，a1、a3、a5和a6构成偶数监督关系：,电路与通信教研室 高渤,43,通信原理【第十一章 差错控制编码】,发端编码时，信息位a6、a5、a4和a3的值决定于输入信号，取值是随机的。监督位a2、a1和a0应根据信息位的取值按监督关系来确定，即监督位应使上3式中S1、S2和S3的值为0（表示编成的码组中应无错码）：,第五节 线性分组码,上式经过移项运算，解出监督位,电路与通信教研室 高渤,44,通信原理【第十一章

25、 差错控制编码】,给定信息位后，可直接按上式算出监督位，结果见下表：,第五节 线性分组码,电路与通信教研室 高渤,45,通信原理【第十一章 差错控制编码】,收端收到每个码组后，先计算出S1、S2和S3，再查表判断错码情况。例如，若接收码组为0000011，按上述公式计算可得：S1=0，S2=1，S3=1。由于S1 S2 S3 等于011，故查表可知在a3位有1错码。,第五节 线性分组码,按照上述方法构造的码称为汉明码。表中所列的（7,4）汉明码的最小码距d0=3。因此，这种码能够纠正1个错码或检测2个错码。由于码率k/n=（n-r）/n=1 r/n，故当n很大和r很小时，码率接近1。可见，汉明

26、码是一种高效码。,电路与通信教研室 高渤,46,通信原理【第十一章 差错控制编码】,三、线性分组码的一般原理,第五节 线性分组码,现在将上面它改写为（式中已经将“”简写成“+”）：,上面（7,4）汉明码的例子有,（1）H矩阵（监督矩阵）,1、线性分组码的构造,（式中已经将“”简写成“+”）。,电路与通信教研室 高渤,47,通信原理【第十一章 差错控制编码】,第五节 线性分组码,上式可表示成如下矩阵形式：,H AT=0T 或 A HT=0,还可以简记为：,式中,A=a6 a5 a4 a3 a2 a1 a00=000,“T”表示将矩阵转置。,H称为监督矩阵。只要监督矩阵H给定，编码时监督位和信息位

27、的关系就完全确定了。,电路与通信教研室 高渤,48,通信原理【第十一章 差错控制编码】,第五节 线性分组码发,（2）H矩阵的性质：,1）H的行数就是监督关系式的数目r H的每行中“1”的位置表示相应码元之间存在的监督关系。例如：1110100。,H矩阵可以分成两部分，如,式中，P为r k阶矩阵，Ir为r r阶单位方阵。具有P Ir形式的H矩阵称为典型阵。,电路与通信教研室 高渤,49,通信原理【第十一章 差错控制编码】,2）H矩阵的各行线性无关 否则得不到 r 个线性无关的监督关系式，也得不到 r 个独立的监督位。若矩阵能写成典型阵形式P Ir，则其各行一定是线性无关。,第五节 线性分组码发,

28、（3）G矩阵（生成矩阵）：,上例中,也可改写成矩阵形式：,电路与通信教研室 高渤,50,通信原理【第十一章 差错控制编码】,或者写成,第五节 线性分组码发,上式表示，在信息位给定后，用信息位的行矩阵乘矩阵Q就产生出监督位。,式中，Q为一个k r阶矩阵，它为P的转置，即 Q=PT。,电路与通信教研室 高渤,51,通信原理【第十一章 差错控制编码】,将Q的左边加上1个k k阶单位方阵，就构成1个矩阵G,第五节 线性分组码发,或者,G称为生成矩阵，因为由它可以产生整个码组，即有,电路与通信教研室 高渤,52,通信原理【第十一章 差错控制编码】,因此，如果找到了码的生成矩阵G，则编码的方法就完全确定了

29、。具有Ik Q形式的生成矩阵，称为典型生成矩阵。由典型生成矩阵得出的码组A中，信息位的位置不变，监督位附加于其后，这种形式的码称为系统码。,第五节 线性分组码发,电路与通信教研室 高渤,53,通信原理【第十一章 差错控制编码】,（4）G矩阵的性质：1）G矩阵的各行是线性无关的 任一码组A都是G的各行的线性组合。G共有k行，若它们线性无关，则可以组合出2k种不同的码组A。,第五节 线性分组码发,2）G的各行本身就是一个码组 如果有 k 个线性无关的码组，则可用其作为生成矩阵 G，并由它生成其余码组。,电路与通信教研室 高渤,54,通信原理【第十一章 差错控制编码】,（5）错码矩阵（错误图样）,第

30、五节 线性分组码发,它就是传输中产生的错码行矩阵,则发送码组和接收码组之差为 B A=E（模2）,设发送码组A为n列的行矩阵，此码组在传输中可能由于干扰引入差错，故接收码组有可能与A不一定相同。若设接收码组为n列的行矩阵B，即,式中,则上式可改写成 B=A+E。,电路与通信教研室 高渤,55,通信原理【第十一章 差错控制编码】,接收码组有错时，E 0，将B当作 A 代入公式 A H T=0，该式不一定成立。错码较多且超过这种编码的检错能力时，B变为另一许用码组，则该式仍能成立，这样的错码是不可检测的。在未超过检错能力时，上式不成立，即其右端不等于0。假设这时该式的右端为S，即,第五节 线性分组

31、码发,将 B=A+E 代入上式，可得 S=（A+E）H T=A H T+E H T，由于A H T=0，得,（6）校正子S,B H T=S,S=E H T,S称为校正子，用来指示错码的位置。S和错码E之间有确定的线性变换关系，若S和E之间一一对应，则S将能代表错码的位置。,电路与通信教研室 高渤,56,通信原理【第十一章 差错控制编码】,2、线性分组码的封闭性 指线性码中的任意两个码组之和仍为改码中的一个码组。,第五节 线性分组码发,若A1和A2是一种线性码中的两个许用码组，则（A1+A2）仍为其中的一个码组。证明：A1和A2是两个码组，则有A1 HT=0，A2 HT=0。,由于线性码具有封闭

32、性，故两个码组（A1和A2）之间的距离（即对应位不同的数目）必定是另一个码组（A1+A2）的重量（即“1”的数目）。因此，最小码距就是码的最小重量（除全“0”码组外）。,电路与通信教研室 高渤,57,通信原理【第十一章 差错控制编码】,学习内容,概 述,1,2,3,4,纠错编码的性能,纠错编码的基本原理,5,第十一章 差错控制编码,简单的实用编码,5,线性分组码,卷积码,7,7,5,5,9,低密度奇偶检验码,6,循环码,8,Turbo码,10,网格编码调制,电路与通信教研室 高渤,58,通信原理【第十一章 差错控制编码】,思考题与习题,思考题P370 120。习题P371 1、3、5、6、7。,Thank You!,含弘光大 继往开来,