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

第六章循环码的译码陆以勤2005年5月第六章循环码的译码陆以勤1一、循环码译码的原理线性分组码的译码：标准阵列译码，伴随式译码 译码电路复杂

rs计算电路

se

译码表

r-

e电路....... rc一、循环码译码的原理线性分组码的译码：标准阵列译码，伴随式译一、循环码译码的原理----线性分组码中求伴随式的电路例1：[7,4,3]循环汉明码，g(x)=x3+x+1,H=111010001110101101001s=rHT=(r6r5r4r3r2r1r0)Tr6+

r5+

r4+

r2r5+

r4+

r3+

r1r6+

r5+

r3+

r0=T=（

s2s1s0)

111010001110101101001一、循环码译码的原理----线性分组码中求伴随式的电路例1：一、循环码译码的原理----利用循环码的特殊性简化电路s

rHTH=[-PTIn-k]=[-(r1(x))T-(r2(x))T…

-(rk(x))TIn-k]其中，ri(x)-xn-i(modg(x))(i=1,2,...,k)。modg(x)s

rHTr(modg(x))s(x)r(x)(c(x)+e(x))e(x)(modg(x))定理1：由g(x)生成的循环码，r(x)的伴随式s(x)满足： s(x)r(x)e(x)(modg(x))

因此，求S(x)可用除以g(x)的电路实现。这样可把n级寄存器降为n-k级。

一、循环码译码的原理----利用循环码的特殊性简化电路s一、循环码译码的原理----求循环码的伴随式电路例1：[7,4,3]循环汉明码，g(x)=x3+x+1,H=111010001110101101001直接从H求s利用除以g(x)电路求s(x)一、循环码译码的原理----求循环码的伴随式电路例1：[7,一、循环码译码的原理----求循环码的伴随式电路系统码的译码通常含有编码电路..........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-1r0rn-k-1r0r

n-k-2相等？再编一次码送过来的监督位在接收端重新生成的监督位一、循环码译码的原理----求循环码的伴随式电路系统码的译码一、循环码译码的原理----求循环码的伴随式电路定理2（定理6.1.1）：设s(x)是r(x)的伴随式，令f(x)xr(x)(modxn-1),则f(x)的伴随式s1(x)xs(x)(modg(x))。证明（课本证明不好）：

r(x)=rn-1xn-1+rn-2xn-2+….+r1x+r0

xr(x)=rn-1xn+rn-2xn-1+….+r1x2+r0x

f(x)=rn-2xn-1+rn-3xn-2+….+r1x2+r0x+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)+xa(x)g(x)+xs(x)=(-rn-1h(x)+xa(x))g(x)+xs(x)s1(x)f(x)xs(x)(modg(x))。一、循环码译码的原理----求循环码的伴随式电路定理2（定理一、循环码译码的原理----求循环码的伴随式电路定理2（定理6.1.1）：设s(x)是r(x)的伴随式，令f(x)xr(x)(modxn-1),则f(x)的伴随式s1(x)xs(x)(modg(x))。

因此，若对r(x)循环移位，所对应的伴随式相当于在除以g(x)电路中无输入右移一位。推论1（推论6.1.1）：设s(x)是r(x)的伴随式，令rj(x)xjr(x)(modxn-1)(j=0,1,…n-1),则ri(x)的伴随式sj(x)xjs(x)(modg(x))。a(x)Fq[x]:rj(x)a(x)r(x)(modxn-1)的伴随式sj(x)a(x)s(x)(modg(x))。一、循环码译码的原理----求循环码的伴随式电路定理2（定理二、循环码的译码电路------梅吉特译码法（只纠一个错）计算s(x)电路(除以g(x))

s(x)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(modxn-1-1)除以g(x)s(x)xs(x)+1如果错误发生在最高位，由于接收字不是码字，所以伴随式不为0，可以通过其伴随式与纠错后（是一个码字）的关系将其校正。如果错误不发生在最高位，而是发生在次高位，通过将其循环移位就可以将错误图样移到最高位，而且伴随式可通过刚求出的伴随式通过移位的方法求出。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开，把上边g(x)除法电路中的伴随式送到下面的伴随式计算电路中，随即关闭门2，且上边g(x)除法电路立即清0。门1再次打开，4级缓冲器一边送出第1组的信息，一边接收第2组r(x)的前k位。与此同时，上边的伴随式电路计算第2组的r(x)的伴随式，而下边的伴随式计算电路，对第一组r(x)的信息元进行纠错。（注意，图6-2（A）的虚线是缩短循环码，见P197）二、循环码的译码电路------梅吉特译码法（系统码）P19三、扩展汉明码的译码0110ss0/s1/s20101t3,不能纠错t=1，可以纠错t2，不能纠错无错三、扩展汉明码的译码0110ss0/s1/s20四、缩短循环码的译码缓存：k->k-ir(x)先移位i次四、缩短循环码的译码缓存：k->k-i五、捕错译码----原理原理如果确知错误集中在检验位，则去掉后面的检验位即可。s(x)r(x)e(x)eI(x)+ep(x)ep(x)modg(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个错误集中在校验位，则要k<n/t定理3：纠t个错误的GF(q)上的[n,k]循环码，捕错译码过程（即循环移位）中已把t个错误集中在最低n-k位以内的充要条件是w(si(x))<=t,其中si为伴随式。如果不在监督位，只要集中在一起，循环移位后变成xkr(x).监督位n-k五、捕错译码----原理原理111最严重的情况，t个错误均匀五、捕错译码----两种简单捕错译码法2.两种简单捕错译码法第1类捕错译码法第2类捕错译码法把接收到r(x)自动乘以xn-k,再进入g(x)的除法电路计算伴随式，即对r(x)的前rn-1至rk位的错误进行纠正。对系统码来说，可以一边纠错一边送出已纠正的信息元。五、捕错译码----两种简单捕错译码法2.两种简单捕错译码五、捕错译码----改正捕错译码法3.改进捕错译码法（戈莱码及其嵩忠雄译码法)戈莱Golay码（23，12，7）是唯一能纠多个错的2元完备码。其扩展码（24，12，8）用于ITU-TH.324中完备码？对于错误图样e(x)=x22+x11（图中打叉的两个点）或e(x)=x17+x11+x6（图中三个空心园点）,不能通过循环移位把所有的错误移动11个监督位中，所以不能采用简单的捕错译码法。戈莱码采用嵩忠雄改进的捕错译码法。通过将接收矢量在译码器中进行循环移位，使信息位上至多存在一个错误，其余的错误都移到监督位上。对于任何可纠的错误图样，经过i次移位，都可使信息位上不多于1个错误，并且只需三个多项式就能包括信息位的这个错误图样。=1+23+23*22/2+23*22*21/(2*3)=1+23+23*11+23*77=1+23(1+11+77)=1+23*89=2048223-12=211=2048五、捕错译码----改正捕错译码法3.改进捕错译码法（戈莱五、捕错译码----改正捕错译码法s(x)e(x)eI(x)+ep(x)sI(x)+ep(x)modg(x)从r(x)求出已知从eI(x)求出ep(x)

s(x)-sI(x)modg(x) ep(x)=s(x)-sI(x) (1)eI(x)=Q(x)xn-ksI(x)modg(x) (2)e(x)=eI(x)+ep(x)=Q(x)xn-k+ep(x) ep(x)=e(x)-Q(x)xn-kw(ep(x))=w(e(x))-w(Q(x))t-w(Q(x)) 由（1）式得w(ep(x))=

w(s(x)-sI(x))，所以w(s(x)-sI(x))t-w(Q(x))

作为判断信息位错误图样是否是Q(x)的条件（充分条件未证）。e(x)=Q(x)xn-k+s(x)-sI(x)对于戈莱码：Q1(x)=0,Q2(x)=x5,Q3(x)=x6。取g(x)=x11+x10+x6+x5+x4+x2+1由（2）可得：sI1=0sI2=x9+x8+x6+x5+x2+xsI3=x10+x9+x7+x6+x3+x2五、捕错译码----改正捕错译码法s(x)e(x)五、捕错译码----改正捕错译码法w(s(x)-sI(x))t-w(Q(x))信息元无错:w(Q1(x))=0;信息元有错:w(Qi(x))=1. i=2,3判断 w(s(x)-sI0)3w(s(x))3

w(s(x)-sIi)2 i=1,2 信息位的错误图样为x11Qi(x)。 w(s(x))>3且w(s(x)-sIi(x))2嵩忠雄译码法(图6-8，p203页）。五、捕错译码----改正捕错译码法w(s(x)-sI(x)六、大数逻辑译码（一）原理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,0……sj

=

en-1hj,n-1+en-2hj,n-2+…+e0hi,0……s0

=

en-1h0,n-1+en-2h0,n-2+…+e0h0,0六、大数逻辑译码（一）原理sn-k-1=en-1hn-k六、大数逻辑译码----原理对错误图样进行监督，变换H为H使新的s的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,0……sj

=

en-1hj,n-1+en-2hj,n-2+…+e0hi,0……s0

=

en-1h0,n-1+en-2h0,n-2+…+e0h0,0六、大数逻辑译码----原理对错误图样进行监督，变换H为H六、大数逻辑译码----原理例：[7，3，4]码，H=101|1000111|0100110|0010011|0001相加H0=101|1000110|0010100|0101s

=(s2,s1,s0

)=(e6,e5,e4,e3,e2,e1,e0

)

101|1000110|0010100|0101s2=s3 =e6

+e4+e3s1=s1 =e6

+e5 +e1 s0=s2+s0=e6

+e2+e0若e6=1,ei=0,i=0,…,5,则s0=s1=s2=1;若e6=0,ei=1,ei=0,i,j=0,…,5,且

ij，则s0，s1，s2只有1个为1;若e6=1,ei=1,ei=0,i,j=0,…,5,且

ij，则s0，s1，s2有2个为1，1个为0;若e6=0,ei=ei=1,ek=0,i,j,k=0,…,5,且

i,j,k互不相等，则s0，s1，s2最多只有2个为1，1个为0。t=1t=2六、大数逻辑译码----原理例：[7，3，4]码，H=10六、大数逻辑译码----原理若e6=1,ei=0,i=0,…,5,则s0=s1=s2=1;若e6=0,ei=1,ei=0,i,j=0,…,5,且

ij，则s0，s1，s2只有1个为1;若e6=1,ei=1,ei=0,i,j=0,…,5,且

ij，则s0，s1，s2有2个为1，1个为0;若e6=0,ei=ei=1,ek=0,i,j,k=0,…,5,且

i,j,k互不相等，则s0，s1，s2最多只有2个为1，1个为0。若e6=1,且t=1,则s0，s1，s2有2个或2个以上为1；若e61,且t=1,则s0，s1，s2有小于2个为1。根据s0，s1，s2中为1的个数决定e6是否有错，因为是循环码，可以循环至下一位（判断e5,e4,e3,e2,e1,e0

是否有错）。这叫一步大数逻辑译码。定理4（定理6.3.1)

一个循环码若能建立J个正交一致校验和式，则该码能纠正t[J/2]个错误，其中[x]表示取x的整数部分。六、大数逻辑译码----原理若e6=1,ei=0,i=0六、大数逻辑译码----原理定理4（定理6.3.1)

一个循环码若能建立J个正交一致校验和式，则该码能纠正t[J/2]个错误，其中[x]表示取x的整数部分。sJ-1

=

en-1+……sJ-2

=

en-1+…………s0

=

en-1+……en-1=1,最多只有[J/2]-1个si为0，大部分si仍为1en-1=0,最多只有[J/2]个si为1根据s0，s1,…,sJ中为1的数目是否多于一半对正交位纠错。一步大数逻辑可译码不多。t(n-1)/2(dev-1)dev:对偶码的距离，要小六、大数逻辑译码----原理定理4（定理6.3.1)一个循六、大数逻辑译码----二步大数逻辑译码分两步，第一步先确定错误发生在某些码元位， 第二步再从这些码元位中确定是哪一个具体的位。定义2对H的行进行线性变换为H0,H0的伴随式为（sJ-1,sJ-2,…,s0

）。若某一码元集合{ci1,ci2,…,cil

}的线性组合 ai1ci1+ai2

ci2+…+ailcil

(aij0,j=1,…,l)在sJ-1,sJ-2,…,s0中出现，而其余码元位置集合至多在其中某一sj(0jJ-1)出现1次，则说sJ-1,sJ-2,…,s0在集合{ci1,ci2,…,cil

}上正交，称sJ-1,sJ-2,…,s0为该集合的正交一致校验和式。六、大数逻辑译码----二步大数逻辑译码分两步，第一步先确定六、大数逻辑译码----二步大数逻辑译码[7，4，3]循环汉明码第1步：确定错误发生在e6,e5,e4上s11=s2 =（e6+e4）

+e3

+e2s10=s1 =（e6+e4）

+e5

+e1s21=s1 =（e6+e5）

+e4

+e1s20=s2+s0 =（e6+e5）

+e2

+e0确定错误是否发生在e6,e4中确定错误是否发生在e6,e5中第2步：确定错误发生在e6上s31

=e6+e4s30

=e6+e5确定错误是否发生在e6上六、大数逻辑译码----二步大数逻辑译码[7，4，3]循环汉六、大数逻辑译码----大数逻辑译码器（二）大数逻辑译码器1.I类大数逻辑译码器由s(x)r(x)(modg(x))求s(x)),一步大数逻辑译码器六、大数逻辑译码----大数逻辑译码器（二）大数逻辑译码器六、大数逻辑译码----大数逻辑译码器s2=s3 =e6

+e4+e3s1=s1 =e6

+e5 +e1 s0=s2+s0=e6

+e2+e0例：[7，3，4]码g(x)=x4+x3+x2+1但大数门＝2可检2个错六、大数逻辑译码----大数逻辑译码器s2=s3 六、大数逻辑译码----大数逻辑译码器二步大数逻辑译码器（7,4,3)循环汉明码，二步大数逻辑译码，P211页图6-11六、大数逻辑译码----大数逻辑译码器二步大数逻辑译码器（7六、大数逻辑译码----大数逻辑译码器2.II类大数逻辑译码器由r(x)和H求s(x)s(x)=r(x)HT六、大数逻辑译码----大数逻辑译码器2.II类大数逻辑译六、大数逻辑译码----大数逻辑可译码的构造（三）大数逻辑可译码的构造1.极长码s=(sn-k-1sn-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-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因此，这样的码字符合大数逻辑译码的原则，又对偶码互为零空间，这样的码字多项式是其对偶码的监督和式，所以汉明码的这一组码字可以用来作其对偶码的译码，其对偶码是大数逻辑可译码，叫极长码，共有n-1个xi(i=0,..,n-2)，J=（n-1）/2六、大数逻辑译码----极长码对偶码互为零空间，码字可用作对六、大数逻辑译码----极长码以F2上的m次本原多项式p*(x)生成[2m-1,2m-1-m,3]汉明码，由于所以生成循环码。定理5（定义6.4.1）设xn-1=g(x)p(x),其中p(x)为本原多项式，则g(x)生成的(n,m)循环码是一个完备的正交码，最小距离为dmin=2m-1

p(x)p*(x)（也是本原多项式）互反g(x)生成c(x) 生成[2m-1,2m-1-m,3]汉明码以这些码字组成集合，可作为正交监督和式组d=3,必有重量为3的码字六、大数逻辑译码----极长码以F2上的m次本原多项式p*(关键，找方法：先由共有(n-1)/2个W(x),六、大数逻辑译码----极长码关键，找方法：先由共有(n-1)/2个W(x),六、大数例：求m=4的一步完备正交极长码的生成多项式及正交监督和式解：查表取4次本原多项式六、大数逻辑译码----极长码例：求m=4的一步完备正交极长码的生成多项式及正交监督解：查由此可写出译码电路六、大数逻辑译码----极长码由此可写出译码电路六、大数逻辑译码----极长码2差集循环码（课本有错）寻找特殊码字作为对偶码的监督和式循环模模六、大数逻辑译码----差集循环码2差集循环码（课本有错）寻找特殊码字作为对偶码的监督和式为使上式只有相同，其余的次数不同，要求互不相同。设由又六、大数逻辑译码----差集循环码为使上式只有相同，其余的次数不同，要求互不相同。设由又六、大可证，若（p为素数），则Z(x)为的反多项式差集个数n-1次J=q+1,共q＋1个校验和式关键，找出叫q阶完备差集六、大数逻辑译码----差集循环码可证，若（p为素数），则Z(x)为的反多项式1)定义：完备差集令P=是一个q＋1阶自然数集，并有若由P中元素构成的(q+1)q个（q＋1取2的排列）有序差集满足:(1)D中所有正差（>0）互不相同

(2)D中所有负差（<0）互不相同

(3)任意两个正差之和不等于q(q+1)+1则称P为q阶完备单差集（完备差集）不等于D中任何正差可见，D中所有q(q+1)+1个差模构成了1~q(q+1)的任何整数六、大数逻辑译码----差集循环码1)定义：完备差集令P=是一个q＋1阶自然数集，并有若由P辛格曾构成了阶完备差集，P为素数，s为任意正整数，特别是阶的完备差集（P218,表6-4，其中右边一栏是P）2）由完备差集构成大数可译码设是一个阶完备差集六、大数逻辑译码----差集循环码辛格曾构成了阶完备差集，P为素数六、大数逻辑译码----差集循环码六、大数逻辑译码----差集循环码第六章循环码的译码陆以勤2005年5月第六章循环码的译码陆以勤43一、循环码译码的原理线性分组码的译码：标准阵列译码，伴随式译码 译码电路复杂

rs计算电路

se

译码表

r-

e电路....... rc一、循环码译码的原理线性分组码的译码：标准阵列译码，伴随式译一、循环码译码的原理----线性分组码中求伴随式的电路例1：[7,4,3]循环汉明码，g(x)=x3+x+1,H=111010001110101101001s=rHT=(r6r5r4r3r2r1r0)Tr6+

r5+

r4+

r2r5+

r4+

r3+

r1r6+

r5+

r3+

r0=T=（

s2s1s0)

111010001110101101001一、循环码译码的原理----线性分组码中求伴随式的电路例1：一、循环码译码的原理----利用循环码的特殊性简化电路s

rHTH=[-PTIn-k]=[-(r1(x))T-(r2(x))T…

-(rk(x))TIn-k]其中，ri(x)-xn-i(modg(x))(i=1,2,...,k)。modg(x)s

rHTr(modg(x))s(x)r(x)(c(x)+e(x))e(x)(modg(x))定理1：由g(x)生成的循环码，r(x)的伴随式s(x)满足： s(x)r(x)e(x)(modg(x))

因此，求S(x)可用除以g(x)的电路实现。这样可把n级寄存器降为n-k级。

一、循环码译码的原理----利用循环码的特殊性简化电路s一、循环码译码的原理----求循环码的伴随式电路例1：[7,4,3]循环汉明码，g(x)=x3+x+1,H=111010001110101101001直接从H求s利用除以g(x)电路求s(x)一、循环码译码的原理----求循环码的伴随式电路例1：[7,一、循环码译码的原理----求循环码的伴随式电路系统码的译码通常含有编码电路..........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-1r0rn-k-1r0r

n-k-2相等？再编一次码送过来的监督位在接收端重新生成的监督位一、循环码译码的原理----求循环码的伴随式电路系统码的译码一、循环码译码的原理----求循环码的伴随式电路定理2（定理6.1.1）：设s(x)是r(x)的伴随式，令f(x)xr(x)(modxn-1),则f(x)的伴随式s1(x)xs(x)(modg(x))。证明（课本证明不好）：

r(x)=rn-1xn-1+rn-2xn-2+….+r1x+r0

xr(x)=rn-1xn+rn-2xn-1+….+r1x2+r0x

f(x)=rn-2xn-1+rn-3xn-2+….+r1x2+r0x+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)+xa(x)g(x)+xs(x)=(-rn-1h(x)+xa(x))g(x)+xs(x)s1(x)f(x)xs(x)(modg(x))。一、循环码译码的原理----求循环码的伴随式电路定理2（定理一、循环码译码的原理----求循环码的伴随式电路定理2（定理6.1.1）：设s(x)是r(x)的伴随式，令f(x)xr(x)(modxn-1),则f(x)的伴随式s1(x)xs(x)(modg(x))。

因此，若对r(x)循环移位，所对应的伴随式相当于在除以g(x)电路中无输入右移一位。推论1（推论6.1.1）：设s(x)是r(x)的伴随式，令rj(x)xjr(x)(modxn-1)(j=0,1,…n-1),则ri(x)的伴随式sj(x)xjs(x)(modg(x))。a(x)Fq[x]:rj(x)a(x)r(x)(modxn-1)的伴随式sj(x)a(x)s(x)(modg(x))。一、循环码译码的原理----求循环码的伴随式电路定理2（定理二、循环码的译码电路------梅吉特译码法（只纠一个错）计算s(x)电路(除以g(x))

s(x)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(modxn-1-1)除以g(x)s(x)xs(x)+1如果错误发生在最高位，由于接收字不是码字，所以伴随式不为0，可以通过其伴随式与纠错后（是一个码字）的关系将其校正。如果错误不发生在最高位，而是发生在次高位，通过将其循环移位就可以将错误图样移到最高位，而且伴随式可通过刚求出的伴随式通过移位的方法求出。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开，把上边g(x)除法电路中的伴随式送到下面的伴随式计算电路中，随即关闭门2，且上边g(x)除法电路立即清0。门1再次打开，4级缓冲器一边送出第1组的信息，一边接收第2组r(x)的前k位。与此同时，上边的伴随式电路计算第2组的r(x)的伴随式，而下边的伴随式计算电路，对第一组r(x)的信息元进行纠错。（注意，图6-2（A）的虚线是缩短循环码，见P197）二、循环码的译码电路------梅吉特译码法（系统码）P19三、扩展汉明码的译码0110ss0/s1/s20101t3,不能纠错t=1，可以纠错t2，不能纠错无错三、扩展汉明码的译码0110ss0/s1/s20四、缩短循环码的译码缓存：k->k-ir(x)先移位i次四、缩短循环码的译码缓存：k->k-i五、捕错译码----原理原理如果确知错误集中在检验位，则去掉后面的检验位即可。s(x)r(x)e(x)eI(x)+ep(x)ep(x)modg(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个错误集中在校验位，则要k<n/t定理3：纠t个错误的GF(q)上的[n,k]循环码，捕错译码过程（即循环移位）中已把t个错误集中在最低n-k位以内的充要条件是w(si(x))<=t,其中si为伴随式。如果不在监督位，只要集中在一起，循环移位后变成xkr(x).监督位n-k五、捕错译码----原理原理111最严重的情况，t个错误均匀五、捕错译码----两种简单捕错译码法2.两种简单捕错译码法第1类捕错译码法第2类捕错译码法把接收到r(x)自动乘以xn-k,再进入g(x)的除法电路计算伴随式，即对r(x)的前rn-1至rk位的错误进行纠正。对系统码来说，可以一边纠错一边送出已纠正的信息元。五、捕错译码----两种简单捕错译码法2.两种简单捕错译码五、捕错译码----改正捕错译码法3.改进捕错译码法（戈莱码及其嵩忠雄译码法)戈莱Golay码（23，12，7）是唯一能纠多个错的2元完备码。其扩展码（24，12，8）用于ITU-TH.324中完备码？对于错误图样e(x)=x22+x11（图中打叉的两个点）或e(x)=x17+x11+x6（图中三个空心园点）,不能通过循环移位把所有的错误移动11个监督位中，所以不能采用简单的捕错译码法。戈莱码采用嵩忠雄改进的捕错译码法。通过将接收矢量在译码器中进行循环移位，使信息位上至多存在一个错误，其余的错误都移到监督位上。对于任何可纠的错误图样，经过i次移位，都可使信息位上不多于1个错误，并且只需三个多项式就能包括信息位的这个错误图样。=1+23+23*22/2+23*22*21/(2*3)=1+23+23*11+23*77=1+23(1+11+77)=1+23*89=2048223-12=211=2048五、捕错译码----改正捕错译码法3.改进捕错译码法（戈莱五、捕错译码----改正捕错译码法s(x)e(x)eI(x)+ep(x)sI(x)+ep(x)modg(x)从r(x)求出已知从eI(x)求出ep(x)

s(x)-sI(x)modg(x) ep(x)=s(x)-sI(x) (1)eI(x)=Q(x)xn-ksI(x)modg(x) (2)e(x)=eI(x)+ep(x)=Q(x)xn-k+ep(x) ep(x)=e(x)-Q(x)xn-kw(ep(x))=w(e(x))-w(Q(x))t-w(Q(x)) 由（1）式得w(ep(x))=

w(s(x)-sI(x))，所以w(s(x)-sI(x))t-w(Q(x))

作为判断信息位错误图样是否是Q(x)的条件（充分条件未证）。e(x)=Q(x)xn-k+s(x)-sI(x)对于戈莱码：Q1(x)=0,Q2(x)=x5,Q3(x)=x6。取g(x)=x11+x10+x6+x5+x4+x2+1由（2）可得：sI1=0sI2=x9+x8+x6+x5+x2+xsI3=x10+x9+x7+x6+x3+x2五、捕错译码----改正捕错译码法s(x)e(x)五、捕错译码----改正捕错译码法w(s(x)-sI(x))t-w(Q(x))信息元无错:w(Q1(x))=0;信息元有错:w(Qi(x))=1. i=2,3判断 w(s(x)-sI0)3w(s(x))3

w(s(x)-sIi)2 i=1,2 信息位的错误图样为x11Qi(x)。 w(s(x))>3且w(s(x)-sIi(x))2嵩忠雄译码法(图6-8，p203页）。五、捕错译码----改正捕错译码法w(s(x)-sI(x)六、大数逻辑译码（一）原理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,0……sj

=

en-1hj,n-1+en-2hj,n-2+…+e0hi,0……s0

=

en-1h0,n-1+en-2h0,n-2+…+e0h0,0六、大数逻辑译码（一）原理sn-k-1=en-1hn-k六、大数逻辑译码----原理对错误图样进行监督，变换H为H使新的s的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,0……sj

=

en-1hj,n-1+en-2hj,n-2+…+e0hi,0……s0

=

en-1h0,n-1+en-2h0,n-2+…+e0h0,0六、大数逻辑译码----原理对错误图样进行监督，变换H为H六、大数逻辑译码----原理例：[7，3，4]码，H=101|1000111|0100110|0010011|0001相加H0=101|1000110|0010100|0101s

=(s2,s1,s0

)=(e6,e5,e4,e3,e2,e1,e0

)

101|1000110|0010100|0101s2=s3 =e6

+e4+e3s1=s1 =e6

+e5 +e1 s0=s2+s0=e6

+e2+e0若e6=1,ei=0,i=0,…,5,则s0=s1=s2=1;若e6=0,ei=1,ei=0,i,j=0,…,5,且

ij，则s0，s1，s2只有1个为1;若e6=1,ei=1,ei=0,i,j=0,…,5,且

ij，则s0，s1，s2有2个为1，1个为0;若e6=0,ei=ei=1,ek=0,i,j,k=0,…,5,且

i,j,k互不相等，则s0，s1，s2最多只有2个为1，1个为0。t=1t=2六、大数逻辑译码----原理例：[7，3，4]码，H=10六、大数逻辑译码----原理若e6=1,ei=0,i=0,…,5,则s0=s1=s2=1;若e6=0,ei=1,ei=0,i,j=0,…,5,且

ij，则s0，s1，s2只有1个为1;若e6=1,ei=1,ei=0,i,j=0,…,5,且

ij，则s0，s1，s2有2个为1，1个为0;若e6=0,ei=ei=1,ek=0,i,j,k=0,…,5,且

i,j,k互不相等，则s0，s1，s2最多只有2个为1，1个为0。若e6=1,且t=1,则s0，s1，s2有2个或2个以上为1；若e61,且t=1,则s0，s1，s2有小于2个为1。根据s0，s1，s2中为1的个数决定e6是否有错，因为是循环码，可以循环至下一位（判断e5,e4,e3,e2,e1,e0

是否有错）。这叫一步大数逻辑译码。定理4（定理6.3.1)

一个循环码若能建立J个正交一致校验和式，则该码能纠正t[J/2]个错误，其中[x]表示取x的整数部分。六、大数逻辑译码----原理若e6=1,ei=0,i=0六、大数逻辑译码----原理定理4（定理6.3.1)

一个循环码若能建立J个正交一致校验和式，则该码能纠正t[J/2]个错误，其中[x]表示取x的整数部分。sJ-1

=

en-1+……sJ-2

=

en-1+…………s0

=

en-1+……en-1=1,最多只有[J/2]-1个si为0，大部分si仍为1en-1=0,最多只有[J/2]个si为1根据s0，s1,…,sJ中为1的数目是否多于一半对正交位纠错。一步大数逻辑可译码不多。t(n-1)/2(dev-1)dev:对偶码的距离，要小六、大数逻辑译码----原理定理4（定理6.3.1)一个循六、大数逻辑译码----二步大数逻辑译码分两步，第一步先确定错误发生在某些码元位， 第二步再从这些码元位中确定是哪一个具体的位。定义2对H的行进行线性变换为H0,H0的伴随式为（sJ-1,sJ-2,…,s0

）。若某一码元集合{ci1,ci2,…,cil

}的线性组合 ai1ci1+ai2

ci2+…+ailcil

(aij0,j=1,…,l)在sJ-1,sJ-2,…,s0中出现，而其余码元位置集合至多在其中某一sj(0jJ-1)出现1次，则说sJ-1,sJ-2,…,s0在集合{ci1,ci2,…,cil

}上正交，称sJ-1,sJ-2,…,s0为该集合的正交一致校验和式。六、大数逻辑译码----二步大数逻辑译码分两步，第一步先确定六、大数逻辑译码----二步大数逻辑译码[7，4，3]循环汉明码第1步：确定错误发生在e6,e5,e4上s11=s2 =（e6+e4）

+e3

+e2s10=s1 =（e6+e4）

+e5

+e1s21=s1 =（e6+e5）

+e4

+e1s20=s2+s0 =（e6+e5）

+e2

+e0确定错误是否发生在e6,e4中确定错误是否发生在e6,e5中第2步：确定错误发生在e6上s31

=e6+e4s30

=e6+e5确定错误是否发生在e6上六、大数逻辑译码----二步大数逻辑译码[7，4，3]循环汉六、大数逻辑译码----大数逻辑译码器（二）大数逻辑译码器1.I类大数逻辑译码器由s(x)r(x)(modg(x))求s(x)),一步大数逻辑译码器六、大数逻辑译码----大数逻辑译码器（二）大数逻辑译码器六、大数逻辑译码----大数逻辑译码器s2=s3 =e6

+e4+e3s1=s1 =e6

+e5 +e1 s0=s2+s0=e6

+e2+e0例：[7，3，4]码g(x)=x4+x3+x2+1但大数门＝2