第四章-BCH码3课件.ppt

1、4/27/2023信道编码信道编码1第四章 BCH码4.1 BCH码概述码概述4.2 预备知识：有限域基础预备知识：有限域基础4.3 BCH码的构造码的构造4.4 BCH码的编码码的编码4.5 BCH码的译码码的译码4/27/2023信道编码信道编码24.4 BCH码的编码p由于由于BCHBCH码是循环码的一个子类，因此码是循环码的一个子类，因此BCHBCH码的编码可采用与循环码同样的方法。码的编码可采用与循环码同样的方法。n编码方程实际应用中，通常采用系统码形式。其编码方程为：C(x)=xn-km(x)+xn-km(x)Mod g(x)4/27/2023信道编码信道编码3p编码电路编码电路实

2、际应用的BCH码通常为高码率码实现中采用n-k级编码电路DDD门m(x)C(x)k+1n1k1kgr-1g14.4 BCH码的编码4/27/2023信道编码信道编码4第四章 BCH码4.1 BCH码概述码概述4.2 预备知识：有限域基础预备知识：有限域基础4.3 BCH码的构造码的构造4.4 BCH码的编码码的编码4.5 BCH码的译码码的译码4/27/2023信道编码信道编码54.5 BCH码的译码pBCHBCH码是循环码，可以采用循环码译码方法，但是码是循环码，可以采用循环码译码方法，但是当纠错能力当纠错能力t t增大，循环码译码器的复杂性迅速增增大，循环码译码器的复杂性迅速增加加n=63

3、n=63 N1 N1没有考虑循环移位特性需识别的错误图样个数没有考虑循环移位特性需识别的错误图样个数 N2N2考虑循环移位特性需识别的错误图样个数考虑循环移位特性需识别的错误图样个数t1234N163201641727637392N2163195439774tiinN1211tiinN114/27/2023信道编码信道编码64.5 BCH码的译码pBCHBCH码是循环码，可以采用循环码译码方法，但是码是循环码，可以采用循环码译码方法，但是当纠错能力当纠错能力t t增大，循环码译码器的复杂性迅速增增大，循环码译码器的复杂性迅速增加；加；p19601960年，彼得森年，彼得森(Peterson)(

4、Peterson)提出了二元提出了二元BCHBCH码译码码译码；不久戈伦斯坦不久戈伦斯坦(Gorenstien)(Gorenstien)和齐尔勒和齐尔勒(Zierler)(Zierler)将其推广到多进制情况；将其推广到多进制情况；p19681968年，伯利坎普年，伯利坎普(Berlekamp)(Berlekamp)首次提出了迭代译首次提出了迭代译码算法；码算法；p19751975年，提出了欧几里德法译码等。年，提出了欧几里德法译码等。4/27/2023信道编码信道编码74.5 BCH码的译码pBCHBCH码译码的一般原理码译码的一般原理假设：(n,k,d)BCH码以,2,2t为根，d=2t+

5、1C(x)=cn-1xn-1+cn-2xn-2+c1x+c0R(x)=rn-1xn-1+rn-2xn-2+r1x+r0E(x)=en-1xn-1+en-2xn-2+e1x+e0传输中产生e(e t)个错误 则：E(x)=xL1+xL2+xLe伴随式译码步骤伴随式译码步骤1)根据根据R(x)计算伴随式计算伴随式S；2)S-E(x)；3)C(x)=R(x)+E(x)4/27/2023信道编码信道编码8pBCHBCH码译码的一般原理码译码的一般原理1)、计算伴随式：ST=HET=HRT0212)2(2)1(22)2(2)1(221221.1.1.1.rrrsssnntntntnnnnt则：则：s s

6、i i=R(=R(i i)i=1,2,)i=1,2,2t2t4.5 BCH码的译码4/27/2023信道编码信道编码94.5 BCH码的译码pBCHBCH码译码的一般原理码译码的一般原理2)、求解错误位置(L1,L2,Le)由ST=HET可得：si=(i)L1+(i)L2+(i)Le =(L1)i+(L2)i+(Le)i i=1,2,2t令：xj=Lj表示错误位置，j=1,2,e则：si=(x1)i+(x2)i+(xe)i 可得到含有e个未知数、2t个方程的高次方程组。0212)2(2)1(22)2(2)1(221221.1.1.1.eeesssnntntntnnnnt只有L1,L2,Le位置

7、为1E(x)=xE(x)=xL1L1+x+xL2L2+x+xLeLe4/27/2023信道编码信道编码10pBCH码译码的一般原理码译码的一般原理si=(x1)i+(x2)i+(xe)i ,i=1,2,2tttetteesssxxxxxxxxx221222212222121.我们的目的是求解我们的目的是求解e e个错误位置个错误位置x x1 1,x,x2 2,x,xe e但直接求解该高次方程组是极其困难的但直接求解该高次方程组是极其困难的4.5 BCH码的译码xj=Lj Lj表示错误位置，表示错误位置，j=1,2,e4/27/2023信道编码信道编码114.5 BCH码的译码pBCHBCH码译

8、码的一般原理码译码的一般原理为此我们引入错误位置多项式(x)：(x)=(1-x1x)(1-x2x)(1-xex)=1+1x+2x2+exex=xk-1(k=1,2,e)为(x)的根因此求错误位置转化为求(x)的根,先求(x)(即求1,2,e)，然后求(x)的根将x=xk-1代入(x)得：1+1xk-1+2xk-2+exk-e=04/27/2023信道编码信道编码124.5 BCH码的译码pBCHBCH码译码的一般原理码译码的一般原理方程两边乘以xke+j j=1,2,e xke+j+1xke+j-1+2xke+j-2+exkj=0该方程对k=1,2,e均成立将上述方程对k求和，并对照：可得：s

9、j+e+1sj+e-1+esj=0其中：j=1,2,eekikieiiixxxxs121.1+1xk-1+2xk-2+exk-e=04/27/2023信道编码信道编码134.5 BCH码的译码pBCHBCH码译码的一般原理码译码的一般原理将e个方程写成方程组形式为：eeeeeeeeeeeeessssssssssss22221122221111211.其中：e=1,2,te2-2e1-2e2e1e11-eeexes.ss.s.sss.ssM系数矩 阵sj+e+1sj+e-1+esj=0 j=1,2,e4/27/2023信道编码信道编码144.5 BCH码的译码pBCHBCH码译码的一般原理码译码

10、的一般原理 因此求解错误位置的问题转化成为解线性方程组的问题。n求出系数K得到错误位置多项式(x)；n再求(x)的根x；n根据x=xk-1，求出xkn由xk=Lk，得到Lk，即知道错误发生的位置EC4/27/2023信道编码信道编码154.5 BCH码的译码pBCHBCH码译码的一般原理码译码的一般原理 因此求解错误位置的问题转化成为解线性方程组的问题。定理：设sj(j=1,2,2t)是设计纠错能力为t的二元BCH码接收码字r(x)的伴随式，如果r(x)的错误个数等于e，则方程组有唯一解，即系数矩阵为非奇异矩阵；如果错误个数小于e，则方程组的系数矩阵为奇异矩阵。eeeeeeeeeeeeesss

11、sssssssss22221122221111211.4/27/2023信道编码信道编码164.5 BCH码的译码pBCHBCH码译码的一般原理码译码的一般原理方程组的求解：由于错误个数e是未知的，可先假设e=t计算系数矩阵Mexe的行列式值|Mexe|如果|Mexe|=0，方程组降阶(e=e-1)并转第步；如果|Mexe|0，则解方程组求得错误位置多项式的系数1,2,e(e为实际错误个数)e2-2e1-2e2e1e11-eeexes.ss.s.sss.ssM系数矩阵4/27/2023信道编码信道编码174.5 BCH码的译码pBCHBCH码译码的一般原理码译码的一般原理n通过求解方程组得到错

12、误位置多项式：(x)=1+1x+2x2+exe(x)的根xk-1即代表错误位置(xk=Lk)n采用试根法求解错误位置多项式(x)的根：(x)一共有e个根，可能值为,2,n将,2,n分别代入(x)，如果(i)=0，则i为(x)的根，即：xk=(i)-1=Lk4/27/2023信道编码信道编码184.5 BCH码的译码pBCHBCH码译码的一般原理码译码的一般原理于是可得到：E(x)=xL1+xL2+xLe则接收多项式R(x)的估值码字为：C(x)=R(x)+E(x)上述译码原理1960年由Peterson提出，因此称为Peterson译码原理。4/27/2023信道编码信道编码194.5 BCH

13、码的译码pBCHBCH码译码的一般原理码译码的一般原理nPeterson译码举例：(15,5,7)二元BCH码以,3,5为根，接收矢量R(x)=x10+x3，求估值码字C(x)。这里是p(x)=x4+x+1的根。首先计算伴随式：s i=R(i)4/27/2023信道编码信道编码204.5 BCH码的译码扩域扩域GF(24)及非零元素的阶：及非零元素的阶：元素 多项式 阶 元素 多项式 阶 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 1

14、5 6 3+2 5 14 3+1 154/27/2023信道编码信道编码214.5 BCH码的译码pBCH码译码的一般原理码译码的一般原理nPeterson译码举例：s1=10+3=12 s2=(s1)2=(12)2=9 s3=30+9=7 s4=(s2)2=(9)2=3 s5=50+15=10 s6=(s3)2=(7)2=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 i)4/27/2023信道编码信道编码224.5 BCH码的译码pBCHBCH

15、码译码的一般原理码译码的一般原理nPeterson译码举例：根据求得的伴随式构造方程组：设e=t=3654321345234123sssssssssssseeeeeeeeeeeeessssssssssss22221122221111211.4/27/2023信道编码信道编码234.5 BCH码的译码pBCHBCH码译码的一般原理码译码的一般原理nPeterson译码举例：计算系数矩阵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

16、+15 2+13 3+2+16 3+2 14 3+14/27/2023信道编码信道编码244.5 BCH码的译码pBCHBCH码译码的一般原理码译码的一般原理nPeterson译码举例：可见实际错误个数eE(x)；错误位置多项式(x)=(1-x1x)(1-x2x)(1-xex)=1+1x+2x2+exe求解错误位置多项式的根xi,i=1,2,e由xi-1得到错误位置=E(x)3)C(x)=R(x)+E(x)eeeeeeeeeeeeessssssssssss22221122221111211.4/27/2023信道编码信道编码29pBCHBCH码译码的一般原理码译码的一般原理n将求解错误位置转化

17、为解线性方程组的问题，但当设计纠错能力t较大时,要不断对系数矩阵进行降阶处理，直到求得一个满秩的exe阶方阵为止，因此是非常复杂的运算，实际中较少应用。在理论上解决了(x)的求解问题。nBerlekamp于1968年提出了求解错误位置多项式的迭代算法，从根本上解决了BCH码译码算法的复杂度，得到了广泛的应用。4.5 BCH码的译码4/27/2023信道编码信道编码30p课下作业：课下作业：1 1、画出上次作业中码长、画出上次作业中码长n=15n=15、纠错、纠错能力能力t=2t=2的本原的本原BCHBCH码的码的n-kn-k级编码电路。级编码电路。2 2、书、书P159-5.4P159-5.44.5 BCH码的译码