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-i

i

j-i=1Kn\{0}={i|i=0,1,…,2n-2}BCHCodes6.

GF(2r)isprimitive

isprimitiveif

m1for1m<2r-1Inotherwords,everynon-zerowordinGF(2r)canbeexpressedasapowerof

Example

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

xmodh(x)(seeTable5.1below) Notethat

15=1. (0110)(1101)=5.

7=12=1111BCHCodesTable1ConstructionofGF(24)usingh(x)=1+x+x4wordpolynomialinxmodh(x)powerof

00000-10001

0=10100x

0010x2

20001x3

311001+x=x4

40110x+x2=x5

50011x2+x3=x6

6BCHCodesTable1(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

14BCHCodes[2]Minimalpolynomials

1.Rootofapolynomial:anelementofF=GF(2r),p(x)

F[x]isarootofapolynomialp(x)iffp()=02.Orderof

Thesmallestpositiveintegermsuchthat

m=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=0

7isarootofp(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+a2

2+a3

3+a4

4 =a0

0+a1

3+a2

6+a3

9+a4

12 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,

5

GF(24) Since{,2,4,8}={

5,10},therootsofm5(x)are

5and10whichmeansthatdegree(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+x2BCHCodesTable2: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+x4BCHCodes[3]CyclicHammingcodes1.ParitycheckmatrixTheparitycheckmatrixofaHammingcodeoflengthn=2r-1hasitsrowsall2r-1nonzerowordsoflengthrisaprimitiveelementof GF(2r)Histheparitycheckma- trixofaHammingcodeof lengthn=2r-1BCHCodes2.GeneratorpolynomialForanyreceivedwordw=w0w1…wn-1 wH=w0+w1+…+wn-1

n-1w()wisacodewordiffisarootofw(x)m

(x)isitsgeneratorpolynomialTheorem5.3.1

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

GF(23),and010astheprimitiveelement.Recallthat

i

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.1wehavethats1

11ands3

8.Then Weformthepolynomialx2+11x+2andfindthatithasroots

4and

13.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=0whichhasroots

4and

13.Correcterrorinpositionsi=4andj=13.Example:

AssumethesyndromeiswH=[w(),w(

3)]=[

3,9].Then(s1)3=(