差错控制的基本概念 精.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页，本讲稿共67页图9.

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

7、点优点是：是：纠错能力强；检错能力与信道干扰变化无关，适应性强；由于只要检测错误就可以了，因此编译码器比较简单。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页通信系统误比特率与通信系统误比特率与Eb/N0关系的曲线关系的

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

10、别表示未编码及编码后所需分别表示未编码及编码后所需要的要的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)根据对信息元的处理方法分类根据对信息元的处理方法分类按照对信息元处理方法的不同，可以将纠错码分为按照对信息元处理方法的不同，可以将纠错码分为分组码分组码和和卷积码卷积码。分组码分组码的构成如图所示。的构成如图所示。其码长为其码长为n=k+r，其中，其中k是信

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

17、，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.几个基本定义几个基本定义定义定义9.2设码字设码字v=

19、(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.4设发码设发码C:(cn-1,c1,c0)或

20、或(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的突发错误，其中的突发错误，其中b称为突发错误长度，该图样称为突发

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

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

23、纠错编码的分类纠错编码的分类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),它的它的(n 1)个校验元是信息元的个校验元是信

25、息元的重复。对二进制系统，只有两个码字：重复。对二进制系统，只有两个码字：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越大，纠错越大，纠错能力越强。若未编码时接收的错误概率为能力越强。若未编码时接收的错误概率为 ，经，经过过n次重复编码后，如果结合次重复编码后，如

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

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

29、生比特长的符号发生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的增大，编码效率趋的增大，编码效率趋近于近于1，但，但d/n则趋近于则趋近于0，即抗干扰能力随之

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

31、用码组的个数为许用码组的个数为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)个随机错误，则要求个随机错误，则要求da+t+1。证明证明（1）

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

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

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

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

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

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

40、能力为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图的二次分裂图，将码字的图的二次分裂图，将码字的符符号号与这些符号必须满足的与这些符号必须满足的限制限制联系起来联系起来.Tanner还介绍了两种基于图形的译码算法，即还介绍了两种基于图形的译码算法，即和积算法

43、和最和积算法和最小和算法小和算法。图图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,x7。三个校验顶点，表示每个码字必须满足的三个校验顶点，表示每个码字必须满足的二进制

44、线性方程二进制线性方程。一个有效码字，它每个校验顶点的邻点。一个有效码字，它每个校验顶点的邻点（即与校验顶点相连的变量）都必须形成模二和为零（即有（即与校验顶点相连的变量）都必须形成模二和为零（即有偶数个偶数个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)则不是，则不是，因为不是每个校验式都满足上述关系。因为不是每个校验式都满足上述关系。可以将可以将Tanner图中的多个校验顶点聚合成一个，如图图中的多个校验顶点聚合成一个，如图

45、9.10(b)所示，称为全局校验，而将图所示，称为全局校验，而将图9.10(a)的形式称为局部的形式称为局部校验。校验。43第43页，本讲稿共67页9.4基于图形的编码基于图形的编码9.4.1编码的图形建模编码的图形建模（2）因式图）因式图通常将含有状态变量的通常将含有状态变量的Tanner图称为因式图。图称为因式图。图图9.11(a)是是(7,4)汉明码的格图，图汉明码的格图，图9.11(b)是对应的因式图。是对应的因式图。格图中从最左边顶点出发向右一系列路径上的标示代表格图中从最左边顶点出发向右一系列路径上的标示代表汉明码的汉明码的16个码字。辅助变量个码字。辅助变量s0,s1,s7不直接

46、表示码字符。不直接表示码字符。第第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基于图形的编码基于图形的编码9.4.1编码的图形建模编码的图形建模因式图可用于建模许多编码结构。因式图可用于

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

49、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基于图形的编码基于图形的编码9.4.2采用和积算法译码采用和积算法译码（1）概率质量函数的因式图表示）概率质量函数的因式图