第五章-差错控制与信道编码.ppt

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,第五章 差错控制与信道编码,结束放映,学习目录,学习,要求,内容简介,内容简介,差错控制就是通过某种方法，发现并纠正数据传输中出现的错误。差错控制技术是提高数据传输可靠性的重要手段之一，现代数据通信中使用的差错控制方式大都是基于信道编码技术来实现的，本章对差错控制的基本概念以及常用的信道编码方案作了比较详细的论述。,返回,结束,学习要求,1.,理解差错控制的基本概念及其原理等；,2.,掌握信道编码的基本原理；,3.,了解常用检错码的特性；,4.,掌握线性分组码的一般特性；,5.,掌握汉明码以及循环码的编译码及其实现原理；,6.,了解卷积码的基本概念。,返回,结束,学习目录,返回,5.1,概述,5.2,常用的简单信道编码,5.3,线性分组码,5.4,卷积码,结束,5.1,概 述,差错控制,是数据通信系统中提高传输可靠性，降低系统传输误码率的有效措施。本节将介绍差错控制和信道编码的基本原理、差错控制的实现方式等内容。,5.1.1,差错控制,5.1.2,信道编码,5.1.3,基于信道编码的差错控制方式,本节内容提要：,5.1.1,差错控制,差错控制,通过某种方法，发现并纠正传输中出现的错误。,香农信道编码定理,在具有确定信道容量的有扰信道中，若以低于信道容量的速率传输数据，则存在某种编码方案，可以使传输的误码率足够小。,基于信道编码的差错控制,在发送端根据一定的规则，在数据序列中按照一定的规则附加一些监督信息，接收端根据监督信息进行检错或者纠错。,5.1.1,差错控制,随机错误,主要由起伏噪声引起，错误码元分布比较分散且彼此统计独立；,突发错误,主要由脉冲噪声引起，错误码元分布集中且彼此具有某种相关性。,错误图样,差错分析,E,中，“,0”,表示正确，“,1”,表示错误,随机错误错误图样,5.1.1,差错控制,突发错误错误图样,5.1.2,信道编码,在不采用信道编码的时候，进入信道的数据码元相互独立，一旦发生错误，将无法发现。例如气象台向电视台传输气象信息。,不可靠数据传输系统,5.1.2,信道编码,将信息序列按照,k,位码元的长度分成若干个信息码组,M,，再将信息码组输入到信道编码器，信道编码器按照一定的算法，产生一个新的,n,位码字,A,输出，,nk,；,收端根据,A,中的相关性判断接收是否正确，并将其恢复成,M,。,编码效率为,k/n,，即所谓,编码效率,是指信道编码后码字中信息码元的数目与码字总码元数目之比。,信道编码的基本思想,5.1.2,信道编码,信道编码的冗余,信息码组,M,由,k,个二进制码元（即比特）组成，所以就有,2,k,个,M,；,A,长度为,n,，,n,位长度的码字共有,2,n,个，信道编码实质是通过一定,的规则，从,2,n,个长度为,n,的码字中选择了其中的,2,k,个，每个被选,中的码字称为许用码字；,未被选中的,2,n,-,2,k,个,n,长的码字称为禁用码字，反映冗余大小。,5.1.2,信道编码,对本节开始时的例子采用,(2,，,1),重复码,:1,1,”-,晴,“0,0,”-,雨,许用码组为,:“1,1,”,和“,0,0,”,禁用码组为：“,01,”,和“,10,”,此时接收端可以发现单个错误，但不能纠正错误,也不能发现,2,位错误，如下图所示：,实例分析,I,5.1.2,信道编码,对本节开始时的例子采用,(3,，,1),重复码,:1,11,”-,晴,“0,00,”-,雨,许用码组为,:1,11,和,0,00,禁用码组为：,001,、,010,、,011,、,100,、,101,、,110,将这种编码用来检错时，可以发现两位以内的错误,将这种编码用来纠错，可以纠正一位错误，如下图所示：,实例分析,II,5.1.2,信道编码,如此译码的原因是信道中错一位的概率远远大于错多位的概率,例如要把该（,3,，,1,）重复码在有一条误码率为,10,-5,的信道传输，则：,错一位的概率为：,P,1,=C,3,1,Pe,(1,Pe),2,=3,10,-5,错二位的概率为：,P,2,=C,3,2,Pe,2,(1,Pe,),=3,10,-10,错三位的概率为：,P,3,=Pe,3,=10,-15,这种译码方法称为,极大似然译码法,其基本原理为,:,构造一个极大似,然函数,L,从,2,k,个许用码组中找到一个码字,C,i,，,当,=,C,i,时,函数,L,可以取得最大值,则认为,C=,C,i,。,5.1.2,信道编码,线性码和非线性码,若,f,(),是线性函数称为线性码,若,f,(),是非线性函数则称为非线性编码,信道编码的分类,信道编码器函数关系式为：,分组码和卷积码,分组码：每个信息码组,M,通过运算产生对应的,A,，记作,(,n,，,k,),卷积码：每个,A,是由,m,(,m,t,),(,n,，,k,),分组码总共有,2,k,个码字，记作,A,i,（,i,=0,1,2,k,-1,）,则这些码字两两之间都有一个码距，定义该,(,n,，,k,),分组码的最小码距为：,5.1.3,基于信道编码的差错控制方式,前向纠错（,FEC:Forward Error Correction,）方式,原理,采用纠错码,收端发现错误后自动纠正,。,特点,无需重发，解码延迟固定，实时性好,无需反馈信道，能用于单向传输信道，特别适用于单点向多点同时传送的方式,编码效率较低，需较大的冗余度（通常约,25-50%,）,译码设备比较复杂,纠错码须与信道特性相匹配，对信道变化的适应性较差,若错误超出纠错码纠错能力,只好将其抛弃,应用,移动通信系统,5.1.3,基于信道编码的差错控制方式,反馈重传（,ARQ:Automatic Repeat Request,）方式,原理,采用检错码，接收端发现错误后，给发送端一个反馈信号，要求重新发送，直到正确为止。,特点,编码效率比较高，只需少量的冗余码（约,5-20%,）就能获得极低的传输误码率；对信道的适应能力强,必须有反馈信道，故不能用于单向传输系统和同播系统,控制规程和过程比较复杂,重发导致信道的有效利用率较低，通信的实时性较差,由于反馈重传的随机性，故不适于实时传输系统,5.1.3,基于信道编码的差错控制方式,反馈重传（,ARQ:Automatic Repeat Request,）方式,工作方式,发送等待,连续工作方式,混合方式,应用,数据通信系统,5.1.3,基于信道编码的差错控制方式,混合纠错（,HEC:Hybrid Error Correction,）方式,原理,采用纠检错码，是,ARQ,和,FEC,方式的折衷方案,特点,集合了,ARQ,和,FEC,的优点，在保证系统较高的有效性的同时,大幅度提高了整个系统的可靠性,应用,移动通信系统，数据传输系统（特别是在使用卫星信道等高时延、大容量的信道传输数据信号时更具优势）,5.1.3,基于信道编码的差错控制方式,信息反馈（,IRQ:Information Repeat Request,）方式,原理,也称回程校验方式，在发端来检测错误。,特点,无需采用纠检错编码，故设备和控制由于规程较简单；,需一条与前向信道相同的反馈信道；,由于采用发端检错，相当于信息传输距离增加一倍，可能导致额外的差错和重传；,可能使整个通信系统的传信率很低；,收发两端需较大容量的存储器来存储传输信息。,5.2,常用的简单信道编码,本节内容提要：,检错码在,ARQ,系统中使用，其生成方式简单，易于实现，检错效果较好，因此得到广泛的应用，本节将介绍奇偶校验码、行列监督码、恒比码、正反码的编译码规则、特性以及应用情况。,5.2.1,奇偶监督码,5.2.2,行列监督码,5.2.3,恒比码,5.2.4,重复码,5.2.5,正反码,5.2.1,奇偶监督码,奇偶监督码,码重为奇数或偶数的,(n,n-1),系统分组码,ITU-T,建议,同步数据传输使用偶监督,异步数据传输使用奇监督,能检查出传输码组中的所有奇数个错误,监督关系,假设将（,n,，,n,-1,）的奇偶监督码的码字记作：,a,n,-1,a,n,-2,a,1,a,0,，,其中,a,0,为监督码元，其余为信息码元，则各码元满足：,5.2.2,行列监督码,行列监督码（水平垂直一致校验码或方阵码）,对水平方向,(,共,L,行,),和垂直方向,(,共,M,列,),同时进行奇偶监督的码，,记作（,LM+L+M+1,LM,）。,(66,，,50),行列监督码的一个码字,该码具有很强的纠检错能力，常用于短波散射信道等信道干扰比,较严重的通信中。,5.2.2,行列监督码,行列监督码（水平垂直一致校验码或,g,方阵码）,根据按列或按行的次序传输，分别能发现小于等于,M+1,或,L+1,长度的突发性错误；,可以检出某些偶数个随机误差；,当传输差错数正好为,4,的倍数，而且构成矩形的四个角，则不能发现这类差错。,5.2.3,恒比码,恒比码（等比码，定比码，等重码）,从所有一定长度的二进制序列中选取“,1”,数目相同的序列作为码字；,该码的特点是码字中,1,，,0,数目恒定，亦即,1,，,0,数目之比恒定。,目前我国电传通信中普遍采用,3,：,2,码，又称,5,中取,3,码，如下所示,国际上通用的,ARQ,电报通信系统中，采用,7,中取,3,码。,可以检测所有奇数个错误和部分偶数个错误。,主要优点是简单易实现。,5.2.4,重复码,(3,，,1),重复码两个码字为,000,和,111,，其最小码距为,3,；,(,n,，,1),重复码也只有全,0,码和全,1,码两个码字，其最小码距为,n,，,却有,2,n,-2,个禁用码组，随着码长的增大，其冗余也变得很大；,该码随码长增加，具有很强的纠检错能力，但其编码效率的急 剧下降；,重复码并不是一种优秀的编码方案，仅用于,速率很低,的数据通信系统中。,重复码,重复码只有一位信息码元，监督码元是信息码元的重复，,所以仅有两个码字；,5.2.5,正反码,正反码,该码型多用于,10,单位码的前向纠错设备中，可以纠正一位错误，,发现全部两个以下的错误，以及大部分两个以上的错误，其本质,就是五单位码的重复；,编码规则,信息码组中,1,的数目为奇数时，监督码是信息码的重复即正码；,信息码组中,1,的数目为偶数时，监督码是信息码的反码。,译码方法,首先将收到的码字中的信息位和监督位按对应位作模,2,运算，,得到一个,5,位码组，若该码字中有奇数个,1,，则将其作为校验码,组，若有偶数个,1,，则取其反码作为校验码组。然后，按照下表,进行纠检错译码,5.2.5,正反码,正反码错误判决表,校验码组的形式,错误情况判断,1,全“,0”,传输正确,2,4,个“,1”,，,1,个“,0”,信息元有,1,位出错，在校验码组中“,0”,对应的位置,3,4,个“,0”,，,1,个“,1”,监督元有,1,位出错，在校验码组中“,1”,对应的位置,4,其它形式,传输出错，且错误位数大于,1,5.3,线性分组码,本节内容提要：,本节将对线性分组码的特点、编译码规则以及应用情况作介绍，主要包括以下四方面内容。,5.3.1,基本概念,5.3.2,线性分组码编码,5.3.3,汉明码,5.3.4,循环码,5.3.1,基本概念,1,有限域,定义了加法“,+”,和乘法“,”,两种运算的有限集合；,q,个元素的有限域又称为伽罗瓦域，记作,GF(,q,),；,对域的逆元操作又演绎出了减法“”和除法运算“,”,，,域具有封闭特性,域中总包含惟一的加法恒等元“,0”,和乘法恒等元“,1”,5.3.1,基本概念,域中任意元素存在惟一的加法逆元,域中任意非零元都存在惟一的乘法逆元,于是减法和除法运算可定义为：,域中元素满足交换律、结合律和分配律运算规则：,5.3.1,基本概念,GF(,q,),中定义的是模,q,的加法和乘法，例如,GF(2),的运算表如表所示：,+,0,1,0,0,1,1,1,0,0,1,0,0,0,1,0,1,加法运算表,乘法运算表,5.3.1,基本概念,2,矢量空间,所有,n,维矢量组成的集合就构成了,n,维矢量空间,V,n,；,矢量对矢量的加法构成一个加法交换群，,即满足封闭性、结合律和交换律，有恒等元和逆元。,满足分配律,满足结合律,对于相乘恒等元,有,矢量空间的性质,8PSK,调制时给出的信号点矢量图，,就是定义在,GF(2),上的,3,维矢量空间,V,3,V,3,=000,，,001,，,010,，,011,，,100,，,101,，,110,，,111,5.3.1,基本概念,集合,S,中存在全零矢量（,0,0,0,），即零元；,集合,S,中任何两个矢量和仍在该集合中，即满足封闭性。,子空间,如果,n,维矢量空间,V,n,的一个子集,S,，满足以下条件，则称其为,V,n,的一个子空间：,矢量与码字的关系,一个码长为,n,的码字可以看成是一个有,n,个元素的矢量；,所有,2,n,个,n,长码字就构成了定义在,GF(2)(,两个元素：,0,、,1,的伽罗瓦域,),上的,n,维矢量空间,V,n,；,对于一个,(,n,，,k,),线性分组码，其编码过程是从,GF(2),上的,n,维矢,量空间,V,n,中，寻找其中遵循某种编码规则的一个子空间，而这,个子空间中的所有码字正好构成了一个加法交换群，所以线性,分组码又称为群码。,5.3.1,基本概念,3,线性分组码性质,封闭性,具有零元,即具有全零码，记作,A,0,。,具有负元,若,A,i,+,A,j,=,A,0,则称其互为负元，（,n,k,）中,A,i,是它本身的负元。,满足结合率和交换率,5.3.2,线性分组码编码,1,生成距阵,矢量的线性无关,若,V,n,中,k,个矢量,A,1,A,2,A,k,，当且仅当 ，,i,=1,2,k,时下式成立,空间的基,在任意一个矢量空间或者子空间中，至少存在一组线性无关的矢量，可以张成这个空间,这一组矢量称为该空间的基，基中矢量的数目称为空间的维数。,5.3.2,线性分组码编码,实例分析,v,1,=(1000),，,v,2,=(0100),，,v,3,=(0010),，,v,4,=(0001),线性无关的，作为基，张成一个,4,维矢量空间,V,4,：,5.3.2,线性分组码编码,生成矩阵,矩阵,G,的每行矢量是基中的矢量，故称之为生成矩阵；,由其可以得到矢量空间中的全部矢量；,上例中选取的基得到的生成矩阵恰好是,4,阶单位矩阵，实际上线性无关的行矢量都可以作为生成矩阵的行矢量。,2,编码原理,线性分组码标记,（,n,，,k,）线性分组码，其码字通常记作：,A,=,a,n,-1,a,n,-2,a,0,1,n,信息码组,M,记作：,M,=,m,k,-1,m,k,-2,m,1,m,0,1,k,5.3.2,线性分组码编码,生成矩阵,G,记作：,编码过程,5.3.2,线性分组码编码,实例,假设一个,(6,，,3),分组生成矩阵为：,编码过程为：,5.3.2,线性分组码编码,该,(6,，,3),码是非系统码，信息元,m,2,、,m,0,、,m,1,分别出现在码字,A,的第,1,、,3,、,5,位，而,2,、,4,、,6,位是编码器产生的监督码元，其码表为：,信息码组,M,m,2,m,1,m,0,码字,A,a,5,a,4,a,3,a,2,a,1,a,0,信息码组,M,m,2,m,1,m,0,码字,A,a,5,a,4,a,3,a,2,a,1,a,0,0 0 0,0 0 1,0 1 0,0 1 1,0 0 0 0 0 0,0 0 1 1 0 1,0 1 0 0 1 1,0 1 1 1 1 0,1 0 0,1 0 1,1 1 0,1 1 1,1 1 0 1 0 1,1 1 1 0 0 0,1 0 0 1 1 0,1 0 1 0 1 1,5.3.2,线性分组码编码,生成矩阵典型化,实例分析,3,系统码编码原理,编码过程,5.3.2,线性分组码编码,(6,，,3),系统分组码表,监督元与信息元之间的一般关系,信息码组,M,m,2,m,1,m,0,码字,A,a,5,a,4,a,3,a,2,a,1,a,0,信息码组,M,m,2,m,1,m,0,码字,A,a,5,a,4,a,3,a,2,a,1,a,0,0 0 0,0 0 1,0 1 0,0 1 1,0 0 0 0 0 0,0 0 1 1 0 1,0 1 0 0 1 1,0 1 1 1 1 0,1 0 0,1 0 1,1 1 0,1 1 1,1 0 0 1 1 0,1 0 1 0 1 1,1 1 0 1 0 1,1 1 1 0 0 0,5.3.2,线性分组码编码,注意到系统码中前,k,位即信息元，将其写成线性方程组的形式,监督关系,5.3.2,线性分组码编码,监督矩阵,监督关系一般表达,或,生成矩阵典型阵一般形式,5.3.2,线性分组码编码,(,n,，,k,),分组码码字可表示为：,(n,，,k),码的一般编码过程,A,=,a,n,-1,a,n,-2,a,n-k,a,r-,1,a,1,a,0,=,m,k,-1,m,k,-2,m,0,a,r-,1,a,1,a,0,对上式两边同时进行矩阵转置得：,5.3.2,线性分组码编码,也即,此时的系数矩阵，即监督矩阵为,5.3.2,线性分组码编码,生成矩阵和监督距阵的关系,(n,，,k),码的一般编码过程,或,即,根据需要选定一监督关系确定,H,阵；,由,H,阵和阵的关系确定,G,阵；,由,A=MG,生成所有码字。,5.3.2,线性分组码编码,伴随式,S,和错误图样,E,的关系,伴随式,二者并不是一一对应的关系，因为错误图样有,2,n,种表现形,式，而伴随式仅有,2,r,种表现形式，（注意,r=,n-k,n,），且其中,S,=0,说明传输无错，这在该,(,n,，,k,),分组码用于检错时已足够。,但发生了错误却不能检出是完全有可能的，例如封闭性错误。,4,伴随式与检错原理,5.3.2,线性分组码编码,(6,，,3),分组码的监督矩阵为：,实例分析,伴随式,5.3.2,线性分组码编码,(6,，,3),分组码伴随式计算电路,5.3.3,汉明码,将监督矩阵记成列矢量的形式，,H,=,h,0,h,1,h,n,-2,h,n,-1,，则,汉明码定义,伴随式和错误图样的关系,单个错误时的伴随式恰好与,H,的一个列矢量对应，只要,H,的各个,列矢量不为,0,矢量，且各不相同，则可以纠正单个错误。,5.3.3,汉明码,汉明码的另一种描述方式：对于任何的整数，必存在一个,(,n,，,k,),汉明码，码长,n,和监督元数目,r=,n-k,满足,n,=2,r,-1(,除去全零情况,),汉明码特点,可以纠正一位传输错误，且,d,0,=3,，,码长和监督元的关系：,n,=2,r,-1,实例分析,(7,，,4),汉明码,首先构造其监督矩阵，此时监督矩阵为,H,37,，,3,位二进制码元的组合有,8,种：,000,、,001,、,010,、,011,、,100,、,101,、,110,、,111,其中不全为零的,7,个正好可用作监督矩阵的列,可得到监督矩阵：,5.3.3,汉明码,任意调换监督矩阵各列位置并不影响码的纠错能力，,将其转化成典型阵的形式，并由其可以得到生成矩阵,G,由,A=MG,得到其所有的码字，如下表所示：,5.3.3,汉明码,假设发送端的码字是,A,15,=1111111,，,传输过程中第,4,位,a,3,出现了错误，即接收的码字是,B=1110111,此时对应的伴随式为：,信息码组,M,m,3,m,2,m,1,m,0,码字,A,a,6,a,5,a,4,a,3,a,2,a,1,a,0,信息码组,M,m,3,m,2,m,1,m,0,码字,A,a,6,a,5,a,4,a,3,a,2,a,1,a,0,0 0 0 0,0 0 0 1,0 0 1 0,0 0 1 1,0 1 0 0,0 1 0 1,0 1 1 0,0 1 1 1,0 0 0 0,0 0 0,0 0 0 1,0 1 1,0 0 1 0,1 0 1,0 0 1 1,1 1 0,0 1 0 0,1 1 0,0 1 0 1,1 0 1,0 1 1 0,0 1 1,0 1 1 1,0 0 0,1 0 0 0,1 0 0 1,1 0 1 0,1 0 1 1,1 1 0 0,1 1 0 1,1 1 1 0,1 1 1 1,1 0 0 0,1 1 1,1 0 0 1,1 0 0,1 0 1 0,0 1 0,1 0 1 1,0 0 1,1 1 0 0,0 0 1,1 1 0 1,0 1 0,1 1 1 0,1 0 0,1 1 1 1,1 1 1,5.3.3,汉明码,下表给出了该（,7,，,4,）汉明码单个错误的错误图样与其对应的伴,随式，可以发现伴随式正是监督矩阵的每一列，且该列的位置恰,好是码元出错的位置。,由于,S,不是全零，可判断传输出错，,而,S,T,=0 1 1,T,，是监督矩阵,H,的第,4,列,这正是错误码元发生的位置,因此可以得到错误图样为,E=0001000,，进而按,B+E,即可纠错。,5.3.3,汉明码,完备性定义,汉明码完备码 性,错误位置,错误图样,E,e,6,e,5,e,4,e,3,e,2,e,1,e,0,伴随式,S,s,2,s,1,s,0,无错,0 0 0 0 0 0 0,0 0 0,b,0,0 0 0 0 0 0 1,0 0 1,b,1,0 0 0 0 0 1 0,0 1 0,b,2,0 0 0 0 1 0 0,1 0 0,b,3,0 0 0 1 0 0 0,0 1 1,b,4,0 0 1 0 0 0 0,1 0 1,b,5,0 1 0 0 0 0 0,1 1 0,b,6,1 0 0 0 0 0 0,1 1 1,5.3.4,循环码,一个,(7,，,3),系统循环码码表如下所示：,1,基本概念,一类具有循环移位特性的线性分组码，,即其中的一个码字经过循环移位后仍然是该分组码的码字,定义,信息码组,M,m,2,m,1,m,0,码字,A,a,6,a,5,a,4,a,3,a,2,a,1,a,0,信息码组,M,m,2,m,1,m,0,码字,A,a,6,a,5,a,4,a,3,a,2,a,1,a,0,0 0 0,0 0 1,0 1 0,0 1 1,0 0 0 0 0 0 0,0 0 1 0 1 1 1,0 1 0 1 1 1 0,0 1 1 1 0 0 1,1 0 0,1 0 1,1 1 0,1 1 1,1 0 0 1 0 1 1,1 0 1 1 1 0 0,1 1 0 0 1 0 1,1 1 1 0 0 1 0,5.3.4,循环码,例如,A,4,=0111001,，对应的码多项式为：,码多项式,(,n,，,k,),循环码中，为了便于描述与计算，经常使用,n,-1,次码多项式,来表示码字，码字,A=,a,n,-1,a,n,-2,a,1,a,0,，它对应的码多项式为：,A,4,向左循环移,1,位得,A,7,=1110010,，这相当于将,A,4,(,x,),乘以,x,，即,5.3.4,循环码,对于,(7,，,3),循环码的码多项式，其最高次数不能超过,6,，解决该,问题的办法是对上式作模,x,7,+1,运算：,A,7,向左循环移,1,位得,A,6,=1100101,，但若将,A,7,(,x,),乘以,x,得到多项式为,其计算过程如下：,5.3.4,循环码,2,生成多项式和生成矩阵,(n,，,k),循环码中的,r=,n-k,次码多项式，其次数最低（,0,元除外）；,其它所有的码多项式都能被,g(x,),整除；,并且,g(x,),是,x,n,+1,的一个因式。,生成多项式,g(x,),例如本节前面给出的,(7,，,3),循环码，其生成多项式为：,5.3.4,循环码,若,g,(,x,),含有,(,x,+1),因式，对应的,(,n,，,k,),系统循环码，,能够检出所有奇数个错误；,(,n,，,k,),系统循环码检错能力与,g,(,x,),的关系,若,g,(,x,),含有常数项,1,因式，且不能整除,x,e,+1,，,则对应的,(,n,，,k,),系统循环码，能够检出所有的两位错误；,若,g,(,x,),含有常数项,1,因式，对应的,(,n,，,k,),系统循环码，,能够检出所有突发长度,r,的突发错误，,并且对突发长度等于,r,+1,的突发错误的漏检率为,2,-(,r,-1),，,对突发长度大于,r,+1,的突发错误的漏检率为,2,-r,。,5.3.4,循环码,CRC-12,：,标准生成多项式,CRC-16,：,CRC-CCITT,：,CRC-32,：,5.3.4,循环码,g,(,x,),、,x,g,(,x,),、,x,2,g,(,x,),、,、,x,k,-1,g,(,x,),是,(,n,，,k,),循环码的,k,个线性无,关的码字，所以可得其生成距阵,G,，用码多项式表示,G,的各行：,生成矩阵,G,若信息码组,M,=,m,k,-1,m,k,-2,m,0,，则：,5.3.4,循环码,上式同时提供了循环码的一种编码方法，但由其得到的循环码,是非系统码，因为此时生成矩阵不是典型阵。,例如本节前面给出的,(7,，,3),循环码，,将该矩阵典型化之后，再按照,A=MG,编码才能得到表本节前面,给出的系统,(7,，,3),循环码；,实际应用中，系统循环码的编译码通常是由,g,(,x,),经过简单的代数,运算来实现。,5.3.4,循环码,系统,(n,，,k),循环码码字：,编码原理,用码多项式来表示为：,3,编码,A,=,a,n,-1,a,n,-2,a,n-k,a,r-,1,a,1,a,0,=,m,k,-1,m,k,-2,m,0,a,r-,1,a,1,a,0,5.3.4,循环码,式中,M,(,x,),是信息码组码多项式，所以只需要确定,r,(,x,),已知循环码的所有码字都能够被,g,(,x,),整除，,r,(,x,),可由下式确定：,(,n,，,k,),循环码的生成多项式为：,编码器,其中,r=,n-k,，则该,(,n,，,k,),系统循环码的编码电路如下图所示：,5.3.4,循环码,r,级线性移位寄存器的初始状态为全零，所有开关均向下连通；,在寄存器时钟的控制下进行,k,次移位，输出,M,(,x,),的系数,(,即信息,码,组,),，同时实现除法电路的功能；,编码器工作过程,5.3.4,循环码,所有开关向下连通，输入下一组信息重复上述过程。,实例分析,所有开关均倒向上方连通，在寄存器时钟的控制下再经过,r=,n-k,次移位，将监督元输出到信道；,本节前面给出的,(7,，,3),循环码生成多项式：,g(x,)=x,4,+x,2,+x+1,由其可得编码电路如下图所示：,5.3.4,循环码,假设,M=110,，编码器工作过程如下表所示,输入,移位寄存器状态,反馈,输出,R,1,R,2,R,3,R,4,f,0,0,0,0,0,0,0,m,2,m,1,m,0,1,1,0,1,1,1,1,0,0,1,0,1,0,1,0,1,1,1,1,1,0,a,6,a,5,a,4,信,息,元,0,0,0,0,0,0,0,0,1,0,0,0,0,1,0,0,0,0,1,0,0,1,0,1,0,1,0,1,a,3,a,2,a,1,a,0,监,督,元,5.3.4,循环码,现在检验上表编码结果，因为,M,=110,，所以,即所得的码字为,A,=1100101,。,5.3.4,循环码,系统循环码的每一个码字都能够被生成多项式,g(x,),整除：,检错译码原理,发送端发送的码字为,3,译码,接收的码字为,错误图样,伴随式,5.3.4,循环码,可以证明：,若,S,等于,0,判定传输无错，否则判定传输出错。,检错译码原理图：,5.3.4,循环码,寄存器置零，开关,S,向下连通；,在寄存器时钟的控制下经,n,次移位后将接收码字,B,输入，此时寄存器中存储的即伴随式,(,n,，,k,),循环码伴随式计算电路,其工作过程如下：,将开关向上打开，经,r=,n-k,次移位读出伴随式。,5.3.4,循环码,纠错译码原理,确定循环码的纠错能力,;,根据,模,g(x,),计算伴随式，若,S(x,),不为零则判定传输出错。,根据,模,g(x,),找到伴随式对应的错误图样,由,A(x,)=,B(x)+E(x,),纠错。,5.4,卷积码,本节内容提要：,卷积码是一类非线性有记忆编码，本节将简要介绍卷积码的编,译码原理。,5.4.1,卷积编码器,5.4.2,卷积码的解析描述,5.4.3,卷积码的图解描述,5.4.4,维特比译码原理,5.4.1,卷积编码器,卷积码通常记作,(,n,，,k,，,m,),，,其中,k,为一次移入编码器的比特数目，,n,为对应于,k,比特输入的编码输出，,m,为约束长度。,卷积码,定义卷积码的编码效率为,k/n,，,可以将其理解为同一时刻，编码器有,k,位比特信息输入，,有,n,位编码比特输出,卷积码有记忆的特性：,卷积编码器的输出不仅和当前输入的,k,比特信息有关，,而且还依赖于之前输入的,m,-1,组,k,比特信息。,5.4.1,卷积编码器,(,n,，,k,，,m,),卷积编码器结构,5.4.1,卷积编码器,可以发现上图中,mk,级寄存器中第一级是多余的，事实上只需要,m,(,k,-1),级即可，所以可以得到卷积码编码器的另一种形式,5.4.1,卷积编码器,(3,，,1,，,3),卷积码的两种等效编码器,实例分析,3,级编码器,2,级编码器,5.4.2,卷积码的解析描述,仍然以上图中的,(3,，,1,，,3),卷积码为例，,由其单位冲击响应可构造生成矩阵为：,生成矩阵法,其中未写出的元素为,0,。,和分组码不同，卷积码并不以块的形式出现，,即其码字可能无限长，故,5-68,式所示的矩阵称为半无限矩阵,此时卷积码可由,C=MG,得到，例如,M,=11101,时,5.4.2,卷积码的解析描述,卷积编码器也可以用,n,个生成多项式来描述，,分别对应,n,个输出支路。,生成多项式法,(3,，,1,，,3),卷积码编码器,上图所示的卷积编码器可以用以下所示的,3,个生成多项式描述,5.4.2,卷积码的解析描述,则对应的码多项式为,所以对应的码字是：,C=111 110 101 010 100 001 011,输入信息为,M,=11101,，对应的多项式为,则各支路码多项式分别为：,5.4.2,卷积码的解析描述,5.4.3,卷积码的图解描述,实例分析,以下图所示的,(2,，,1,，,3),卷积码器,假设初始状态为,a,，输入序列为,M,=110100,，,则有状态图很容易得到编码序列为,C,=100100011111,。,状态图法,5.4.3,卷积码的图解描述,树图法,输入为,110100,时，编码输出为,100100011111,，如图中虚线所示,5.4.3,卷积码的图解描述,网格图法,5.4.4,维特比译码原理,END,返回,结束,