channel coding 4信道編碼第四部分

BCHCodesOUTLINE[1]Finitefields[2]Minimalpolynomials[3]CyclicHammingcodes[4]BCHcodes[5]Decoding2error-correctingBCHcodesBCHCodes[1]Finitefields1.Irreduciblepolynomialf(x)K[x],f(x)hasnoproperdivisorsinK[x] Eg. f(x)=1+x+x2isirreducible f(x)=1+x+x2+x3=(1+x)(1+x2)isnotirreducible

f(x)=1+x+x4isirreducibleBCHCodes2.Primitivepolynomialf(x)isirreducibleofdegreen>1f(x)isnotadivisorof1+xmforanym<2n-1 Eg.f(x)=1+x+x2isnotafactorof1+xmform<3sof(x)isaprimitivepolynomialf(x)=1+x+x2+x3+x4isirreduciblebut1+x5=(1+x)(1+x+x2+x3+x4)andm=5<24-1=15sof(x)isnotaprimitivepolynomialBCHCodes3.DefinitionofKn[x]

ThesetofallpolynomialsinK[x]havingdegreelessthannEachwordinKncorrespondstoapolynomialinKn[x]MultiplicationinKnmoduloh(x),withirreducibleh(x)ofdegreenIfweusemultiplicationmoduloareducibleh(x),say,1+x4todefinemultiplicationofwordsinK4,however:

(0101)(0101)(x+x3)(x+x3) =x2+x6 =x2+x2(mod1+x4) =0

0000(K4-{0000}isnotclosedundermultiplication.)

BCHCodes4.DefinitionofField(Kn,+,x)(Kn,+)isanabeliangroupwithidentitydenoted0Theoperationxisassociativeax(bxc)=(axb)xcThereisamultiplicativeidentitydenoted1,with101xa=ax1=a,aKnTheoperationxisdistributiveover+ax(b+c)=(axb)+(axc)Itiscommunicativeaxb=bxa,a,bKnAllnon-zeroelementshavemultiplicativeinversesGaloisFields:GF(2r)Foreveryprimepowerorderpm,thereisauniquefinitefieldoforderpmDenotedbyGF(pm)BCHCodesExampleLetusconsidertheconstructionofGF(23)usingtheprimitivepolynomialh(x)=1+x+x3todefinemultiplication.Wedothisbycomputingximodh(x): word ximodh(x) 100 1 010 x 001 x2 110 x31+x 011 x4x+x2 111 x51+x+x2 101 x61+x2BCHCodes5.UseaprimitivepolynomialtoconstructGF(2n)LetKnrepresentthewordcorrespondingtoxmodh(x)i

ximodh(x)m1form<2n-1sinceh(x)dosenotdivide1+xmform<2n-1Sincej=iforjiiffi=j-iij-i=1Kn\{0}={i|i=0,1,…,2n-2}BCHCodes6.

GF(2r)isprimitiveisprimitiveifm1for1m<2r-1Inotherwords,everynon-zerowordinGF(2r)canbeexpressedasapowerofExample

ConstructGF(24)usingtheprimitivepolynomialh(x)=1+x+x4.Writeeveryvectorasapowerof

xmodh(x)(seeTable5.1below) Notethat15=1. (0110)(1101)=5.7=12=1111BCHCodesTable1ConstructionofGF(24)usingh(x)=1+x+x4wordpolynomialinxmodh(x)powerof00000-100010=10100x0010x220001x3311001+x=x440110x+x2=x550011x2+x3=x66BCHCodesTable1(continue)ConstructionofGF(24)usingh(x)=1+x+x4wordpolynomialinxmodh(x)powerof11011+x+x3=x7710101+x2=x880101x+x3=x9911101+x+x2=x10100111x+x2+x3=x111111111+x+x2+x3=x121210111+x2+x3=x131310011+x3=x1414BCHCodes[2]Minimalpolynomials

1.Rootofapolynomial:anelementofF=GF(2r),p(x)F[x]isarootofapolynomialp(x)iffp()=02.OrderofThesmallestpositiveintegermsuchthatm=1inGF(2r)isaprimitiveelementifithasorder2r-1BCHCodes3.MinimalpolynomialofThepolynomialinK[x]ofsmallestdegreehavingasrootDenotedbym(x)m(x)isirreducibleoverKIff(x)isanypolynomialoverKsuchthatf()=0,thenm(x)isafactoroff(x)m(x)isuniquem(x)isafactorofBCHCodesExampleLetp(x)=1+x3+x4,andletbetheprimitiveelementinGF(24)constructedusingh(x)=1+x+x4(seeTable5.1): p()=1+3+4=1000+0001+1100=0101=9isnotarootofp(x).However p(7)=1+(7)3+(7)4=1+21+28=1+6+13=1000+0011+1011=0000=07isarootofp(x).BCHCodes4.FindingtheminimalpolynomialofReducetofindalinearcombinationofthevectors{1,,2,…,r},whichsumsto0Anysetofr+1vectorsinKrisdependent,suchasolutionexistsRepresentm(x)bymi(x)where=Ieg.

Findthem(x),=3,GF(24)constructedusingh(x)=1+x+x4BCHCodesUsefulfacts:f(x)2=f(x2)

Iff()=0,thenf(2)=(f())2=0Ifisarootoff(x),soare,2,4,…,Thedegreeofm(x)is|{,2,4,…,}|BCHCodesExampleFindthem(x),=3,GF(24)constructedusingh(x)=1+x+x4Letm(x)=m3(x)=a0+a1x+a2x2+a3x3+a4x4thenwemustfindthevaluefora0,a1,…,a4{0,1}

m()=0=a01+a1+a22+a33+a44 =a00+a13+a26+a39+a412 0000=a0(1000)+a1(0001)+a2(0011)+a3(0101)+a4(1111)

a0=a1=a2=a3=a4=1and

m(x)=1+x+x2+x3+x4BCHCodesExampleLet

m5(x)betheminimalpolynomialsof=5,5GF(24) Since{,2,4,8}={5,10},therootsofm5(x)are5and10whichmeansthatdegree(m5(x))=2.Thusm5(x)=a0+a1x+a2x2: 0=a0+a15+a210

=a0(1000)+a1(0110)+a2(1110) Thusa0=a1=a2=1andm5(x)=1+x+x2BCHCodesTable2:MinimalpolynomialsinGF(24)constructedusing1+x+x4ElementofGF(24)Minimalpolynomial01,2,4,83,6,9,125,107,11,13,14x1+x1+x+x41+x+x2+x3+x41+x+x21+x3+x4BCHCodes[3]CyclicHammingcodes1.ParitycheckmatrixTheparitycheckmatrixofaHammingcodeoflengthn=2r-1hasitsrowsall2r-1nonzerowordsoflengthrisaprimitiveelementof GF(2r)Histheparitycheckma- trixofaHammingcodeof lengthn=2r-1BCHCodes2.GeneratorpolynomialForanyreceivedwordw=w0w1…wn-1 wH=w0+w1+…+wn-1n-1w()wisacodewordiffisarootofw(x)m(x)isitsgeneratorpolynomialTheorem5.3.1

AprimitivepolynomialofdegreeristhegeneratorpolynomialofacyclicHammingcodeoflength2r-1BCHCodesExample: Letr=3,son=23-1=7.Usep(x)=1+x+x3toconstruct

GF(23),and010astheprimitiveelement.Recallthati

ximodp(x).ThereforeaparitycheckmatrixforaHammingcodeoflength7isBCHCodes3.DecodingthecyclicHammingcodew(x)=c(x)+e(x),wherec(x)isacodeword,e(x)istheerrorw()=e()ehasweight1,e()=j,jisthepositionofthe1inec(x)=w(x)+xjBCHCodesExample: SupposeGF(23)wasconstructedusing1+x+x3.m1(x)=1+x+x3isthegeneratorforacyclicHammingcodeoflength7.Suppose w(x)=1+x+x3+x6isreceived.Then w()=1+2+3+6 =100+001+110+101 =110 =3

e(x)=x3andc(x)=w(x)+x3=1+x2+x6

BCHCodes[4]BCHcodes1.BCH:Bose-Chaudhuri-HocquenghamAdmitarelativelyeasydecodingschemeTheclassofBCHcodesisquiteextensiveForanypositiveintegersrandtwitht2r-1-1,thereisaBCHcodesoflengthn=2r-1whichist-errorcorrectingandhasdimensionkn-rtBCHCodes2.

Paritycheckmatrixforthe2error-correctingBCHThe2error-correctingBCHcodesoflength2r-1isthecycliclinearcodes,generatedbyg(x)=,r4Thegeneratorpolynomial:g(x)=m1(x)m3(x)Degree(g(x))=2r,thecodehasdimensionn-2r=2r-1-2rBCHCodesExample:

isaprimitiveelementinGF(24)constructedwithp(x)=1+x+x4.Wehavethatm1(x)=1+x+x4andm3(x)=1+x+x2+x3+x4.Therefore g(x)=m1(x)m3(x)=1+x4+x6+x7+x8 isthegeneratorfora2error-correctingBCHcodeoflength15BCHCodes3.TheparitycheckmatrixofC15(distanced=5)

(Table3)BCHCodes[5]Decoding2error-correctingBCHcodes1.Errorlocatorpolynomial

w(x):receivedword

syndromewH=[w(),w(3)]=[s1,s3]Histheparitycheckmatrixforthe(2r-1,2r-2r-1,5)2error-correctingBCHcodewithgeneratorg(x)=m1(x)m3(x)wH=0ifnoerrorsoccurredIfoneerroroccurred,theerrorpolynomiale(x)=xi wH=eH=[e(),e(3)]=[i,3i]=[s1,s3],BCHCodesIftwoerrorsoccurred,sayinpositionsiandj,ij,e(x)=xi+xj,wH=eH=[e(),e(3)]=[i+j,3i+3j]=[s1,s3]Theerrorlocatorpolynomial:BCHCodesExample: Letww(x)beareceivedwordwithsyndromess1=0111=w()ands3=1010=w(3),wherewwasencodedusingC15.FromTable5.1wehavethats111ands38.Then Weformthepolynomialx2+11x+2andfindthatithasroots4and13.Thereforewecandecidethatthemostlikelyerrorsoccurredinpositions4and13,e(x)=x4+x13,themostlikelyerrorpatternis 0000100000000010BCHCodes2.DecodingalgorithmofBCHcodesCalculatethesyndromewH=[s1,s3]=[w(),w(3)]Ifs1=s3=0,noerrorsoccurredIfs1=0ands30,askforretransmissionIf(s1)3=s3,asingleerroratpositioni,wheres1=iFromthequadraticequation: (*)Ifequation(*)hastwodistinctrootsiandj,correcterrorsatpositionsiandjIfequation(*)doesnothavetwodistinctrootsinGF(2r),concludethatatleastthreeerrorsoccurredBCHCodesExample:

AssumewisreceivedandthesyndromeiswH=01111010[11,8].Now Inthiscaseequation(*)isx2+11x+2=0whichhasroots4and13.Correcterrorinpositionsi=4andj=13.Example:

AssumethesyndromeiswH=[w(),w(3)]=[3,9].Then(s1)3=(