[经济学]第四章 BCH码ppt课件

1、通信工程系挪动通信教研室通信工程系挪动通信教研室信道编码2022-5-4信道编码信道编码2第四章 BCH码4.1 BCH码概述码概述4.2 预备知识：有限域根底预备知识：有限域根底4.3 BCH码的构造码的构造4.4 BCH码的编码码的编码4.5 BCH码的译码码的译码2022-5-4信道编码信道编码34.4 BCH码的编码p由于由于BCHBCH码是循环码的一个子类，因此码是循环码的一个子类，因此BCHBCH码的编码可采用与循环码同样的方法。码的编码可采用与循环码同样的方法。n编码方程编码方程实际应用中，通常采用系统码形式。实际应用中，通常采用系统码形式。其编码方程为：其编码方程为：C Cx

2、x=x=xn-kn-km mx x+x+xn-kn-km mx x Mod gMod gx x2022-5-4信道编码信道编码4p编码电路编码电路实际应用的实际应用的BCHBCH码通常为高码率码码通常为高码率码实现中采用实现中采用n-kn-k级编码电路级编码电路DDD门m(x)C(x)k+1n1k1kgr-1g14.4 BCH码的编码2022-5-4信道编码信道编码5第四章 BCH码4.1 BCH码概述码概述4.2 预备知识：有限域根底预备知识：有限域根底4.3 BCH码的构造码的构造4.4 BCH码的编码码的编码4.5 BCH码的译码码的译码2022-5-4信道编码信道编码64.5 BCH码

3、的译码pBCHBCH码是循环码，可以采用循环码译码方法，但是码是循环码，可以采用循环码译码方法，但是当纠错才能当纠错才能t t增大，循环码译码器的复杂性迅速增增大，循环码译码器的复杂性迅速增加加n=63n=63 N1 N1没有考虑循环移位特性需识别的错误图样个数没有考虑循环移位特性需识别的错误图样个数 N2N2考虑循环移位特性需识别的错误图样个数考虑循环移位特性需识别的错误图样个数t1234N163201641727637392N2163195439774tiinN1211tiinN112022-5-4信道编码信道编码74.5 BCH码的译码pBCHBCH码是循环码，可以采用循环码译码方法，但

4、是码是循环码，可以采用循环码译码方法，但是当纠错才能当纠错才能t t增大，循环码译码器的复杂性迅速增增大，循环码译码器的复杂性迅速增加；加；p19601960年，彼得森年，彼得森PetersonPeterson提出了二元提出了二元BCHBCH码译码译码码；不久戈伦斯坦；不久戈伦斯坦GorenstienGorenstien和齐尔勒和齐尔勒ZierlerZierler将其推广到多进制情况；将其推广到多进制情况；p19681968年，伯利坎普年，伯利坎普BerlekampBerlekamp首次提出了迭代首次提出了迭代译码算法；译码算法；p19751975年，提出了欧几里德法译码等。年，提出了欧几里德

5、法译码等。2022-5-4信道编码信道编码84.5 BCH码的译码pBCHBCH码译码的一般原理码译码的一般原理假设假设：n,k,dn,k,dBCHBCH码以码以,2 2,2t2t为根，为根，d=2t+1d=2t+1C Cx x=c=cn-1n-1x xn-1n-1+c+cn-2n-2x xn-2n-2+c+c1 1x+cx+c0 0R Rx x=r=rn-1n-1x xn-1n-1+r+rn-2n-2x xn-2n-2+r+r1 1x+rx+r0 0E Ex x=e=en-1n-1x xn-1n-1+e+en-2n-2x xn-2n-2+e+e1 1x+ex+e0 0传输中产生传输中产生e

6、e e te t个错误个错误 那么：那么：E Ex x=x=xL1L1+x+xL2L2+x+xLeLe伴随式译码步骤伴随式译码步骤1 根据根据Rx计算伴随计算伴随式式S；2S-Ex；3 Cx=Rx+Ex2022-5-4信道编码信道编码9pBCHBCH码译码的一般原理码译码的一般原理1 1、计算伴随式：、计算伴随式：S ST T=HE=HET T=HR=HRT T0212)2(2) 1(22)2(2) 1(221221.1.1.1.rrrsssnntntntnnnnt那么：那么：s si i = R = R i i i=1,2,2t i=1,2,2t4.5 BCH码的译码2022-5-4信道编码

7、信道编码104.5 BCH码的译码pBCHBCH码译码的一般原理码译码的一般原理2 2、求解错误位置、求解错误位置L L1 1,L,L2 2,L,Le e由由S ST T=HE=HET T可得：可得： s si i= =i iL L1 1+ +i iL L2 2+i iL Le e = =L L1 1i i + +L L2 2i i +L Le ei i i=1,2,2ti=1,2,2t令：令：x xj j=L Lj j表示错误位置，表示错误位置，j=1,2,ej=1,2,e那么：那么：s si i = =x x1 1i i + +x x2 2i i +x xe ei i 可得到含有可得到含有

8、e e个未知数、个未知数、2t2t个方程的高次方程组。个方程的高次方程组。0212)2(2)1(22)2(2)1(221221.1.1.1.eeesssnntntntnnnnt只有L1,L2,Le位置为1E(x)=xE(x)=xL1L1+x+xL2L2+x+xLeLe2022-5-4信道编码信道编码11pBCH码译码的一般原理码译码的一般原理si =x1i +x2i +xei ,i=1,2,2tttetteesssxxxxxxxxx221222212222121.我们的目的是求解我们的目的是求解e e个错误位置个错误位置x x1 1,x,x2 2,x,xe e但直接求解该高次方程组是极其困难的

9、但直接求解该高次方程组是极其困难的4.5 BCH码的译码xj=Lj Lj表示错误位置，表示错误位置，j=1,2,e2022-5-4信道编码信道编码124.5 BCH码的译码pBCHBCH码译码的一般原理码译码的一般原理为此我们引入错误位置多项式为此我们引入错误位置多项式x x： x x= =1-x1-x1 1x x1-x1-x2 2x x1-x1-xe ex x =1+ =1+1 1x+x+2 2x x2 2+e ex xe ex=xx=xk k-1-1 k=1,2,ek=1,2,e 为为x x的根的根因此求错误位置转化为求因此求错误位置转化为求x x的根的根, ,先求先求x x即求即求1 1

10、, , 2 2 ,e e，然后求，然后求x x的根的根将将x=xx=xk k-1-1代入代入x x得：得： 1+ 1+ 1 1x xk k-1-1+2 2x xk k-2-2+e ex xk k-e-e=0=02022-5-4信道编码信道编码134.5 BCH码的译码pBCHBCH码译码的一般原理码译码的一般原理方程两边乘以方程两边乘以x xk ke+je+j j=1,2,e j=1,2,e x xk ke+je+j + +1 1x xk ke+j-1e+j-1+2 2x xk ke+j-2e+j-2+e ex xk kj j=0=0该方程对该方程对k=1,2,ek=1,2,e均成立均成立将上

11、述方程对将上述方程对k k求和，并对照：求和，并对照：可得：可得：s sj+ej+e+1 1s sj+e-1j+e-1+e es sj j=0=0其中：其中：j=1,2,ej=1,2,eekikieiiixxxxs121.1+ 1xk-1+2xk-2+exk-e=02022-5-4信道编码信道编码144.5 BCH码的译码pBCHBCH码译码的一般原理码译码的一般原理将将e e个方程写成方程组形式为：个方程写成方程组形式为：eeeeeeeeeeeeessssssssssss22221122221111211.其中：e = 1,2,te2-2e1 -2e2e1e11 - eeexes.ss.s.

12、sss.ssM系数矩 阵sj+e+1sj+e-1+esj=0 j=1,2,e2022-5-4信道编码信道编码154.5 BCH码的译码pBCHBCH码译码的一般原理码译码的一般原理 因此求解错误位置的问题转化成为解线性方程因此求解错误位置的问题转化成为解线性方程组的问题。组的问题。n求出系数求出系数K K得到错误位置多项式得到错误位置多项式x x ；n再求再求x x的根的根x x；n根据根据x=xx=xk k-1-1，求出，求出x xk kn由由x xk k=LkLk，得到，得到L Lk k，即知道错误发生的位置，即知道错误发生的位置E EC C 2022-5-4信道编码信道编码164.5 B

13、CH码的译码pBCHBCH码译码的一般原理码译码的一般原理 因此求解错误位置的问题转化成为解线性方程组的问题。因此求解错误位置的问题转化成为解线性方程组的问题。 定理定理 ：设：设s sj j j=1,2,2tj=1,2,2t是设计纠错才能为是设计纠错才能为t t的二元的二元BCHBCH码接收码字码接收码字r rx x的伴随式，假如的伴随式，假如r rx x的错误个数的错误个数等于等于e e，那么方程组有唯一解，即系数矩阵为非奇异矩阵；，那么方程组有唯一解，即系数矩阵为非奇异矩阵；假如错误个数小于假如错误个数小于e e，那么方程组的系数矩阵为奇异矩阵。，那么方程组的系数矩阵为奇异矩阵。eeee

14、eeeeeeeeessssssssssss22221122221111211.2022-5-4信道编码信道编码174.5 BCH码的译码pBCHBCH码译码的一般原理码译码的一般原理方程组的求解：方程组的求解：由于错误个数由于错误个数e e是未知的，可先假设是未知的，可先假设e=te=t计算系数矩阵计算系数矩阵M Mexeexe的行列式值的行列式值|M|Mexeexe| |假如假如|M|Mexeexe|=0|=0，方程组降阶，方程组降阶e=e-1e=e-1并转第并转第步；假如步；假如|M|Mexeexe|0|0，那么解方程组求得错误，那么解方程组求得错误位置多项式的系数位置多项式的系数1 1,

15、2 2,e e e e为实际为实际错误个数错误个数e2-2e1 -2e2e1e11 -eeexes.ss.s.sss.ssM系数矩阵2022-5-4信道编码信道编码184.5 BCH码的译码pBCHBCH码译码的一般原理码译码的一般原理n通过求解方程组得到错误位置多项式：通过求解方程组得到错误位置多项式： x x=1+=1+1 1x+x+2 2x x2 2+e ex xe ex x的根的根x xk k-1-1即代表错误位置即代表错误位置x xk k=L Lk kn采用试根法求解错误位置多项式采用试根法求解错误位置多项式x x的根：的根： x x一共有一共有e e个根，可能值为个根，可能值为,2

16、 2,n n将将,2 2,n n分别代入分别代入x x，假如，假如i i=0=0，那么，那么i i为为x x的根，即：的根，即：x xk k= =i i-1-1= =LkLk2022-5-4信道编码信道编码194.5 BCH码的译码pBCHBCH码译码的一般原理码译码的一般原理于是可得到：于是可得到：E Ex x=x=xL1L1+x+xL2L2+x+xLeLe那么接收多项式那么接收多项式R Rx x的估值码字为：的估值码字为： C C x x=R=Rx x+E+Ex x上述译码原理上述译码原理19601960年由年由PetersonPeterson提出，因此称为提出，因此称为PetersonP

17、eterson译码原理。译码原理。2022-5-4信道编码信道编码204.5 BCH码的译码pBCHBCH码译码的一般原理码译码的一般原理nPetersonPeterson译码举例：译码举例： 15,5,715,5,7二元二元BCHBCH码以码以, , 3 3, , 5 5为根，接收矢量为根，接收矢量R Rx x=x=x1010+x+x3 3，求估值，求估值码字码字C C x x。这里。这里是是p px x=x=x4 4+x+1+x+1的的根。根。首先计算伴随式：首先计算伴随式： s s i i = R = R i i2022-5-4信道编码信道编码214.5 BCH码的译码扩域扩域GF24及

18、非零元素的阶：及非零元素的阶：元素元素 多项式多项式 阶阶 元素元素 多项式多项式 阶阶 0 0 7 3+1 15 1 1 1 8 2+1 15 15 9 3+ 5 2 2 15 10 2+1 3 3 3 5 11 3+2+ 15 4 +1 15 12 3+2+1 5 5 2+ 3 13 3+2+1 15 6 3+2 5 14 3+1 152022-5-4信道编码信道编码224.5 BCH码的译码pBCH码译码的一般原理码译码的一般原理nPeterson译码举例：译码举例： s1= 10+ 3= 12 s2=s12=122= 9 s3= 30+ 9= 7 s4=s22=92= 3 s5= 50

19、+ 15= 10 s6=s32=72= 140 0 7 3+11 1 8 2+1 9 3+2 2 10 2+1 3 3 11 3+2+4 +1 12 3+2+15 2+ 13 3+2+16 3+2 14 3+1s si i = R = R i i2022-5-4信道编码信道编码234.5 BCH码的译码pBCHBCH码译码的一般原理码译码的一般原理nPetersonPeterson译码举例：译码举例：根据求得的伴随式构造方程组：根据求得的伴随式构造方程组： 设设e=t=3e=t=3654321345234123sssssssssssseeeeeeeeeeeeessssssssssss22221

20、122221111211.2022-5-4信道编码信道编码244.5 BCH码的译码pBCHBCH码译码的一般原理码译码的一般原理nPetersonPeterson译码举例：译码举例：计算系数矩阵计算系数矩阵M M的行列式的值：的行列式的值：73109731297345234123sssssssssM 计算得计算得：|M| = 00 0 7 3+11 1 8 2+1 9 3+2 2 10 2+1 3 3 11 3+2+4 +1 12 3+2+15 2+ 13 3+2+16 3+2 14 3+12022-5-4信道编码信道编码254.5 BCH码的译码pBCHBCH码译码的一般原理码译码的一般原理nPetersonPeterson译码举例：译码举例：可见实际错误个数可见实际错误个数et=3eES-Ex x；错误位置多项式错误位置多项式x x= =1-x1-x1 1x x1-x1-x2 2x x1-x1-xe ex x= = 1+1+1 1x+x+2 2x x2