Chapter 14 Some error-correcting codes and their a

Chapter14Someerror-correctingcodesandtheirapplicationsJ.D.Key114.1IntroductionInthischapterwedescribethreetypesoferror-correctinglinearcodesthathavebeenusedinmajorapplications,viz.photographsfromspacecraft(firstorderReed-Mullercodes),compactdiscs(Reed-Solomoncodes),andcomputermemories(ex-tendedbinaryHammingcodes).Error-correctingcodeswerefirstdevelopedinthe1940sfollowingatheoremofClaudeShannon[14]thatshowedthatalmosterror-freecommunicationcouldbeobtainedoveranoisychannel.Themessagetobecommunicatedisfirst“encoded”,i.e.turnedintoacodeword,byadding“redundancy”.Thecodewordisthensentthroughthechannelandthereceivedmessageis“decoded”bythereceiverintoamessageresembling,ascloselyaspossible,theoriginalmessage.Thedegreeofresemblancewilldependonhowgoodthecodeisinrelationtothechannel.Suchcodeshavebeenusedtogreateffectinsomeimportantapplications,andwewilldescribeherethecodesthatareusedinthreeoftheseapplications,showinghowtheycanbeconstructedandhowtheycanbeused:•Computermemories[11]:thecodesusedareextendedbinaryHammingcodes,thelatterbeingperfectsingle-error-correcting;•Photographsfromspacecraft:thecodesinitiallyusedwerefirst-orderReed-Mullercodes,whichcanbeconstructedastheorthogonalextendedHam-mingcodes;laterthebinaryextendedGolaycodewasused;•Compactdiscs[7]:thecodesusedareReed-Solomoncodes,constructedusingcertainfinitefieldsoflargeprime-powerorder.1Chapter14of“AppliedMathematicalModeling:AMultidisciplinaryApproach”,D.R.ShierandK.T.Wallenius(Eds.),Chapman&Hall/CRCPress,BocaRaton,FL,19991Afteranintroductorysectiononthenecessarybackgroundtocodingtheory,includingsomeoftheeffectiveencodinganddecodingmethods,wewilldescribehowthecodescanbeusedineachoftheseapplications,andgiveasimpledescriptionhoweachoftheseclassesofcodescanbeconstructed.Wewillnotincludedetailsoftheimplementationofthecodes,norofthemathematicalbackgroundtothetheory;thereaderisencouragedtoconsultthepapersandbooksinthebibliographyforthis.Thosereaderswhoarefamiliarwiththeelementaryconceptsincodingtheoryshouldpassimmediatelyontotheapplications,andreferbacktoSection14.2whennecessary.Thefinalsectioncontainssomesimpleexercisesandsomeprojectsforfurtherstudy.14.2BackgroundcodingtheoryMoredetailedaccountsoferror-correctingcodescanbefoundin:Hill[6],Pless[13],MacWilliamsandSloane[10],vanLint[9],andAssmusandKey[1,Chapter2].SeealsoPeterson[12]foranearlyarticlewrittenfromtheengineers’pointofview.Proofsofalltheresultsquotedherecanbefoundinanyofthesetexts;oursummaryherefollows[1].Theusualpictorialrepresentationoftheuseoferror-correctingcodestosendmessagesovernoisychannelsisshownintheschematicdiagramFigure14.1.source?messageencoder-codewordchannelNOISE?-receivedvectordecoder?decodedmessagereceiverFigure14.1:AnoisycommunicationschannelHereamessageisfirstgivenbythesourcetotheencoderthatturnsthemessageintoacodeword,i.e.astringoflettersfromsomealphabet,chosenaccordingtothecodeused.Theencodedmessageisthensentthroughthechannel,whereitmaybesubjectedtonoiseandhencealtered.Whenthismessagearrivesatthedecoderbelongingtothereceiver,itisequatedwiththemostlikelycodeword,i.e.theone(shouldthatexist)that,inaprobabilisticsensedependingonthechannel,wasprobablysent,andfinallythis“mostlikely”codewordisdecodedandthemessageispassedontothereceiver.Example14.1Supposeweuseanalphabetofjusttwosymbols,0and1,andwehaveonlytwomessages,forexample“no”correspondingto0,and“yes”correspond-2ingto1.Wewishtosendthemessage“no”,andweaddredundancybysimplyrepeatingthemessagefivetimes.Thusweencodethemessageasthecodeword(00000).Thechannelmightinterferewiththemessageandcouldchangeitto,say,(10100).Thedecoderassessesthemessageanddecidesthatofthetwopossiblecodewords,i.e.(00000)and(11111),theformeristhemorelikely,andhencethemessageisdecoded,correctly,as“no”.Wehavemadeseveralassumptionshere:forexamplewehaveassumedthattheprobabilityofanerroratanypositioninthewordislessthan12,thateachcodewordisequallylikelytobesent,andthatthereceiverisawareofthecodeused.Definition14.1LetFbeafiniteset,oralphabet,ofqelements.Aq-arycodeCisasetoffinitesequencesofsymbolsofF,calledcodewordsandwrittenx1x2...xn,or(x1,x2,...,xn),wherexi∈Ffori=1,...,n.Ifallthesequenceshavethesamelengthn,thenCisablockcodeofblocklengthn.Thecodeusedintheexampleaboveisablockcode,calledtherepetitioncodeoflength5:itcanbegeneralizedtolengthnandtoanyalphabetofsizeq,andhencewillhaveqcodewordsoftheformxx···x,wherex∈F.GivenanalphabetF,itwillbeconvenient,andalsoconsistentwithterminologyforcartesianproductsofsetsandforvectorspaceswhenFisafield,todenotethesetofallsequencesoflengthnofelementsofFbyFnandtocallthesesequencesvectors,referringtothememberofFintheithpositionasthecoordinateati.Weuseeithernotation,x1x2···xnor(x1,x2,...,xn),forthevectors.AcodeoverFofblocklengthnisthusanysubsetofFn.Theformalprocessinthereasoningofthesimpleexamplegivenaboveusestheconceptofthedistancebetweencodewords.Definition14.2Letv=(v1,v2,...,vn)andw=(w1,w2,...,wn)betwovectorsinFn.TheHammingdistance,d(v,w),betweenvandwisthenumberofcoordinateplacesinwhichtheydiffer:d(v,w)=|{i|vi6=wi}|.WewillusuallyrefertotheHammingdistanceassimplythedi