理学分组码现代编码技术曾凡鑫学习教案.pptx

《理学分组码现代编码技术曾凡鑫学习教案.pptx》由会员分享，可在线阅读，更多相关《理学分组码现代编码技术曾凡鑫学习教案.pptx（159页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、会计学1理学理学(lxu)分组码现代编码技术曾凡鑫分组码现代编码技术曾凡鑫第一页，共159页。表表3.1消息消息(xio xi)的编码、译码关系的编码、译码关系第1页/共159页第二页，共159页。定义定义，x=(x1，x2，xn)，y=(y1，y2，yn)，称，称dist(x，y)=|i|xiyi，i=1，2，n|为码字为码字x与与y的汉明距离。的汉明距离。码字间的汉明距离满足下列码字间的汉明距离满足下列三角不等式：三角不等式：dist(x，y)dist(x，z)+dist(z，y)在一个码在一个码中，任意两个不同码字间汉明距中，任意两个不同码字间汉明距离的最小者称为离的最小者称为(chn

2、wi)这个这个码的最小汉明距离。码的最小汉明距离。第2页/共159页第三页，共159页。定义设有码定义设有码C，称，称 为码为码C的最小汉的最小汉明距离。明距离。在一个码中，码字中非零码在一个码中，码字中非零码元的数目也是一个重要的参数，元的数目也是一个重要的参数，这个这个(zh ge)参数通常称为码字参数通常称为码字的汉明重量。的汉明重量。第3页/共159页第四页，共159页。定义定义(dngy)设有码设有码C，称，称wt(x)=|i|xi0，i=1，2，n|为码字为码字x的汉明的汉明重量。重量。定义定义(dngy)设有码设有码C，0=(0，0)，称称wt(C)=minwt(x)|xC，x0

3、 为码为码C的最小汉明重的最小汉明重量。量。第4页/共159页第五页，共159页。例例设有码设有码C2=(a1，a2，a3，a4，a5，a6，a7，a8)，式中，式中a1=(0000000)a2=(0011101)a3=(0100111)a4=(0111010)a5=(1001110)a6=(1010011)a7=(1101001)a8=(1110100)求求dist(a2，a4)，dist(a3，a7)，wt(a8)，dist(C2)，wt(C2)。解解dist(a2，a4)=4，dist(a3，a7)=4，wt(a8)=4，dist(C2)=4，wt(C2)=4第5页/共159页第六页，共

4、159页。定义设有码定义设有码C，如果，如果，有，有x+yC，则称码，则称码C是线是线性码。性码。所有的这样所有的这样2k个码字构成的个码字构成的集合称为集合称为(chn wi)分组码。须分组码。须注意一点，注意一点，nk个校验元可以放个校验元可以放在码字中的任何位置，如果码字在码字中的任何位置，如果码字前前k位固定为信息码，则这种分位固定为信息码，则这种分组码称为组码称为(chn wi)系统分组码，系统分组码，如图如图 3.1 所示。所示。n n图 3.1系统(xtng)(n，k)分组码码字结构第6页/共159页第七页，共159页。定义将定义将k位信息码通过位信息码通过(tnggu)一定的规

5、则添加一定的规则添加nk个校验元而形成长为个校验元而形成长为n的码字，的码字，如果所有这样的码字组成一个线如果所有这样的码字组成一个线性码，则称为性码，则称为(n，k)线性分组码。线性分组码。定义称定义称(n，k)线性分组码线性分组码的的 为码率。为码率。第7页/共159页第八页，共159页。例构造奇偶校验码。对例构造奇偶校验码。对X=0，1的的k维扩展信源维扩展信源Xk添加一位添加一位校验位形成一个长为校验位形成一个长为k+1的码字，的码字，即即且满足关系：且满足关系：x1+x2+xk+xk+1=0(偶校验偶校验)即信息码即信息码(x1x2xk)中如有偶数个中如有偶数个1，则，则xk+1=0

6、，如有奇数，如有奇数(j sh)个个1，则则xk+1=1。或或x1+x2+xk+xk+1=1(奇校验奇校验)即信息码即信息码(x1x2xk)中如有偶数个中如有偶数个1，则，则xk+1=1，否则，否则xk+1=0。第8页/共159页第九页，共159页。解仅讨论偶校验，所得结解仅讨论偶校验，所得结论适合于奇校验。设发送码字论适合于奇校验。设发送码字(x1x2xkxk+1)，接收矢量为，接收矢量为(y1y2ykyk+1)，如果无错，则，如果无错，则接收矢量应满足式；如果产生奇接收矢量应满足式；如果产生奇数个错误，则数个错误，则y1+y2+yk+yk+1=1，因为一个因为一个(y)码码元元x发生错误意

7、味着这个码元变发生错误意味着这个码元变为为x+1，为讨论方便，不防设，为讨论方便，不防设y1，y2，y2r+1发生错误，于是发生错误，于是y1+y2+yk+yk+1=(1+x1)+(1+x2)+(1+x2r+1)+x2r+2+xk+xk+1=(2r+1)+(x1+x2+xk+xk+1)=2r+1=1(mod2)说明不满足式，从而发现错误，说明不满足式，从而发现错误，但无法判别哪些码元、多少码元但无法判别哪些码元、多少码元出错，所以无纠错能力。出错，所以无纠错能力。第9页/共159页第十页，共159页。如果是偶数个错误，则有如果是偶数个错误，则有 y1+y2+yk+yk+1=2r+(x1+x2+

8、xk+xk+1)=2r=0(mod2)说明满足式，因而无法检出错误。说明满足式，因而无法检出错误。综合起来，奇偶校验码能检综合起来，奇偶校验码能检奇数奇数(j sh)个错误，不能检偶个错误，不能检偶数个错误，无纠错能力，码率为数个错误，无纠错能力，码率为。第10页/共159页第十一页，共159页。定理在一个线性分组码中，定理在一个线性分组码中，码的最小汉明距离等于码的最小汉明距离等于(dngy)码的最小汉明重量。码的最小汉明重量。证明设证明设C是线性分组码，是线性分组码，则则0C，再设，再设xC，满足，满足wt(x)=wt(C)，即有，即有dist(C)dist(x，0)=wt(x)=wt(C

9、)另一方面，设另一方面，设x，yC且且dist(x，y)=dist(C)，因为，因为，且，且wt(z)=dist(x，y)，所以所以wt(C)wt(z)=dist(x，y)=dist(C)故故 dist(C)=wt(C)第11页/共159页第十二页，共159页。定理对一个二元定理对一个二元(n，k)线线性分组码性分组码C，有，有(1)能纠正能纠正t个错误的充要条个错误的充要条件是件是dist(C)=2t+1；(2)能检测能检测s个错误的充要条个错误的充要条件是件是 dist(C)=s+1；(3)能纠正能纠正t个错误，并能发个错误，并能发现现s(st)个错误的充要条件是个错误的充要条件是dist

10、(C)=t+s+1。证明只证结论证明只证结论(1)，其余，其余(qy)省略。设发送码字为省略。设发送码字为x，接收矢量为接收矢量为y，z是是C中不等于中不等于x的的任意码字。任意码字。必要性。假设必要性。假设x传送后发传送后发生了生了r(t)个错误，则有个错误，则有dist(x，y)=rt由汉明距离的三角不等式，由汉明距离的三角不等式，有有dist(z，y)dist(x，z)dist(x，y)dist(C)dist(x，y)=2t+1rt+1 第12页/共159页第十三页，共159页。式说明接收矢量式说明接收矢量y最像码最像码C中中的的x，按选大原则，接收端能正，按选大原则，接收端能正确译出码

11、确译出码x，即纠正了矢量，即纠正了矢量y中的中的r个错误。个错误。充分性。使用反证法。假充分性。使用反证法。假设设dist(C)2t+1，那么必定存在，那么必定存在两个两个(lin)不同的码字不同的码字x=(x1，x2，xn)和和z=(z1，z2，zn)满足满足dist(x，z)2t+1。由码。由码字间距离的定义，字间距离的定义，x与与z间至多有间至多有2t个码元对应不同，分两种情况个码元对应不同，分两种情况来讨论。来讨论。情况情况1：设：设x与与z间有间有2r(2t+1)个码元对应不同。不妨个码元对应不同。不妨设设，j=1，2，2r。取矢。取矢量量y=(y1，y2，yn)，式中：，式中：第1

12、3页/共159页第十四页，共159页。于是于是(ysh)，由，由rt得到得到 dist(x，y)=rt 且且 dist(z，y)=rt 第14页/共159页第十五页，共159页。情况情况2：设：设x与与z间有间有2r+1(deg(h(x)，那么，那么用校验多项式来进行编码的电路用校验多项式来进行编码的电路会简单一些。会简单一些。第80页/共159页第八十一页，共159页。根据根据(gnj)式和式，有式和式，有式中，式中，(cn1，cn2，cnk)=(mk1，mk2，m0)。第81页/共159页第八十二页，共159页。简化简化(jinhu)后得到后得到第82页/共159页第八十三页，共159页。

13、式写成方程组形式，校验式写成方程组形式，校验(xio yn)元与信息元的关系为元与信息元的关系为第83页/共159页第八十四页，共159页。从式看出，校验元从式看出，校验元cnk1取决于信息取决于信息(xnx)码码(mk1，mk2，m1，m0)与校验多与校验多项式的系数项式的系数(h0，h1，hk1)的内积，的内积，cnk2取决于取决于(mk2，mk3，m1，m0，cnk1)与与(h0，h1，hk1)的内的内积，以此类推，积，以此类推，c0取决于取决于(ck，ck1，c1)与与(h0，h1，hk1)的内积，这说明可以从校的内积，这说明可以从校验元验元cnk1开始，以开始，以cnk1，cnk2，

14、c1，c0的顺序的顺序来递推校验元。完成这一递推过来递推校验元。完成这一递推过程的一般电路见图程的一般电路见图3.7。第84页/共159页第八十五页，共159页。n n图 3.7根据校验(xio yn)多项式h(x)构成的循环码编码电路第85页/共159页第八十六页，共159页。例用校验多项式例用校验多项式h(x)=x4+x3+x2+1来产生系统来产生系统(xtng)(7，4)循环码的码字循环码的码字(1001011)。解解(1)本例产生码字的电本例产生码字的电路如图路如图3.8所示。所示。n n图 3.8基于(jy)校验多项式的(7，4)循环码编码电路第86页/共159页第八十七页，共159

15、页。(2)工作原理如下工作原理如下(rxi)：门门1和门和门2开，移位寄存器开，移位寄存器清零。清零。门门1关，门关，门2开，输入信息开，输入信息码码(1001)，输出端获得码字前，输出端获得码字前4位码元位码元(m3m2m1m0)。各移位寄存。各移位寄存器内容见表器内容见表3.7。第87页/共159页第八十八页，共159页。表表3.7图图3.8编码编码(bin m)电路的编码电路的编码(bin m)过程过程第88页/共159页第八十九页，共159页。信息码输入完毕后，门信息码输入完毕后，门1开，门开，门2关，在时钟脉冲未到来关，在时钟脉冲未到来前，移位前，移位(y wi)寄存器寄存器D和和D

16、4的输入端信号为的输入端信号为h0m3+h1m2+h2m1+h3m0=11+00+10+11=0即校验元即校验元c2=0，当时钟脉冲到来，当时钟脉冲到来时，时，c2进入进入D4和和D，同时输出校，同时输出校验元验元c2=0；在时钟脉冲未到来前，；在时钟脉冲未到来前，移位移位(y wi)寄存器寄存器D和和D4的输的输入端信号为入端信号为h0m2+h1m1+h2m0+h3c2=10+00+11+10=1即即c1=1，当时钟脉冲到来时，输，当时钟脉冲到来时，输出出c1=1，并且进入，并且进入D4。类推可得。类推可得c0=1。门门1和门和门2开，移位开，移位(y wi)寄存器清零，准备下一组码寄存器清

17、零，准备下一组码字的编码。字的编码。第89页/共159页第九十页，共159页。循环码的译码方法循环码的译码方法(fngf)设设(n，k)循环码发送的码字、循环码发送的码字、接收矢量和错误图样及所对应的接收矢量和错误图样及所对应的码字多项式、接收矢量多项式和码字多项式、接收矢量多项式和错误图样多项式如下：错误图样多项式如下：设设y(x)除以除以g(x)的余式为的余式为s(x)，即存在一个，即存在一个q1(x)使使y(x)=q1(x)g(x)+s(x)第90页/共159页第九十一页，共159页。由定理知，如由定理知，如s(x)=0，则，则y(x)为正确码字；如为正确码字；如s(x)0，则，则y(x

18、)产生了错误。因此，产生了错误。因此，s(x)是否是否为零是判断接收矢量为零是判断接收矢量y(x)是否有是否有错的关键，称错的关键，称s(x)为伴随式多项为伴随式多项式。式。又因为又因为y(x)=c(x)+e(x)，c(x)=q2(x)g(x)所以有所以有s(x)=e(x)(mod g(x)式表示伴随式多式表示伴随式多项式在模项式在模g(x)下与错误图样多项下与错误图样多项式相同，并且可以式相同，并且可以(ky)由一个由一个除法电路来计算。除法电路来计算。第91页/共159页第九十二页，共159页。定理定理(dngl)s(x)是接收是接收矢量矢量y的多项式的多项式y(x)的伴随式，的伴随式，s

19、(1)(x)是是Ly的多项式的多项式Ly(x)的伴随的伴随式，那么式，那么 s(1)(x)=xs(x)(mod g(x)证明由式，证明由式，有有s(x)=y(x)(mod g(x)于是可得于是可得xs(x)=xy(x)(mod g(x)第92页/共159页第九十三页，共159页。又因为又因为Ly(x)=xy(x)(mod(xn1)联合式和式，在模联合式和式，在模g(x)下下Ly(x)的伴随式为的伴随式为s(1)(x)=xs(x)(mod g(x)一般一般(ybn)地，多项式循地，多项式循环移位后存在关系：环移位后存在关系：s(i)(x)=xis(x)(modg(x)(i=1，2，n1)定理表明

20、接定理表明接收矢量多项式在模收矢量多项式在模xn1下的循下的循环移位与伴随式在模环移位与伴随式在模g(x)下的循下的循环移位是一一对应的。环移位是一一对应的。第93页/共159页第九十四页，共159页。有了以上的准备，现在有了以上的准备，现在(xinzi)可以讨论循环码的译可以讨论循环码的译码电路了。循环码的译码电路主码电路了。循环码的译码电路主要由三部分组成要由三部分组成(见图见图3.9)：伴随伴随式计算电路、错误图样计算电路式计算电路、错误图样计算电路以及接收矢量移位寄存器和纠错以及接收矢量移位寄存器和纠错电路。为便于理解，以纠正一个电路。为便于理解，以纠正一个错误的循环码为例来说明。当且

21、错误的循环码为例来说明。当且仅当错误是可纠正，并且出错位仅当错误是可纠正，并且出错位恰好位于错误图样的最高位时，恰好位于错误图样的最高位时，错误图样计算电路输出信号错误图样计算电路输出信号“1”，并由纠错电路纠错；相，并由纠错电路纠错；相反，如果输出的信号是反，如果输出的信号是“0”，则认为最高位是正确的。对于错则认为最高位是正确的。对于错误不在最高位的情况，通过码组误不在最高位的情况，通过码组和伴随式同时循环移位，使错误和伴随式同时循环移位，使错误移至最高位来纠错。移至最高位来纠错。第94页/共159页第九十五页，共159页。n n图 3.9循环码的译码电路(dinl)第95页/共159页第

22、九十六页，共159页。例由生成多项式例由生成多项式g(x)=x4+x3+x2+1产生产生(7，3)循循环码发送码字环码发送码字c=(0111010)，接收，接收矢量为矢量为y=(0110010)，完成译码。，完成译码。解解(1)译码电路见图译码电路见图3.10。移位寄存器移位寄存器D6D0储存接收矢量储存接收矢量y；移位寄存器；移位寄存器T3T0 计算伴随计算伴随式；非门和与门检测式；非门和与门检测(jin c)错错误图样。当误图样。当T3T0输出输出(1110)时，时，与门输出与门输出“1”，因为接收矢量，因为接收矢量y的多项式的多项式y(x)=x5+x4+x，所以接，所以接收矢量收矢量y对

23、应的伴随式多项式对应的伴随式多项式s(x)=y(x)(modg(x)=x3，其中伴其中伴随式是随式是(1000)，只有当接收矢量，只有当接收矢量为为(1111010)时，即错误图样为时，即错误图样为(1000000)，对应的伴随式，对应的伴随式多项式为多项式为x3+x2+x，其伴随式才，其伴随式才是是(1110)。既然图。既然图3.9中伴随式检中伴随式检测测(jin c)电路不是针对接收矢电路不是针对接收矢量量y=(0110010)而设计的，而设计的，第96页/共159页第九十七页，共159页。为什么本电路仍然能完成纠错呢为什么本电路仍然能完成纠错呢？其原因？其原因(yunyn)在于在于(7，

24、3)循循环码的全部错误图样与伴随式有环码的全部错误图样与伴随式有一一对应的循环移位，即使以一一对应的循环移位，即使以(1110)来设计伴随式检测电路，来设计伴随式检测电路，经过经过4次循环移位也能找到伴随次循环移位也能找到伴随式式(1000)，见表，见表3.8。表。表3.8告诉我告诉我们，以任意伴随式设计伴随式检们，以任意伴随式设计伴随式检测电路，经过循环后伴随式计算测电路，经过循环后伴随式计算电路一定能找到所对应的伴随式，电路一定能找到所对应的伴随式，并由伴随式检测电路输出纠错信并由伴随式检测电路输出纠错信号，纠正错误。号，纠正错误。第97页/共159页第九十八页，共159页。n n图 3.

25、10例的译码电路(dinl)第98页/共159页第九十九页，共159页。表表3.8例的全部错误图样与伴随例的全部错误图样与伴随(bn su)式的循环移位式的循环移位第99页/共159页第一百页，共159页。(2)电路工作原理如下：电路工作原理如下：门门1和门和门2开，各移位寄存开，各移位寄存器清零。器清零。门门1关，门关，门2开。接收开。接收(jishu)矢量矢量y=(0110010)送入移送入移位寄存器位寄存器D6D0和和T3T0，每送，每送一个码元，伴随式计算电路计算一个码元，伴随式计算电路计算一次伴随式，各移位寄存器的状一次伴随式，各移位寄存器的状态见表态见表3.9。当接收。当接收(ji

26、shu)矢矢量全部输入后，由于伴随式非量全部输入后，由于伴随式非(0000)，故认为有错，但伴随式，故认为有错，但伴随式也不为也不为(1110)，故需要继续查错。，故需要继续查错。第100页/共159页第一百零一页，共159页。门门1开，门开，门2关。一方面移关。一方面移位寄存器位寄存器D6D0的内容移入输出的内容移入输出端，另一方面伴随式计算电路在端，另一方面伴随式计算电路在无输入自循环。由表无输入自循环。由表3.9可以看出，可以看出，当第当第10个时钟结束后，伴随式输个时钟结束后，伴随式输出为出为(1110)，第，第11个脉冲到来时，个脉冲到来时，与门输出与门输出“1”，D6输出输出“0”

27、，输出端被输入输出端被输入“1+0=1”，刚好，刚好纠正接收矢量产生纠正接收矢量产生(chnshng)的错误，同时，伴随式寄存器被的错误，同时，伴随式寄存器被全部清零。全部清零。D6D0的内容继续移的内容继续移入输入端，到全部矢量移完为止。入输入端，到全部矢量移完为止。门门1和门和门2开，各移位寄存开，各移位寄存器清零，准备译出下一接收矢量。器清零，准备译出下一接收矢量。第101页/共159页第一百零二页，共159页。表表3.9图图3.10 译码电路的工作译码电路的工作(gngzu)过程过程第102页/共159页第一百零三页，共159页。3.43.4BCHBCH码码码码BCHBCH码的定义及最

28、小汉明距离码的定义及最小汉明距离码的定义及最小汉明距离码的定义及最小汉明距离定义设定义设定义设定义设mm是一正整数，是一正整数，是一正整数，是一正整数，m0m0是任意整数，是任意整数，是任意整数，是任意整数，GF(q)GF(q)表示有表示有表示有表示有q q个元素个元素个元素个元素(yun s)(yun s)的有限域，其中的有限域，其中的有限域，其中的有限域，其中q q是一个素数或素数的幂，是一个素数或素数的幂，是一个素数或素数的幂，是一个素数或素数的幂，GF(qm)GF(qm)是是是是GF(q)GF(q)的扩域，的扩域，的扩域，的扩域，a aGF(qm)GF(qm)，如果一个循环码由，如果一

29、个循环码由，如果一个循环码由，如果一个循环码由GF(q)GF(q)上的多项式上的多项式上的多项式上的多项式g(x)g(x)生成，生成，生成，生成，并且并且并且并且g(x)g(x)的根包含下面的根包含下面的根包含下面的根包含下面d-1d-1个根：个根：个根：个根：a a，a 2 a 2，a 3 a 3，a d a d1 1 那么，称这个由那么，称这个由那么，称这个由那么，称这个由g(x)g(x)生成的循环码为设计距离为生成的循环码为设计距离为生成的循环码为设计距离为生成的循环码为设计距离为d d的的的的q q元元元元BCHBCH码。码。码。码。第103页/共159页第一百零四页，共159页。如果

30、定义中如果定义中g(x)有一个根是有一个根是GF(qm)中的本原元，那么中的本原元，那么g(x)生生成的成的BCH码码长必定为码码长必定为n=qm1，称这种，称这种BCH码为本原码为本原BCH码，码，否则称为非本原否则称为非本原BCH码。非本原码。非本原BCH码是存在的，其码长是码是存在的，其码长是qm1的因子，本书不讨论这种情况。的因子，本书不讨论这种情况。BCH码的优势码的优势(yush)之一之一在于，如果确定了在于，如果确定了BCH码的生成码的生成多项式多项式g(x)的连续根，则由的连续根，则由g(x)生成的生成的BCH码的实际最小汉明距码的实际最小汉明距离不小于设计距离。离不小于设计距

31、离。第104页/共159页第一百零五页，共159页。定理定理BCH码的最小汉明距码的最小汉明距离至少为离至少为d。证明因为证明因为BCH码为一循环码为一循环码，所以任意码字多项式码，所以任意码字多项式c(x)必必定是生成多项式定是生成多项式g(x)的倍数的倍数(bish)，即存在多项式，即存在多项式q(x)满满足足c(x)=q(x)g(x)。设码字多项式。设码字多项式c(x)为为c(x)=cn1xn1+cn2xn2+c1x+c0 将生成多项式将生成多项式g(x)的连续的连续d1个个根式代入式，得到方程组根式代入式，得到方程组第105页/共159页第一百零六页，共159页。写成矩阵写成矩阵(j

32、zhn)形式，有形式，有HcT=0T 式中：式中：c=(cn1，cn2，c1，c0)第106页/共159页第一百零七页，共159页。由式知，式的矩阵由式知，式的矩阵H是是g(x)生成的生成的BCH码的校验矩阵。根据码的校验矩阵。根据定理，只需证明定理，只需证明H中任意中任意d1列列线性无关线性无关(wgun)，那么这个，那么这个BCH码的最小距离至少为码的最小距离至少为d。用反证法。假设用反证法。假设H中中i1，i2，id1列线性相关，即存在不列线性相关，即存在不全为零的全为零的l1，l2，ld1使使第107页/共159页第一百零八页，共159页。设设BCH码的生成多项式码的生成多项式g(x)

33、为为g(x)=gnkxnk+gnk1xnk1+g1x+g0同样，由于同样，由于g(x)，xg(x)，x2g(x)，xk1g(x)为为BCH码的一组码的一组基，因此基，因此(ync)BCH码的生成矩码的生成矩阵为阵为第108页/共159页第一百零九页，共159页。BCH码的编码方法码的编码方法1.二元二元BCH码码二元信号在工程上最容易实二元信号在工程上最容易实现，因而二元现，因而二元 BCH码在工程上码在工程上应用最广泛。对给定的正整数应用最广泛。对给定的正整数m和和d(d=2t+1，t2，称，称GF(q)上码长上码长n=q1的本原的本原BCH码为码为RS码。码。最小汉明距离至少为最小汉明距离

34、至少为d的的RS码的生成多项式为码的生成多项式为g(x)=(xa)(xa 2)(xa d1)例设例设q=23，a GF(q)且且是一本原元，是一本原元，a是多项式是多项式x3+x+1的根，求最小汉明距离至少为的根，求最小汉明距离至少为5的的RS码的生成矩阵和校验矩阵。码的生成矩阵和校验矩阵。第117页/共159页第一百一十八页，共159页。解因为解因为(yn wi)要求要求RS码码的最小汉明距离至少为的最小汉明距离至少为5，所以，所以应选应选a，a 2，a3，a4为生成多项为生成多项式的根，即式的根，即g(x)=(xa)(xa2)(xa3)(xa4)=x4+a3x3+x2+ax+a3根据式，根

35、据式，RS码的校验矩阵为码的校验矩阵为第118页/共159页第一百一十九页，共159页。根据根据(gnj)式，式，RS码的校码的校验矩阵为验矩阵为第119页/共159页第一百二十页，共159页。BCH码的译码方法码的译码方法1.一般一般(ybn)译码方法译码方法设发送端发送码字多项式为设发送端发送码字多项式为c(x)=cn1xn1+cn2xn2+c1x+c0接收端接收的矢量多项式为接收端接收的矢量多项式为y(x)=rn1xn1+rn2xn2+r1x+r0产生的错误图样多项式为产生的错误图样多项式为e(x)=en1xn1+en2xn2+e1x+e0第120页/共159页第一百二十一页，共159页

36、。假定共产生了假定共产生了v个错误，即个错误，即错误的图样在错误的图样在x的的l1,l2，lv次次幂处不为零。幂处不为零。式表明式表明(biomng)接收矢量接收矢量y的的出错，如果接收端能确出错，如果接收端能确定出错位置及错误值，用定出错位置及错误值，用y(x)e(x)不难将错误纠正。为方便，不难将错误纠正。为方便，常称常称为错误位置。为了确为错误位置。为了确定错误位置及错误值，需要计算定错误位置及错误值，需要计算伴随式和错位多项式。伴随式和错位多项式。第121页/共159页第一百二十二页，共159页。1)BCH码的伴随码的伴随(bn su)式式BCH码的伴随码的伴随(bn su)式仍式仍然

37、是校验矩阵与接收矢量的乘积，然是校验矩阵与接收矢量的乘积，设设d=2t+1，由式有，由式有第122页/共159页第一百二十三页，共159页。令令，则式可简化为，则式可简化为第123页/共159页第一百二十四页，共159页。将式写成方程组形式将式写成方程组形式(xngsh)，有，有第124页/共159页第一百二十五页，共159页。2)BCH码的错误位置多项式码的错误位置多项式定义定义(dngy)设设BCH码可码可以纠正以纠正t个错误，称多项式个错误，称多项式为错误位置多项式。式中，为错误位置多项式。式中，Xi与与i(i=1，2，t)间满足：间满足：第125页/共159页第一百二十六页，共159页

38、。很明显，错误位置多项式的很明显，错误位置多项式的根刚好根刚好(gngho)是错误位置数是错误位置数Xi(i=1，2，t)的倒数，即的倒数，即 ，更清楚地，有，更清楚地，有将式两边同时乘以将式两边同时乘以，得，得第126页/共159页第一百二十七页，共159页。将式两边再同时将式两边再同时(tngsh)乘以乘以(i=1，2，t)，得，得当当i取遍取遍1，2，t时，式有时，式有t个个方程，将这方程，将这t个方程加在一起，得个方程加在一起，得到到第127页/共159页第一百二十八页，共159页。将式代入式，有将式代入式，有将式写成方程组形式将式写成方程组形式(xngsh)，即，即第128页/共15

39、9页第一百二十九页，共159页。将伴随式将伴随式Si(i=1，2，2t)视为已知数，视为已知数，i(i=1，2，2t)视为未知数，式是含有视为未知数，式是含有t个未知数个未知数t个方程的线性方程组，这个方程个方程的线性方程组，这个方程组有唯一组有唯一(wi y)一组解的充要条一组解的充要条件是系数矩阵应当是满秩的。为件是系数矩阵应当是满秩的。为方便，将式写成矩阵形式，即方便，将式写成矩阵形式，即第129页/共159页第一百三十页，共159页。下述定理保证方程组有唯一下述定理保证方程组有唯一(wi y)一组解。一组解。定理如果定理如果Sj(j=1，2，t)是由是由t个不同的非零数对个不同的非零数

40、对(Yi，Xi)组成的，那么矩阵组成的，那么矩阵是满秩矩阵，否则为非满秩矩阵。是满秩矩阵，否则为非满秩矩阵。第130页/共159页第一百三十一页，共159页。根据求解线性方程组的克莱根据求解线性方程组的克莱姆法则，下面三种简单情况能直姆法则，下面三种简单情况能直接求出方程组的解。接求出方程组的解。第一种情况：产生第一种情况：产生1个错误个错误(cuw)。由式，得由式，得S11=S2所以，错误所以，错误(cuw)位置多项式位置多项式为为(x)=1(S2/S1)x第二种情况：产生第二种情况：产生2个错误个错误(cuw)。由式，得到线性方程为由式，得到线性方程为第131页/共159页第一百三十二页，

41、共159页。于是于是(ysh)，有解，有解所以，错误位置多项式为所以，错误位置多项式为(x)=1+1x+2x2第132页/共159页第一百三十三页，共159页。第三种情况：产生第三种情况：产生3个错误。个错误。根据式，得到线性方程根据式，得到线性方程(xin xn fn chn)为为于是，有解于是，有解第133页/共159页第一百三十四页，共159页。，第134页/共159页第一百三十五页，共159页。所以，错误位置多项式为所以，错误位置多项式为(x)=1+1x+2x2+3x3获得错误位置多项式后可以获得错误位置多项式后可以用试探法寻找错误位置多项式的用试探法寻找错误位置多项式的根。遗憾的是，

42、随着错误数的增根。遗憾的是，随着错误数的增加，直接加，直接(zhji)求解线性方程组求解线性方程组变得越来越困难。变得越来越困难。第135页/共159页第一百三十六页，共159页。例设例设a是不可约多项式是不可约多项式x4+x+1的根，的根，GF(24)由多项式由多项式x4+x+1生成，查表生成，查表3.10得以得以a，a3，a5为根生成能纠正为根生成能纠正3个错误个错误(cuw)长度为长度为n=15的的(15，5)二二元元BCH码的生成多项式码的生成多项式g(x)=2467，即，即g(x)=x10+x8+x5+x4+x2+x+1。假设接收矢量多项式为假设接收矢量多项式为y(x)=x14+x8

43、，则接收的矢量正确，则接收的矢量正确吗？如有错，请纠正。吗？如有错，请纠正。解解(1)求解本例需要用求解本例需要用x4+x+1所产生的有限域的元素，所产生的有限域的元素，为方便，将有限域的元素表列于为方便，将有限域的元素表列于表表3.12。第136页/共159页第一百三十七页，共159页。表表3.12 由由x4+x+1产生产生(chnshng)的有限域的有限域GF(24)第137页/共159页第一百三十八页，共159页。(2)计算接收矢量计算接收矢量(shling)的伴随式。的伴随式。第138页/共159页第一百三十九页，共159页。由表由表3.12，得，得第139页/共159页第一百四十页，

44、共159页。(3)找满秩矩阵找满秩矩阵(j zhn)。因为因为所以所以第140页/共159页第一百四十一页，共159页。(4)找错误位置找错误位置(wi zhi)多多项式。根据式，有项式。根据式，有所以，错误位置所以，错误位置(wi zhi)多项式多项式为为(x)=1+6x+7x2第141页/共159页第一百四十二页，共159页。(5)找错误位置。因为找错误位置。因为 ()=1+6+72=1+7+9=0(7)=1+67+714=1+13+6=0所以所以(suy)，错误位置多项式，错误位置多项式有根有根于是，找到错误位置，即于是，找到错误位置，即第142页/共159页第一百四十三页，共159页。

45、由式，得错误由式，得错误(cuw)图样图样多项式为多项式为e(x)=x14+x8(6)纠正错误纠正错误(cuw)：发送：发送的码字为的码字为c(x)=y(x)e(x)=0即发送的码字是即发送的码字是c=(0，0，0)(15个个0)。第143页/共159页第一百四十四页，共159页。2.二元二元BCH码的译码方法码的译码方法二元二元BCH码的错误位置多项码的错误位置多项式的迭代算法如下。式的迭代算法如下。假设假设(jish)已经迭代出第已经迭代出第n步的错误位置多项式：步的错误位置多项式：第第n+1步迭代如下：步迭代如下：(1)如果如果dn=0，那么，那么(n+1)(x)=(n)(x)，ln+1

46、=ln。(2)如果如果dn0，那么在第，那么在第1/2，0，1，n1次迭代中找次迭代中找出一次迭代出一次迭代m，满足，满足2mlm 最最大且大且dm0，然后更新下列公式：，然后更新下列公式：第144页/共159页第一百四十五页，共159页。继续迭代继续迭代n+2步，直到迭代步，直到迭代出出(t)(x)为止。为止。(t)(x)就是所求就是所求的错误位置的错误位置(wi zhi)多项式多项式(x)。如果如果deg(x)t，则表示发生了，则表示发生了t个以上的错误，无法纠正；否则，个以上的错误，无法纠正；否则，纠正错误。纠正错误。第145页/共159页第一百四十六页，共159页。迭代算法初始值。迭代

47、算法初始值。每次迭代需要前两步迭代后每次迭代需要前两步迭代后的结果，为方便的结果，为方便(fngbin)，选，选迭代次数以迭代次数以1/2开始，即开始，即n=1/2，1/2(x)=1，d1/2=1，l1/2=0，2nl1/2=1n=0，0(x)=1，d0=S1，l0=0，2nl0=0迭代算法流程图见图迭代算法流程图见图3.11。第146页/共159页第一百四十七页，共159页。n n图 3.11错误(cuw)位置多项式迭代算法流程图第147页/共159页第一百四十八页，共159页。例题设同于例，用迭代算例题设同于例，用迭代算法求出错误法求出错误(cuw)位置多项式。位置多项式。解解(1)计算伴

48、随式。由式计算伴随式。由式知，伴随式分别为知，伴随式分别为S1=6，S2=12，S3=8，S4=9，S5=0，S6=(2)迭代求解错误迭代求解错误(cuw)位位置多项式。初始值：置多项式。初始值：n=1/2，1/2(x)=1，d1/2=1，l1/2=0，2nl1/2=1 n=0，(0)(x)=1，d0=S1=6，l0=0，2nl0=0第一次迭代第一次迭代(n=0)：因为：因为d0=60，所以，选，所以，选m=1/2，得到得到第148页/共159页第一百四十九页，共159页。第二次迭代第二次迭代(n=1)：因为：因为(yn wi)d1=130，所以，选，所以，选m=0，得得第149页/共159页

49、第一百五十页，共159页。第三次迭代第三次迭代(n=2)：因为：因为d2=0，所以，所以(3)(x)=(2)(x)=1+6x+7x2，l3=l2=2因为因为(3)(x)已算出，所以迭已算出，所以迭代结束，错误位置多项式为代结束，错误位置多项式为(x)=(3)(x)=1+6x+7x2这一结果相同于例。迭代算这一结果相同于例。迭代算法很适合法很适合(shh)于计算机编程于计算机编程实现，特别是对码长较大和纠错实现，特别是对码长较大和纠错能力较强的能力较强的BCH更为有效。为方更为有效。为方便读者理解，例的迭代过程见表便读者理解，例的迭代过程见表3.13。第150页/共159页第一百五十一页，共15

50、9页。表表3.13 例的错误例的错误(cuw)位置多项式迭代过程位置多项式迭代过程第151页/共159页第一百五十二页，共159页。习题习题习题习题3 31.1.证明式。证明式。证明式。证明式。2.2.已知一个码的全部已知一个码的全部已知一个码的全部已知一个码的全部(qunb)(qunb)码字如下：码字如下：码字如下：码字如下：(0000000)(0000000)(1101100)(1101100)(1011010)(1011010)(0110110)(0110110)(1110001)(1110001)(1000111)(1000111)(0101011)(0101011)(0011101)