《线性分组码的例子.ppt》由会员分享,可在线阅读,更多相关《线性分组码的例子.ppt(18页珍藏版)》请在三一办公上搜索。
1、线性分组码的例子,2009年秋,内容提要,汉明码RM码格雷码交织码,汉明码,对任意整数m2,存在满足如下条件的汉明码码长n=2m-1信息符号数k=2m-m-1校验符号数n-k=m纠错能力t=1(dmin=3)该码的奇偶校验阵H由所有非零的m维列向量构成,前m列可写成单位阵。H的任何两列都不同,且非零,故任意两列相加不为0,故最小距离至少为3;而任意两列之和必定为H的某个列向量,因为H包括所有非零m维列向量,故有三个列向量之和为0,所以最小距离为3,汉明码的标准阵,可将所有重量为t=1的n=2m-1个向量作为陪集首,共2m-1个,又因为n-k=m,即该码有2m个陪集,因此0向量和所有重量为1的m
2、维向量首构成了标准阵的所有陪集首故汉明码只能纠正t=1个错误,可用查表译码完备码:若标准阵的陪集首全都是重量小于等于t的向量(错误模式),即可纠正错误模式的重量都小于等于t。汉明码和(23,12)格雷码是完备码,完备码很少,汉明码的改造,删除H的若干列,如重量为偶数的列,得到新的H,其最小距离为4,称为“缩短的汉明码”缩短汉明码保证校验位数目不变,减少了信息位的数目,降低了码率纠错能力没变,陪集首依然没变,全是重量为1的错误模式,检错能力?译码:看校正子的情况:0,重量为奇数(可纠正1个错,查表),重量为偶数(不可纠正错误)漏检率很低,符合漏检率的理论上界,故是好的差错检测码,检测两个错,纠正
3、一个错的码 SEC-DED,首先构造码长n=2m-1,最小距离为3的汉明码从此汉明码的H阵中删除一些列,得到H0满足:每列有奇数个11的个数尽可能小每一行中1的个数都应该相等或极可能接近均值第一个条件保证最小距离至少为4,二、三个条件为了实现简单,Hsiao提出了一种构造H0的算法并找到了一些最优的SEC-DED码,Reed-Muller,RM码,r阶RM(r,m)码,纠正多个错误,Muller提出,Reed译码码长:n=2m维数(信息序列的长度):最小距离:dmin=2m-r若令m=5,r=2,那么n=32,k(2,5)=16,dmin=8,即存在一个(32,16)RM码,RM码的构造,设v
4、0是全1向量,1=i=m,由此定义了v0,v1,vm定义向量运算“”,ab=(a1b1,a2b2,anbn),简记为ab集合Grm(r,m)=v0,v1,vm,v1v2,v1v3,vm-1vm,vm-r+1vm共有k(r,m)个元素,是(2m,k)RM码的生成向量,即可张成整个码空间的基。将每个元素看成矩阵的一行,就得到生成矩阵。集合Grm(r-1,m)是Grm(r,m)的真子集,是r-1阶RM码的生成矩阵。,RM码,Grm(r,m)中所有向量都是偶数重量m-r-1阶RM码(m-r-1,m)的对偶码是r阶RM码(r,m)零阶RM码RM(0,m)是重复码而(m-1)阶RM码是单奇偶校验码,k=2
5、m-1,RM码的译码,例子说明,此码是最小距离为4的(16,11)线性码,假设信息序列:观察上述11个生成向量,注意到除了v1v2,其他生成向量每连续4个分量一组求和都是0,可推出:,4个彼此独立的方程求a12的值,可用于校验,若接受序列中只有一个错误,则4个值中只错一个,采用大多数原则可纠错,这就是大数逻辑判决准则译码,RM码的译码,aij被正确译码后,考虑传输没出错,则有利用基向量的特点,发现两个连续分量的和的关系,构建ai的独立判定方程,再用大数逻辑判决译码类似上面步骤,最后译码a0,共三步(r+1步),(24,12)格雷码,汉明码外唯一一个非平凡二进制完备码(23,12)格雷码,最小距
6、离7(23,12)格雷码通过增加一个总的奇偶校验位,构成(24,12)码,最小距离为8,但非完备码设其生成矩阵G=P I12,P 如右,且满足:P沿对角线对称,且PP=I H=I12,P,自偶码,格雷码的译码,设错误模式为e=(x,y),校正子s=eHT=(x,y)HT=(x,y)I PT=x+yPT=x+yP,可得到y=(x+s)P对任何可纠正错误模式e,满足w(e)4,有四种可能:(1)w(y)=0,w(x)=3,(2)w(y)=1,w(x)=2,(3)w(y)=2,w(x)=1,(4)w(y)=3,w(x)=0,令ej分别表示这四种可能的错误模式,ej=(x,y),其中w(y)=j,0=
7、j4,令ui表示仅第i个分量为1的12维向量,pi=uiP表示P的第i行若e=e0,则有s=x,w(s)=w(x)=3,e=(x,y)=(s,0)若e=e1,令y=ui,则有s=x+pi,即x=s+pi,e=(x,y)=(s+pi,ui)若e=e2或e3,w(x)=0,则有e=(x,y)=(0,sP)若e=e2且w(x)=1,令x=ui,则y=(x+s)P=(ui+s)P=pi+sP,故e=(x,y)=(ui,pi+sP),(24,12)格雷码的译码,计算接受序列r的校正子s若w(s)=3,则令e=(s,0),跳到步骤8若某个pi,有w(s+pi)=2,令e=(s+pi,ui),跳到步骤8计算
8、sP若w(sP)=2 or 3,则令e=(0,sP)并转步骤8若某个pi,w(sP+pi)=2,则令e=(ui,sP+pi),跳到步骤8若校正子s与可纠错模式e不相同,则停止译码或要求重传,译码错误令译出的码字v=r+e,充分利用了码和错误模式的结构特点设计算法,乘积码,乘积码是短的分量码构造高效长码的一种技术设有两个线性码C1(n1,k1)和C2(n2,k2),可构造一个(n1n2,k1k2)的线性码,其码字是一个n1n2的矩阵,此矩阵的每一行是C1的码字,每一列是C2的码字,这是一个二维码,是C1和C2的直积如右图所示乘积码 的码矩阵,乘积码,构造过程:对待编码的k1k2信息序列 置于右边
9、矩阵的右上角信息位的每一行采用C1中的码字进行编码,得到行校验位,即得到k2xn1矩阵对每一列采用C2中的码字进行编码,得到列校验位和校验位的校验位乘积码的最小距离dmin=d1d2乘积码的码率较低,交织码,给定一个线性码C(n,k),可以构造一个()线性码,交织码,interleaved code交织方法:取C的 个码字排成 行的矩阵形式,然后按照逐列的方式传输该矩阵,称为交织深度或交织度,交织码和码C具有相同的dmin交织码简单说就是按列的方式传输码字当且仅当上述矩阵的每一行的错误模式都是可纠正错误模式时,错误可纠正,分组交织码,设有个 线性分组码Ci(n,ki),从这些码中,各取一个码字做行,构成一矩阵按列传输矩阵这 个码的交织构成了一个()交织码,记为 用于纠正聚集突发错误,