差错控制的基本概念 精选PPT.ppt

《差错控制的基本概念 精选PPT.ppt》由会员分享，可在线阅读，更多相关《差错控制的基本概念 精选PPT.ppt（67页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、差错控制的基本概念 1第1页，此课件共67页哦本章内容提要本章内容提要差错控制系统及其理论基础差错控制系统及其理论基础纠错编码的基本概念及其本质纠错编码的基本概念及其本质纠错编码方法的性能评价、纠错编码方法的性能评价、基于图形的编码基于图形的编码2第2页，此课件共67页哦差错控制的理论基础主要是香农第二定理和近世代数。差错控制的理论基础主要是香农第二定理和近世代数。（1）香农第二定理）香农第二定理 这个抗干扰信道编码定理作为一个这个抗干扰信道编码定理作为一个存在性存在性定理，指出可以用任意接近信定理，指出可以用任意接近信道容量的信息传输速率传送消息，且出错的概率可以任意小。道容量的信息传输速率

2、传送消息，且出错的概率可以任意小。引发了人们对纠错码的研究。引发了人们对纠错码的研究。纠错码理论的中心任务就是要针对具有不同干扰特性的各种信道设纠错码理论的中心任务就是要针对具有不同干扰特性的各种信道设计出编码效率高、抗干扰性能好、而编译码设备又较简单的纠错码计出编码效率高、抗干扰性能好、而编译码设备又较简单的纠错码或检错码。或检错码。9.1.1差错控制的理论基础差错控制的理论基础9.1差错控制系统及其基础差错控制系统及其基础3第3页，此课件共67页哦（2）近世代数）近世代数经典代数学以数为主要的研究对象，而近世代数将研究对象由数经典代数学以数为主要的研究对象，而近世代数将研究对象由数扩展到向

3、量、矩阵等，以研究更为一般的代数运算的规律和性质扩展到向量、矩阵等，以研究更为一般的代数运算的规律和性质为目标，推动了以讨论群、环、域、多项式、向量空间等性质和为目标，推动了以讨论群、环、域、多项式、向量空间等性质和结构为主要内容的理论的发展。结构为主要内容的理论的发展。近世代数又称为近世代数又称为抽象代数抽象代数，在研究信道编码的许多具体构造，在研究信道编码的许多具体构造规律时，发现规律时，发现用近世代数的理论能够对编码结构给予非常吻合用近世代数的理论能够对编码结构给予非常吻合的描述的描述，因此成为信道编码的重要理论基础。，因此成为信道编码的重要理论基础。9.1.1差错控制的理论基础差错控制

4、的理论基础9.1差错控制系统及其基础差错控制系统及其基础4第4页，此课件共67页哦差错控制系统根据它们的纠、检错能力；差错控制系统根据它们的纠、检错能力；对信道的要求及适应性；编、译码器的复对信道的要求及适应性；编、译码器的复杂性；编、译码的实时性等性能指标可以杂性；编、译码的实时性等性能指标可以分为如下分为如下4类类自动请求重传系统自动请求重传系统前向纠错系统前向纠错系统信息重复查询系统信息重复查询系统混合纠错系统混合纠错系统9.1.2差错控制系统差错控制系统9.1差错控制系统及其基础差错控制系统及其基础5第5页，此课件共67页哦图9.1 ARQ系统(1)自动请求重传系统自动请求重传系统 通

5、信系统在接收端检测到传输错误并自动告知发送方，请求发送方重发，称为自动请求重发，简称反馈重传。系统构成如图9.1所示。9.1.2差错控制系统差错控制系统9.1差错控制系统及其基础差错控制系统及其基础6第6页，此课件共67页哦该系统接收端在收到的信码中检测出错码时，即设法通知发送端重发，直到正确收到为止。所谓检测出错码，是指在若干接收码元中知道有一个或一些是错的，但不一定知道该错码的准确位置。图9.2列举了3种最流行的ARQ方式停止 等待式ARQ具有回拉功能的连续ARQ具有选择性重发功能的连续ARQ9.1.2差错控制系统差错控制系统9.1差错控制系统及其基础差错控制系统及其基础7第7页，此课件共

6、67页哦图9.2自动请求重发（ARQ）8第8页，此课件共67页哦停止等待式ARQ只需要半双工连接，因为发射机在接到确认信号后才进行下一个传送；具有回拉功能的连续ARQ需要全双工连接，通信双方的终端设备同时传输，发送方传送信息数据，接收方传送确认信号和非确认信号，在ARQ过程中，发送方被“拉回”到错误传送的消息处，从错误消息开始处重发所有的信息数据；具有选择性重发功能的连续ARQ也需要全双工连接，但它只要求错误的消息重发，然后发射机从先前停止的地方继续发送原序列而不重发已经正确接收的消息。9.1.2差错控制系统差错控制系统9.1差错控制系统及其基础差错控制系统及其基础9第9页，此课件共67页哦A

7、RQ系统的系统的优点优点是：是：纠错能力强；检错能力与信道干扰变化无关，适应性强；由于只要检测错误就可以了，因此编译码器比较简单。ARQ系统的系统的缺点缺点：必须有反向信道，否则只能检错收、发两端必须互相配合信源能够被控制实时性较差因此它只适用于当发生错误需要重发的情况。9.1.2差错控制系统差错控制系统9.1差错控制系统及其基础差错控制系统及其基础10第10页，此课件共67页哦(2)前向纠错（前向纠错（FEC）系统）系统系统的接收端不仅能在收到的消息序列中发现错误，还能够将其纠正。前向纠错系统的基本组成如图9.3所示。图9.3 FEC系统9.1.2差错控制系统差错控制系统9.1差错控制系统及

8、其基础差错控制系统及其基础11第11页，此课件共67页哦纠错编码主要应用在数字通信中，根本目的是提高通信的可靠性。根据香农第二定理，只要信道的信息传输速率小于信道容量，接近无差错传输的编码就是一定存在的，且信道容量C、信号带宽B和到达接收端的信噪比S/N满足香农公式。因此，可以把纠错编码看成这3个参量相互影响彼此权衡的结果。在数字通信中，信噪比通常用Eb/N0来表示，其中Eb和 N0分别为信号的比特能量和噪声的功率谱密度，它们在数值上和S/N相等。9.1.2差错控制系统差错控制系统9.1差错控制系统及其基础差错控制系统及其基础12第12页，此课件共67页哦通信系统误比特率与通信系统误比特率与E

9、b/N0关系的曲线关系的曲线两者采用相同的调制方法和两者采用相同的调制方法和同样的信道，同样的信道，可见信道编码使得在同样信可见信道编码使得在同样信噪比情况下降低了误比特率，噪比情况下降低了误比特率，或者在更低的信噪比情况下或者在更低的信噪比情况下也能达到误比特率的要求。也能达到误比特率的要求。9.1.2差错控制系统差错控制系统9.1差错控制系统及其基础差错控制系统及其基础图9.4 典型编码与未编码的差错性能比较13第13页，此课件共67页哦定义定义9.1 对于给定的误比特率，对于给定的误比特率，编码增益编码增益G是指通过是指通过编码所能实现的编码所能实现的Eb/N0的减少量的减少量，即：，即

10、：(9.1)其中其中和和分别表示未编码及编码后所分别表示未编码及编码后所需要的需要的Eb/N0。例如，为了获得低于例如，为了获得低于104的误比特率，对于未编码的误比特率，对于未编码情况必须使情况必须使Eb/N0至少保持在至少保持在12dB以上，而采用编以上，而采用编码后仅需至少保持在码后仅需至少保持在8dB以上，在这种情况下获得以上，在这种情况下获得了了4dB的编码增益。的编码增益。9.1.2差错控制系统差错控制系统9.1差错控制系统及其基础差错控制系统及其基础14第14页，此课件共67页哦FEC系统的系统的优点优点是：是：收端可自动发现错误、纠正错误；不需反向信道；收端可自动发现错误、纠正

11、错误；不需反向信道；能进行一点对多点的同播，可以是双向通信或单向通信；能进行一点对多点的同播，可以是双向通信或单向通信；与与ARQ相比，译码实时性好；相比，译码实时性好；控制电路比控制电路比ARQ简单。简单。FEC系统的系统的缺点缺点主要有：主要有：译码比较复杂；译码比较复杂；所选用的纠错码要和信道的干扰情况相匹配，对信道的适应性所选用的纠错码要和信道的干扰情况相匹配，对信道的适应性较差，一般以最坏的信道条件来设计纠错码；较差，一般以最坏的信道条件来设计纠错码；通常是以注入冗余度为代价来换取编码增益，注入的冗余度越大编通常是以注入冗余度为代价来换取编码增益，注入的冗余度越大编码增益越高，一般情

12、况下编码效率较低。码增益越高，一般情况下编码效率较低。9.1.2差错控制系统差错控制系统9.1差错控制系统及其基础差错控制系统及其基础15第15页，此课件共67页哦(3)信息重复查询系统（信息重复查询系统（IRQ）是指接收端将收到的消息原封不动地转发回发送端，在发送是指接收端将收到的消息原封不动地转发回发送端，在发送端与原发送消息相比较的系统。如果发现错误，则发送端再端与原发送消息相比较的系统。如果发现错误，则发送端再进行重发，直至正确为止。进行重发，直至正确为止。原理和设备都较简单，但需要有双向信道，因为相当于每一原理和设备都较简单，但需要有双向信道，因为相当于每一消息都至少传送了两次，所以

13、传输效率较低。消息都至少传送了两次，所以传输效率较低。(4)混合纠错系统（混合纠错系统（HEC）HEC系统将反馈重传技术与前向纠错技术相结合。系统将反馈重传技术与前向纠错技术相结合。当出现少量错码并在接收端能够纠正时，即用前向纠错方法当出现少量错码并在接收端能够纠正时，即用前向纠错方法纠正之；当错码较多超过其纠正能力但尚能检测时，就进行纠正之；当错码较多超过其纠正能力但尚能检测时，就进行自动反馈重传。自动反馈重传。混合纠错结合了混合纠错结合了ARQ和和FEC两者的优点。两者的优点。9.1.2差错控制系统差错控制系统9.1差错控制系统及其基础差错控制系统及其基础16第16页，此课件共67页哦1.

14、差错控制码的分类差错控制码的分类不同的差错控制系统需要不同的差错控制码。从差错控制码功能的不同的差错控制系统需要不同的差错控制码。从差错控制码功能的角度，可将常见的差错控制码分为以下角度，可将常见的差错控制码分为以下3类：类：（1）检错码）检错码：只能发现错误，不能纠正错误。在一些仅需给出：只能发现错误，不能纠正错误。在一些仅需给出错误提示以及错误提示以及ARQ系统中使用这类码。系统中使用这类码。（2）纠错码）纠错码：能够发现错误也能纠正错误。：能够发现错误也能纠正错误。FEC和和HEC系统都系统都使用这类码。使用这类码。（3）纠删码）纠删码：能够发现并纠正或删除错误。：能够发现并纠正或删除错

15、误。纠错码的应用最为广泛。纠错码的应用最为广泛。9.2.1纠错编码的分类纠错编码的分类9.2纠错编码的基本概念及其本质纠错编码的基本概念及其本质17第17页，此课件共67页哦2.纠错码的分类纠错码的分类 图图9.5纠错码分类示意图纠错码分类示意图9.2.1纠错编码的分类纠错编码的分类9.2纠错编码的基本概念及其本质纠错编码的基本概念及其本质18第18页，此课件共67页哦(1)根据对信息元的处理方法分类根据对信息元的处理方法分类按照对信息元处理方法的不同，可以将纠错码分为按照对信息元处理方法的不同，可以将纠错码分为分组码分组码和和卷卷积码积码。分组码分组码的构成如图所示。的构成如图所示。其码长为

16、其码长为n=k+r，其中，其中k是信息元个数，是信息元个数，r是监督（校验）是监督（校验）元个数，监督元只与本组信息元有关。元个数，监督元只与本组信息元有关。通常将分组码写成码通常将分组码写成码(n,k)，或称为，或称为(n,k)码。码。9.2.1纠错编码的分类纠错编码的分类9.2纠错编码的基本概念及其本质纠错编码的基本概念及其本质19第19页，此课件共67页哦卷积码卷积码的构成如图所示，其中的构成如图所示，其中n0k0。最主要特点是最主要特点是n0k0个监督元不仅与本组的信息元有关，个监督元不仅与本组的信息元有关，还与前还与前m段的信息元有关。段的信息元有关。类似于分组码，也称类似于分组码，

17、也称n0为卷积码的码长，为卷积码的码长，k0为信息元个数，为信息元个数，m为存储级数。通常将卷积码写成码为存储级数。通常将卷积码写成码(n0,k0,m)，或称为，或称为(n0,k0,m)码。码。9.2.1纠错编码的分类纠错编码的分类9.2纠错编码的基本概念及其本质纠错编码的基本概念及其本质20第20页，此课件共67页哦（2）根据校验元与信息元之间的关系分类）根据校验元与信息元之间的关系分类根据校验元与信息元之间关系的不同，可以将纠错码分为根据校验元与信息元之间关系的不同，可以将纠错码分为线性码线性码和和非线性码非线性码。（3）根据纠正错误的类型分类）根据纠正错误的类型分类纠随机错误码纠随机错误

18、码纠突发错误码纠突发错误码纠同步错误码纠同步错误码既纠随机又纠突发错误码。既纠随机又纠突发错误码。（4）根据每个码元的取值分类）根据每个码元的取值分类二进制码二进制码q进制码，其中进制码，其中q=pm，p为素数，为素数，m为正整数。为正整数。（5）根据码的结构特点分类）根据码的结构特点分类循环码、非循环码、系统码，完备码等。循环码、非循环码、系统码，完备码等。9.2.1纠错编码的分类纠错编码的分类9.2纠错编码的基本概念及其本质纠错编码的基本概念及其本质21第21页，此课件共67页哦9.2.2纠错编码的分类纠错编码的分类9.2纠错编码的基本概念及其本质纠错编码的基本概念及其本质1.几个基本定义

19、几个基本定义定义定义9.2设码字设码字v=(v0,v1,vn-1)C，令，令w(v)为码字为码字v中那些中那些不为不为0的码元的个数，即的码元的个数，即(9.2)则则w(v)是码字是码字v的汉明重量，简称重量。的汉明重量，简称重量。定义定义9.3码码C中所有那些不等于中所有那些不等于0的码字的重量的最小值的码字的重量的最小值称为码称为码C的最小重量。的最小重量。即(9.3)22第22页，此课件共67页哦根据最小汉明距离的定义，根据最小汉明距离的定义，(n，k)码的最小汉明距离码的最小汉明距离d为该种为该种编码中任两个码字间距离的最小值，即编码中任两个码字间距离的最小值，即(9.4)定义定义9.

20、4设发码设发码C:(cn-1,c1,c0)或或(c0,c1,cn-1)，收码，收码R:(rn-1,r1,r0)或或(r0,r1,rn-1)，则定义，则定义信道的错误图样为信道的错误图样为E:(en-1,e1,e0)或或(e0,e1,en-1)，其中，其中(9.5)由定义可知由定义可知R=C+E(9.6)E=CR(9.7)9.2.2纠错编码的分类纠错编码的分类9.2纠错编码的基本概念及其本质纠错编码的基本概念及其本质23第23页，此课件共67页哦定义定义9.5在错误图样中，若在错误图样中，若“1”集中于某个长度集中于某个长度b内，则称该种内，则称该种错误为长度为错误为长度为b的突发错误，其中的突

21、发错误，其中b称为突发错误长度，该图样称称为突发错误长度，该图样称为为突发错误图样。突发错误图样。典型的突发错误图样为：典型的突发错误图样为：00111100，中间含有，中间含有b个连续个连续的的1。对于一些编码（例如循环码），突发错误图样也包。对于一些编码（例如循环码），突发错误图样也包括首尾相接的错误，其错误图样为：括首尾相接的错误，其错误图样为：11000011，其，其中两段分别连续的中两段分别连续的1的个数共为的个数共为b。9.2.2纠错编码的分类纠错编码的分类9.2纠错编码的基本概念及其本质纠错编码的基本概念及其本质24第24页，此课件共67页哦定义定义9.6分组码是对每段分组码是对

22、每段k位长的信息组，以一定规则增加位长的信息组，以一定规则增加r=nk个监督个监督(校验校验)元，组成长为元，组成长为n的序列的序列(cn 1,cn 2,c1,c0)，称这个序列为码字或码组、码矢。在二进制的情况下，称这个序列为码字或码组、码矢。在二进制的情况下，k位长的信息组共位长的信息组共2k个，通过编码器后，码字还是个，通过编码器后，码字还是2k个，个，称称这这2k个码字的集合为个码字的集合为(n，k)分组码分组码。n长序列的可能排列共有长序列的可能排列共有2n种，其中只有种，其中只有2k个个n重构成了重构成了(n,k)分组码，称它们为分组码，称它们为许用码组许用码组，其余的，其余的2n

23、2k个个n重为重为禁用码组禁用码组。9.2.2纠错编码的分类纠错编码的分类9.2纠错编码的基本概念及其本质纠错编码的基本概念及其本质25第25页，此课件共67页哦定义定义9.7(n0,k0,m)卷积码卷积码是对每段是对每段k0长的信息组以一定的规则增长的信息组以一定的规则增加加r0=n0k0个监督个监督(校验校验)元，组成长为元，组成长为n0的码段；的码段；n0k0个校验元个校验元不仅与本段的信息元有关，且与前不仅与本段的信息元有关，且与前m段的信息元有关；编码约束长段的信息元有关；编码约束长度度nc=n0(m+1)，它表示，它表示k0个信息元从输入编码器到离开时，在码个信息元从输入编码器到离

24、开时，在码序列中影响的码元数目。序列中影响的码元数目。定义定义9.8将信息位在码字中所占的比例称为编码效率，也称为将信息位在码字中所占的比例称为编码效率，也称为码字效率码字效率，通常也用，通常也用R表示。对于分组码，有表示。对于分组码，有R=k/n (9.8)对于卷积码，有对于卷积码，有R=k0/n0 (9.9)编码效率是衡量编码有效性的基本参数编码效率是衡量编码有效性的基本参数。9.2.2纠错编码的分类纠错编码的分类9.2纠错编码的基本概念及其本质纠错编码的基本概念及其本质26第26页，此课件共67页哦2.纠错码举例纠错码举例（1）重复码重复码重复码是重复码是k=1的分组码的分组码(n,1)

25、,它的它的(n 1)个校验元是信息元的个校验元是信息元的重复。对二进制系统，只有两个码字：重复。对二进制系统，只有两个码字：00.0，11.1，其中，其中1和和0的个数均为的个数均为n。重复码的译码采用重复码的译码采用大数判决方法大数判决方法，也称为大数准则，或最大似，也称为大数准则，或最大似然准则、最小距离准则，即译码时以大于然准则、最小距离准则，即译码时以大于n/2的最小整数作为的最小整数作为判决门限。判决门限。若若n是奇数，可以实现完全的译码，称为是奇数，可以实现完全的译码，称为完备译码完备译码；若若n是偶数，则会出现是偶数，则会出现1、0个数相等的情况，将导致译码失败，个数相等的情况，

26、将导致译码失败，称为称为不完备译码不完备译码，但由于检出了错误，可作删除处理或结合，但由于检出了错误，可作删除处理或结合ARQ进行译码。进行译码。9.2.2纠错编码的分类纠错编码的分类9.2纠错编码的基本概念及其本质纠错编码的基本概念及其本质27第27页，此课件共67页哦重复码重复码特点特点：d=n，随着，随着n的增大，抗干扰能力越来越强，但的增大，抗干扰能力越来越强，但R=1/n随之下降，编码效率越来越低；随之下降，编码效率越来越低；检错能力大于或等于纠错能力，距离检错能力大于或等于纠错能力，距离d越大，纠错能越大，纠错能力越强。若未编码时接收的错误概率为力越强。若未编码时接收的错误概率为

27、，经过，经过n次重次重复编码后，如果结合复编码后，如果结合ARQ技术，其接收的错误概率可技术，其接收的错误概率可降低到降低到。9.2.2纠错编码的分类纠错编码的分类9.2纠错编码的基本概念及其本质纠错编码的基本概念及其本质28第28页，此课件共67页哦（2）奇偶校验码）奇偶校验码奇偶校检码是只有一个校验元的分组码奇偶校检码是只有一个校验元的分组码(n,n1)，即，即k=n1，其组成和方法如图，其组成和方法如图9.8所示。所示。若每个码字中若每个码字中1的个数为偶数，则为偶校验；若每个码字的个数为偶数，则为偶校验；若每个码字中中1的个数为奇数，则为奇校验。的个数为奇数，则为奇校验。图9.8 奇偶

28、校检码的组成和编码方法9.2.2纠错编码的分类纠错编码的分类9.2纠错编码的基本概念及其本质纠错编码的基本概念及其本质29第29页，此课件共67页哦由于每个码字均按同一规则构成，所以奇偶校验码是一种由于每个码字均按同一规则构成，所以奇偶校验码是一种致校验码致校验码。码的性能码的性能在接收端，译码过程包括检验码字的各比特的模在接收端，译码过程包括检验码字的各比特的模2和是否为和是否为0，如果，如果结果是结果是1，则代表码字中存在错误。它是一种检错码且只能检测奇，则代表码字中存在错误。它是一种检错码且只能检测奇数个错。数个错。假设所有比特发生错误的可能性是相同的，且相互独立，则一个假设所有比特发生

29、错误的可能性是相同的，且相互独立，则一个n比特长的符号发生比特长的符号发生j位错误的可能性为位错误的可能性为(9.10)9.2.2纠错编码的分类纠错编码的分类9.2纠错编码的基本概念及其本质纠错编码的基本概念及其本质30第30页，此课件共67页哦设无法检测的错误概率为设无法检测的错误概率为Pnd，则有，则有(9.12)如果是奇校验，则求和的上限值为如果是奇校验，则求和的上限值为(n 1)/2。奇偶校验码特点：奇偶校验码特点：（1）d=2，能检，能检1个错，也能检奇数个错；个错，也能检奇数个错；（2）R=(n1)/n，编码效率很高。随着，编码效率很高。随着n的增大，编码效率趋的增大，编码效率趋近

30、于近于1，但，但d/n则趋近于则趋近于0，即抗干扰能力随之下降。，即抗干扰能力随之下降。9.2.2纠错编码的分类纠错编码的分类9.2纠错编码的基本概念及其本质纠错编码的基本概念及其本质31第31页，此课件共67页哦纠纠错错编编码码的的本本质质是是通通过过在在发发端端的的码码字字中中引引入入可可控控的的冗冗余余度度换换取取传传输可靠性的提高。输可靠性的提高。以分组码为例，它获得纠、检错能力的本质，是由于以分组码为例，它获得纠、检错能力的本质，是由于加入了加入了(n k)个监督码元个监督码元。k个码元的消息集合最多具有个码元的消息集合最多具有2k个消息组合，个消息组合，同样，同样，n个码元的码字集

31、合最多具有个码元的码字集合最多具有2n个消息组合个消息组合许用码组的个数为许用码组的个数为2k而禁用码组的个数为而禁用码组的个数为(2n2k)。若由于错误使接收到的码字落到了禁用码组里，就必然可被若由于错误使接收到的码字落到了禁用码组里，就必然可被检测出来，同时也给纠正提供了可能，这取决于编码的结构。检测出来，同时也给纠正提供了可能，这取决于编码的结构。如果由于错误而使接收到的码字落到了许用码组里，则无无法判别如果由于错误而使接收到的码字落到了许用码组里，则无无法判别是无错还是有错，从而造成不可检测的错误。是无错还是有错，从而造成不可检测的错误。9.2.3纠错编码的本质纠错编码的本质9.2纠错

32、编码的基本概念及其本质纠错编码的基本概念及其本质32第32页，此课件共67页哦这种以注入冗余度来获取可靠性提高的方法，必这种以注入冗余度来获取可靠性提高的方法，必然带来然带来信息传输速率的降低信息传输速率的降低。但根据香农第二定理，信息传输速率接近于信道但根据香农第二定理，信息传输速率接近于信道容量且具有任意小错误概率的通信是存在的，即容量且具有任意小错误概率的通信是存在的，即编码效率接近于编码效率接近于1且又能使错误概率任意小的信且又能使错误概率任意小的信道编码是存在道编码是存在的，这就给编码工作者提出了严峻的的，这就给编码工作者提出了严峻的课题。课题。在后面几章将会看到，人们发现的在后面几

33、章将会看到，人们发现的所谓所谓“好码好码”，主要是主要是在同样的编码效率下具有更高的纠错或检错在同样的编码效率下具有更高的纠错或检错功能功能。9.2纠错编码的基本概念及其本质纠错编码的基本概念及其本质9.2.3纠错编码的本质纠错编码的本质33第33页，此课件共67页哦编码性能优劣可以用最小码距编码性能优劣可以用最小码距d的大小来表征的大小来表征。定理定理9.1任一任一(n，k)分组码，若要在码字内：分组码，若要在码字内：(1)检测检测a个随机错误，则要求个随机错误，则要求d a+1；(2)纠正纠正t个随机错误，则要求个随机错误，则要求d 2t+1；(3)检测检测a个并纠正个并纠正t(t a)个

34、随机错误，则要求个随机错误，则要求da+t+1。证明证明（1）可以由图9.9(a)简单证明：9.3纠错编码方法的性能评价纠错编码方法的性能评价图9.9(a)34第34页，此课件共67页哦设一码组设一码组A位于位于0点。点。若码组若码组A中发生一位错码，则可以认为中发生一位错码，则可以认为A的位置将移动至以的位置将移动至以0点为圆心、以点为圆心、以1为半径的圆上某点，但其位置不会超出此圆；为半径的圆上某点，但其位置不会超出此圆；若码组若码组A中发生两位错码，则其位置不会超出以中发生两位错码，则其位置不会超出以0点为圆心、点为圆心、以以2为半径的圆。为半径的圆。因此，只要最小码距不小于因此，只要最

35、小码距不小于3（如图中（如图中B点），在此半径为点），在此半径为2的的圆上及圆内就不会有其它码组。这就是说，码组圆上及圆内就不会有其它码组。这就是说，码组A发生两位以发生两位以下错码时，不可能变成另一任何许用码组，因而能检测错码的位下错码时，不可能变成另一任何许用码组，因而能检测错码的位数等于数等于2。同理，如果一种编码的最小距离为同理，如果一种编码的最小距离为d，则将能检测，则将能检测(d 1)个个错码；反之，若要求检测错码；反之，若要求检测a个错码，则最小码距个错码，则最小码距d至少应不至少应不小于小于(a+1)。9.3纠错编码方法的性能评价纠错编码方法的性能评价35第35页，此课件共67

36、页哦（2）可以图可以图9.9(b)来加以说明。来加以说明。9.3纠错编码方法的性能评价纠错编码方法的性能评价图9.9 码距与检错和纠错能力的关系（b）36第36页，此课件共67页哦图中画出码组图中画出码组A和和B的距离为的距离为5。码组码组A或或B若发生不多于两位错码，则其位置均不会超出以原位若发生不多于两位错码，则其位置均不会超出以原位置为圆心，以置为圆心，以2为半径的圆。为半径的圆。若接收码组落于以若接收码组落于以A为圆心的圆上，就判决收到的是码组为圆心的圆上，就判决收到的是码组A；若；若落于以落于以B为圆心的圆上，就判决为码组为圆心的圆上，就判决为码组B。这样，就能够纠正两位错码。这样，

37、就能够纠正两位错码。若这种编码中除码组若这种编码中除码组A和和B外，还有许多种不同码组，但任外，还有许多种不同码组，但任两码组之间的码距均不小于两码组之间的码距均不小于5，则以各码组的位置为中心、以，则以各码组的位置为中心、以2为半径画出的圆都不会互相重叠。为半径画出的圆都不会互相重叠。每种码组如果发生不超过两位错码都将能被纠正。每种码组如果发生不超过两位错码都将能被纠正。因此，当最小码距因此，当最小码距d=5时，能够纠正两个错码，且最多能纠正两时，能够纠正两个错码，且最多能纠正两个。若错码达到个。若错码达到3个，就将落于另一圆上，从而发生错判。个，就将落于另一圆上，从而发生错判。为纠正为纠正

38、t个错码，最小码距个错码，最小码距d应不小于应不小于(2t+1)。9.3纠错编码方法的性能评价纠错编码方法的性能评价37第37页，此课件共67页哦9.3纠错编码方法的性能评价纠错编码方法的性能评价(3)先说明什么是先说明什么是“检测检测a个并纠正个并纠正t(t a)个错误个错误”（简称（简称“纠纠检结合检结合”）。）。在某些情况下，要求对于出现较频繁但错码数很少的码组，按在某些情况下，要求对于出现较频繁但错码数很少的码组，按前向纠错方式工作，以节省反馈重发时间；同时又希望对一些前向纠错方式工作，以节省反馈重发时间；同时又希望对一些错码数较多的码组，在超过该码的纠错能力后，能自动按检错错码数较多

39、的码组，在超过该码的纠错能力后，能自动按检错重发方式工作，以降低系统的总误码率。重发方式工作，以降低系统的总误码率。这种工作方式就是这种工作方式就是“纠检结合纠检结合”。在上述在上述“纠检结合纠检结合”系统中，差错控制设备按照接收码组与许用码系统中，差错控制设备按照接收码组与许用码组的距离自动改变工作方式。若接收码组与某一许用码组间的距组的距离自动改变工作方式。若接收码组与某一许用码组间的距离在纠错能力离在纠错能力t范围内，则按纠错方式工作；若与任何许用码范围内，则按纠错方式工作；若与任何许用码组间的距离都超过组间的距离都超过t，则按检错方式工作。，则按检错方式工作。38第38页，此课件共67

40、页哦以图以图9.9(c)来加以说明。设码的检错能力为来加以说明。设码的检错能力为a，则当码组，则当码组A中中存在存在a个错码时，该码组与任一许用码组（例如图中码组个错码时，该码组与任一许用码组（例如图中码组B）的）的距离应至少为距离应至少为t+1，否则将进入许用码组，否则将进入许用码组B的纠错能力范围内，的纠错能力范围内，而被错纠为而被错纠为B。这样就要求最小码距。这样就要求最小码距d至少为至少为a+t+1。9.3纠错编码方法的性能评价纠错编码方法的性能评价（c）图9.9 码距与检错和纠错能力的关系39第39页，此课件共67页哦9.4基于图形的编码基于图形的编码编码的主要挑战编码的主要挑战是设

41、计接近信道容量同时具备合理的译码复是设计接近信道容量同时具备合理的译码复杂度的编码方案。杂度的编码方案。Turbo码、低密度奇偶校验码（码、低密度奇偶校验码（LDPC）等专门的等专门的Turbo类类编码采用简单的迭代译码算法，在许多重要的信道上都编码采用简单的迭代译码算法，在许多重要的信道上都能非常接近香农极限，它们的能非常接近香农极限，它们的共同特征是都可作为基于图共同特征是都可作为基于图形的编码来理解形的编码来理解。图形编码方案在图形编码方案在保持合理的译码复杂度的同时接近信道容量保持合理的译码复杂度的同时接近信道容量。低密度奇偶校验码、低密度奇偶校验码、Turbo码和大部分可译的码和大部

42、分可译的接近香农极限的接近香农极限的纠错码纠错码都可以理解成都可以理解成图形编码图形编码。图形能构造出用于迭代译码的图形能构造出用于迭代译码的和积译码算法和积译码算法。因式（因子）图因式（因子）图用来描述编码以及在译码时必须处理的联合概率用来描述编码以及在译码时必须处理的联合概率分布。分布。40第40页，此课件共67页哦9.4基于图形的编码基于图形的编码9.4.1编码的图形建模编码的图形建模（1）Tanner图图Tanner定义了一种称为定义了一种称为Tanner图的二次分裂图，将码字的图的二次分裂图，将码字的符符号号与这些符号必须满足的与这些符号必须满足的限制限制联系起来联系起来.Tanne

43、r还介绍了两种基于图形的译码算法，即还介绍了两种基于图形的译码算法，即和积算法和最小和积算法和最小和算法和算法。图图9.10给出（给出（7，4）汉明码的两种）汉明码的两种Tanner图图。41第41页，此课件共67页哦图9.10 （7，4）汉明码的两种Tanner图：a)局部校验;b)全局校验9.4基于图形的编码基于图形的编码9.4.1编码的图形建模编码的图形建模42第42页，此课件共67页哦9.4基于图形的编码基于图形的编码9.4.1编码的图形建模编码的图形建模图图9.10(a)有有7个变量顶点，用圆圈表示，对应每个码字中的个变量顶点，用圆圈表示，对应每个码字中的7个个符号符号x1,x2,x

44、7。三个校验顶点，表示每个码字必须满足三个校验顶点，表示每个码字必须满足的二进制线性方程的二进制线性方程。一个有效码字，它每个校验顶点的。一个有效码字，它每个校验顶点的邻点（即与校验顶点相连的变量）都必须形成模二和为邻点（即与校验顶点相连的变量）都必须形成模二和为零（即有偶数个零（即有偶数个1）的构造。）的构造。例如例如(x1,x2,x7)=(1,1,1,0,0,0,0)和和(x1,x2,x7)=(0,1,1,1,0,1,0)是有效码字，是有效码字，(x1,x2,x7)=(1,1,1,0,1,1,0)则不则不是，因为不是每个校验式都满足上述关系。是，因为不是每个校验式都满足上述关系。可以将可以

45、将Tanner图中的多个校验顶点聚合成一个，如图图中的多个校验顶点聚合成一个，如图9.10(b)所示，称为全局校验，而将图所示，称为全局校验，而将图9.10(a)的形式称为局部校的形式称为局部校验。验。43第43页，此课件共67页哦9.4基于图形的编码基于图形的编码9.4.1编码的图形建模编码的图形建模（2）因式图）因式图通常将含有状态变量的通常将含有状态变量的Tanner图称为因式图。图称为因式图。图图9.11(a)是是(7,4)汉明码的格图，图汉明码的格图，图9.11(b)是对应的因式图。是对应的因式图。格图中从最左边顶点出发向右一系列路径上的标示代表汉明码的格图中从最左边顶点出发向右一系

46、列路径上的标示代表汉明码的16个码字。辅助变量个码字。辅助变量s0,s1,s7不直接表示码字符。不直接表示码字符。第第i个格区约束了个格区约束了(si-1,xi,si)的可能的组合；事实上，在此线的可能的组合；事实上，在此线性格图的例子里，这些三元组总能形成线性码。性格图的例子里，这些三元组总能形成线性码。44第44页，此课件共67页哦图9.11(a)（7，4）汉明码的trellis图；(b)对应的因式图 45第45页，此课件共67页哦9.4基于图形的编码基于图形的编码9.4.1编码的图形建模编码的图形建模例如，第例如，第3个格区由（个格区由（00,1,01），（），（01,0,10）等）等8

47、个线性组个线性组合构成了局部编码。合构成了局部编码。这码可以认为是二进制（这码可以认为是二进制（5,3）码，如图）码，如图9.11(b)所示。注意到所示。注意到状态变量通常并不是二进制的，图状态变量通常并不是二进制的，图9.11(b)的因式图用并行线的的因式图用并行线的数量对应构成每个状态变量的比特数。数量对应构成每个状态变量的比特数。两端的状态两端的状态s0和和s7规定总为规定总为0，因此实际上它们是零比特变量或，因此实际上它们是零比特变量或常量，于是它们与图常量，于是它们与图9.11(b)因式图的连接用虚线表示。因式图的连接用虚线表示。46第46页，此课件共67页哦9.4基于图形的编码基于

48、图形的编码9.4.1编码的图形建模编码的图形建模因式图可用于建模许多编码结构。因式图可用于建模许多编码结构。例如例如Turbo码便是根据图码便是根据图9.12(a)所示编码原理构成的。此编所示编码原理构成的。此编码器输入码器输入k信息比特信息比特x=(x1,xk)，产生两个不同的奇偶校，产生两个不同的奇偶校验比特流验比特流p=(p1,pk)和和q=(q1,qk)，选择，选择(x,p)对和对和(x,q)对对，使其分别是，使其分别是(2k,k)码码C1和和C2中的码字，通常选择中的码字，通常选择C1和和C2为同为同样的编码器，图中样的编码器，图中代表信息比特的置换，即用于计算代表信息比特的置换，即

49、用于计算q的信息比特与的信息比特与p的相同，但顺序不同。的相同，但顺序不同。图图9.12(b)是对应的因式图，其组成码均由单个校验顶点建模是对应的因式图，其组成码均由单个校验顶点建模而成。在图而成。在图9.12(c)中，这些全局校验被分解为与中，这些全局校验被分解为与C1和和C2的格的格图表示相对应的链状图。图表示相对应的链状图。47第47页，此课件共67页哦图9.12 (a)并行链接码的编码；(b)对应的因式图；(c)格图结构码的因式图 48第48页，此课件共67页哦9.4基于图形的编码基于图形的编码9.4.2采用和积算法译码采用和积算法译码当考虑到译码问题时，基于图形建模的编码的作用就显当

50、考虑到译码问题时，基于图形建模的编码的作用就显现出来了。现出来了。译码本质上是一个统计推导问题：给定一系列的观察（噪译码本质上是一个统计推导问题：给定一系列的观察（噪声信道输出对发送的码字的响应），推测最有可能发送的声信道输出对发送的码字的响应），推测最有可能发送的是哪一个码字（是哪一个码字（ML译码），或者各码元最可能的取值（逐码译码），或者各码元最可能的取值（逐码元元MAP译码）。译码）。和积算法试图通过沿着因式图的边线传递消息的方式来解决和积算法试图通过沿着因式图的边线传递消息的方式来解决逐码元逐码元MAP译码问题。译码问题。49第49页，此课件共67页哦9.4基于图形的编码基于图形的编