GroupsandCodingGroupsandCodingCodingofBinaryInformationandErrorDetectionDecodingandErrorCorrectionCodingofBinaryInformationandErrorDetectionEncodingfunctionHammingdistanceGroupCodesParitycheckmatrixCodingtheoryIntoday’smodernworldofcommunication,dataitemsareconstantlybeingtransmittedfrompointtopoint.Thebasicproblemintransmissionofdataisthatofreceivingthedataassentandnotreceivingadistortedpieceofdata.Codingtheoryhasdevelopedtechniquesforintroducingredundantinformation(引入冗余信息)intransmitteddatathathelpindetecting,andsometimesincorrecting,errors.UnitofinformationMessage(消息)isafinitesequenceofcharactersfromafinitealphabetB={0,l}Word(字)isasequenceofm0'sandl's.GroupsThesetBisagroupunderthebinaryoperation+(mod2addition)ItfollowsthatBm=B

B

…

B(nfactors)isagroupundertheoperatordefinedby(x1,x2,…,xm)(y1,y2,…,ym) =(x1+y1,x2+y2,

…,xm+ym)AnelementinBmwillbewrittenas(b1,b2,...,bm)ormoresimplyasb1b2...bmTransmissionchannelandNoiseAnelementx

Bmissentthroughthetransmissionchannelandisreceivedasanelementxt

Bm.TransmissionchannelandNoiseNoise(噪聲)

inthetransmissionchannelmaycausea0tobereceivedasal,orviceversa,leadxxt對(duì)錯(cuò)對(duì)對(duì)時(shí)Encodingfunction-編碼函數(shù)Choose:anintegern>mandaone-to-onefunctione:Bm

Bneiscalledan(m,n)encodingfunction,representingeverywordinBmasawordinBn.Ifb

Bm,thene(b)iscalledthecodeword(碼字)representingb.EncodingfunctionIfthetransmissionchannelisnoiseless,thenxt=xforallxinBn.Inthiscasex=e(b)isreceivedforeachb

Bm,andsinceeisaknownfunction,bmaybeidentified.EncodingfunctionIngeneral,errorsintransmissiondooccur.Wewillsaythatthecodewordx=e(b)hasbeentransmittedwithkorfewererrorsifxandxtdifferinatleast1butnomorethankpositions.Errordetect–差錯(cuò)檢測(cè)Lete:Bm

Bnbean(m,n)encodingfunction.e

detectskorfewererrorsifwheneverx=e(b)istransmittedwithkorfewererrors,thenxt

isnotacodeword(thusxtcouldnotbexandthereforecouldnothavebeencorrectlytransmitted).Forb

Bn,thenumberofl'sinxiscalledtheweight(權(quán))ofxandisdenotedby|x|Example1FindtheweightofeachofthefollowingwordsinB5.x=01000 |x|=1x=11100 |x|=3x=00000 |x|=0x=11111 |x|=5Example2

paritycheckcode–奇偶校驗(yàn)碼Thefollowingencodingfunctione:Bm

Bm+1iscalledtheparity(m,m+1)checkcode:Ifb=b1b2…bm

Bm,define e(b)=b1b2…bm

bm+1whereExample2

paritycheckcodeLetm=3.Thene(000)=0000e(001)=0011e(010)=0101e(011)=0110e(100)=1001e(101)=1010e(110)=1100e(111)=1111Supposenowthatb=111.Thenx=e(b)=1111Example3Considerthe(m,3m)

encodingfunctione:Bm

B3m.Ifb=b1b2…bm

Bm,define e(b)=b1b2…bmb1b2…bmb1b2…bmExample3Supposenowthatb=011Thene(011)=011011011.Assumenowwereceivetheword011111011.Thisisnotacodeword,sowehavedetectedtheerror.(00,10,01,11)

(00,11)(1,1)(1,0)(0,1)(0,0)Bm(0,1)->Bn(000,111)(1,1,1)(0,1,1)(1,1,0)(0,1,0)(1,0,1)(0,0,1)(1,0,0)(0,0,0)Hammingdistance–海明距離LetxandybewordsinBm.TheHammingdistance

(x,y)betweenxandyistheweight,|xy|,ofx

y.Thedistancebetweenx=x1x2…xmandy=y1y2…ymisthenumberofvariousofisuchthatxi

yi,thatis,thenumberofpositionsinwhichxandydiffer.Usingtheweightofx

yisaconvenientwaytocountthenumberofdifferentpositions.Example4Findthedistancebetweenxandy:(a)x=110110,y=000101(b)x=001100,y=010110.Solution(a)x

y=110011,so|x

y|=4(b)x

y=011010,so|x

y|=3Theorem1

propertiesofdistancefunctionLetx,y,andzbeelementsofBm.Then(a)(x,y)=(y,x)(b)(x,y)≥0(c)(x,y)=0ifandonlyifx=y(d)(x,y)≤(x,z)+(z,y)Proofof(d)(x,y)=|x

y|=|x

0

y| =|x

z

z

y|

≤|x

z|+|

z

y|MinimumdistanceTheminimumdistanceofanencodingfunctione:Bm

Bnistheminimumofthedistancesbetweenalldistinctpairsofcodewords;thatis, min{(e(x),e(y))|x,y

Bm}Example5Considerthefollowing(2,5)encodingfunctione:Theorem2An(m,n)encodingfunctione:Bm

Bncandetectkorfewererrorsifandonlyifitsminimumdistanceisatleastk+l.Proof

theminimumdistanceisatleastk+1Letb

Bm,andletx=e(b)

Bnbethecodewordrepresentingb.xistransmittedandisreceivedasxt.Ifxtwereacodeworddifferentfromx,then(x,xt)≥

k+l,soxwouldbetransmittedwithk+lormoreerrors.Thus,ifxistransmittedwithkorfewererrors,thenxtcannotbeacodeword.Thismeansthatecandetectkorfewererrors.Proof

ecandetectkorfewererrorsSupposethattheminimumdistancebetweencodewordsisr

≤

kLetxandybecodewordswith(x,y)=r.Ifx=y,thatis,ifxistransmittedandismistakenlyreceivedasy,thenr≤kerrorshavebeencommittedandhavenotbeendetected.Thusitcontradictwithecandetectkorfewererrors.Q.E.D.Example6

Howmanyerrorswilledetect?Considerthe(3,8)encodingfunctione:B3

B8definedbyGroupCodes–群碼An(m,n)encodingfunctione:Bm

Bniscalledagroupcodeife(Bm)={e(b)|e(b)

Bn}=Ran(e)isasubgroupofBnSubgroupsRecallfromthedefinitionofsubgroupgiveinSection9.4thatNisasubgroupofBnif(a)theidentityofBnisinN,(b)ifxandybelongtoN,thenx

y

N,and(c)ifxisinN,thenitsinverseisinN.Example7:iseagroupcode?Considerthe(3,6)encodingfunctione:B3

B6definedbyExample7:iseagroupcode?WemustshowthatthesetofallcodewordsN={000000,001100,010011,011111,100101,101001,110110,111010}isasubgroupofB6.Theorem3Lete:Bm

Bnbeagroupcode.Theminimumdistanceofeistheminimumweightofanonzerocodeword.ProofofTheorem3Letbetheminimumdistanceofthegroupcode,andsupposethat=(x,y),wherexandyaredistinctcodewords.Also,letbetheminimumweightofanonzerocodewordandsupposethat=|z|foracodewordz.ProofofTheorem3Sinceeisagroupcode,x

yisanonzerocodeword.Thus=(x,y)=|x

y|≥

.Ontheotherhand,since0andzaredistinctcodewords,=|z|=|z

0|=(z,0)≥

Hence=.Q.E.D.Example8Theminimumdistanceofthegroupcodeinis2Tocheckthisdirectlywouldrequire28differentcalculations.ConstructinggroupcodeAreviewonBooleanmatricesmod-2sum

DEmod-2BooleanproductD*ETheorem4LetDandEbem

pBooleanmatrices,andletFbeap

nBooleanmatrix.Then(D

E)*F=(D*F)(E*F).Thatis,adistributivepropertyholdsforand*.NotationWeshallnowconsidertheelementx=x1x2…xn

Bn

asthe1

nmatrix[x1x2…xn]Theorem5Letmandnbenonnegativeintegerswithm<n,r=n-m,andletHbeann

rBooleanmatrix.ThenthefunctionfH:Bn

BrdefinedbyfH(x)=x*H,x

Bn;isahomomorphismfromthegroupBntothegroupBr.ProofIfxandyareelementsinBn,thenfH(x

y)=(xy)*H

=(x*H)(y*H) byTheorem4 =fH(x

)

fH(y).HencefHisahomomorphismfromBntoBrQ.E.D.Corollary1Letm,n,r,H,andfHbeasinTheorem5.ThenN={x

Bn|x*H=0}isanormalsubgroupofBn.Proof:NisthekernelofthehomomorphismfH,soitisanormalsubgroupofBn.Paritycheckmatrix–

一致性檢驗(yàn)矩陣Letm<nandr=n–m,thefollowingn

rBooleanmatrixiscalledaparitycheckmatrix.EncodingfunctionDefineanencodingfunctioneH:Bm

BnIfb=b1b2…bm,letx=eH(b)=b1b2…bm

x1x2…xr,where(1)eH:Bm

Bn

inmatrixformatTheorem6Letx=y1y2…ymx1…xr

Bn.Thenx*H=0

ifandonlyifx=eH(b)forsomeb

Bm.Proof:x*H=0

x=eH(b)forsomeb

BmSupposethatx*H=0Proof:x*H=0

x=eH(b)forsomeb

Bm

Notethatxi+xi=0.SoaddxitoithrowandgetLettingb1=y1,b2=y2,...,bm=ym,weseethatx1,x2,...,xrsatisfytheequationsin(l).Thusb=b1b2…bm

Bmandx=eH(b)Proof:x*H=0

x=eH(b)forsomeb

Bm

Converselyifx=eH(b),theequationsin(l)canberewrittenbyaddingxitobothsidesoftheithequation,i=l,2,...,n,aswhichshowsx*H=0Q.E.D.Corollary2eH(Bm)={eH(b)|b

Bm}isasubgroupofBn

Proof:TheresultfollowsfromtheobservationthateH(Bm)=ker(fH)andfromCorollaryl.ThuseHisagroupcode.Example11Letm=2,n=5,andDeterminethegroupcodeeH:B2B5.Solution11Homework19,23,25,27P412Thanksforyourattention!Comingupnext…DecodingandErrorCorrectionDecodingandErrorCorrection譯碼與糾錯(cuò)BnBr

Bn/N{xN|x∈Bn}={(x*H=y|y∈Br)}N={x=e(b),b∈Bm}={(x*H=0)|x∈Bn

}fH

(x)

=x*HfR

(x)

=[x]R=

xNxRyifonlyifx-1y∈NfH

(x)=fH

(y)F(xN)=fH

(x)

=x*HDecodingFunction–譯碼函數(shù)Consideran(m,n)encodingfunction e:Bm

Bn.Oncetheencodedwordx=e(b)

Bn,forb

Bm,isreceivedasthewordxt,wearefacedwiththeproblemofidentifyingthewordbthatwastheoriginalmessage.DecodingFunctionConsideran(m,n)encodingfunction e:Bm

Bn.Anontofunctiond:Bn

Bmiscalledan(n,m)decodingfunctionassociatedwithe(與e關(guān)聯(lián)的譯碼函數(shù))ifd(xt)=b'

Bmissuchthatwhenthetransmissionchannelhasnonoise,thenb'=b,thatis,d

o

e=1BmDecodingFunctionThedecodingfunctiondisrequiredtobeontosothateveryreceivedwordcanbedecodedtogiveawordinBm.Itdecodesproperlyreceivedwordscorrectly,butthedecodingofimproperlyreceivedwordsmayormaynotbecorrect.Example1ConsidertheparitycheckcodethatisdefinedinExample2ofSection11.1Definethedecodingfunctiond:Bm+1

Bm.Ify=yly2…ymym+l

Bm+1,thend(y)=yly2…ymObservethatifb=blb2…bm

Bm,then(d

o

e)(b)=d(e(b))=bsod

o

e=1BmForaconcreteexample,letm=4.Thend(10010)=1001andd(11001)=1100DecodingfunctionLetebean(m,n)encodingfunctionandletdbean(n,m)decodingfunctionassociatedwithe.Thepair(e,d)issaidtocorrectkorfewererrors

ifwheneverx=e(b)istransmittedcorrectlyorwithkorfewererrorsandxtisreceived,thend(xt)=b.Thusxtisdecodedasthecorrectmessageb.Example2Considerthe(m,3m)encodingfunctiondefinedinExample3ofSection11.1.Definethedecodingfunctiond:Bm

B3m.Lety=y1y2…ymym+1…y2my2m+1…y3m,Thend(y)=z1z2…zmwhereE.g.xt=011011111,thend(xt)=011Maximumlikelihoodtechnique–極大似然技術(shù)SinceBmhas2melements,thereare2mcodewordsinBn.Listitasx(1),x(2),...,x(2m)Ifthereceivedwordisxt,wecompute(x(i),xt)for1≤i≤2m,andchoosethefirstcodeword,sayitisx(s),suchthatMaximumlikelihooddecodingfunctionThatis,x(s)isacodewordthatisclosesttoxtandthefirstinthelist.Ifx(s)=e(b),wedefinethemaximumlikelihooddecodingfunction

dassociatedwithebyd(xt)=bTheorem1Supposethateisan(m,n)encodingfunctionanddisamaximumlikelihooddecodingfunctionassociatedwithe.Then(e,d)cancorrectkorfewererrorsifandonlyiftheminimumdistanceofeisatleast2k+l.Example3

Howmanyerrorscan(e,d)correct?The(3,8)encodingfunctione:B3

B8andletdbean(8,3)maximumlikelihooddecodingfunctionassociatedwithe.ConstructingmaximumlikelihooddecodingfunctionassociatedwithagivengroupcodeTheorem2IfKisafinitesubgroupofagroupG,theneveryleftcosetofKinGhasexactlyasmanyelementsasK.ProofLetaKbealeftcosetofKinG,wherea

G.Considerthefunctionf:K

aKdefinedbyf(k)=ak,fork

K.Weshowthatfisonetooneandonto.Toshowthatfisonetoone,weassumethatf(kl)=f(k2),kl,k2

K.Thenakl=ak2Leftmultiplya-1,wehavekl=k2ProofToshowthatfisonto,letbbeanarbitraryelementinaK.Thenb=akforsomek

K.Wenowhavef(k)=ak=bsofisonto.Sincefisonetooneandonto,KandaKhavethesamenumberofelements.Q.E.DGroupcodewordLete:Bm

Bnbean(m,n)encodingfunctionthatisagroupcode.ThusthesetNofcodewordsinBnisasubgroupofBnwhoseorderis2m,sayN={x(1),x(2),...,x(2m)}.Cosetleader–陪集頭Supposethatthecodewordx=e(b)istransmittedandthatthewordxtisreceived.Theleftcosetofxtisxt

N={1,2,...,2m}wherei=xt

x(i)ifjisacosetmemberwithsmallestweight,thenx(j)mustbeacodewordthatisclosesttoxt.Anelementj,havingsmallestweight,iscalledacosetleader.ProcedureForobtainingamaximumlikelihooddecodingfunctiondassociatedwithagivengroupcodee:Bn

Bm

ProcedureStep1:DeterminealltheleftcosetsofN=e(Bm)inBnStep2:Foreachcoset,findacosetleader(awordofleastweight).Step3:Ifthewordxtisreceived,determinethecosetofNtowhichxtbelongs.Step4:LetbeacosetleaderforthecosetdeterminedinStep3.Computex=xt

.Ifx=e(b),weletd(xt)=b.Thatis,wedecodextasb.DecodingtableConstructingadecodingtable,eachrowisaleftcosetofNwiththefirstelement(i)thecosetleader.DecodingtableIfwereceivethewordxt,welocateitinthetable.IfxistheelementofNthatisatthetopofthecolumncontainingxt,thenxisthecodewordclosesttoxt.ifx=e(b),thend(xt)=b.Example4Considerthe(3,6)groupcodeN={000000,001100,010011,011111,100101,101001,110110,111010}={x(1),x(2),...,x(8)}.Example4

Constructingdecodingtable:==============================================================000000001100010011011111100101101001110110111010--------------------------------------------------------------000001001101010010111110100100101000110111111011000010001110010001011101100111101011110100111000000100001000010111011011100001101101110010111110010000011100000011001111110101111001100110101010100000101100110011111111000101001001010110011010000110001010010101011001100011101111110000111100010100011000000111001011110001111101100010101110==============================================================001010000110011001010101101111100011111100110000SimplifieddecodingtechniqueSupposethatthe(m,n)groupcodeiseH:Bm

Bn

,whereHisagivenparitycheckmatrix.SimplifieddecodingtechniqueThenthefunctionfH:Bn

BrdefinedbyfH(x)=x*H,x

BnisahomomorphismfromthegroupBntothegroupBr.Theorem3Ifm,n,r,H,andfHareasdefined,thenfHisonto.ProofLetb=b1b2…brbeanyelementinBr.Lettingx=01…0mb1b2…br

Thenx*H=b.ThusfH(x)=b,sofHisonto.Q.E.DSyndrome–特征值ItfollowsfromCorollarylofSection9.5thatBrandBn/Nareisomorphic,whereN={x

Bn|x*H=0}=ker(fH)=eH(Bm)undertheisomorphismg:Bn/N

Brdefinedbyg(xN)=fH(x)=x*HTheelementx*HiscalledthesyndromeofxTheorem4LetxandybeelementsinBn.ThenxandylieinthesameleftcosetofNinBn

ifandonlyiffH(x)=fH(y)ifandonlyiftheyhavethesamesyndrome.ProofItfollowsfromTheorem4ofSection9.5thatxandylieinthesameleftcosetofNinBnifandonlyifxy=(-x)y

N.SinceN=ker(fH),xy

NifandonlyiffH(x

y)=0BrfH(x)

fH(y)=0BrfH(x)=fH(y)Q.E.D.DecodingprocedureSupposethatwecomputethesyndromeofeachcosetleader.Ifthewordxtisreceived,wealsocomputefH(xt),thesyndromeofxt.BycomparingfH(xt)andth