差错控制编码

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,第八章,差错控制编码,8.1,差错控制编码的基本概念,数字通信中，根据不同的目的，编码可分为,信源编码,和,信道编码,。,信源编码是为了提高数字通信的有效性，以及为了使模拟信号数字化而采取的编码。,信道编码是为了降低误码率，提高数字通信的可靠性而采取的编码。,数字信号在传输的过程中，加性噪声、码间串扰等都会产生误码。为了提高系统的抗干扰性能，可以加大发射功率，降低接收设备本身的噪声，以及合理选择调制、解调方法等。此外，还可以采用信道编码技术。,2024/9/13,2,差错控制编码的基本思想,：,在发送端根据要传输的数字序列（信息码元）按一定的规律加入多余码元，使原来不相关的数字序列变为相关，然后把这些多余码元和有关的信息码元一起传送，接收端根据信息码元与多余码元之间的相关规则进行检验，从而发现错误。这时，或者通过反馈信道要求对方重发有错的信息，以进行纠错；或者由接收端的译码器自动把错误纠正。,这些多余码元称为校验元或监督元。它的加入不改变信息本身，也就是说，它不传送新的信息，它的作用只是使信道译码器能够检测和纠正差错，从而控制系统差错概率，提高可靠性但这是以系统的有效性为代价的。,2024/9/13,3,8.1.1,差错控制方式,2024/9/13,4,前向纠错方式,前向纠错方式记作,FEC,（,Forword,Error Correction,）,发端编码器将数字信息按一定规则附加多余码元，组成有纠错能力的码,，发端发送能够纠正错误的码；,收端译码器按预先规定的规则译码；若发现错误，确定其出错位置并进行纠正。,优点：,单向传输，,只有正向信道；适合于只能提供单向信道的场合；一点发送多点接收的同播方式；译码延迟固定，适用于实时传输系统。,缺点：,编译码设备复杂，为了纠正较多的错误，需要附加的多余码元较多，因而传输效率较低。,2024/9/13,5,检错重发方式,又称自动请求重传方式，记作,ARQ,（,Automatic Repeat Request,）。,发端编码器将数字信息按一定规则附加多余码元，使之具有一定的检错能力，收端译码器按一定规则对数据码元组进行错误判决，并把判决结果形成应答信号，通过反馈信道回送到发端，发端根据收到的应答信号，把收端认为有错的那组数据码元再次重传，直到码元组无错为止。,优点：,只需要少量的多余码元就能获得极低的输出误码率，并且其成本和复杂性均比前向纠错低缺点。,缺点：,必须提供反向信道；不能进行同播（一点发多点收），收发端应有缓冲存储器和控制器；此外当信道干扰较大时，整个系统可能处在重传循环中，因而通信效率降低，信息传输连贯性差，不适于实时传输系统，,主要在计算机通信中应用。,常用的检错重发系统有三种，即停发等候重发、返回重发和选择重发。,2024/9/13,6,2024/9/13,7,混合纠错方式,混合纠错方式记作,HEC,（,Hybrid Error Correction,）,发端发送具有自动纠错同时又具有检错能力的码。收端收到码后，检查差错情况，如果错误在码的纠错能力范围以内，则自动纠错，如果超过了码的纠错能力但能检测出来，则经过反馈信道请求发端重发。,这种方式具有自动纠错和检错重发的优点，可达到较低的误码率，因此，近年来得到广泛应用,。,在实际通信系统中，选择那种差错控制方式，要视具体情况而定，可以根据信源的性质，信息传输的特点信道干扰的种类和对误码率的要求而适当选择差错控制方式。,2024/9/13,8,8.1.2,差错控制编码的分类,根据信息元和监督元的函数关系，可分为,线性码,和,非线性码,。如果函数关系是线性的，即满足一组线性方程式，则称为线性码，否则为非线性码。,根据上述关系涉及的范围，可分为,分组码,和,卷积码,。分组码的各码元仅与本组的信息元有关；卷积码中的码元不仅与本组的信息元有关，而且还与前面若干组的信息元有关。,根据码的用途，可分为,检错码,和,纠错码,。检错码以检错为目的，不一定能纠错；而纠错码以纠错为目的，一定能检错。,2024/9/13,9,8.1.3,几种简单的检错码,(1),奇偶监督码,设码字,A=,a,n,-1,a,n,-2,a,1,a,0,，,对偶监督码有：,a,n,-1,a,n,-2,a,1,a,0,= 0,奇监督码情况相似， 只是码组中“,1”,的数目为奇数， 即,满足条件：,a,n,-1,a,n,-2,a,1,a,0,= 1,而检错能力与偶监督码相同。,2024/9/13,10,奇偶监督码,编码方法：把信息码元分组，在每组信息码元,的后面附加一位监督码元，使得,码组中,1,的数目为奇数或偶数即可,编码规则：码组长度,n,；信息位,n-1,特点：是一种能发现奇数个差错的分组码；,n,较大，即编码码组较长时，编码效率,接近于,1,;,（,n-1,）,/n,信息码元比,码组码元,适用于检测随机的零星错码,加性白噪声造,成的,2024/9/13,11,8.1.3,几种简单的检错码,(2),二维奇偶监督码,(6,11),行列监督码,2024/9/13,12,二维奇偶监督码,编码方法：把码元排成方阵，按行列进行奇偶校验,分别附加一位监督码元,特点：不仅可检测每行（每列）中奇数个错误，而且,可通过水平监督和垂直监督来确定错码的位置,纠正仅一行（一列）出现的奇数个错误,通过水平监督和垂直监督的关系可以发现单行中出现,的偶数个错误；但不能发现构成矩形的,4,个错误码元,适用于突发差错,由突发干扰（突发脉冲，如：,闪电，电火花等）在短时间内错码成串出现，在某,一行中出现多个错码,2024/9/13,13,8.1.3,几种简单的检错码,(3),重复码,在每位信息码元之后，用简单重复多次的方法编码。,例：重复两次时，用,111,传输,1,码，用,000,传输,0,码,编码方法：每位信息码元简单重复多次；,收端 译码采用多数表决法；,例：重复,2,次,特点：纠正,1,个错，检出,2,个错,2024/9/13,14,8.1.3,几种简单的检错码,(4),恒比码,码字中,1,的数目与,0,的数目保持恒定比例的码称为恒比码,。,这种码在检测时，只要计算接收码元中,1,的数目是否正确，,就知道有无错误。,2024/9/13,15,恒比码,例：,5,中取,3,恒比码,用于电报电码,每个码组长度为,5,，共有,2,5,=32,种不同的码组，,其中有,3,个,1,的码组为可用码组，共有,10,种,表示,10,个阿拉伯数字，用它拼成汉字（每,4,阿拉,伯数字组成,1,个汉字电码）；其余的,22,个为禁用,码组。,特点：简单；除了,1,错为,0,与,0,错为,1,成对出现（对换,性）差错不能检测外，其它任何奇数个或偶数,个错码都可以被检测出来。,只适用于传输种类较少且有固定代码的字符，而不适用于表示由信源来的二进制随机，数字序列。,2024/9/13,16,8.1.3,几种简单的检错码,(4),ISBN,国际统一图书编号,例,ISBN 0,471,02977,7,2024/9/13,17,8.1.4,检错和纠错的基本原理,如用,三位二进制编码来代表八个字母,000 A100E,001 B101F,010C110G,011D111H,不管哪一位发生错误，都会使传输字母错误,如用三位字母传四个字母,000 A011B101 C110D,发生一位错误，准用码字将变成禁用码字，接收端就能知道出错，但是不能纠错,。,如果进一步将许用码组限制为两种,000 A 111 B,检错和纠错能力是用信息量的冗余度来换取的。,2024/9/13,18,检错和纠错的基本原理,检错和纠错能力是用信息量的冗余度换取的,与码组之间的差别有关；不同的编码方法和形式，检错和纠错能力不同。,例：,n = 3,，共有,8,种组合，都用于传输消息，在传输过程中若发生一个误码，则一种码组就会错误地变成另一种码组，但接收端却不能发现错误，因为任何一个码组都是许用码组。,2024/9/13,19,在差错控制编码中，定义码组中非零码元的数目为码字的,汉明,(Hamming),重量,， 简称,码重,。例如，码字,10110,，码重,w,=3,。,定义两个等长码组之间相应位取值不同的数目为这两个码组的,汉明,(Hamming),距离,， 简称,码距,。例如,11000,与,10011,之间的距离,d=3,。,码组集中任意两个码字之间距离的最小值称为,码的最小距离,，用,d,min,表示。最小码距是码的一个重要参数， 它是衡量码检错、纠错能力的依据。,2024/9/13,20,最小码距与检错纠错能力的关系,码组内的距离反映了码组之间的差别，最小距离越大，说明两个码组间的最小差别越大，或者说其中一个码组错为另一个码组的可能性就越小，那么其检错和纠错能力也就越强，因此可以说最小码距是衡量一种纠错编码的检错，纠错能力大小的标准。,2024/9/13,21,码的最小距离直接关系着码的检错和纠错能力；任一,(,n,k,),分组码，若要在码字内,:,(1),检测,e,个随机错误，则要求码的最小距离,d,min,e,+1;,(2),纠正,t,个随机错误， 则要求码的最小距离,d,min,2,t,+1;,(3),纠正,t,个同时检测,e,(,t,),个随机错误，则要求码的最小距离,d,min,t,+,e,+1,。,t,1,e,A,B,2024/9/13,22,用差错控制编码提高通信系统的可靠性， 是,以降低有效性为代价换来的,。我们定义编码效率,R,来衡量有效性,:,R,c,=,k/n,其中,k,是信息元的个数，,n,为码长。,对纠错码的基本要求是,:,检错和纠错能力尽量强； 编码效率尽量高；编码规律尽量简单,。实际中要根据具体指标要求，保证有一定纠、检错能力和编码效率，并且易于实现。,编码效率,2024/9/13,23,8.2,线性分组码,线性分组码的构成,将信息序列划分为等长,(k,位,),的序列段,共有,2,k,个不同的序列段，在每一信息,段之后，附加,m,位监督元，构成长度,n = k + m,的分组码,(n,，,k),监督元与信息码元为线性关系,2024/9/13,24,例,信息元长度,k = 3,共有,2,k,= 8,个不同的信息组,每组信息组加,4,个监督元，构成一个长度为,7,的,(7,，,3),线性分组码。,设：,每组信息元为,C,1,C,2,C,3,监督元为,C,4,C,5,C,6,C,7,根据下列线性方程组求监督元,C,4,= C,1,+ C,3,C,5,= C,1,+ C,2,+ C,3,C,6,= C,1,+ C,2,C,7,= C,2,+ C,3,2024/9/13,25,例,(7,，,3),码有,8,个信息组，信息组按上方程组求得每个,信息组的,4,个监督元，得到,(7,，,3),码的所有,8,个码字,信息组 码元,0 0 0 0 0 0 0 0 0 0,0 0 1 0 0 1 1 1 0 1,0 1 0 0 1 0 0 1 1 1,0 1 1 0 1 1 1 0 1 0,1 0 0 1 0 0 1 1 1 0,1 0 1 1 0 1 0 0 1 1,1 1 0 1 1 0 1 0 0 1,1 1 1 1 1 1 0 1 0 0,重要特性，线性码有封闭性,2024/9/13,26,8.2,线性分组码,设分组码由,n,位码组构成，记为,c,1,，,c,2,，,，,c,n,，信息码组由,k,位码组成，记为,d,1,，,d,2,，,，,d,k,。则该分组码记为（,n,，,k,）码。,码组和信息码组可用行矩阵,C,和,D,表示,若为线性分组码，,C,中的,n,个元素都是由,D,中的,k,个元素经线性组合形成的。可用一联立方程表示为,2024/9/13,27,将码组,C,写成矩阵形式,矩阵,G,称为生成矩阵，它是一个,kn,的矩阵,2024/9/13,28,生成矩阵,G,2024/9/13,29,生成矩阵,G,I,k,单位矩阵，,k,行,k,列,(k x k,阶,),P,矩阵，,k,行,m,列,(k x m,阶,),编码前,k,位，编码后有,n,位，,2,n, 2,k,；,选择,P,矩阵，可得到有较强检错纠错能力，实现,方法尽可能简单，编码效率又高的线性分组码,由于线性码具有封闭性，故任何二个码组之间的距离必须与某一个码组中“,1,”,的个数相等，而码组中非零码元的数目“,1,”,的个数为码组的重量（码重）所以线性码任意二个码字之间的距离必须等于码中某一个码字的重量,线性码最小码距正好等于非零码的最小码重,估算线性码的差错控制能力：,求最小码距,最小码重,2024/9/13,30,例,已知（,6,，,3,）码的生成距阵，求：编码码组,2024/9/13,31,监督矩阵,H,校验矩阵或监督矩阵,H,：,m x n,阶,P,T,:,m,行,k,列,k + m = n,列,2024/9/13,32,伴随式（校正子）,S,设发送码组,C=,c,n,-1,c,n,-2,c,1,c,0,，,在传输过程中可能 发生误码。接收码组,R,=,r,n,-1,r,n,-2,r,1,r,0,，,则收发码组之差定,义为错误图样,E,，,也称为误差矢量， 即,E,=RC,=,e,n,-1,e,n,-2,e,1,e,0,，,且,当,r,i,=,c,i,当,r,i,c,i,令,S,=,RH,T,，,称为,伴随式,或,校正子,S = RH,T,= CH,T,EH,T,=,EH,T,S,只与错误图形有关，与发送的码组,C,无关,H,T,：,n x m,阶；,E,：,1x n,阶；,S,：,1x m,阶；,S = s,1,s,2,s,m,解得误差矢量,E,，,求得纠错后的码组,C = R,E,2024/9/13,33,检错与纠错,检错：当码组出现错误,S,为非零矢量,纠错：,S = RH,T,= CH,T,EH,T,=,EH,T,S,与,E,之间有着确定的线性关系,由,H,矩阵,确定（也就是与,G,（,P,）,矩阵有关）,S=s,1,s,2,s,m,共有,2,m,种不同的形式，除全,0,外，可代表,2,m,-1,种有错误的图形,信息码组有,2,k,个错误图形，有多种不同的形式可能有,2,k,种解答；为了选择正确的结果，要使用最大似然比准则，选择与,R,最相似的,C,（与,R,距离最小的码组,E,是,1,码最小的矢量）,。,2024/9/13,34,例：（,6,，,3,）码,2024/9/13,35,S,与,E,对照表,E,S,0 0 0 0 0 0 0 0 0,1 0 0 0 0 0 1 0 1,0 1 0 0 0 0 0 1 1,0 0 1 0 0 0 1 1 0,0 0 0 1 0 0 1 0 0,0 0 0 0 1 0 0 1 0,0 0 0 0 0 1 0 0 1,1 0 0 0 1 0 1 1 1,（,6,，,3,）,码具有纠,1,位错的能力,发生,1,个错误的情况：,S,是,H,T,的第,i,行，说明,R,中第,i,位,产生了错误，可以把它纠正,发生,2,个错误的情况：,除,S=111,对应第,1,，,5,位有错,其它的双错不能得到纠正,例：,接收码组,R111011,2024/9/13,36,查表法译码器的原理,S = RH,T,= CH,T,EH,T,=,EH,T,算出伴随式,S,与最小码重的差错,矢量,E,的对照表，提供译码使用,2024/9/13,37,汉明码,按上述方法构造的能纠正单个错误的线性分组码称为,汉明码。,对于线性分组码，为了指示所有单错位置和无错的情况，必须满足不等式,汉明码具有以下特点：,汉明码的编码效率,2024/9/13,38,汉明界,如果码组有纠,t,个差错的能力，则应能指出无错、单错到,t,个差错所有可能的情况，校验位数,m,应满足不等式：,汉明界，是纠正,t,个差错的一个必要条件,2024/9/13,39,8.3,循环码,特点,线性分组码,循环性,任一许用码字经过循环移位后，得到的码组仍为一个许用码组,如 是循环码的一许用码组,则 也是一许用码组,移位,i,次得到 也是许用码组,2024/9/13,40,8.3.1,循环码的特点及表达,码多项式表示,以此类推，码组,C,移位,i,次，相应的码多项式,c,(i),(x),是,x,i,c(x),除以,（,x,n,+1),后的余式。,在模,（,x,n,+1),意义下，若,c(x,),是码多项式，则,x,i,c(x),都是码多项式。,2024/9/13,41,循环码的编码过程,一个,k,位的信息码组 可用信息多项式表示,假设码组多项式可表示为,如果,(,n,+1),是,g(,),的倍式,C,（,1,）,(,)=,d(,)g(,)+ aC,1,g(,),=,d(,)+ aC,1,g(,)= d,1,(,)g(,),d,1,(,),对应某个信息码组,2024/9/13,42,生成多项式,g(,),(,n,+1),是,g(,),的倍式，且,g(,),为,n-k,次多项式，所以对,(,n,+1),进行因式分解，便可得到相应的,g(,),。,对,(,n,+1),进行因式分解可由计算机完成，有表格给出。,由信息多项式求解码多项式,C(,) =,d(,),g(,),n-1,次,k-1,次,n-k,次,2024/9/13,43,例,(7,，,4) n=7,k=4,m=,n-k,=3,g(,),应为,(,7,+ 1,),的,3,次因式,+ 1 =,(,+ 1,) (,+, + 1,) (,+,+ 1,),g,1,() =,(,+, + 1,),g,2,() =,(,+,+ 1,),D = 1010 ,d(,) =,(,+,),C,1,() = d()g,1,() =,(,+,) (,+, + 1,),= ,+,+,+,C,1,= 1001110,C,2,() = d()g,2,() =,(,+,) (,+,+ 1,),= ,+,+,+,C,= 1110010,注：,1.,不同的生成多项式得到不同的码组,2.,由此编码法得到的不是系统码（前,4,位不是,D=1010,）,2024/9/13,44,非系统码系统码,系统码用多项式表示为,k-1,次,m-1,次,由式（,8,31,）码组多项式表示为,综合两式有,2024/9/13,45,例,(7,，,4) n=7,k=4,m=,n-k,=3,g(,),应为,(,7,+ 1,),的,3,次因式,+ 1 =,(,+ 1,) (,+, + 1,) (,+,+ 1,),g,1,() =,(,+, + 1,),g,2,() =,(,+,+ 1,),D = 1010 ,d(,) =,(,+,),-4,d(,) =,(,+,),=,+,4,R,1,() =,-4,d(,)/ g,1,() =,(,+ 1,),C,1,() =,-4,d(,) +,R,1,() =,+,4,+, + 1,C,1,= 1010011,-4,d(,) =,(,+,),=,+,4,R,2,() = ,-4,d(,)/ g,2,() = 1,C,2,() =,-4,d(,) +,R,2,() = ,+,4,+ 1,C,2,= 1010001,注：,不同的生成多项式得到不同的系统循环码,2024/9/13,46,8.3.2,循环码的编码和译码,原理：按系统码的生成方式,以,(7,4),码为例,2024/9/13,47,循环码的译码器,发送码组多项式,c(x,),是生成多项式,g(x,),的倍式。如果经信道传输后发生错误，接收码组多项式,r(x,),不再是,g(x,),的倍式,接收码组表示为,由,s(,),确定,e(,),同样使用最,大似然比准则，对应最小码重,的差错多项式，列出译码表，,由,s(,),对照译码表确定,e(,),译码三步,伴随式,S,的计算,由,S,得到错误图样,纠正,2024/9/13,48,