信息论第九章.ppt

,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,第,9,章 信道的纠错编码,9.1,差错控制的基本形式,9.2,纠错码分类与基本概念,9.3,线性分组码的数学基础,9.4,线性分组码,9.5,循环码,9.6 BCH,码,9.7,卷积码,前向纠错,(FEC),：,发送端的信道编码器将信息码组编成具有一定纠错能力的码。接收端信道译码器对接收码字进行译码，若传输中产生的差错数目在码的纠错能力之内时，译码器对差错进行定位并加以纠正。,自动请求重发,(ARQ),：,用于检测的纠错码在译码器输出端只给出当前码字传输是否可能出错的指示，当有错时按某种协议通过一个反向信道请求发送端重传已发送的码字全部或部分。,9.1,差错控制的基本方式,混合纠错,(HEC),：,是,FEC,与,ARQ,方式的结合。发端发送同时具有自动纠错和检测能力的码组，收端收到码组后，检查差错情况，如果差错在码的纠错能力以内，则自动进行纠正。如果信道干扰很严重，错误很多，超过了码的纠错能力，但能检测出来，则经反馈信道请求发端重发这组数据。,9.1,差错控制的基本方式,分组码,：编码的规则仅局限于本码组之内，本码组的监督元仅和本码组的信息元相关。,信息码组由,k,个二进制码元组成，共有,2,k,个不同的信息码组；附加,n,k,个码元，每个监督元取值与该信息码组的,k,个码元有关；编码器输出长度,n,；这,2,k,个码字的集合称为,(,n,k,),分组码；,卷积码,：本码组的监督元不仅和本码组的信息元相关，而且还与本码组相邻的前,n,1,个码组的信息元相关,。,9.2,纠错码分类,是否可用线性方程组来表示,线性码,：编码规则可以用线性方程表示；,非线性码,：编码规则不能用线性方程表示；,按码字的结构分,系统码,：,前,k,个码元与信息码组一致；,非系统码,：没有系统码的特性。,按纠正差错的类型可分为,纠正随机错误的码,和,纠正突发错误的码,；,按码字中每个码元的取值可分为,二进制码,和,多进制码,。,9.2,纠错码分类,汉明距离,/,距离：在,(,n,k,),线性码中，两个码字,U,、,V,之间对应码元位上符号取值不同的个数，称为码字,U,、,V,之间的汉明距离。,线性分组码的一个码字对应于,n,维线性空间中的一点，码字间的距离即为空间中两,对应点的距离。,码距与纠检错能力,汉明重量,/,码字重量,/,W,：码字中非,0,码元符号的个数，称为该码字的汉明重量。,在二元线性码中，码字重量就是码字中含“,1”,的个数。,最小距离与最小重量的关系,：线性分组码的最小距离等于它的非零码字的最小重量。,一般地说，线性码的最小距离越大，意味着任意码字间的差别越大，则码的检、纠错能力越强。,最小距离与检、纠错能力,最小距离与纠错能力,：,(,n,k,),线性码能纠,t,个错误的充要条件是码的最小距离为,几何意义,：,最小距离与检错能力,：,(,n,k,),线性码能够发现,l,个错误的充要条件是码的最小距离为,d,min=,l,+1,或,l,=,d,min,1,线性空间的概念,定理：（,n,k,）线性分组码是,n,维,n,重线性空间的一个,k,维线性子空间。,线性空间相关概念：,（,1,）,n,维线性空间：由,n,个线性无关的矢量组成基底，它们的全部线性组合所构成的空间。若矢量长度也为,n,，则称,n,维,n,重线性空间,S,。,（,2,）线性子空间：从,n,个基底中选出一组,k,（,k ,出错越少的情况，发生概率越大，,E,的重量越轻，所以该译码方法实际上体现了最小距离译码准则，即最大似然译码。,标准阵列译码表,上述的概率译码，如每接收一个码,R,就要解一次线性方程，那就太麻烦了。好在伴随式,S,的数目是有限的,2,n-k,个，如果,n-k,不太大，我们可以预先把不同,S,下的方程组解出来，把各种情况下的最大概率译码输出列成一个码表。这样，在实时译码时就不必再去解方程，而只要象查字典那样查一下码表就可以了。这样构造的表格叫做,标准阵列译码表。,表中所列码字是接收到的码字,R,。,将没有任何差错时的收码,R,放在第一行，收码等于发码,R=C(C,C,i,i,=0,1,2,k,-1,),差错图案为全零,E,0,=(,0,00,),，伴随式为全零,S,0,=(,0,00,),。由于有,2,k,个码字，码表有,2,k,列。,在第,2,到第,n,+1,的,n,行中差错图案的所有重量为,1(,共,n,个,),。,如果,(1+,n,)2,n-k,，再在下面行写出全部带有,2,个差错的图案,(,共 个,),。,如果总行数,(1+,n,+),仍然小于,2,n-k,，再列出带有,3,个差错的图案，以此类推，直到放满,2,n-k,行，每行一个,E,j,对应一个不同的伴随式,S,j,。这样，表的行数,2,n-k,正好等于伴随式的数目。,标准阵列译码表的构成,S,0,E,0,S,1,E,1,S,j,E,j,E,0,+C,0,=0+0=0,E,0,+C,1,=C,1,E,0,+C,i,=C,i,E,1,+C,0,=E,1,E,1,+,C,i,E,j,+C,0,=E,j,E,j,+,C,1,E,j,+,C,i,标准阵列译码表,E,1,+C,1,陪集和子集,译码表中有,2,n-k,行，每行是一个,陪集,，每陪集的第一个元素,(,位于第一列,),叫,陪集首,。同一陪集（同一行）中的所有元素对应共同的一个伴随式。第一行陪集的陪集首是全零伴随式,S,0,所对应的全零差错图案,E,0,(,无差错,),，而第,j,行陪集的陪集首是伴随式,S,j,所对应的重量最小的差错图案,E,j,(C,0,=0,R,j,=E,j,),。,定理,：在标准阵列中，一个陪集的所有,2,k,个,n,重有相同的伴随式，不同的陪集伴随式互不相同。,译码表中有,2,k,列，每列是一个,子集,，每子集的第一个元素,(,位于第一行,),叫,子集头,。同一子集（同一列）中的所有元素对应同一个码字，第一列子集的子集头是全零码字,C,0,，而第,i,列子集的子集头是码字,C,i,(E,0,=0,R,i,=C,i,),。,例,一个,(5,2),系统线性码的生成矩阵是,G=,设收码,R=(10101),，构造标准阵列译码表，译出发码的估值,解：,(1),构造标准阵列译码表。分别以信息组,m=(00),、,(01),、,(10),、,(11),及已知的,G,求得,4,个许用码字为,C,1,=(00000),、,C,2,=(10111),、,C,3,=(01101),、,C,4,=(11010),。,求出校验矩阵：,H=P,T,I,3,=,列出方程组：,S=(,s,1,s,2,s3,)=,(,e,1,e,2,e,5),伴随式有,2,n,-,k,2,3,8,种组合，差错图案中代表无差错的有一种，代表一个差错的图案有 种，已有,6,种。,代表两个差错的图案有 种。只需挑选其中的两个，挑选方法可有若干种，不是唯一的。先将,E,j,=(00000),、,(10000),、,(01000),、,(00100),、,(00010),、,(00001),代入上面的线性方程组，解得对应的,S,j,分别是,(000),、,(111),、,(101),、,(100),、,(010),、,(001),。剩下的伴随式中，,(011),所对应的差错图案是,2,k,个即,(00011),、,(10100),、,(01110),、,(11001),其中,(00011),和,(10100),并列重量最轻，任选其中一个如,(00011),。同样可得伴随式,(110),所对应的最轻差错图案之一是,(00110),。,译码表的构成,S,0,=000,E,0,+C,0,=00000,C,1,=10111,C,2,=01101,C,3,=11010,S,1,=111,E,1,=10000,00111,11101,01010,S,2,=101,E,2,=01000,11111,00101,10010,S,3,=100,E,3,=00100,10011,01001,11110,S,4,=010,E,4,=00010,10101,01111,11000,S,5,=001,E,5,=00001,10110,01100,11011,S,6,=011,E,6,=00011,10100,01110,11001,S,7,=110,E,7,=00110,10001,01011,11100,标准阵列译码表,将接收码,R,10101,译码,可选以下三种方法之一译码：,直接搜索码表，查得,(10101),所在列的子集头是,(10111),，因此译码输出取为,(10111),。,先求伴随式,RHT=(10101),HT=(010)=S,4,，确定,S,4,所在行，再沿着行对码表作一维搜索找到,(10101),最后顺着所在列向上找出码字,(10111),。,先求出伴随式,RHT=(010)=S,4,并确定,S,4,所对应的陪集首（差错图案）,E,4,=(00010),，再将陪集首与收码相加得到码字,C=R+E,4,=(10101)+(00010)=(10111),。,上述三种方法由上而下，查表的时间下降而所需计算量增大，实际使用时可针对不同情况选用。,对上例作进一步分析，还可以看到，该,(5,2),码的,d,min,=3,纠错能力是,t,=INT(3-1)/2=1,。因此，译码阵列中只有前,6,行具有唯一性、可靠性，真正体现了最大似然译码准则，而第,7,、,8,行的差错图案,(00011),和,(00110),中包含两个“,1”,，已超出了,t,=1,的纠错能力，译码已不可靠。比如，当收码,R,(10100),时，根据码表译出的码字是,(10111),，与收码,R,的汉明距离是,2,，然而收码,R,与全零码字,(00000),的汉明距离也是,2,，为什么不能译成,(00000),呢？事实上，码表的第,7,、,8,行本身就不是唯一的。注意在码表计算过程中，伴随式,(011),所对应的,4,个差错图案中有两个并列重量最轻，如果当时选的不是,(00011),而是,(10100),，那么码表第,7,行就不是现在这样了。,对本例 题的,分析,任何一个二元,(,n,k,),线性分组码都有,2,n-k,个伴随式，假如该码的纠错能力是,t,，则对于任何一个重量小于等于,t,的差错图案，都应有一个伴随式与之对应，也就是说，伴随式的数目满足条件,上式称作,汉明限,，任何一个纠,t,码都应满足上述条件。,完备码,(Perfect code),完备码,某二元,(,n,k,),线性分组码能使等式,成立，即该码的伴随式数目不多不少恰好和不大于,t,个差错的图案数目相等，相当于在标准译码阵列中能将所有重量不大于,t,的差错图案选作陪集首，而没有一个陪集首的重量大于,t,，这时的校验位得到最充分的利用。这样的二元,(,n,k,),线性分组码称为,完备码,。,汉明码,(Hamming Code),汉明码不是指一个码，而是代表一类码。,汉明码的纠错能力,t,=1,，既有二进制的，也有非二进制的。二进制时，汉明码码长,n,和信息位,k,服从以下规律：,(,n,k,)=(2,m,-1,2,m,-1-,m,),其中,m,=,n-k,，是正整数。,当,m,3,、,4,、,5,、,6,、,7,、,8,时，有汉明码,(7,4),、,(15,11),、,(31,26),、,(63,57),、,(127,120),、,(255,247),。,汉明码是完备码，因为它满足上述等式。,汉明码校验矩阵的构成,汉明码的校验矩阵,H,具有特殊的性质，能使构造方法简化。一个,(,n,k,),码的校验矩阵有,n,k,行和,n,列，二进制时,n-k,个码元所能组成的列矢量总数是,2,n-k,-1,恰好和校验矩阵的列数,n,=2,m,-1,相等。只要排列所有列，通过列置换将矩阵,H,转换成系统形式，就可以进一步得到相应的生成矩阵,G,。,例,构造一个,m,=3,的二元,(7,，,4),汉明码。,解：先利用汉明码的特性构造一个,(7,，,4),汉明码的校验矩阵,H,，再通过列置换将它变为系统形式：,0 0 0 1 1 1 1,列置换,1 1 1 0 1 0 0,H=0 1 1 0 0 1 1,0 1 1 1 0 1 0 =P,T,I,3,1 0 1 0 1 0 1 1 1 0 1 0 0 1,再得生成矩阵,G,为,1 0 0 0 1 0 1,G=I,4,P=0 1 0 0 1 1 1,0 0 1 0 1 1 0,0 0 0 1 0 1 1,1,、循环码的多项式描述,2,、循环码的生成多项式,3,、系统循环码,4,、多项式运算电路,5,、循环码的编码电路,6,、循环码的译码,7,、循环汉明码,8,、缩短循环码,第,4,节循环码,(1),循环码的性质,循环码是线性分组码的一个重要子类；,由于循环码具有,优良的代数结构,，使得可用简单的反馈移位寄存器实现编码和伴随式计算，并可使用多种简单而有效的译码方法；,循环码是研究最,深入,、理论最,成熟,、应用最,广泛,的一类线性分组码。,第,4,节循环码,(2),循环码的定义,循环码,：,如果,(,n,k,),线性分组码的任意码矢,C,=(,C,n,1,C,n,2,C,0,),的,i,次循环移位，所得矢量,C,(,i,),=(,C,n,1,i,C,n,2,i,C,0,C,n,1,C,n,i,),仍是一个码矢，则称此线性码为,(,n,k,),循环码,。,第,4,节循环码,(3),码多项式,码多项式,：为了运算的方便，将码矢的各分量作为,多项式的系数，把码矢表示成多项式，称为码多项式。其一般表示式为,C,(,x,)=,C,n,1,x,n,1,+,C,n,2,x,n,2,+,C,0,),码多项式,i,次循环移位的表示方法,记码多项式,C,(,x,),的一次左移循环为,C,(1),(,x,),，,i,次左移循环为,C,(,i,),(,x,),第,4,节循环码,码多项式的模,(,x,n,+1),运算,0,和,1,两个元素模,2,运算下构成域,。,第,4,节循环码,码矢,C,循环,i,次所得码矢的码多项式,C,(,x,),乘以,x,，再除以,(,x,n,+1),，得,第,4,节循环码,上式表明,：,码矢循环一次的码多项式,C,(1),(,x,),是原码多项式,C,(,x,),乘以,x,除以,(,x,n,+1),的余式。写作,因此，,C,(,x,),的,i,次循环移位,C,(,i,),(,x,),是,C,(,x,),乘以,x,i,除以,(,x,n,+1),的余式，即,结论,：循环码的码矢的,i,次循环移位等效于将码多项式乘,x,i,后再模,(,x,n,+1),。,第,4,节循环码,(4),举例：,(7,3),循环码,可由任一个码矢，比如,(0011101),经过循环移位，得到其它,6,个非,0,码矢；,也可由相应的码多项式,(,x,4,+,x,3,+,x,2,+1),，乘以,x,i,(,i,=1,2,6),，再模,(,x,7,+1),运算得到其它,6,个非,0,码多项式。移位过程和相应的多项式运算如表,6.3.1,所示。,第,4,节循环码,第,4,节循环码,循环码的生成矩阵,在,(,n,k,),循环码的,2,k,个码字中，取前,(,k,1),位皆为,0,的码字,g,(,x,),（其次数,r,=,n,k,），再经,(,k,1),次循环移位，共得到,k,个码字,:,g,(,x,),xg,(,x,),x,k,1,g,(,x,),这,k,个码字显然是相互独立的，可作为码生成矩阵的,k,行，于是得到,循环码的生成矩阵,G,(,x,),第,4,节循环码,(2),循环码的生成多项式,码的生成矩阵一旦确定，码就确定了；,这就说明：,(,n,k,),循环码可由它的一个,(,n,k,),次码多项式,g,(,x,),来确定；,所以说,g,(,x,),生成了,(,n,k,),循环码，因此,称,g,(,x,),为码的生成多项式,。,第,4,节循环码,(3),生成多项式,和,码多项式,的关系,定理,：,在,(,n,k,),循环码中，生成多项式,g,(,x,),是惟一的,(,n,k,),次码多项式，且次数是最低的,。,定理,：在,(,n,k,),循环码中，每个码多项式,C,(,x,),都是,g,(,x,),的倍式；而每个为,g,(,x,),倍式且次数小于或等于,(,n,1),的多项式，必是一个码多项式,。,第,4,节循环码,定理,6.3.3,(,定理,6.3.2,的逆定理,),：,在一个,(,n,k,),线性码中，如果全部码多项式都是最低次的,(,n,k,),次码多项式的倍式，则此线性码为一个,(,n,k,),循环码,。,第,4,节循环码,码字循环关系图,单纯,循环码的,码字循环图：,(7,3),循环码,第,4,节循环码,推广循环码的,码字循环图：,(6,3),循环码,第,4,节循环码,(4),如何寻找一个合适的生成多项式,由下面式子可知：循环码的多项式等于信息多项式乘以生成多项式。,这说明,：对一个循环码只要生成多项式一旦确定，码就确定了，编码问题就解决了。,所以,：,作一循环码的关键，就在于寻找一个适当的生成多项式,。,定理,：,(,n,k,),循环码的生成多项式,g,(,x,),是,(,x,n,+1),的因式，即,x,n,+1=,h,(,x,),g,(,x,),。,定理,：,若,g,(,x,),是一个,(,n,k,),次 多项式，且为,(,x,n,+1),的因式，则,g,(,x,),生成一个,(,n,k,),循环码,。,结论,：,当求作一个,(,n,k,),循环码时，只要分解多项式,(,x,n,+1),，从中取出,(,n,k,),次因式作生成多项式即可,。,第,4,节循环码,举例,：求,(7,3),循环码的生成多项式。,解,：,分解多项式,x,n,+1,，取其,4,次因式作生成多项式,x,7,+1=(,x,+1)(,x,3,+,x,2,+1)(,x,3,+,x,+1),可将一次和任一个三次因式的乘积作为生成多项式，因而可取,g,1,(,x,)=(,x,+1)(,x,3,+,x,2,+1)=,x,4,+,x,2,+,x,+1,或,g,2,(,x,)=(,x,+1)(,x,3,+,x,+1)=,x,4,+,x,3,+,x,2,+1,第,4,节循环码,