资源描述：
《《纠错码学习大纲》.doc》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。
1、《纠错码学习大纲》陆以勤第三章线性分组码一、线性分组码l线性分组码[n,k,d]是方程HCT=0T的k维解空间,H是由Fq(q=pm,p为素数)中元素组成的秩为n-k的n-k´n矩阵。张成该码空间的一组基组成的k´n矩阵G称为[n,k,d]的生成矩阵.d可由两种方法求出(1)定理4:d=;(2)定理7:若H的任意r列线性无关,并存在r+1列线性相关,则d=r+1;反之,若d=r+1,则H的任意r列线性无关,而必存在有相关的r+1列.由此可知,只要找到一个秩为n-k的n-k´n矩阵H或k个线性无关的n维向量(由它们可构成G)就可以生成一个线性分组码[n,k]。关键是为使[n,k]有纠t个错误
2、的能力,必须要d³2t+1.因此,H必须满足任意2t列线性无关,并存在2t+1列线性相关.对于二元码,只要H任意两列不等并且不含全0的列,这个码至少可纠一个错.例如,H的列向量按1~2m-1的二进制排列,任意两列线性无关,而存在线性相关的3列,因此可得[2m-1,2m-1-m,3]的码(汉明码).l由H的标准形式H=[QIn-k]或相应的G的标准形式G=[Ik-QT]确定的线性分组码称为系统码,系统码保留了信息位并在后面加监督位.l若把H作为生成矩阵则生成[n,k,d]的对偶码[n,n–k,d’],G是它的监督矩阵.l由已知码[n,k]可对信息段和监督段进行简单的增删构造成新的码,从而使信
3、息段和监督段的长度适合不同的需要.这种构造过程的关键问题是新码最小距离的变化.这可从监督矩阵变换后列向量的相关性的变化来研究.例如,由H¢=可把一个偶检验位加到原码字的最后,使[n,k]扩展为[n+1,k].对于汉明码[2m-1,2m-1-m,3],由于d=3,H任两列线性无关同时存在线性相关的3列,而在H¢中,任三列线性无关(最后一位3个1相加不为0),但存在线性相关的4列(原在H中线性相关的3列加上H¢的最后一列),所以H¢确定了扩展汉明码[2m,2m-1-m,4].二、线性分组码的译码l伴随式译码R®S计算电路R.......S®E译码表.......R-E电路线性分组码的伴随式译码
4、电路由于线性分组码[n,k,d]是方程HCT=0T的解空间,任一码字C满足CTH=0.若C经过信道到达终端变为R=C+E.如没有发生错误(E=0),则RTH=0;如果发生错误即E¹0,这时有两种情况:1)EÎ[n,k,d],这时RÎ[n,k,d],也就是R变成了另外一个码字,RTH仍等于0;2)EÏ[n,k,d],这时RTH=CTH+ETH=ETH¹0,只与E有关.由此可见,如果码字间的距离足够大以至发生了错误也不会变成另一个码字,则可从S=RTH判断码字在传输中是否有错,错误的图样是什么.S称为伴随式.通过伴随式与错误的图样的一一对应关系来译码叫伴随式译码。l标准阵列译码由于Fq上线性码
5、C=[n,k]是n维矢量线性空间V的qk阶加法子群,故V可划分为qn/qk=qn-k个C的不同陪集(包括C).如果第一个陪集C+E2的陪集首E2取V-C中重量最小者,第二个陪集C+E3的陪集首E3取V-C-(C+E2)中重量最小者,依次类推可得C的各个陪集,由它们排列成译码的标准阵列.可证，标准阵列译码符合最小距离译码原则.群码C译为Ci以剩余矢量中重量最小者为陪集首S1=0C1=0C2......Ci........CqkS2E2C2+E2......Ci+E2......Cqk+E2陪集C+Em..............................................
6、..........................SmEmC2+Em......Ci+Em.....Cqk+Em.................................................................................Sqn-kEqn-kCqn-k+Em....Cqn-k+Em.......Cqn-k+Em伴随式错误图样标准阵列伴随式译码表l完备码由标准阵列可看出,Fq上线性码[n,k]能纠正qn-k个错误图样。而t个错误(包括无错和小于t)的图样共有(q-1)i个，所以2n-k³(q-1)i。满足2n-k=(q-1)i的线性码称为
7、完备码。完备码的纠错能力达到极限。特别地，汉明码[2m-1,2m-1-m,3]是能纠一个错的2元完备码(=1+2m-1=2m).戈莱(Golay)码[23,12,7]是目前唯一已知能纠多个错误的2元完备码.
