信息论第9章 纠错编码.ppt

第9章 纠错编码; ? 因为通过分别进行信源的数据压缩编码和信道的数据传输编码，即能做到有效又可靠地传输信息，又能大大地简化通信系统的设计，因此在实际通信系统中得到广泛应用。 ? 针对各种不同信源如文本、语音、静止图像、活动图像等数据压缩的研究形成了数据压缩理论与技术； ? 而针对信道编码问题的研究又形成了另一独立的分支-----纠错码理论。 ;3;白噪声定义:白噪声是指功率谱密度在整个频域内 均匀分布的噪声。 ;附：定义－白噪声是指功率谱密度在整个频域内均匀分布的噪声。 严格地说，白噪声只是一种理想化模型，因为实际噪声的功率谱密度不可能具有无限宽的带宽，否则它的平均功率将是无限大，是物理上不可实现的。然而，白噪声在数学处理上比较方便，因此它是系统分析的有力工具。一般，只要一个噪声过程所具有的频谱宽度远远大于它所作用系统的带宽，并且在该带宽中其频谱密度基本上可以作为常数来考虑，就可以把它作为白噪声来处理。例如，热噪声和散弹噪声在很宽的频率范围内具有均匀的功率谱密度，通常可以认为它们是白噪声。; ;信息论与纠错编码理论几乎同时在二次大战结束后不久诞生的。前者首先有shannon以他的不朽著作“通信的数学理论”为标志建立起来的，而后者则以Hamming的经典著作“纠错与检错编码”为代表。Shannon与Hamming都在贝尔实验室工作，彼此非常熟悉，在Shannon的文章中也利用了Hamming关于纠错编码的结果。 Shannon理论讨论了信息的度量，以及对于信息表示和传输的基本限制。Shannon的信道编码定理表明只要信息传输速率小于信道容量，则信息传输可以以任何小的错误概率进行。但是Shannon并没有告诉人们如何去实现这一点。Hamming提出的纠错编码理论却正是为了试图解决这个问题。;在通信中信源编码、信道编码与数据转换编码常常是同时使用的。;9.1基本概念; ? 通过在传输的信息码元后增加一些多余的码元(称为校验元)，纠错编码可以在信息损失或错误后还能在接收端恢复原代码。 ? 根据信息码元和校验码元之间不同的关系，纠错码按结构分类大致如下页图所示。 ;; 线性码——信息码元与校验码元之间呈线性关系。 非线性码——信息码元与校验码元之间不存在线性关系。 分组码——把信息序列以每k个码元分组，然后把每组k个信息元按一定规律产生r个多余的校验元，输出序列每组长为n＝k+r，则每一码字的r个校验元只与本码字的k个信息冗有关，与别的码字的信息位无关，记为分组码(n, k)。 卷积码——把信息序列以每ko(通常较小)个码元分段，编码器输出该段的校验元r＝n- ko不但与本段的ko个信息元有关，而且还与其前面m段的信息元有关，故记为卷积码(n，ko ，m) 。 ;13;其中分组码又可分循环码和非循环码：? 循环码——该码书的特点是，若将其全部码字分成若干组，则每组中任一码字中码元循环移位后仍是这组的码字。? 非循环码——任一码字中码元的循环移位后不一定再是该码书中的码字 。按照纠正错误类型可分为纠正随机错误码、纠正突发错误码、纠正随机与突发错误码以及纠正同步错误码等。 另外，按照每个码元取值来分，有二元码和q元码。目前传输系统或存储系统大都采用二进制的数字系统，所以一般提到的纠错码都是指二元码。; ; 对于某一种编码满足上述要求是非常重要的。;n;分组码;19;编码效率;线性分组码;系统码;汉明距离;24;25;最小码距;汉明重量; 信道编码提供了对于信息传输发生差错的控制能力。这种控制能力由编码器的纠错能力与检错能力来表征。检错是指当信息在信道上传输发生错误时，译码器能发现传输有误，并及时的告诉接受者；而纠错则是译码器能自动纠正这个错误的能力。 下面以重复码为例说明编码的纠错和检错能力。;例1 考虑一个把1bit信息数据重复3次的重复编码。该编码器实现 “0” ? “000” ， “1” ? “111” 这时n=3,k=1,r=2.;例1 （续） 如果采用下表方式译码，则上述重复码可以纠正任何一位错误。;;9.2纠错码分类;33;34;35;36;37;38;39;40;9.3线性分组码;42;43;44;45;46;47;48;49;50;51;52;53;9.3.2线性分组码的检纠错能力;55;56;57;58;59;60;61;62;63;64;65;66;9.3.3校验矩阵与最小距离的关系;68;69;70;71;9.3.4线性分组码的伴随式;73;9.3.5线性分组码的译码;75;76;汉明码;78;79;80;9.4 几种重要的码;82;83;84;85;86;87;88;89;90;91;92;93;94;95;96;9.4.2卷