第一章纠错码基本概念课件

第一章 纠错码的基本概念 课程简介课程简介信道编码学时：信道编码学时：30 30 信源编码学时：信源编码学时：6 6经典信道编码方法：经典信道编码方法：9090现代信道编码方法：现代信道编码方法：9090教材：王新梅教材：王新梅纠错码：原理与方法纠错码：原理与方法修订版，西电出版社修订版，西电出版社教师：信源部分教师：信源部分-信道部分信道部分-陈燕，陈东华陈燕，陈东华第一章 纠错码的基本概念 第一章 纠错码的基本概念 信道编码的发展历程通信的数学理论，通信的数学理论，Shannon(1948)Shannon(1948)汉明码，汉明码，Hamming(1950)Hamming(1950)级连码，级连码，Forney(1966)Forney(1966)卷积码及有效译码卷积码及有效译码,(60,(60年代年代)RSRS码及码及BCHBCH码的有效译码码的有效译码(60(60年代年代)TCMTCM，Ungerboeck(1982),Forney(1984)Ungerboeck(1982),Forney(1984)TurboTurbo码，码，Berrou(1993)Berrou(1993)LDPC LDPC 码，码，Gallager(1963),Macky(1996)Gallager(1963),Macky(1996)空时编码空时编码,Tarokh(2000),Tarokh(2000)第一章 纠错码的基本概念 目前及未来信道编码研究的方向目前及未来信道编码研究的方向 未来移动通信系统的目标未来移动通信系统的目标 未来移动通信系统中的信道特点未来移动通信系统中的信道特点支持更高容量高质量的语音和数据传输支持更高容量高质量的语音和数据传输有更严重的码间干扰有更严重的码间干扰 有更大的多谱勒频移有更大的多谱勒频移 通信终端在更高的移动速度下实现可靠传输通信终端在更高的移动速度下实现可靠传输 香农信息理论的限制香农信息理论的限制 AWGN SISO 第一章 纠错码的基本概念 针对速率问题针对速率问题 针对抗衰落的问题针对抗衰落的问题多址方式的变化：多址方式的变化：TDMATDMA、FDMAFDMA、CDMACDMA 高性能信道编码技术高性能信道编码技术主要利用时间分集主要利用时间分集 接收分集技术接收分集技术主要利用空间分集主要利用空间分集 调制方式的变化：高阶调制方式、调制方式的变化：高阶调制方式、OFDMOFDM 解决上述问题的常用方法解决上述问题的常用方法单天线系统单天线系统第一章 纠错码的基本概念 针对速率问题针对速率问题方式：方式：采用多天线阵系统采用多天线阵系统依据：依据：多天线阵的信道容量理论多天线阵的信道容量理论解决上述问题的一种新思路解决上述问题的一种新思路多天线阵系统多天线阵系统 针对抗衰落的问题针对抗衰落的问题空时编码技术空时编码技术同时利用时间分集和空间分集同时利用时间分集和空间分集 第一章 纠错码的基本概念 信道编码学时分配如下信道编码学时分配如下纠错码的基本概念纠错码的基本概念纠错码的基本概念纠错码的基本概念2 2 2 2代数初步，多项式环与有限代数初步，多项式环与有限代数初步，多项式环与有限代数初步，多项式环与有限域域域域7 7 7 7线性分组码线性分组码线性分组码线性分组码4 4 4 4循环码与循环码与循环码与循环码与BCHBCHBCHBCH码码码码7 7 7 7卷积码基础卷积码基础卷积码基础卷积码基础6 6 6 6TurboTurboTurboTurbo码、码、码、码、LDPCLDPCLDPCLDPC码、空时码码、空时码码、空时码码、空时码4 4 4 4第一章 纠错码的基本概念 第一章 纠错码的基本概念 1.1 1.1 数字通信系统的组成及信道模型数字通信系统的组成及信道模型 1.2 1.2 差错控制系统和纠错码分类差错控制系统和纠错码分类 1.3 1.3 最大似然译码和纠错码的基本概念最大似然译码和纠错码的基本概念 1.4 1.4 信道编码定理信道编码定理 第一章 纠错码的基本概念 1.1 数字通信系统的组成及信道模型数字通信系统的组成及信道模型 一、一、数字通信系统的组成数字通信系统的组成通通信信的的目目的的是是要要把把对对方方不不知知道道的的消消息息及及时时可可靠靠地地(有有时时还还须须秘秘密密地地)传传送送给给对对方方，因因此此，要要求求一一个个通通信信系系统统传传输消息必须可靠与快速。输消息必须可靠与快速。数字通信系统中数字通信系统中可靠与快速的矛盾可靠与快速的矛盾：u要要求求快快速速，则则每每个个数数据据码码元元所所占占的的时时间间缩缩短短、波波形形变变窄窄、能能量量减减少少，从从而而在在受受到到干干扰扰后后产产生生错错误误的的可可能能性性增增加加，传送消息的可靠性减低。传送消息的可靠性减低。u要求可靠，要求可靠，则传送消息的速率变慢。则传送消息的速率变慢。第一章 纠错码的基本概念 图图 1-1 数字通信系统模型数字通信系统模型与与信信源源匹匹配配，实现数据压缩实现数据压缩与与 信信 道道 匹匹配配，实实 现现较较 少少 的的 差差错传输错传输第一章 纠错码的基本概念 我我们们关关心心的的是是图图中中的的信信道道编编、译译码码器器即即纠纠错错编编、译译码码器器两两个个方方框框，为为了了研研究究方方便便，将将上上述述模模型型再再进进一一步步简简化成图所示的模型。在此模型中化成图所示的模型。在此模型中u信信源源是是指指原原来来的的信信源源和和信信源源编编码码器器，其其输输出出是是二二(多多)进制信息序列。进制信息序列。u信信道道是是包包括括发发射射机机、实实际际信信道道(或或称称传传输输媒媒质质)和和接接收收机机在在内内的的广广义义信信道道(又又称称编编码码信信道道)，它它的的输输入入是是二二(多多)进制数字序列，输出一般也是二进制数字序列，输出一般也是二(多多)进制数字序列进制数字序列.u信宿信宿可以是人或计算机。可以是人或计算机。第一章 纠错码的基本概念 图图 1-2 数字通信系统简化模型数字通信系统简化模型 突出研究目标突出研究目标突出研究目标突出研究目标第一章 纠错码的基本概念 二、二、信道模型信道模型现现在在以以图图1-21-2的的模模型型来来讨讨论论二二进进制制数数字字序序列列通通过过该该系系统统时时所所发发生生的的情情况况。设设从从信信源源送送出出字字母母A A，它它的的二二进进制制序序列为列为1100011000，以基带信号传送，以基带信号传送，图图 1 3 11000发送的已调信号波形发送的已调信号波形第一章 纠错码的基本概念 经经发发射射机机调调制制后后，送送往往信信道道的的已已调调信信号号如如图图 1 1-3 3所所示示。由由于于信信道道的的干干扰扰，从从信信道道输输出出端端的的信信号号产产生生了了失失真真，如图如图 1-41-4所示。所示。图图 1-4 接收端收到的失真信号波形接收端收到的失真信号波形失真严重失真严重第一章 纠错码的基本概念 这这些些失失真真信信号号送送入入接接收收机机进进行行判判决决时时，由由于于第第一一、二二、四四、五五码码元元的的波波形形失失真真不不大大，容容易易正正确确地地判判为为1 1、1 1和和0 0、0 0；但但对对第第三三个个码码元元来来说说，由由于于失失真真严严重重而而难难于于判判决。这时有以下三种判决方法：决。这时有以下三种判决方法：u一是勉强作出是一是勉强作出是0 0还是还是1 1的判决，即所谓的判决，即所谓硬判决硬判决；u另另一一种种是是对对该该码码元元暂暂且且不不作作判判决决，而而输输出出一一个个未未知知或或待定的信号待定的信号“x x”，称其为，称其为删除删除符号；符号；u第第三三种种方方法法是是输输出出一一种种有有关关该该码码元元的的信信息息，例例如如关关于于0 0和和1 1的的后后验验概概率率或或似似然然函函数数，这这种种作作法法称称为为软软判判决决。当当然软判决的性能较好，但实现起来较复杂。然软判决的性能较好，但实现起来较复杂。第一章 纠错码的基本概念 在在二二进进制制硬硬判判决决情情况况下下，信信道道可可用用下下图图所所示示的的简简单单模模型型表表示示。图图中中，p p0101和和p p1010分分别别是是0 0错错成成1 1和和1 1错错成成0 0的的概概率率，称称信信道道转转移概率。该信道的信道转移概率矩阵可用移概率。该信道的信道转移概率矩阵可用 描描述述。如如果果p p0101=p p1010=p pe e，则则称称这这种种信信道道为为二二进进制制对对称称信信道道，简简称称BSCBSC。否否则则，称称为为不不对对称称信信道道。若若p p0101或或p p1010等等于于零零，则则称称为为Z Z信信道道。通通常常BSCBSC是是一一种种无无记记忆忆信信道道，所所以以也也称称随随机机信信道道，它它说说明明数数据据序列中出现的错误彼此无关。序列中出现的错误彼此无关。第一章 纠错码的基本概念 如如果果信信道道的的输输入入是是二二进进制制符符号号，而而输输出出是是离离散散的的q(qq(qp pm m2)2)进进制制符符号号，如如图图 1 1-6 6所所示示，且且p p(i i0)0)p p(q q-1-1-i i1)1)，i i0 0，1 1，q-q-1 1，则则这这种种信信道道称称为为离离散散无无记记忆忆信信道道(DMC)(DMC)，显然显然BSCBSC是是DMCDMC的一种特殊情况。的一种特殊情况。DMCDMC的信道转移概率矩阵的信道转移概率矩阵图图 1-6 DMC第一章 纠错码的基本概念 上上述述两两种种信信道道模模型型只只是是为为了了讨讨论论问问题题方方便便而而简简化化成成理理想想的的情情况况，它它们们表表达达了了某某些些实实际际信信道道传传送送信信号号的的主主要要特特征征。例例如如，卫星信道或深空信道，可近似看成是卫星信道或深空信道，可近似看成是BSCBSC，称为，称为随机信道随机信道。但但有有很很多多实实际际信信道道如如高高频频、散散射射，移移动动等等信信道道，由由于于各各种种干干扰扰所所造造成成的的错错误误，往往往往不不是是单单个个地地而而是是成成群群成成串串地地出出现现的的，也也就就是是一一个个错错误误的的出出现现，往往往往引引起起其其前前后后码码元元的的错错误误(突突发发错错误误)，表表现现为为错错误误之之间间的的相相关关性性。产产生生这这种种错错误误的的信信道道称称有有记记忆信道或突发信道忆信道或突发信道。但但由由于于实实际际信信道道干干扰扰的的复复杂杂性性，所所引引起起的的错错误误往往往往不不是是单单纯纯的的一一种种，而而是是两两种种错错误误形形式式并并存存，只只不不过过有有的的信信道道以以某某种种错错误误形形式为主。式为主。第一章 纠错码的基本概念 像像这这种种随随机机错错误误与与突突发发错错误误并并存存的的信信道道，称称为为组组合合信信道道或或复复合合信信道道。作作为为检检错错与与纠纠错错用用的的抗抗干干扰扰码码，必必须须针针对对这这几几类类信信道道，设设计计能能纠纠正正随随机机错错误误或或纠纠正正突突发发错错误误的的码码，或或者者设设计计既既能能纠纠正正随机错误又能纠正突发错误的码。随机错误又能纠正突发错误的码。克服突发错误有效的办法：级联交织克服突发错误有效的办法：级联交织第一章 纠错码的基本概念 由由于于目目前前在在信信道道中中传传输输或或计计算算机机内内部部运运算算的的数数据据序序列列，大大部部分分是是二二进进制制数数字字序序列列，因因此此以以后后主主要要讨讨论论二二进进制制数数字字通通信信中中的的纠纠错错码码，当当然然这这些些纠纠错错码码往往往往可可以以推推广广到到q(q(素素数数或或素素数数的的幂幂)进进制制情情况况，这这将将在在以以后后具具体体讨讨论论时时予予以以说说明明。二二进进制制情情况下，况下，序列之间序列之间0 0、1 1两个符号按下列规则进行运算：两个符号按下列规则进行运算：+01001110模模2相加相加 模模2相乘相乘01001110为了简便，今后用为了简便，今后用+和和表示模表示模2 2相加和相乘。相加和相乘。在模在模2 2情况情况下，下，加和减是一回事。加和减是一回事。第一章 纠错码的基本概念 三、三、错误图样错误图样发发送送的的是是n n个个码码元元长长的的序序列列C C：(c cn n-1-1，c cn n-2-2，c c1 1，c c0 0)，经经信信道道传传输输到到达达接接收收端端(纠纠错错码码译译码码器器输输入入端端)的的序序列列为为R R：(r rn n-1-1，r rn n-2-2，r r1 1，r r0 0)。由由于于信信道道中中存存在在干干扰扰，R R序序列列中中的的某某些些码码元元可可能能与与C C序序列列中中对对应应码码元元的的值值不不同同，也也就就是是说说产产生生了了错错误误。由由于于二二进进制制序序列列中中的的错错误误不不外外乎乎是是1 1错错成成0 0或或0 0错错成成1 1，因因此此，如如果果把把信信道道中中的的干干扰扰也也用用二二进进制制序序列列E E：(e en n-1-1，e en n-2-2，e e1 1，e e0 0)表表示示，则则相相应应有有错错误误的的各各位位e ei i取取值值为为1 1，无无错错的的各各位位取取值值为为0 0，而而R R就就是是C C与与E E序序列列模模2 2相相加加的的结结果果，我我们们称称E E为信道的为信道的错误图样错误图样或或干扰矢量干扰矢量。第一章 纠错码的基本概念 例例如如，发发送送序序列列C C：(1111100000)(1111100000)，收收到到的的序序列列R R：(1001010000)(1001010000)，第第二二、三三、五五、六六位位产产生生了了错错误误，因因此此信信道道的的错错误误图图样样E E的的二二、三三、五五、六六位位取取值值为为1 1，其其它它各各位位取取值值为为0 0，即即E E：(0110110000)(0110110000)。用用式式子可表示成：子可表示成：发送序列发送序列C:1111100000 错误图样错误图样E：0110110000 接收序列接收序列R：1001010000+即即RC+E，或或E=R-C。第一章 纠错码的基本概念 信信道道干干扰扰所所造造成成的的错错误误可可在在序序列列中中的的任任一一位位出出现现，且且也也可可以以在在n n长长序序列列中中同同时时出出现现一一位位、二二位位，甚甚至至n n位位错错误误。因因此此，若若发发送送的的C C序序列列长长为为n n，则则信信道道中中可可能能产产生生的的错错误误图样图样E E共有共有2 2n n种种。若若为为突突发发信信道道，则则在在错错误误图图样样E E中中，第第一一个个1 1与与最最后后一一个个1 1之之间间的的长长度度称称为为突突发发长长度度，其其图图样样称称为为突突发发图图样样。在该例中，突发图样是在该例中，突发图样是(11011)(11011)，突发长度为突发长度为5 5。第一章 纠错码的基本概念 1.2 差错控制系统和纠错码分类差错控制系统和纠错码分类(1)(1)重传反馈方式重传反馈方式(ARQ)(ARQ)应应用用ARQARQ方方式式纠纠错错的的通通信信系系统统如如图图 1 1-9 9所所示示。发发送送端端发发出出能能够够发发现现(检检测测)错错误误的的码码，接接收收端端收收到到通通过过信信道道传传来来的的码码后后，在在译译码码器器根根据据该该码码的的编编码码规规则则，判判决决收收到到的的码码序序列列中中有有无无错错误误产产生生，并并通通过过反反馈馈信信道道把把判判决决结结果果用用判判决决信信号号告告诉诉发发端端。发发端端根根据据这这些些判判决决信信号号，把把接接收收端端认认为为有有错错的的消消息息再再次次传传送送，直直到到接接收端认为正确接收为止。收端认为正确接收为止。第一章 纠错码的基本概念 图1-9ARQ通信系统第一章 纠错码的基本概念 ARQARQ方式的缺点：方式的缺点：必必须须有有反反馈馈信信道道，且且要要求求信信源源能能够够控控制制，系系统统收收发发两两端端必必须须互互相相配配合合、密密切切协协作作，控控制制电电路路比比较较复复杂杂。反反馈馈重重发发的的次次数数与与信信道道干干扰扰情情况况有有关关，若若信信道道干干扰扰很很频频繁繁，则则系系统统经经常常处处于于重重发发消消息的状态，息的状态，传送消息的连贯性和传送消息的连贯性和实时性较差实时性较差。ARQARQ方式的优点是：方式的优点是：编编译译码码设设备备简简单单；在在一一定定的的多多余余度度码码元元下下，检检错错码码的的检检错错能能力力比比纠纠错错码码的的纠纠错错能能力力要要高高得得多多，因因而而整整个个系系统统的的纠纠错错能能力力极极强强；由由于于检检错错码码的的检检错错能能力力与与信信道道干干扰扰的的变变化化基基本本无无关关，因因此此这这种种系统的系统的适应性很强适应性很强，如短波、散射等干扰情况复杂的信道中。，如短波、散射等干扰情况复杂的信道中。第一章 纠错码的基本概念(2)(2)前向纠错方式前向纠错方式(FEC)(FEC)发发送送端端发发送送能能够够被被纠纠错错的的码码，接接收收端端收收到到这这些些码码后后，通通过过纠纠错错译译码码器器不不仅仅能能自自动动地地发发现现错错误误，而而且且能能自自动动地地纠纠正正接接收收码字传输中的错误。码字传输中的错误。优优点点是是不不需需要要反反馈馈信信道道，能能进进行行一一个个用用户户对对多多个个用用户户的的同同播播通信，译码实时性较好，控制电路比通信，译码实时性较好，控制电路比ARQARQ的简单。的简单。缺缺点点是是译译码码设设备备复复杂杂，所所选选用用的的纠纠错错码码必必须须与与信信道道的的干干扰扰情情况相匹配，对信道的适应性差。况相匹配，对信道的适应性差。但但随随着着编编码码理理论论的的发发展展和和编编译译码码设设备备所所需需的的VLSIVLSI成成本本的的降降低低，译译码码设设备备有有可可能能做做得得越越来来越越简简单单，成成本本越越来来越越低低，FECFEC在在数数字通信中得到广泛应用。字通信中得到广泛应用。第一章 纠错码的基本概念(3)(3)混混合合纠纠错错方方式式(HEC)(HEC)这这种种方方式式是是发发送送端端发发送送的的码码不不仅仅能能够够被被检检测测出出错错误误，而而且且还还具具有有一一定定的的纠纠错错能能力力。接接收收端端收收到到码码序序列列以以后后，首首先先检检验验错错误误情情况况，如如果果在在纠纠错错码码的的纠纠错错能能力力以以内内，则则自自动动进进行行纠纠错错。如如果果错错误误很很多多，超超过过了了码码的的纠纠错错能能力力，但但能能检检测测出出来来，则则接接收收端端通通过过反反馈馈信信道道，要要求求发发端端重重新新传传送送有有错错的的消消息息。这这种种方方式式在在一一定定程程度度上上避避免免了了FECFEC方方式式要要求求用用复复杂杂的的译译码码设设备备和和ARQARQ方方式式信信息息连连贯贯性性差差的的缺缺点点，并并能能达达到到较较低低的的误码率，误码率，因此在实际中的应用越来越广。因此在实际中的应用越来越广。第一章 纠错码的基本概念 除除了了上上述述三三种种主主要要方方式式以以外外，还还有有所所谓谓狭狭义义信信息息反反馈馈系系统统(IRQ)(IRQ)。这这种种方方式式是是接接收收端端把把收收到到的的消消息息原原封封不不动动地地通通过过反反馈馈信信道道送送回回发发送送端端，发发送送端端比比较较发发送送的的与与反反馈馈回回来来的的消消息息，从从而而发发现现错错误误，并并且且把把传传错错的的消消息息再再次次传传送送，最最后后达达到到使使对对方方正正确确接收消息的目的。接收消息的目的。为为了了便便于于比比较较，我我们们把把上上述述几几种种方方式式用用图图 1 1-1010所所示示的的框框图图表表示示。图图中中，有有斜斜线线的的方方框框表表示示在在该该端端检检出出错错误误。在在实实际际系系统统设设计计中中，如如何何根根据据实实际际情情况况选选择择哪哪种种差差错错控控制制方方式式是是一一个个比比较复杂的问题，由于时间所限，这里不再讨论较复杂的问题，由于时间所限，这里不再讨论.第一章 纠错码的基本概念 图图 1-10 差错控制的基本方式差错控制的基本方式 第一章 纠错码的基本概念 二、二、纠错码的分类纠错码的分类 上上述述各各种种差差错错控控制制系系统统中中所所用用到到的的码码，不不外外乎乎是是能能在在译译码码器器自自动动发发现现错错误误的的检检错错码码，或或者者不不仅仅能能发发现现错错误误而而且且能能自自动动纠纠正正错错误误的的纠纠错错码码，或或者者能能纠纠正正删删除除错错误误的的纠纠删删码码。但但这这三三类类码码之之间间没没有有明明显显区区分分，以以后后将将看看到到，任任何何一一类类码码，按按照照译译码码方方法不同，法不同，均可作为检错码、均可作为检错码、纠错码或纠删码来使用。纠错码或纠删码来使用。除了上述的划分方法以外，除了上述的划分方法以外，通常还按以下方式对纠错码进通常还按以下方式对纠错码进行分类：行分类：第一章 纠错码的基本概念(1)(1)按按照照对对信信息息元元处处理理方方法法的的不不同同，分分为为分分组组码码与与卷卷积积码码两大类。两大类。分分组组码码是是把把信信源源输输出出的的信信息息序序列列，以以k k个个码码元元划划分分为为一一段段，通通过过编编码码器器把把这这段段k k个个信信息息元元按按一一定定规规则则产产生生r r个个校校验验(监监督督)元元，输输出出长长为为n nk+rk+r的的一一个个码码组组。因因此此每每一一码码组组的的校校验验元元仅仅与与本本组组的的信信息息元元有有关关，而而与与别别组组无无关关。分分组组码码用用(n n，k k)表表示示，n n表示码长，表示码长，k k表示信息位。表示信息位。卷卷积积码码是是把把信信源源输输出出的的信信息息序序列列，以以k k0 0个个(k k0 0通通常常小小于于k k)码码元元分分为为一一段段，通通过过编编码码器器输输出出长长为为n n0 0(k k0 0)一一段段的的码码段段。但但是是该该码码段段的的n n0 0-k k0 0个个校校验验元元不不仅仅与与本本组组的的信信息息元元有有关关，而而且且也也与与其其前前m m段段的的信信息息元元有有关关，称称m m为为编编码码存存贮贮。因因此此卷卷积积码码用用(n n0 0，k k0 0，m m)表示。表示。第一章 纠错码的基本概念(2)(2)根根据据校校验验元元与与信信息息元元之之间间的的关关系系分分为为线线性性码码与与非非线线性性码码。若若校校验验元元与与信信息息元元之之间间的的关关系系是是线线性性关关系系(满满足足线线性性叠叠加加原理原理)，则称为线性码则称为线性码;否则，称为非线性码。否则，称为非线性码。(3)(3)按按照照纠纠正正错错误误的的类类型型可可分分为为纠纠正正随随机机(独独立立)错错误误的的码码、纠纠正正突突发发错错误误的的码码和和纠纠正正同同步步错错误误的的码码，以以及及既既能能纠纠正正随随机机错错误又能纠正突发错误的码。误又能纠正突发错误的码。第一章 纠错码的基本概念(4)(4)按按照照每每个个码码元元取取值值来来分分，可可分分为为二二进进制制码码与与q q进进制制码码(q=pq=pm m，p p为素数，为素数，m m为正整数为正整数)。(5)(5)按按照照对对每每个个信信息息元元保保护护能能力力是是否否相相等等可可分分为为等等保保护护纠纠错错码码与与不不等等保保护护(UEP)(UEP)纠纠错错码码。除除非非特特别别说说明明，今今后后讨讨论论的的纠纠错错码码均均指指等等保保护护能能力力的的码码。此此外外，在在分分组组码码中中按按照照码码的的结结构构特特点点，又又可可分分为为循循环环码码与与非非循循环环码码。为为了了清清楚楚起起见见，我我们们把把上上述述分分类类用图用图 1-111-11表示。表示。第一章 纠错码的基本概念 图图 1-11 纠错码分类纠错码分类第一章 纠错码的基本概念 1.3 最大似然译码和纠错码的基本概念最大似然译码和纠错码的基本概念 一、一、基本定义基本定义利用纠错码进行差错控制的数字通信系统如图利用纠错码进行差错控制的数字通信系统如图 1-121-12所示，所示，图图 1-12 1-12 利用分组码的数字通信模型利用分组码的数字通信模型第一章 纠错码的基本概念 由此可如下定义分组码由此可如下定义分组码 定定义义1.3.1 1.3.1 分分组组码码是是对对每每段段k k位位长长的的信信息息组组，以以一一定定规规则则增增加加r=n-kr=n-k个个校校验验元元，组组成成长长为为n n的的序序列列：(cncn-1-1，cncn-2-2，c c1 1，c c0)0)，称称这这个个序序列列为为码码字字(码码组组、码码矢矢)。在在二二进进制制情情况况下下，信信息息组组总总共共有有2 2k k(q(q进进制制为为q qk k)个个，因因此此通通过过编编码码器器后后，相相应应的的码码字字也也有有2 2k k个个，称称这这2 2k k个个码码字字集合为集合为(n n，k k)分组码。分组码。第一章 纠错码的基本概念 n n长长序序列列的的可可能能排排列列总总共共有有2 2n n种种(每每一一n n长长序序列列称称为为n n重重)，而而(n n，k k)分分组组码码的的码码字字集集合合只只有有2 2k k种种。所所以以，分分组组码码的的编编码码问问题题就就是是定定出出一一套套规规则则，以以便便从从2 2n n个个n n重重中中选选出出2 2k k个个码码字字，不不同同的的选选取取规规则则就就得得到到不不同同的的码码。我我们们称称被被选选取取的的2 2k k个个n n重为重为许用码组许用码组，其余的其余的2 2n n-2-2k k个为个为禁用码组禁用码组。称称R Rk kn n为为码码率率，表表示示(n n，k k)分分组组码码中中，信信息息位位在在码码字中所占的比重。字中所占的比重。R R是衡量分组码有效性的一个基本参数。是衡量分组码有效性的一个基本参数。第一章 纠错码的基本概念 图图 1 1-1313是是一一个个(2,(2,1,1,2)2)卷卷积积码码编编码码器器。若若输输入入的的信信息息序序列列以以k k0 01 1个个码码元元分分段段输输入入，则则输输出出以以n n0 02 2个个码码元元为为一一段段输输出出，如如输输入入的的信信息息序序列列M M(1(1 1 1 0 0 1 1 0 0 0)0)，输输出出的的码码序序列列为为C C(11(11，1010，1010，0000，0101，1111，0000，)。可可知知随随着着信信息息元元的的不不断断输输入入，输输出出的的是是一一个个半半无无限限长长的的码码序序列列，由由此此可可如如下下定义卷积码。定义卷积码。第一章 纠错码的基本概念 图图 1-13 一个一个(2，1，2)卷积码编码器卷积码编码器第一章 纠错码的基本概念 定定义义1.3.2 1.3.2 (n n0 0，k k0 0，m m)卷卷积积码码是是对对每每段段k k0 0长长的的信信息息组组以以一一定定的的规规则则增增加加r r0 0n n0 0-k k0 0个个校校验验元元，组组成成长长为为n n0 0的的码码段段。n n0 0-k k0 0个个校校验验元元不不仅仅与与本本段段的的信信息息元元有有关关，且且与与前前m m段段的的信信息息元元有有关关，当当信信息息元元不不断断输输入入时时，输输出出的的码码序序列列是是一一个个半半无无限限长长序序列列。(n n0 0，k k0 0，m m)卷卷积积码码的的码码率率R Rk k0 0 n n0 0 。与与分分组组码码的的码码长长n n相相对对应应，在在卷卷积积码码中中称称n nc cn n0 0(m m+1)+1)为为编编码码约约束束长长度度，说说明明k k0 0个个信信息息元元从从输输入入编编码码器器到到离离开开时时在在码码序序列列中中影影响响的的码码元元数数目目，如图如图 1-131-13中中(2(2，1 1，2)2)卷积码的卷积码的n nc c 6 6。第一章 纠错码的基本概念 二、二、最大似然译码最大似然译码由由图图1-21-2可可知知，信信道道输输出出的的R R是是一一个个二二(或或q)q)进进制制序序列列，而而译译码器的输出是一个信息序列码器的输出是一个信息序列M M的估值序列的估值序列 。译译码码器器的的基基本本任任务务就就是是根根据据一一套套译译码码规规则则，由由接接收收序序列列R R给给出出与与发发送送的的信信息息序序列列M M最最接接近近(最最好好是是相相同同)的的估估值值序序列列 。由由于于M M与与码码字字C C之之间间存存在在一一一一对对应应关关系系，所所以以这这等等价价于于译译码码器器根根据据R R产产生生一一个个C C的的估估值值序序列列 。显显然然，当当且且仅仅当当C CC C时时，M M，这时译码器正确译码。，这时译码器正确译码。第一章 纠错码的基本概念 如如果果译译码码器器输输出出的的 C C，则则译译码码器器产产生生了了错错误误译译码码。之之所所以以产产生生错错误误译译码码是是由由于于：信信道道干干扰扰很很严严重重，超超过过了了码码本本身身的的纠纠错错能能力力；其其次次，由由于于译译码码设设备备的的故故障障(这这点点本本书书不不予予讨讨论论)。当当给定接收序列给定接收序列R R时，译码器的条件译码错误概率定义为时，译码器的条件译码错误概率定义为所以译码器的错误译码概率所以译码器的错误译码概率 第一章 纠错码的基本概念 P P(R R)是是接接收收R R的的概概率率，与与译译码码方方法法无无关关，所所以以译译码码错错误误概概率率最小的最佳译码规则是使最小的最佳译码规则是使 因此，如果译码器对输入的因此，如果译码器对输入的R R，能在，能在2 2k k个码字中选择一个使个码字中选择一个使 最最大大的的码码字字C Ci i作作为为C C的的估估值值序序列列 ，则则这这种种译译码码规规则则一一定定使使译译码码器器输输出出错错误误概概率率最最小小，称称这这种种译译码规则为码规则为最大后验概率译码最大后验概率译码。（1.3.1）第一章 纠错码的基本概念 由贝叶斯公式由贝叶斯公式可可知知，若若发发端端发发送送每每个个码码字字的的概概率率P P(C Ci i)均均相相同同，且且由由于于P P(R R)与与译码方法无关，所以译码方法无关，所以 对对DMCDMC而言而言（1.3.2）（1.3.3）这里码字这里码字Ci(ci1，ci2，cin)，i1，2，2k。第一章 纠错码的基本概念 一一个个译译码码器器的的译译码码规规则则若若能能在在2 2k k个个码码字字C C中中选选择择某某一一个个C Ci i使使式式(1.3.2)(1.3.2)成成为为最最大大，则则这这种种译译码码规规则则称称为为最最大大似似然然译译码码(MLD)(MLD)，P P(R RC C)称称为为似似然然函函数数，相相应应的的译译码码器器称称为为最最大大似似然然译译码码器器。由于由于loglogb bx x与与x x是单调关系，因此式是单调关系，因此式(1.3.2)(1.3.2)与式与式(1.3.3)(1.3.3)可写成可写成 称称loglogb b P P(R RC C)为为对对数数似似然然函函数数或或似似然然函函数数。对对于于DMCDMC信信道道，MLDMLD是是使使译译码码错错误误概概率率最最小小的的一一种种最最佳佳译译码码准准则则或或方方法法，但但此此时时要要求求发发端端发发送送每每一一码码字字的的概概率率P P(C Ci i)()(i i1 1，2 2，,2,2k k)均均相相等等，否否则则MLDMLD不不是是最最佳佳的的。在在以以后后的的讨讨论论中中，都都认认为为P P(C Ci i)均均近近似似相相等。等。第一章 纠错码的基本概念 三、三、汉明汉明(Hamming)(Hamming)距离与重量距离与重量定定义义1.3.3 1.3.3 两两个个n n重重x x、y y之之间间，对对应应位位取取值值不不同同的的个个数数，称为它们之间的汉明距离，用称为它们之间的汉明距离，用d d(x x，y y)表示。表示。例如，若例如，若x x:(10101):(10101)，y y：(01111)(01111)，则，则d d(x x，y y)3 3。定定义义1.3.4 1.3.4 n n重重x x中中非非零零码码元元的的个个数数，称称为为它它的的汉汉明明重重量量，简称重量，用简称重量，用w w(x x)表示。表示。例例如如，若若x x：(10101)(10101)，则则w w(x x)3 3。若若y y：(01111)(01111)，则则w w(y y)4 4，等等。，等等。第一章 纠错码的基本概念 定定义义 1.3.5 1.3.5 (n n，k k)分分组组码码中中，任任两两个个码码字字之之间间距距离离的的最最小小值，值，称为该分组码的称为该分组码的最小汉明距离最小汉明距离d d0 0，简称，简称最小距离最小距离例例如如(3,2)(3,2)码码，n n3 3，k k2 2，共共有有2 22 24 4个个码码字字：000000，011011，101101，110110，显然，显然d d0 02 2。d d0 0是是(n n，k k)分分组组码码的的另另一一个个重重要要参参数数。它它表表明明了了分分组组码码抗抗干干扰扰能能力力的的大大小小。以以后后将将看看到到：d d0 0越越大大，码码的的抗抗干干扰扰能能力力越越强强，在在同同样样译译码码方方法法下下它它的的译译码码错错误误概概率率越越小小。由由上上可可知知，R R和和d d0 0是是(n n，k k)分分组组码码的的两两个个最最重重要要参参数数。纠纠错错编编码码的的基基本本任任务务之之一一就就是是构构造造出出R R一一定定、d d0 0尽尽可可能能大大的的码码，或或d d0 0一一定定、R R尽尽可可能能高高的的码码。下下面面用用几个具体例子说明码的几个具体例子说明码的R R、d d0 0以及译码错误概率之间的关系。以及译码错误概率之间的关系。第一章 纠错码的基本概念 定理定理1.3.1 1.3.1 任一任一(n n，k k)分组码，若要在码字内：分组码，若要在码字内：(1)(1)检测检测e e个随机错误，个随机错误，则要求码的最小距离则要求码的最小距离d de e+1+1；(2)(2)纠正纠正t t个随机错误，则要求个随机错误，则要求d d22t t+1;+1;(3)(3)纠纠正正t t个个随随机机错错误误，同同时时检检测测e e(t t)个个错错误误，则则要要求求d dt t+e e+1+1。(4)(4)纠正纠正t t个错误和个错误和个删除，则要求个删除，则要求d d22t t+1+1。证证明明(1)(1)由由图图1-14(a)1-14(a)可可知知，若若C C1 1发发生生了了e e个个错错误误变变为为C C1 1，则则d d(C C1 1，C C1 1)e e，设设e ed d-1-1，则则d d(C C1 1 ，C C2 2)1 1，故故C C1 1 C C2 2，因因此此译译码码器器不不会会将将C C1 1错错判判成成C C2 2，检检测测到到e e=d d-1-1个个错错误。误。第一章 纠错码的基本概念 图图 1-14 纠错码纠错能力的几何解释纠错码纠错能力的几何解释第一章 纠错码的基本概念(2)(2)设设C C1 1与与C C2 2是是(n n，k k)码码中中任任两两码码字字距距离离之之最最小小者者，且且为为2 2t t+1+1。则则C C1 1错错了了t t个个错错误误以以后后变变成成C C1 1，它它们们之之间间的的距距离离d d(C C1 1，C C1 1)=t)=t，但但d d(C C1 1，C C2 2)t t+1+1。d d(C C1 1，C C2 2)d(d(C C1 1，C C1 1)，如如图图 1-14(b)1-14(b)所所示示，所所以以译译码码器器可可以以根根据据它它们们之之间间的的距距离离的的大大小正确译码，小正确译码，从而纠正从而纠正t t个错误。个错误。(3)(3)这这里里所所指指的的同同时时，是是当当错错误误个个数数t t时时，该该码码能能纠纠正正t t个个错错；当当错错误误个个数数大大于于t t而而小小于于e e时时，则则码码能能发发现现e e个个错错误误。由由(1)(1)和和(2)(2)的证明可直接得到结论的证明可直接得到结论(3)(3)，请读者自行证明。请读者自行证明。由由此此定定理理可可知知，一一个个距距离离为为d d的的分分组组码码，至至多多能能纠纠正正t t(d d-1)-1)2 2(x x是是x x的的整整数数部部分分)个个错错误误。该该定定理理确确定定了了码码的的纠纠错错能能力力与与它它的的距距离离之之间间的的关关系系，是是纠纠错错码码理理论论中中最最基基本本的的定理之一。定理之一。第一章 纠错码的基本概念 1.4 信道编码定理信道编码定理 信信道道编编码码定定理理 每每个个信信道道具具有有确确定定的的信信道道容容量量C C，对对任任何何小小于于C C的的码码率率R R，存存在在有有速速率率为为R R码码长长为为n n的的分分组组码码及及(n n0 0，k k0 0，m)m)卷卷积积码码，若若用用最最大大似似然然译译码码，则则随随着着码码长长的的增增加加其其译译码码错错误误概概率率p p可任意小，可任意小，即即 和和(1.4.1)第一章 纠错码的基本概念 式式中中，A Ab b和和A Ac c为为大大于于0 0的的系系数数，E Eb b(R R)和和E Ec c(R R)为为正正实实函函数数，称称为为误误差差指指数数，它它与与R R、C C的的关关系系如如图图1 1-1515所所示示。图图中中，C C1 1、C C2 2为为信信道道容容量量，且且C C1 1C C2 2。由由信信息息论论的的基基本本知知识识可可知知，在在高高斯斯白白噪噪声声信信道时，道时，信道容量信道容量 式式中中，W W是是信信道道所所能能提提供供的的带带宽宽，P PS SE ES ST T是是信信号号功功率率，E ES S是是信信号号能能量量，T T是是分分组组码码信信号号的的持持续续时时间间即即信信号号宽宽度度，P PS SW W是是单单位位频频带的信号功率，带的信号功率，N N0 0是单位频带的噪声功率，是单位频带的噪声功率，P PS S (WNWN0 0)是信噪比。是信噪比。第一章 纠错码的基本概念 由由式式(1.4.1)(1.4.1)和和图图 1-151-15可可看看出出，信信道道容容量量C C、码码长长n n和和错错误误概概率率p p之之间间的的转转换换关关系系。为为了了满满足足一一定定误误码码率率p p的的要要求求，可可用用以以下下两两类方法实现。类方法实现。一一是是增增加加信信道道容容量量C C，从从而而使使E E(R R)增增加加。由由C C的的表表示示式式(1.4.2)(1.4.2)可可知知，增增加加C C的的方方法法可可以以采采用用如如加加大大系系统统带带宽宽或或增增加加信信噪噪比比的的方方法法来来达达到到。例例如如，采采用用调调频频、调调相相等等宽宽带带调调制制方方法法；增增加加发发射射机机的的功功率率；应应用用高高增增益益天天线线；采采用用分分集集接接收收及及低低噪噪声声器器件件等等方方法法。这这些些措措施施是是从从根根本本上上改改善善信信道道、增增加加信信道道容容量量、减减少少误误码率的方法，码率的方法，是通信设计工作者经常采用的传统方法。是通信设计工作者经常采用的传统方法。第一章 纠错码的基本概念 图图 1-15 信道容量信道容量C、码长、码长n和错误概率和错误概率p之间的转换关系之间的转换关系第一章 纠错码的基本概念 另另一一种种方方法法是是在在R R一一定定下下，增增加加分分组组码码长长n(n(也也就就是是增增加加分分组组信信号号持持续续时时间间T T)，可可使使p p随随n n的的增增加加而而呈呈指指数数下下降降。但但由由于于码码长长n n的的增增加加，当当R R保保持持一一定定时时，可可能能发发送送的的码码字字数数2 2k k指指数数增增加加，从从而而增增加加了了译译码码设设备备的的复复杂杂性性。这这种种方方法法就就是是信信道道编编码码定定理理所所指指出出减减少少误误码码率率的的另另一一方方向向，它它为为通通信信设设计计工工作作者者提提供供了了一一条条新的途径。新的途径。第一章 纠错码的基本概念 在在极极限限情情况况n n时时，要要求求带带宽宽W W。根根据据计计算算，此此时时只只要要求求信信噪噪比比E Eb bN N0 0-1.6dB-1.6dB，就就可可实实现现高高斯斯白白噪噪声声信信道道下下的的无无误误传传输输。这这就就是是带带宽宽无无限限高高斯斯白白噪噪声声信信道道的的极极限限传传输输能能力力，称称为为ShannonShannon限限。图图 1 1-1616给给出出了了未未编编码码的的PSKPSK与与应应用用各各类类纠纠错错码码后后，误误码码率率与与信信噪噪比比之之间间的的关关系系曲曲线线。由由此此图图看看到到：应应用用R R1 12 2的的(24(24，12)12)分分组组码码后后，在在误误码码率率为为1010-5-5时时比比未未编编码码的的大大约约可可节节省省3 3 dBdB的的功功率率(称称编编码码增增益益)；而而用用R R1 12 2，约约束束度度N N为为8 8的的卷卷积积码码软软判判决决维维特特比比(Viterbi)(Viterbi)译译码码，在在误误码码率率为为1010-5-5时时，大大约约可可节节省省5dB5dB的的功功率率。一一般般情情况况下下，应应用用纠纠错错码码后后，大大约约能能得到从零点几到几个得到从零点几到几个dBdB程度不等的编码增益。程度不等的编码增益。第一章 纠错码的基本概念 图图 1-16 各种码的性能比较各种码的性能比较