channelcoding4信道编码第四部分

p1.BCHCodesp2.OUTLINE[1]Finitefields[2]Minimalpolynomials[3]CyclicHammingcodes[4]BCHcodes[5]Decoding2error-correctingBCHcodesp3.BCHCodes[1]Finitefields1.Irreduciblepolynomialf(x)K[x],f(x)hasnoproperdivisorsinK[x]Eg.f(x)=1+x+x2isirreduciblef(x)=1+x+x2+x3=(1+x)(1+x2)isnotirreduciblef(x)=1+x+x4isirreduciblep4.BCHCodes2.Primitivepolynomialf(x)isirreducibleofdegreen1f(x)isnotadivisorof1+xmforanym2n-1Eg.f(x)=1+x+x2isnotafactorof1+xmform3sof(x)isaprimitivepolynomialf(x)=1+x+x2+x3+x4isirreduciblebut1+x5=(1+x)(1+x+x2+x3+x4)andm=524-1=15sof(x)isnotaprimitivepolynomialp5.BCHCodes3.DefinitionofKn[x]ThesetofallpolynomialsinK[x]havingdegreelessthannEachwordinKncorrespondstoapolynomialinKn[x]MultiplicationinKnmoduloh(x),withirreducibleh(x)ofdegreenIfweusemultiplicationmoduloareducibleh(x),say,1+x4todefinemultiplicationofwordsinK4,however:(0101)(0101)(x+x3)(x+x3)=x2+x6=x2+x2(mod1+x4)=00000(K4-{0000}isnotclosedundermultiplication.)p6.BCHCodes4.DefinitionofField(Kn,+,x)(Kn,+)isanabeliangroupwithidentitydenoted0Theoperationxisassociativeax(bxc)=(axb)xcThereisamultiplicativeidentitydenoted1,with101xa=ax1=a,aKnTheoperationxisdistributiveover+ax(b+c)=(axb)+(axc)Itiscommunicativeaxb=bxa,a,bKnAllnon-zeroelementshavemultiplicativeinversesGaloisFields:GF(2r)Foreveryprimepowerorderpm,thereisauniquefinitefieldoforderpmDenotedbyGF(pm)p7.BCHCodesExampleLetusconsidertheconstructionofGF(23)usingtheprimitivepolynomialh(x)=1+x+x3todefinemultiplication.Wedothisbycomputingximodh(x):wordximodh(x)1001010x001x2110x31+x011x4x+x2111x51+x+x2101x61+x2p8.BCHCodes5.UseaprimitivepolynomialtoconstructGF(2n)LetKnrepresentthewordcorrespondingtoxmodh(x)iximodh(x)m1form2n-1sinceh(x)dosenotdivide1+xmform2n-1Sincej=iforjiiffi=j-iij-i=1Kn\{0}={i|i=0,1,…,2n-2}p9.BCHCodes6.GF(2r)isprimitiveisprimitiveifm1for1m2r-1Inotherwords,everynon-zerowordinGF(2r)canbeexpressedasapowerofExampleConstructGF(24)usingtheprimitivepolynomialh(x)=1+x+x4.Writeeveryvectorasapowerofxmodh(x)(seeTable5.1below)Notethat15=1.(0110)(1101)=5.7=12=1111p10.BCHCodesTable1ConstructionofGF(24)usingh(x)=1+x+x4wordpolynomialinxmodh(x)powerof00000-100010=10100x0010x220001x3311001+x=x440110x+x2=x550011x2+x3=x66p11.BCHCodesTable1(continue)ConstructionofGF(24)usingh(x)=1+x+x4wordpolynomialinxmodh(x)powerof11011+x+x3=x7710101+x2=x880101x+x3=x9911101+x+x2=x10100111x+x2+x3=x111111111+x+x2+x3=x121210111+x2+x3=x131310011+x3=x1414p12.BCHCodes[2]Minimalpolynomials1.Rootofapolynomial:anelementofF=GF(2r),p(x)F[x]isarootofapolynomialp(x)iffp()=02.OrderofThesmallestpositiveintegermsuchthatm=1inGF(2r)isaprimitiveelementifithasorder2r-1p13.BCHCodes3.MinimalpolynomialofThepolynomialinK[x]ofsmallestdegreehavingasrootDenotedbym(x)m(x)isirreducibleoverKIff(x)isanypolynomialoverKsuchthatf()=0,thenm(x)isafactoroff(x)m(x)isuniquem(x)isafactorof121rxp14.BCHCodesExampleLetp(x)=1+x3+x4,andletbetheprimitiveelementinGF(24)constructedusingh(x)=1+x+x4(seeTable5.1):p()=1+3+4=1000+0001+1100=0101=9isnotarootofp(x).Howeverp(7)=1+(7)3+(7)4=1+21+28=1+6+13=1000+0011+1011=0000=07isarootofp(x).p15.BCHCodes4.FindingtheminimalpolynomialofReducetofindalinearcombinationofthevectors{1,,2,…,r},whichsumsto0Anysetofr+1vectorsinKrisdependent,suchasolutionexistsRepresentm(x)bymi(x)where=Ieg.Findthem(x),=3,GF(24)constructedusingh(x)=1+x+x4p16.BCHCodesUsefulfacts:f(x)2=f(x2)Iff()=0,thenf(2)=(f())2=0Ifisarootoff(x),soare,2,4,…,Thedegreeofm(x)is|{,2,4,…,}|iniiniiiniiixaxaxa)()()(022022012r12rp17.BCHCodesExampleFindthem(x),=3,GF(24)constructedusingh(x)=1+x+x4Letm(x)=m3(x)=a0+a1x+a2x2+a3x3+a4x4thenwemustfindthevaluefora0,a1,…,a4{0,1}m()=0=a01+a1+a22+a33+a44=a00+a13+a26+a39+a4120000=a0(1000)+a1(0001)+a2(0011)+a3(0101)+a4(1111)a0=a1=a2=a3=a4=1andm(x)=1+x+x2+x3+x4p18.BCHCodesExampleLetm5(x)betheminimalpolynomialsof=5,5GF(24)Since{,2,4,8}={5,10},therootsofm5(x)are5and10whichmeansthatdegree(m5(x))=2.Thusm5(x)=a0+a1x+a2x2:0=a0+a15+a210=a0(1000)+a1(0110)+a2(1110)Thusa0=a1=a2=1andm5(x)=1+x+x2p19.BCHCodesTable2:MinimalpolynomialsinGF(24)constructedusing1+x+x4ElementofGF(24)Minimalpolynomial01,2,4,83,6,9,125,107,11,13,14x1+x1+x+x41+x+x2+x3+x41+x+x21+x3+x4p20.BCHCodes[3]CyclicHammingcodes1.ParitycheckmatrixTheparitycheckmatrixofaHammingcodeoflengthn=2r-1hasitsrowsall2r-1nonzerowordsoflengthrisaprimitiveelementofGF(2r)Histheparitycheckma-trixofaHammingcodeoflengthn=2r-12221rHp21.BCHCodes2.GeneratorpolynomialForanyreceivedwordw=w0w1…wn-1wH=w0+w1+…+wn-1n-1w()wisacodewordiffisarootofw(x)m(x)isitsgeneratorpolynomialTheorem5.3.1AprimitivepolynomialofdegreeristhegeneratorpolynomialofacyclicHammingcodeoflength2r-1p22.BCHCodesExample:Letr=3,son=23-1=7.Usep(x)=1+x+x3toconstructGF(23),and010astheprimitiveelement.Recallthatiximodp(x).ThereforeaparitycheckmatrixforaHammingcodeoflength