信道的纠错编码课件

,信道的纠错编码,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,信道的纠错编码,*,第9章 信道的纠错编码,信道编码的概念,线性分组码,循环码,1,信道的纠错编码,信道编码的纠错原理,信道编码的目的：提高系统的可靠性,实现方法：,增加冗余度,信道编码的纠错原理,根据一定的规律在待发送的信息码元中人为的加入一些冗余码元，,这些,冗余,码元与信息码元之间以某种确定的规则相互关联（约束）。,在接收端按照既定的规则检验信息码元与监督码元之间的关系。如果传输过程出错，则信息码元与监督码元之间的关系将受到破坏，从而可以发现错误乃至纠正错误。,纠错码,2,信道的纠错编码,纠错码的分类,按功能分：,检错码：仅能检测误码。,纠错码：可纠正误码。,按信息码元与监督码元之间的检验关系分：,线性码：满足线性关系。,非线性码：不存在线性关系。,按信息码元在编码后是否保持原形式：,系统码：信息码元与监督码元在分组内有确定位置，,编码后的信息码元保持位置不变。,非系统码：信息位打乱，与编码前位置不同。,3,信道的纠错编码,纠错码的分类,按信息码元与监督码元之间的约束方式不同分：,分组码,：将信息码元分为,k,位一组，每组相互独立，再按编码规则变成,n,位码（,nk),，其中,n-k,=r,位为监督码元，我们称之为（,n,k,),分组码。,本码组的监督码元仅和本码组的信息码元相关。,卷积码,：本码组的监督码元不仅和本码组的信息码元相关，而且与前面码组的信息码元有关。,4,信道的纠错编码,错误图样, 当系统无干扰时 R=C, 当系统有干扰时 R=C+E,其中，E称为信道的错误图样，,E=(e,0,e,1,e,n-1,)；e,i, 0,1；当e,i,=1，则第i位上有错；反之，无错。,例： C = 0 0 1 0 1 1 0 1,E = 0 1 0 0 1 0 0 1,R = 0,1,1 0,0,1 0,0,由信道的对称性可知 p(0/1)=p(1/0)=p(e=1)=p,反之，若已知R ，E 则可求出C，这就是纠错码的原理，如： E = 0 1 0 0 1 0 0 1,R = 0,1,1 0,0,1 0,0,C = 0 0 1 0 1 1 0 1,5,信道的纠错编码,检错与纠错的原理, 编码效率,设：信息码长度为k，经信道编码后长度为n，则我们定义编码效率R为：,R=k/n, 几种简单的检纠错码,奇,/,偶校验码,检错码,重复码,纠错码,6,信道的纠错编码,检错与纠错方式和能力, 检纠错方式,FEC,（前向纠错）,纠错,ARQ,（自动请求重发）,检错, 几个概念,汉明距离,/,距离,：在线性码中，两个码字,U,、,V,之间对应码元位上符号取值不同的个数，称为码字,U,、,V,之间的汉明距离。,例如,：,(7,3),码的两个码字,U,=0011101,V,=0100111,，它们之间第,2,、,3,、,4,和,6,位不同。因此，码字,U,和,V,的距离为,4,。,线性分组码的一个码字对应于,n,维线性空间中的一点，码字间的距离即为空间中两,对应点的距离。,7,信道的纠错编码,检错与纠错方式和能力,最小码距,：在码集合中，任两个码字间的距离为最小时，该码距即为码集合的最小码距。,码字的重量,：码字中非,0,码元符号的个数，称为该码字,的重量，又称为汉明重量。,码的最小重量,：线性分组码,C,I,中，,非,0,码字,重量最小,值，叫做码,C,I,的最小重量：,W,min,=,min,W,(,V,),V,C,I,V,0,最小码距与最小重量的关系,：线性分组码的最小码距,等于它的最小重量。,8,信道的纠错编码,检错与纠错能力-1,最小码距与纠错能力的关系：,定理：,(,n,k,),线性码能纠,t,个错误的充要条件是码的最小距离为,d,min,=2,t,+ 1,或,t,= (,d,min,1)/2,V,9,信道的纠错编码,检错与纠错能力-2,最小码距与检错能力的关系：,定理：,(,n,k,),线性码能够发现,e,个错误的充要条件是码的最小距离为,d,min,=,e,+ 1,或,e,=,d,min,1,V,e,10,信道的纠错编码,检错与纠错能力-3,最小码距与检、纠错能力的关系：,定理：,(,n,k,),线性码能纠,t,个错误，并能发现,e,个错误,(,e,t,),的充要条件是码的最小距离为,d,min,=,t,+,e,+1,或,t,+,e,=,d,min,1,e,V,V,11,信道的纠错编码,线 性 分 组 码,一、线性分组码的描述,线性分组码是同时具有分组特性和线性特性的纠错码。,定义,：一个,（n,k）,线性分组码C是称为码字c的n维向量的集合。,式中： 为消息矢量， 是一个k行n列的秩为,k（nk),的矩,阵，我们称它为线性码的,生成矩阵,。,第一种编码方法,12,信道的纠错编码,线 性 分 组 码,例：,（4,3）偶校验码是一个（4,3）线性分组码，其,生成矩阵为,求消息码010，110所对应的线性码。,解：,13,信道的纠错编码,线 性 分 组 码,将消息码直接代入有：,思考,：此码是否为系统码？,14,信道的纠错编码,线 性 分 组 码,二、线性分组码的性质及定理,当消息码为零向量,0,0,，所得的码字为零码字00。,线性分组码的封闭性：线性分组码中任意两个码字之和仍然是该码的码字。,G,中每一行,g,i,=(,g,in-,1,g,in-2,g,i0,),都是一个码字；,对每一个信息组,m,，由矩阵,G,都可以求得 (,n,k,) 线性码对应的码字。信息码组长,k,位，有 2,k,个不同的信息码组，则有 2,k,个码字与它们一一对应。,在由 (,n,k,) 线性码构成的线性空间,V,n,的,k,维子空间中，一定存在,k,个,线性独立,的码字：,g,0,g,1,g,k-1,，码,C,i,中其它任何码字,C,都可以表为这,k,个码字的一种,线性组合,，即,15,信道的纠错编码,线 性 分 组 码,16,信道的纠错编码,线 性 分 组 码,三、线性分组码的监督阵, 线性分组码的监督阵,编码就是给已知信息码组按预定规则添加监督码元，以构成码字。,在,k,个信息码元之后附加,r,(,r,=,n,k,),个监督码元，使每个监督码元是其中某些信息码元的模,2,和。,举例：,k,=3,r,=4,，构成,(7,3),线性分组码。设码字为,(,C,6,C,5,C,4,C,3,C,2,C,1,C,0,),C,6,C,5,C,4,为信息元，,C,3,C,2,C,1,C,0,为监督元，每个码元取“,0”,或“,1”,监督元可按下面方程组计算,17,信道的纠错编码,线 性 分 组 码,一致监督方程/一致校验方程,：确定信息元得到监督元规则的一组方程称为监督方程/校验方程。由于,所有码字都按同一规则确定,，又称为一致监督方程/一致校验方程。,由于一致监督方程是线性的，即监督元和信息元之间是线性运算关系，所以由线性监督方程所确定的分组码是线性分组码。,第二种编码方法,18,信道的纠错编码,线 性 分 组 码,信息码组,(,101,),，即,C,6=,1,C,5=,0,C,4=,1,代入监督方程得：,C,3=,0,C,2=,0,C,1=,1,C,0=,1,由信息码组,(,101,),编出的码字为,(,101,0011,),。其它,7,个码字如下。,表,9.1,(7,3),分组码编码表,信息组,对应码字,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,19,信道的纠错编码,线 性 分 组 码,为了运算方便，将监督方程写成矩阵形式，得,:,20,信道的纠错编码,线 性 分 组 码,推广到一般情况：对,(,n,k,),线性分组码，每个码字中的,r,(,r,=,n,k,),个监督元与信息元之间的关系可由下面的线性方程组确定,令上式的系数矩阵为,H,，码字行阵列为,C,同样有,我们称,H,为一致监督阵,/,监督阵,。,21,信道的纠错编码,线 性 分 组 码,一致监督阵H,22,信道的纠错编码,线 性 分 组 码, 监督阵与生成阵的关系,由于生成矩阵,G,的每一行都是一个码字，所以,G,的每行都满足,H,r,n,C,T,n,1,=,0,T,r,1,，则有,H,r,n,G,T,n,k,=,0,T,r,k,或,G,k,n,H,T,n,r,=,0,kr,线性分组码的监督矩阵与生成矩阵正交,。,23,信道的纠错编码,四、(n,k)线性码的对偶码,对偶码,：对一个(,n,k,)线性码,C,I,，由于,H,r,n,G,T,n,k,=,0,T,r,k,，,如果以,G,作监督矩阵，而以,H,作生成矩阵，可构造另一个码,C,Id,，码,C,Id,是一个,(,n,n,k,),线性码，称码,C,Id,为原码的,对偶码,。,例如,：,(7,4)线性码的对偶码是(7,3)码：,(7,3)码的监督矩阵,H,(7,3),是(7,4)码生成矩阵,G,(7,4),线 性 分 组 码,24,信道的纠错编码,线 性 分 组 码,五、生成阵和监督阵的标准形式, 生成阵的标准形式,通过,行,初等变换，将,G,化为,左边,k,列,是单位子阵的标,准形式，我们称之为,生成阵的标准形式,25,信道的纠错编码,线 性 分 组 码, 线性系统分组码,用生成阵的标准形式产生的码集合 称为,线性系统分组码。,设： 则有：,则有：,依次排在码的前面,监督元依次排在码的后部,26,信道的纠错编码,线 性 分 组 码,线性系统分组码,：用标准生成矩阵,G,k,n,编成的码字，前面,k,位为信息数字，后面,r,=,n,k,位为校验数字，这种,信息数字在前,校验数字在后,的线性分组码称为线性系统分组码。,信 息 码,监 督 码,C,n-1,C,n-k,C,n-k-1,C,0,27,信道的纠错编码,线 性 分 组 码,例：(7,4) 线性码的生成矩阵为,1,1,0,1,0,0,0,0,1,1,0,1,0,0,1,1,1,0,0,1,0,1,0,1,0,0,0,1,7,4,=,*,G,),(,1,1,0,1,0,0,0,0,1,1,0,1,0,0,1,1,1,0,0,1,0,1,0,1,0,0,0,1,0,1,0,1,),1010,(,7,4,4,1,7,1,4,1,=,=,=,=,*,*,*,*,G,m,C,m,，则,若,28,信道的纠错编码,线 性 分 组 码, 监督阵的标准形式,同样对监督阵的各行进,行,初等变换，将,右边r列,化为单位阵即可得到,监督阵的标准形式,。,29,信道的纠错编码,线 性 分 组 码, 监督阵与生成阵的转换关系,由于系统码的监督阵与生成阵同样彼此正交，所以有：,所以，上述等式提供了监督阵与生成阵的互求。即，,30,信道的纠错编码,线 性 分 组 码,例：,31,信道的纠错编码,线 性 分 组 码,例：二元(7,3)码，若生成矩阵已知，求生成矩阵和监督矩阵的标准形式。,解：,得：,行和行相加放入第行,行和, 行相加放入第行,32,信道的纠错编码,线 性 分 组 码,六、线性码的最小距离与监督阵的关系,定理,1,设H为(n,k),线性码的一致监督阵，,若,H,中任意S列线性无关，而存在S+1列线性相关，则码的最小距离为S+1。,即， d,min,=S+1,定理,2,若码的最小距离为S+1，则该码的,监督阵有,任意S列线性无关，而必存在线性相关的S+1列。,推理,在二元线性码的监督阵,H,中，如果任一列都不为全零，且任二列都不相等，则该码能纠一个错。,例：,33,信道的纠错编码,线 性 分 组 码 的 译 码,一、译码器的任务,设：发送的码字,C,=(,c,n,-1,，,c,n,-2,， ，,c,1,，,c,0,)， 通过有扰信道传输， 信道产生的错误图样,E,=(,e,n,-1,e,n,-2,， ,e,1,e,0,)。接收端译码器收到的,n,重码,R,=(,r,n,-1,r,n,-2,r,1,r,0,)， 其中,R,=,C,+E,。,译码器的,任务,：,根据编码规则和信道特性，对接收码字,R,作出判决，此判决过程又称为,译码,。,译码器按任务可分为：检错译码和纠错译码。,检错译码：输出接收码字，及差错标志。,纠错译码：输出纠正的码字（在纠错能力之内）,输出接收码字及出错标志。（超出纠错能力）,34,信道的纠错编码,线 性 分 组 码 的 译 码,二、检纠错译码原理, 伴随式和错误检测,用监督矩阵编码，当然也用监督矩阵译码。当收到一个接收码字,R,后，可用监督矩阵,H,来检验,R,是否满足监督方程，即,HR,T,0,T,是否成立。若关系式成立，则认为,R,是一个码字，否则判为码字在传输中发生了错误。因此，,HR,T,的值是否为0,是检验码字出错与否的依据。,把,S,RH,T,或,S,T,HR,T,，称为接收码字,R,的,伴随式,(或监督子，或校验子)。, 不可检测的错误图样,与码矢相同的错误图样是不可检测的错误图样。,它在数量上与,非,零码矢一样多2,k,-1个。（含零码为2,k,个),35,信道的纠错编码,线 性 分 组 码 的 译 码,根据上述原理，我们可知：, 伴随式检错原理,设：,发送码字,C,(,c,n,1,c,n,2,c,0,)，信道的错误图样为,E,(,e,n,1,e,n,2,e,0,) ，,式中：若,e,i,0，表示第i位无错，若,e,i,1，则表示第i位有错，,i,n,1，,n,2，0。那么，接收码字,R,=(,r,n,1,r,n,2,r,0,),=,C,E,=(,c,n,1,+,e,n,1,，,c,n,2,+,e,n,2,，,c,0,+,e,0,),检错译码基本原理,判为无错（,可能有错,）,一定出错,36,信道的纠错编码,线 性 分 组 码 的 译 码,将接收字用监督矩阵进行检验，即求接收码字的伴随式：,其中H阵用,列,来表示，即，,所以：,S,T,HR,T,H,(,C,E,),T,HC,T,HE,T,由于,HC,T,0,T,，则有：,S,T,HE,T,所以，,37,信道的纠错编码,线 性 分 组 码 的 译 码,由上面分析得到如下结论：,(1)伴随式仅与错误图样有关，而与发送的具体码字无关，即伴随式仅由错误图样决定。,(2)伴随式是错误的判别式：若,S,0，则判没有出错，（或存在一个不可检测的错误，接收字是一个码字），若,S,0，则判有错。,(3)不同的错误图样具有不同的伴随式，它们是一一对应的，,二元码伴随式是,H,阵中与错误码元对应列之和。,38,信道的纠错编码,线 性 分 组 码 的 译 码,例：,设(7,3)线性分组码的校验矩阵为,试确定以下三种情况时的译码器的输出,（1）接收码字,R,=(1010011)，,（2）接收码字,R,=(1110011)，,（3）接收码字,R,=(0011011)，,39,信道的纠错编码,线 性 分 组 码 的 译 码,解：对于有：,传输过程中,没有,误码，,40,信道的纠错编码,线 性 分 组 码 的 译 码,对于 有：,，第2位出错，,41,信道的纠错编码,线 性 分 组 码 的 译 码,对于 有：,与 中的任一列都不相同，,不能确定到底是哪两位出错，不能正确译码。,42,信道的纠错编码,线 性 分 组 码 的 译 码,定理：可纠t个错误的二元线性分组码与校验元个数的关系：,三、采用伴随式纠错译码的方法, 查表法, 标准阵列法,几个概念,许用码组：在,(,n,k,),线性码中，与,2,k,个消息码对应的码字称为许用码组。,禁用码组：在,(,n,k,),线性码中，除了消息码外的,2,n,-2,k,个码字。,标准阵列的构造,43,信道的纠错编码,线 性 分 组 码 的 译 码,先将,2,k,个码字排成一行，作为,标准阵列,的第一行，并将全,0,码字,C,0,=(000),放在第一行的最左边的位置上；,然后在剩下的,(2,n,2,k,),个,n,重码中选取一个,重量最轻,的,n,重,E,1,放在全,0,码字,C,0,下面，再将,E,1,分别和各码字相加，放在对应码字下面构成阵列第二行,;,在第二次剩下的,n,重码中，选取重量最轻的,n,重,E,2,，放在,E,1,下面，并将,E,2,分别加到第一行各码字上，得到第三行；,直到全部,n,重码字用完为止。得到,(,n,k,),线性码的标准阵列。,（,注意：,作为错误图样的,E,i,不能与表内的其它码字相同！）,44,信道的纠错编码,线 性 分 组 码 的 译 码,例：已知(6,3)线性分组码的生成阵为,求它的标准阵列。,解：由生成阵可得该码许用码组的全部码字：,消息码,线性分组码,消息码,线性分组码,000,000000,100,100110,001,001101,101,101011,010,010011,110,110101,011,011110,111,111000,45,信道的纠错编码,线 性 分 组 码 的 译 码,则它的标准阵列为：,000000,001101,010011,011110,100110,101011,110101,111000,000001,001100,010010,011111,100111,101010,110100,111001,000010,000100,001000,010000,100000,100001,001111,001001,000101,011101,101101,101100,010001,010111,011011,000011,110011,110010,011100,011010,010110,001110,111110,111111,100100,100010,101110,110110,000110,000111,101001,101111,100011,111011,010101,001010,110111,110001,111101,100101,001011,010100,111010,111100,110000,101000,011000,011001,46,信道的纠错编码,线 性 分 组 码 的 译 码,有关标准阵列的几个概念：,(n,，,k,),线性码的标准阵列有,2,k,列,(,和码矢数相等,),，,2,n,/2,k,2,n,k,行，且任何两列和两行都没有相同的元素，即列和行都不相交。,标准阵列的每一行叫做码的一个陪集，每个陪集的第一个元素叫做,陪集首,，,信道干扰的错误图样是陪集首,。,2,n,k,个陪集首称为可纠正的错误图样。,这,2,n,k,个可纠的错误图样，包括,0,码矢在内，也就是说，把,无错的情况也看成一个可纠的错误图样。,定理,：,(,n,k,),线性码可纠,2,n-k,个错误图样。,定理：,在标准阵列中，一个陪集的所有,2,k,个,n,重码字有相同的伴随式，不同陪集的伴随式互不相同。,译码原理：,收到的,n,重,R,落在某一列中， 则译码器就译成相应于该列最上面的码字。,47,信道的纠错编码,标准阵列译码=最小距离译码法=最佳译码法,陪集首是可纠正的错误图样，为了使译码错误概率最小，应选取出现概率最大的错误图样作陪集首；,重量较轻的错误图样出现概率较大，所以在构造标准阵列时是选取重量最轻的,n,重作陪集首；,这样，当重量较轻的错误图样为陪集首时（可纠的错误图样），接收矢量与原发送码矢间的距离（等于陪集首）最小；,因此，选择重量最轻的元素作陪集首，按标准阵列译码就是按最小距离译码；,所以标准阵列译码法也是最佳译码法。,线 性 分 组 码 的 译 码,48,信道的纠错编码,线 性 分 组 码 的 译 码,补充习题：, 已知(7,4)线性分组码的生成阵为：,求：该码的全部码字，监督,阵，若接收到码字为,1001100时，译码器,的输出。, 已知(8,4)系统线性码的监督方程为：,式中,m=(m,3,m,2,m,1,m,0,),，,为信息,矢量，,c,3,c,2,c,1,c,0,，,为编码监督,字。,求：该码的生成阵，监督阵并,证明,d,min,=4。,49,信道的纠错编码,