信息论与编码第6章(纠错)

第6章信道编码2020/1/71第六章信道编码第6章信道编码2020/1/72问题的提出•愿望：信息传输多快好省。•现实：（1）速度：受信道容量的限制，不可能无限大；（2）质量：受信道噪声的干扰，传输错误不可避免。•衡量信息传输可靠性的指标：平均差错率Pe。•Pe与信道的统计特性有关，不可能为零，有时甚至很大。•降低Pe的方法：先对消息进行编码再送入信道传送，这种为降低平均差错率而进行的编码称为信道编码；在信道输出端加信道译码器进行信息还原。•香农第二编码定理所给出的结论：只要信道编码和译码的方法得当，就可使平均差错率趋于零。编码信道XN信道编码器fUˆUY信道信道译码器F第6章信道编码2020/1/736.1有扰离散信道的编码理论6.2纠错编译码的基本原理与分析方法6.3线性分组码6.4卷积码6.5其它信道编码内容第6章信道编码2020/1/746.1有扰离散信道的编码定理6.1.1差错和差错控制系统分类6.1.2矢量空间与码空间6.1.3随机编码与信道编码定理第6章信道编码2020/1/756.1.1差错和差错控制系统分类•差错率是衡量传输质量的重要指标之一,它有几种不同的定义。•码元差错率/符号差错率–指在传输的码元总数中发生差错的码元数所占的比例(平均值),简称误码率(Errorsymbolrate)。–是指信号差错概率•比特差错率/比特误码率(Errorbitrate)：–在传输的比特总数中发生差错的比特数所占比例–是指信息差错概率•对二进制传输系统,符号差错等效于比特差错;对多进制系统,一个符号差错对应多少比特差错却难以确定第6章信道编码2020/1/76•为定量地描述信号的差错,定义差错图样E:E=C－R(模M)•最常用的二进制码可当作特例来研究,其差错图样等于收码与发码的模2加,即E=C⊕R或C=R⊕E•设发送的码字C1111111111接收的码字R1001001111差错的图样E0110110000•差错图样中的“1”既是符号差错也是比特差错,差错的个数叫汉明距离。•差错图样类型•随机差错,突发差错：差错图样第6章信道编码2020/1/77纠错码分类•从功能角度讲,差错码分为检错码和纠错码•按照对信息序列的处理方法,有分组码和卷积码•按照码元与原始信息位的关系,分为线性码和非线性码•按照适用的差错类型,分成:纠随机差错码和纠突发差错码•按照构造码的理论：代数码、几何码、算术码和组合码。第6章信道编码2020/1/78信道编码的基本思想•信道编码–按一定规则给数字序列m增加一些多余的码元,使不具有规律性的信息序列m变换为具有某种规律性的数码序列C；–码序列中的信息序列码元与多余码元之间是相关的；–信道译码器利用这种预知的编码规则译码。检验接收到的数字序列R是否符合既定的规则,从而发现R中是否有错,或者纠正其中的差错；–根据相关性来检测/发现和纠正传输过程中产生的差错就是信道编码的基本思想。第6章信道编码2020/1/79差错控制系统分类•前向纠错(FEC)：–发送端的信道编码器将信息码组编成具有一定纠错能力的码。•自动请求重发(ARQ)：–发端发送检错码,如CRC(循环冗余校验码)•混合纠错(HEC)：–是FEC与ARQ方式的结合。•信息反馈(IRQ)：第6章信道编码2020/1/7106.1.2矢量空间与码空间分组码的一个码字可以看作一个n重矢量，所以可以用矢量空间来分析和理解分组码。F表示码元所在的数域，对于二进制码，F代表二元域{0,1}。设n重有序元素的集合V={Vi},则称集合V是数域F上的n维矢量空间，或称n维线性空间，n维矢量又称n重(n-tuples)。线性空间的基底、自然基底、子空间、矢量正交、矢量空间正交、对偶空间“重数”：构成矢量的有序元素的个数；“维数”：张成矢量空间基底的个数；维数不可能大于重数，而当维数小于重数时说明这是个子空间。第6章信道编码2020/1/711码空间和分组编码的任务消息k长(n,k)码字n长qk种分组编码器qn种k维k重矢量n维n重矢量通常qnqk，分组编码的任务是要在n维n重矢量空间的qn种可能组合中选择其中的qk个构成一个码空间，其元素就是许用码的码集。•选择一个ｋ维n重子空间作为码空间。•确定由k维k重信息空间到ｋ维n重码空间的映射方法。•码空间的不同选择方法，以及信息组与码组的不同映射算法，就构成了不同的分组码。第6章信道编码2020/1/7126.1.3随机编码与信道编码定理如果不考虑编码的具体方法，而是运用概率统计的方法在特定信道条件下对编码信号的性能作出统计分析，求出差错概率的上，下限边界，其中最优码所能达到的差错概率上界称为随机码界。随机编码的含义机编码。间，则称这种编码为随果随机的选取一个子空种选法，如该子空间的选取有好多重空间的一个子空间。维成的空间为个码字组由所有重空间中的一个元素，维所以码字为码字的长度为个不同的消息。而总共有元符号组成的码组，则个，由编成长度为种符号。其中每个消息有分组码，设消息组对于NNqNNNqqNNqmmmmKNkkk,),,...,,(),(110第6章信道编码2020/1/713错误概率的上界对于离散无记忆信道（DMC）。错误平均概率的上界为：exp(())ErPNER•E(R)为可靠性函数，也叫误差指数•码率：R=(lbM)/N–M是可能的信息组合数，M=qK–N是每码字的码元数，–R表示每码元携带的信息量，单位是每符号比特（bit/symbol）–是全部码集的平均差错概率eP第6章信道编码2020/1/714•正定理：只要传信率R小于信道容量C，总存在一种信道码（及解码器），可以以所要求的任意小的差错概率实现可靠的通信。•逆定理：信道容量C是可靠通信系统传信率R的上边界，如果RC，就不可能有任何一种编码能使差错概率任意小。•上述两定理统称为有扰或噪声信道的信道编码定理信道编码定理第6章信道编码2020/1/7156.2纠错编译码的基本原理与分析方法6.2.1纠错编码的基本原理6.2.2译码方法---最优译码和最大似然译码第6章信道编码2020/1/7166.2.1纠错编码的基本原理6.2.1纠错编码的基本思想一、从编码定理出发讨论纠错码的基本原理：)(RNEereP从上面的公式可以看出：要减小Pe：（1）增大N;（2）增大Er(R)；1增大信道容量C（1）扩展带宽。（2）加大功率。（3）减小噪声功率。2减小码率R(=KlbQ/N)3增大码长NC,R,K/N不变第6章信道编码2020/1/717二、从冗余度和噪声均化讨论纠错码的基本原理：冗余度：就是在信息流中插入冗余比特，插入的冗余比特与信息比特存在着特定的相关性。这样如果在传输过程中有个别信息比特受损，也可以从冗余比特中恢复或发现受损比特。从而保证了信息传输的可靠性。传输冗余比特必然要动用冗余的资源:时间,频带,功率,设备复杂度噪声均匀化：就是让差错随机化，以便符合编码定理的条件从而得到符合编码定理结果。其基本思想是设法将危害较大的，较为集中的噪声干扰分摊开来，使不可恢复的信息损伤最小。（1）增加码长。（2）卷积。（3）交织。第6章信道编码2020/1/718译码算法的已知条件是要求已知：（1）实际接收到的码字序列{r},r=(r1,r2,…..rN)。（2）发送端所采用的编码算法和该算法产生的码集XN,满足。NiNiiiXcccc),.....,,(21（3）信道模型及信道参数。消息组m),...,,(21kmmm(N,K)编码器NiXC码字),...,,(21iNiiccc信道r接收码),...,,(21Nrrr最佳/最大似然译码^ic码字估值),...,,(21iNiiccc消息还原),...,,(21kmmmim消息6.2.2译码方法---最优译码和最大似然译码第6章信道编码2020/1/719译码规则与错误概率•信道编码是一个一一对应的变换或函数，称为编码函数f；•信道译码也是一个函数，称为译码函数F。编码信道XN信道编码器fUUY信道信道译码器F由于是一一对应变换，其反变换唯一确定。因此，讨论译码函数时，只考虑从中还原出就可以了。f1fˆXFY平均差错率Pe与译码规则F有关。第6章信道编码2020/1/720两种典型的译码规则两种典型的译码规则：最佳译码规则、极大似然译码规则1、最佳译码规则：平均差错率最小的译码规则。XYDMC12{,,,}rAaaa12{,,,}sBbbb信道译码FˆX12{,,,}rAaaaN1()1()|sejjjjPPbPFbb**(|)()|)(,:,jjjjiijjPabPaFbaAbBFaAb*(,(,)jjijPabPab*(|))((|)()jjijjjPbPPbPabab**(,(,))(,:,jjijjjjiPabPaFbaAbBFabA按“后验概率最大”原则定出，又称最大后验概率译码规则按“联合概率最大”原则定出，又称最大联合概率译码规则第6章信道编码2020/1/7212、极大似然译码规则按“转移概率最大”原则定出，称为极大似然译码规则。•实际应用中，经常只知道信道的统计特性(转移概率)，而不知道信源的统计特性(输入概率)，这时求不出联合概率和后验概率，因此无法确定最佳译码规则。•既然只知道转移概率，就只能按转移概率的某种约束条件制订译码规则。•按最大转移概率条件来确定的译码规则，称为极大似然译码规则。**(),:(|)(|),jjjjjjiiFbaAbBFPbaPbaaA第6章信道编码2020/1/722极大似然译码规则与最佳译码规则等价的条件**(|)(|)(),:,jjjjjjiiPbaPbFbaAbaAaBF极大似然译码规则最佳译码规则结论：信道输入等概时，极大似然译码规则与最佳译码规则等价。*(|)(|)jjjiPbaPba*(,(,)jjijPabPab证明：输入等概*()()jiPaPa**(|)()((|))jjjiijPaPaPbaPba（1）信道输入是近似等概的：因为信道前级有信源编码器存在。（2）极大似然译码规则近似最佳，可以放心使用。注：**(|)()|)(,:,jjjjiijjPabPaFbaAbBFaAb第6章信道编码2020/1/723•最佳译码，也叫最大后验概率译码(MAP)•最大似然译码(MLD)**(|)()|)(,:,jjjjiijjPabPaFbaAbBFaAb消息组mi码字ci接收码r估值消息ˆmax(/)iiPccrˆmax(/)iiPcrc信道ˆicˆim消息还原编码器译码**(|)(|)(),:,jjjjjjiiPbaPbFbaAbaAaBF第6章信道编码2020/1/724码字的似然函数12121(/)(,,....,),(,,.....,),max(/)max(/)NiiiNNjijjprrrcccpprciiircrcrc一般情况下，称为码字的似然函数。对于无记忆信道，如果则有：为了方便计算，可以利用对数运算将乘法运算转化为加法运算。即：)/(logmax)/(logmax1ijNjjicrpcrp第6章信道编码2020/1/725BSC信道第6章信道编码2020/1/726,((/)1,(ijjjijijjpcrprcpcr在极大似然译码算法中有：时）时）汉明距离译码是一种硬判决译码。由于BSC信道是对称的，只要发送的码字独立、等概，汉明距离译码也就是最佳译码。1(/)(/)(1)()(1)1NdNddNjijjppprcppppirc最大似然译码等效于最小汉明距离译码。第6章信道编码2020/1/7276.3线性分组码•6.3.1线性分组码的生成矩阵和校验矩阵•6.3.2伴随式与标准阵列译码•6.3.3码距,纠错能力,MDC码等•6.3.4完备码,循