现代信息理论编码与技术chapter6课件.ppt

1、第六章 循环码的译码陆以勤2005年5月一、循环码译码的原理n线性分组码的译码：标准阵列译码，伴随式译码译码电路复杂 rs计算电路 se 译码表 r-e电路.rc一、循环码译码的原理-线性分组码中求伴随式的电路例1：7,4,3 循环汉明码，g(x)=x3+x+1,H=111010001110101101001s=r HT=(r6 r5 r4 r3 r2 r1 r0)Tr6+r5+r4+r2r5+r4+r3+r1r6+r5+r3+r0=T=（s2 s1 s0)111010001110101101001一、循环码译码的原理-利用循环码的特殊性简化电路ns rHTH=-PT In-k=-(r1(x)

2、T-(r2(x)T-(rk(x)T In-k 其中，ri(x)-xn-i(mod g(x)(i=1,2,.,k)。I 1.Hn121Tknknnnxxxxmod g(x)s rHT r (mod g(x)s(x)r(x)(c(x)+e(x)e(x)(mod g(x)定理1：由g(x)生成的循环码，r(x)的伴随式s(x)满足：s(x)r(x)e(x)(mod g(x)因此，求S(x)可用除以g(x)的电路实现。这样可把n级寄存器降为n-k级。一、循环码译码的原理-求循环码的伴随式电路例1：7,4,3 循环汉明码，g(x)=x3+x+1,H=111010001110101101001直接从H求s

3、利用除以g(x)电路求s(x)一、循环码译码的原理-求循环码的伴随式电路系统码的译码通常含有编码电路.mk-1mk-2m0cn-1=mk-1cn-2=mk-2cn-k=m0cn-k-1cn-k-2.c0求监督位.求监督位rn-1rn-2rn-krn-1rn-krn-2.rn-k-1r0rn-k-1r0r n-k-1r 0r n-k-2相等？再编一次码送过来的监督位在接收端重新生成的监督位一、循环码译码的原理-求循环码的伴随式电路定理2（定理6.1.1）：设s(x)是r(x)的伴随式，令f(x)xr(x)(mod xn-1),则f(x)的伴随式s1(x)xs(x)(mod g(x)。证明（课本证

4、明不好）：r(x)=rn-1xn-1+rn-2xn-2+.+r1x +r0 xr(x)=rn-1xn +rn-2xn-1+.+r1x2+r0 x f(x)=rn-2xn-1+rn-3xn-2+.+r1x2+r0 x+rn-1 =-rn-1xn +xr(x)+rn-1 =-rn-1(xn-1)+xr(x)=-rn-1h(x)g(x)+x(a(x)g(x)+s(x)=-rn-1h(x)g(x)+x a(x)g(x)+xs(x)=(-rn-1h(x)+x a(x)g(x)+xs(x)s1(x)f(x)xs(x)(mod g(x)。一、循环码译码的原理-求循环码的伴随式电路定理2（定理6.1.1）：设

5、s(x)是r(x)的伴随式，令f(x)xr(x)(mod xn-1),则f(x)的伴随式s1(x)xs(x)(mod g(x)。因此，若对r(x)循环移位，所对应的伴随式相当于在除以g(x)电路中无输入右移一位。推论1（推论6.1.1）：设s(x)是r(x)的伴随式，令rj(x)xjr(x)(mod xn-1)(j=0,1,n-1),则ri(x)的伴随式sj(x)xjs(x)(mod g(x)。a(x)Fqx:rj(x)a(x)r(x)(mod xn-1)的伴随式sj(x)a(x)s(x)(mod g(x)。二、循环码的译码电路-梅吉特译码法（只纠一个错）计算s(x)电路(除以g(x)s(x)

6、e(x)(判别最高位是否有错）r(x)缓冲.r(x)c(x)+r(x)=rn-1xn-1+rn-2xn-2+r1x+r0 x(rn-1+1)xn-1+rn-2xn-2+r1x+r0)=x(r(x)+xn-1)xr(x)+1(mod xn-1-1)除以g(x)s(x)xs(x)+1如果错误发生在最高位，如果错误发生在最高位，由于接收字不是码字，所以伴随式不为由于接收字不是码字，所以伴随式不为0，可以通过其伴，可以通过其伴随式与纠错后（是一个码字）的关系将其校正。随式与纠错后（是一个码字）的关系将其校正。如果错误不发生在最高位，如果错误不发生在最高位，而是发生在次高位，通过将其循环移位就可以将错误

7、图而是发生在次高位，通过将其循环移位就可以将错误图样移到最高位，而且伴随式可通过刚求出的伴随式通过移位的方法求出。样移到最高位，而且伴随式可通过刚求出的伴随式通过移位的方法求出。rn-1有错，纠正相当于s(x)移位后加1二、循环码的译码电路-梅吉特译码法（系统码）系统码只纠信息位的错二、循环码的译码电路-梅吉特译码法（只纠一个错）例1：7,4,3 循环汉明码，g(x)=x3+x+1,H=111010001110101101001二、循环码的译码电路-梅吉特译码法（系统码）P195页开始，门1开，门2关。移位4次后，门1关，使4级缓冲器停止移位，g(x)除法电路再移位3次可求出s(x)。此时门2

8、开，把上边g(x)除法电路中的伴随式送到下面的伴随式计算电路中，随即关闭门2，且上边g(x)除法电路立即清0。门1再次打开，4级缓冲器一边送出第1组的信息，一边接收第2组r(x)的前k位。与此同时，上边的伴随式电路计算第2组的r(x)的伴随式，而下边的伴随式计算电路，对第一组r(x)的信息元进行纠错。（注意，图6-2（A）的虚线是缩短循环码，见P197）三、扩展汉明码的译码0110ss0/s1/s20 10 1t 3,不能纠错t=1，可以纠错t2，不能纠错无错四、缩短循环码的译码n缓存：k-k-inr(x)先移位i次五、捕错译码-原理1.原理如果确知错误集中在检验位，则去掉后面的检验位即可。s

9、(x)r(x)e(x)eI(x)+ep(x)ep(x)mod g(x)由于s(x)n-k,ep(x)n-k,g(x)=n-k所以s(x)=e(x)=ep(x)伴随式等于错误图样。111最严重的情况，t个错误均匀分布，相隔n/tn信息位k要使t个错误集中在校验位，则要kn/t定理3：纠t个错误的GF(q)上的n,k循环码，捕错译码过程（即循环移位）中已把t个错误集中在最低n-k位以内的充要条件是w(si(x)3 且 w(s(x)-sIi(x)2嵩忠雄译码法嵩忠雄译码法(图图6-8，p203页）。页）。六、大数逻辑译码（一）原理sn-k-1=en-1hn-k-1,n-1+en-2hn-k-1,n-

10、2+e0hn-k-1,0sn-k-2=en-1hn-k-2,n-1+en-2hn-k-2,n-2+e0hn-k-2,0sj =en-1hj,n-1+en-2hj,n-2+e0hi,0s0 =en-1h0,n-1+en-2h0,n-2+e0h0,00,00,20,12,02,22,11,01,21,10210210,02,01,00,22,21,20,12,11,1.),.,(HH),.,(.HhhhhhhhhheeeersssshhhhhhhhhknknnnknnknnnknnknnnTTknknnnknnknnknknnknnkn六、大数逻辑译码-原理对错误图样进行监督，变换H为H使新的s的

11、sn-k-1,sn-k-1,s0对对e的某一位都作监督，而对其它位只监督一次。定义定义1（定义（定义6.3.1)若对H的行进行线性组合变换为H0,使H0的每行某一特定位n-i都为1，而其它位只在其中一行为1，则称H为正交于n-i位的正交一致校验矩阵，n-i称为正交码元位。sn-k-1=en-1hn-k-1,n-1+en-2hn-k-1,n-2+e0hn-k-1,0sn-k-2=en-1hn-k-2,n-1+en-2hn-k-2,n-2+e0hn-k-2,0sj =en-1hj,n-1+en-2hj,n-2+e0hi,0s0 =en-1h0,n-1+en-2h0,n-2+e0h0,00,02,0

12、1,00,22,21,20,12,11,1.Hhhhhhhhhhnnknnknnknknnknnkn六、大数逻辑译码-原理例：7，3，4码，H=101|1000111|0100110|0010011|0001相加相加H0=101|1000110|0010100|0101s =(s 2,s 1,s 0)=(e6,e5,e4,e3,e2,e1,e0)101|1000110|0010100|0101s 2=s3 =e6 +e4+e3s 1=s1 =e6+e5 +e1 s 0=s2+s0 =e6 +e2 +e0若若e6=1,ei=0,i=0,5,则则s 0=s 1=s 2=1;若若e6=0,ei=1,

13、ei=0,i,j=0,5,且且 i j，则则s 0，s 1，s 2只有只有1个为个为1;若若e6=1,ei=1,ei=0,i,j=0,5,且且 i j，则则s 0，s 1，s 2有有2个为个为1，1个为个为0;若若e6=0,ei=ei=1,ek=0,i,j,k=0,5,且且 i,j,k互不相等互不相等，则则s 0，s 1，s 2最最多只有多只有2个为个为1，1个为个为0。t=1t=2六、大数逻辑译码-原理若若e6=1,ei=0,i=0,5,则则s 0=s 1=s 2=1;若若e6=0,ei=1,ei=0,i,j=0,5,且且 i j，则则s 0，s 1，s 2只有只有1个为个为1;若若e6=1

14、,ei=1,ei=0,i,j=0,5,且且 i j，则则s 0，s 1，s 2有有2个为个为1，1个为个为0;若若e6=0,ei=ei=1,ek=0,i,j,k=0,5,且且 i,j,k互不相等互不相等，则则s 0，s 1，s 2最多最多只有只有2个为个为1，1个为个为0。若若e6=1,且且t=1,则则s 0，s 1，s 2有有2个或个或2个以上为个以上为1；若若e6 1,且且t=1,则则s 0，s 1，s 2有小于有小于2个为个为1。根据根据s 0，s 1，s 2中为中为1的个数决定的个数决定e6 是否有错，因为是循环码，可以循环至是否有错，因为是循环码，可以循环至下一位（判断下一位（判断e

15、5,e4,e3,e2,e1,e0 是否有错）。是否有错）。这叫这叫一步大数逻辑译码一步大数逻辑译码。定理定理4（定理（定理6.3.1)一个循环码若能建立一个循环码若能建立J个正交一致校验和式，则该码能纠个正交一致校验和式，则该码能纠正正t J/2个错误，其中个错误，其中x表示取表示取x的整数部分。的整数部分。六、大数逻辑译码-原理定理定理4（定理（定理6.3.1)一个循环码若能建立一个循环码若能建立J个正交一致校验和式，则该码能纠正个正交一致校验和式，则该码能纠正t J/2个错误，其中个错误，其中x表示取表示取x的整数部分。的整数部分。sJ-1=en-1+sJ-2=en-1+s0 =en-1+

16、en-1=1,最多只有J/2-1个si为0，大部分si仍为仍为1en-1=0,最多只有J/2个si为1根据根据s 0，s 1,s J中为中为1的数目是否多于一半对正交位纠错。的数目是否多于一半对正交位纠错。一步大数逻辑可译码不多。一步大数逻辑可译码不多。t(n-1)/2(dev-1)dev:对偶码的距离，要小对偶码的距离，要小六、大数逻辑译码-二步大数逻辑译码分两步，第一步先确定错误发生在某些码元位，第二步再从这些码元位中确定是哪一个具体的位。定义定义2 对H的行进行线性变换为H0,H0的伴随式为（s J-1,s J-2,s 0）。若某一码元集合ci1,ci2,cil 的线性组合 ai1 ci

17、1+ai2 ci2+ailcil (aij 0,j=1,l)在s J-1,s J-2,s 0中出现，而其余码元位置集合至多在其中某一s j(0 j J-1)出现1次，则说s J-1,s J-2,s 0在集合ci1,ci2,cil 上正交，称s J-1,s J-2,s 0为该集合的正交一致校验和式。六、大数逻辑译码-二步大数逻辑译码100111001001110011101H7，4，3循环汉明码第第1步：确定错误发生在步：确定错误发生在e6,e5,e4上上s 11=s2 =（e6+e4）+e3+e2s 10=s1 =（e6+e4）+e5+e1s 21=s1=（e6+e5）+e4+e1s 20=s

18、2+s0=（e6+e5）+e2+e0确定错误是否发生在e6,e4中中确定错误是否发生在e6,e5中中第第2步：确定错误发生在步：确定错误发生在e6上上s 31 =e6+e4s 30 =e6+e5确定错误是否发生在e6 上上六、大数逻辑译码-大数逻辑译码器（二）大数逻辑译码器1.I类大数逻辑译码器由s(x)r(x)(mod g(x)求s(x),一步大数逻辑译码器六、大数逻辑译码-大数逻辑译码器s 2=s3 =e6 +e4+e3s 1=s1 =e6+e5 +e1 s 0=s2+s0 =e6 +e2 +e0例：7，3，4码g(x)=x4+x3+x2+1但大数门但大数门2可检可检2个错个错六、大数逻辑

19、译码-大数逻辑译码器二步大数逻辑译码器（7,4,3)循环汉明码，二步大数逻辑译码，P211页图6-11六、大数逻辑译码-大数逻辑译码器2.II类大数逻辑译码器由r(x)和H求s(x)s(x)=r(x)H T六、大数逻辑译码-大数逻辑可译码的构造（三）大数逻辑可译码的构造1.极长码TknknTThhheeHrHs021s=(sn-k-1 sn-k-2 s0)sn-k-1=ehn-k-1sn-k-2=ehn-k-2.s0 =eh0内积sn-k-1=an-k-1sn-k-1+an-k-2sn-k-2+a0s0=e(an-k-1hn-k-1+an-k-2hn-k-2+a0h0)=ehhn-k-1,hn

20、-k-2,h0为对偶码码字hn-k-1,hn-k-2,h0线性组合，为对偶码另一码字h 六、大数逻辑译码-极长码对偶码互为零空间，码字可用作对偶码的监督和式，因此可寻找一些特殊的对偶码组，符合大数逻辑译码原则（都有最高位，其它位只出现1次）例如汉明码由于最小距离为3，一定存在重量为3的码字，取一些特殊的码字。w1(x)=xn-1+xj1+xi1w2(x)=xn-1+xj2+xi2w1(x)w2(x)j1 j2 且i1 i2 反证，若j1=j2 w1(x)+w2(x)=xi1+xi2码字重量小于3因此，这样的码字符合大数逻辑译码的原则，又对偶码互为零空间，这样的码字多项式是其对偶码的监督和式，所

21、以汉明码的这一组码字可以用来作其对偶码的译码，其对偶码是大数逻辑可译码，叫极长码，共有n-1个xi(i=0,.,n-2)，J=（n-1）/2六、大数逻辑译码-极长码以F2上的m次本原多项式p*(x)生成2m-1,2m-1-m,3汉明码，由于1|)(12mxxp所以生成循环码。定理5（定义6.4.1）设xn-1=g(x)p(x),其中p(x)为本原多项式，则g(x)生成的(n,m)循环码是一个完备的正交码，最小距离为dmin=2m-1p(x)p*(x)（也是本原多项式）互反互反g(x)生成c(x)生成2m-1,2m-1-m,3 汉明码ijnxxxxW1)(10nji以这些码字组成集合，可作为正交

22、监督和式组d=3,必有重量为3的码字关键，找ijnxxxxW1)(方法：先由iijnxWxPWxPxWWxxxW1|)(|)()(Wxi)(*modxp共有(n-1)/2 个W(x),122112211mmnJ121mJd六、大数逻辑译码-极长码例：求m=4的一步完备正交极长码的生成多项式及正交监督 和式解：1)(711)(/1)(1)(824151234235781115414xxxpdJxxxxxxxxpxxgxxxpdmknm）（查表取4次本原多项式六、大数逻辑译码-极长码)(mod)()()()(mod)()(62121421013141101314110113141xpxWxxxWx

23、xxxWxxxxWxpxxWxxxW231475714681454914411143612142)()()()(1)()(xxxxWxxxxWxxxxWxxxxWxxxWxxxxW由此可写出译码电路六、大数逻辑译码-极长码2 差集循环码（课本有错）寻找特殊码字作为对偶码的监督和式qlnlnlnnxxxxxW1111021)(循环11211111101)()(lnllnllnnlxxxxxWxxWq模1nxqqqqqlnllnllnllnnlqxxxxxxWxxW111110321)()(模1nx六、大数逻辑译码-差集循环码为使上式)()(0 xWxWq只有1nx相同，其余的次数不同，要求jil

24、l 互不相同。设由)()()()()(1101021xhxmxxZxxxxxxxWqqqqqqlnlnlllllln对偶码的生成多项式1|)(nxxh又)1),()(nxxZxh六、大数逻辑译码-差集循环码qlnlnlnnxxxxxW1111021)()1),()(nxxZxhspq 可证，若（p为素数），则13)(snxhZ(x)为 的反多项式)(xZqqqqlllllliilxxxxxZ2111)(0,1)1(qqn差集个数n-1次2 qdJ=q+1,共q1个校验和式关键，找出 叫q阶完备差集,10qlll六、大数逻辑译码-差集循环码1)定义：完备差集令P=,10qlll是一个q1阶自然数

25、集，并有),1(0210qqllllq若由P中元素构成的(q+1)q个（q1取2的排列）有序差集,jillDij满足:(1)D中所有正差（0）互不相同 (2)D中所有负差（0）互不相同 (3)任意两个正差之和不等于q(q+1)+1则称P为q阶完备单差集（完备差集）正差jill 负差ijll)(1)1(jillqq不等于D中任何正差可见，D中所有q(q+1)+1个差模构成了1q(q+1)的任何整数六、大数逻辑译码-差集循环码辛格曾构成了 阶完备差集，P为素数，s为任意正整数，特别是 阶的完备差集（P218,表6-4，其中右边一栏是P）spq sq22）由完备差集构成大数可译码,0210slllP设 是一个 阶完备差集s21221)12(22ssssn13 skn22112ssdslllxxxxZ2211)()(,1()(xZxxhn)(1)(xhxxgn六、大数逻辑译码-差集循环码1)(122lllssxxxZ)(*210 xZxWsln011WxWl022WxWl022WxWssl六、大数逻辑译码-差集循环码