POLYNOMIAL-CODES-OVER-CERTAIN-FINITE-FIELDS

PolynomialCodesOverCertainFiniteFieldsAuthor(s):I.S.ReedandG.SolomonSource:JournaloftheSocietyforIndustrialandAppliedMathematics,Vol.8,No.2(Jun.,1960),pp.300-304Publishedby:SocietyforIndustrialandAppliedMathematicsStableURL::13-05-201613:28UTCYouruseoftheJSTORarchiveindicatesyouracceptanceoftheTerms&ConditionsofUse,[e-mail]ppliedMathematicsiscollaboratingwithJSTORtodigitize,preserveandextendaccesstoJournaloftheSocietyforIndustrialandAppliedMathematicsThiscontentdownloadedfrom128.250.144.144onFri,13May201613:28:41UTCAllusesubjectto*tI.S.REEDANDG.SOLOMON:Introduction.AcodeisamappingfromavectorspaceofdimensionmoverafinitefieldK(denotedbyVfl%(K))intoavectorspaceofhigherdimensionnmoverthesamefield(Vn(K)).KisusuallytakentobethefieldoftwoelementsZ2,inwhichcaseitisamappingofm-tuplesofbinarydigits(bits)inton-tuplesofbinarydigits.Ifonetransmitsnbits,theadditionaln-mbitsareredundantandallowonetorecovertheoriginalmessageintheeventthatnoisecorruptsthesignalduringtrans-missionandcausessomebitsofthecodetobeinerror.Amultiple-error-correctingcodeofordersconsistsofacodewhichmapsm-tuplesofzerosandonesinton-tuplesofzerosandones,wheremandnbothdependons,andadecodingprocedurewhichrecoversthemessagecompletely,assumingnomorethanserrorsoccurduringtransmissioninthevectorofnbits.TheHammingcode[1]isanexampleofasystematiconebiterror-correct-ingcode.Wepresenthereanewclassofredundantcodesalongwithadecodingprocedure.LetKbeafieldofdegreenoverthefieldoftwoelementsZ2.Kcontains2'elements.ItsmultiplicativegroupiscyclicandisgeneratedbypowersofawhereaistherootofasuitableirreduciblepolynomialoverZ2.WediscusshereacodeEwhichmapsm-tuplesofKinto2-tuplesofK.ConsiderthepolynomialP(x)ofdegreem-1P(x)=ao+alx++amx1,whereatEKandm2n.CodeEisthemappingofthem-tuple(ao,a1,...,am-i)intothe2'-tuple(P(O),P(a),P(a2),*...P(1));thism-tuplemightbesomeencodedmessageandthecorresponding2'-tupleistobetransmitted.Thismappingofmsymbolsinto2'symbolswillbeshowntobe(2'-m)/2or(2n-m-1)/2symbolcorrecting,dependingonwhethermisevenorodd.AnaturalcorrespondenceisestablishedbetweenthefieldelementsofKandcertainbinarysequencesoflengthn.Underthiscorrespondence,codeEmayberegardedasamappingofbinarysequencesofmnbitsintobinarysequencesofn2nbits.ThuscodeEcanbeinterpretedtobeasys-tematicmultiple-error-correctingcodeofbinarysequences.*ReceivedbytheeditorsJanuary21,1959andinrevisedformAugust26,1959.tTheworkreportedherewasperformedatLincolnLaboratory,atechnicalcenteroperatedbyMassachusettsInstituteofTechnologywiththejointsupportoftheArmy,NavyandAirForce,undercontract.IStaffmembers,LincolnLaboratory,MassachusettsInstituteofTechnology,Lexington73,Massachusetts.300Thiscontentdownloadedfrom128.250.144.144onFri,13May201613:28:41UTCAllusesubjectto(2-m-1)/2bitssinceeachsymbolofthecodeisrepresentedbynconsecutivebits.Hencewhenthebinaryerrorsarestronglycorrelatedoroccurinbursts,thiscodemaybemoredesirablethanothermoreefficientmultiple-error-correctioncodes.Finally,itshouldbementionedthatcodeEmaybegeneralizedtopoly-nomialsofthemthdegreeinseveralvariablesoverK.Evidently,forK=Z2,suchcodesreducetoReed-Mullercodes[2].ThecodeE.ConsiderthefieldK=Z2(a).ThisisthevectorspaceoverZ2withbasis1,a,a2a*n-lwhereaistherootofasuitableirreduciblepolynomialoverZ2.ThenonzeroelementsofKformamultiplicativecyclicgroup.ThuswemayrepresenttheelementsofKintheorderO3X#X...2fX1=1where:isageneratorofthemultiplicativecyclicgroup.LetP(x)=ao+a1x+a2x2+*+amaxm-1.ThecodeEsends(ao,a,,..am2,am-l)--(p(O),p(#)7p(#2),..,pP(02)),(1)I)Uponreceivingthemessage(P(O),P(3),I,P(1)),wemaydecodethemessagebysolvingsimultaneouslyanymofthe2nequations,P(O)=aoP(3)=ao+a43+a2f3++amiflm1P(j2)=ao+a1f2+a2f4+...+am,2m-2P(1)=ao+a,+a2++am-,.Wenotethatanymoftheseequationsarelinearlyindependentsincethecoefficientdeterminantfor,say,P(ai),,)P(am),is2m-11aa1...a12m-11a2a2...a22m-11amam...amwhichisaVandermondedeterminantwhosevalueis=Jjji(a,+aj)50.ThusinthecaseofnoerrorsinthereceivedvaluesofP),weobtain()determinationsof(ao,*,a.-).Thiscontentdownloadedfrom128.250.144.144onFri,13May201613:28:41UTCAllusesubjectto(*)willimmediatelydisturbtheunanimityofthevaluesobtainedforthean's.Indeed,forsufficientlysmallnumbersoferrors,bylookingatthelargestnumberofdeterminationsforany(ao,***,a,-)(thepluralityofvotesreceivedbyanym-tuple)wemaydetecttheorderofer