cylcic codes peterson paper

PROCEEDINGS OFTHEIRE Theconventional solutiontotheproblemisshownin Fig.10.Afewmomentsofstudywillindicatethatit doesinfactperformtherequiredoperation.TheFlow TableLogicsolutionisshowninFig.11.Againthe problemiseasilycheckedforcorrectperformance. Thesimplicityofthewiringandtheregularityofthe circuitarequiteapparent.Suchanapproachshould certainlyprovevaluablewhenbatch-fabricated devices becomeareaility.Aswasstatedearlier,whenapplied toonesuchtechnology(EL-PC)thedesignanidfabri- cationofcircuitsisgreatlysimplified.Anearlymodel ofanEL-PCcombination lockisshowninFig.12. CONCLUSION TheFlowTableLogictechniqueforcircuitdesign presentedherewasintendedforusewithbatch-fabri- cated(orperhapsmicro-miniature) devices,hencethe emphasisonsimplicityandregularity.Theseareob- tainedinsomecasesattheexpenseofactualcompo- nentcount.Theexchangewasfelttobeacceptable, however,sinceminimizing thenumberofactiveele- mentsisnotguaranteeofminimumcost.Aninteresting pointthatshouldbeconsideredisthelogicaldelayas-sociatedwithcircuitsdesignedbytheFlowTableLogic technique.Thecircuitcangofromonestatetoany otherstateinapproximately twologicaldelays.Thus onehasnotsacrificedspeedinthequestforregularity. Theeaseofcircuitdesignishouldalsobeanadvanitage ofthistechnique. Asistrueinmostdevelopments, therearesome problemareasthatstillrequireinvestigation. Thecod- ingoftheinputlinesand,infact,thecodingofthe statesoftheflowtablearefarfromoptimum.Onlyfur- therworkcanrevealwhetherthiscanbeimproved withoutsacrificingthesimplicityofthecircuit.Inaddi- tion,thenecessarydelayrequiredisnotfoundinall technologies andthusImlustbecarefullyconsideredin thesolutionofaproblem. ACKNOWLEDGMENT Thematerialpresentedrepresentstheeffortsofthe authorsplusthatofR.J.Domenico.Inaddition,the authorsareindebtedtoE.J.Skiko,J.Earle,andR. Robelenformanyhelpfuldiscussions.TheEL-PCcom- binationlockwasconstructed byDr.J.A.O'Connell andB.Narken. CyclicCodesforErrorDetection* W.W.PETERSONt, MEMBER, IRE,ANDD.T.BROWNt, MEMBER, IRE Summary-Cyclic codesaredefinedanddescribedfromanew viewpointinvolvingpolynomials. ThebasicpropertiesofHamming andFirecodesarederived.Thepotentialities ofthesecodesfor errordetectionandtheequipmentrequiredforimplementing error detectionsystemsusingcycliccodesaredescribedindetail. INTRODUCTION FTHEmanydevelopments intheareaoferror- detectionanderror-correcting codesduringthe pastthreeyears,probablythemostimportant havepertainedtocycliccodes.Sincetheirintroduction byPrange,Iveryattractiveburst-errorcorrectingcyclic *ReceivedbytheIRE,August1,1960;revisedmnianuscript re-ceivedOctober28,1960.tUniversityofFlorida,Gainesville,Fla.tIBMCorp.,Poughkeepsie, N.Y. IE.Prange,"CyclicError-Correcting CodesinTwoSymbols,"AirForceCambridgeResearchCenter,Bedford,Mass.,Tech.NoteAFCRC-TN-57-103, September,1957;"SomeCyclicError-Correct-ingCodeswithSimpleDecodingAlgorithms," Tech.NoteAFCRC-TN-58-156,April,1958;"TheRoleofCosetEquivalence intheAnalysisandDecodingofGroupCodes,"Tech.NoteAFCRC-TR-59-164;June,1959.codeshavebeenfoundbyAbramson,2,3 Fire,4Melas,5 andReiger.!Cycliccodesforcorrectingrandomerrors havebeenfoundbyPrange,'GreenandSanSoucie,78 BoseandRay-Chaudhuri,9 andMelas.'0Encodinganid 2N.M.Abramson,"AClassofSystematicCodesforNon-Inde-pendentErrors,"ElectronicsRes.Lab.,StanfordUniversity,Stan-ford,Calif.,Tech.Rept.No.51;December,1958. 3N.M.Abramson,"ErrorCorrectingCodesfromLinearSe-quentialNetworks,"presentedattheFourthLondonSymp.onInl-formationTheory,London,Eng.;August,1960. 4P.Fire,"AClassofMultiple-Error-Correcting BinaryCodesforNon-Independent Errors,"SylvaniaElectricProducts,Inc.,MountainView,Calif.,Rept.No.RSL-E-2;March,1959. 5C.M.Melas,"Anewgroupofcodesforcorrectionfordependent errorsindatatransmission," IBMf.Res.Dev.,vol.4,pp.58-65;January,1960. 6S.H.Reiger,"Codesforthecorrectionofclusterederrors," IRETRANS.ONINFORMATION THEORY,Vol.IT-6,pp.16-21;March,1960. 7J.H.Green,Jr.,andR.L.SanSoucie,"Anerror-correcting ei-coderanddecoderofhighefficienvcy."PROC.IRE,vol.46,pp.1744-1755;October,1958. 8N.Zeiler,"OnaVariationoftheFirstOrderReed-MullerCodes,"M.I.T.LincolnLab.,Lexington,Mass.,pp.34-80;October,1958. 9R.C.BoseandD.K.Ray-Chaudhuri, "Aclassoferror-correct-ingbinarygroupcodes,"InformationandControl,vol.3,pp.68-79,March,1960;"Furtherresultsonerrorcorrectingbinarygrotupcodes,"InformationandControl;tobepublished. 1"C.M.Melas,"Acycliccodefordoubleerrorcorrectioi," IBMJ.Res.Dev.,vol.4,pp.364-366;July,1960.228 January PetersonandBrown:CyclicCodesforErrorDetection errorcorrectingproceduresforthesecodesarerelatively easilyimplemented usingshift-registers withfeedback connections. 11""2 Thefirstfunctionofthispaperistointroducecyclic codesfromaniewviewpointrequiringonlyelementary mathematics andtoderivethebasicpropertiesof HammingandFirecodes.Second,thepotentialities of cycliccodesforerrordetectionandtheequipmenit re- quiiredforimplementing errordetectionisystemsusinig cycliccodesaredescribedindetail. POLYNOMIAL REPRESENTATION OF BINARYINFORMATION Wewillbecotncernedwithcodingamessageofk binarydigitsbyappendingn-kbinarydigitsasa checkandtransmittinig thekinformatioindigitsand thenithen-kcheckdigits.Itisconvenienttothinikof thebinarydigitsascoefficientsofapolynomialinthe dutntnmvariableX.Forexample,amessage110101is represented bythepolynomial 1+X+X3+X5. The polynomial iswrittenlow-order-to-high-order because thesepolynomials willbetratnsmittedserially,high- orderfirst,aniditisconvenitional toindicatesignalflow asoccurrinigfromlefttoright. Thesepolynomials willbetreatedaccordingtothe lawsofordiniaryalgebrawithoneexception.Addition istobedonemodulotwo: 1Xa+IXa=OXa1Xa+OXa=1Xa=OXa+lXa OXa+OXa =OXa -1Xa= 1Xa. Forexample: addition 1+x +X3+X4 1+X X+X2multiplication +X4I+X I+X+X2 +X4 x +XI+X4I+X+X3+X4 X+X2+XI+X15 1+X2+XI +X5 Inadditiontotheassociative,distributive, anidcom- mnutativepropertiesofpolyniomials underthiskindof algebra, wehave,asinordinaryalgebra,uniquefactori- zation;thatis,every,polynomial canbefactoredinto primeorirreduciblefactorsinonlyoneway.'3 ALGEBRAIC DESCRIPTION OFCYCLICCODES Acycliccodeisdefinedintermsofageneratorpoly- nomialP(X)ofdegree n-k.Apolynomial ofdegreeless 1'J.E.Meggitt,"Errorcorrectingcodesforcorrectingburstsof errors,"IBMJ.Res.Dev.,vol.4,pp.329-334;July,1960. 12W.W.Peterson,"ErrorCorrecting andErrorDetectingCodes,"TechnologyPress,Cambridge,Mass.,tobepublished. 13See,forexample,R.D.Carmichael, 'Introduction tothe TheoryofGroupsofFiniteOrder,"DoverPublications, Inc.,NewYork,N.Y.,p.256;1956.thannisacodepolynomial,i.e.,acceptablefortrans- mission,ifandonlyifitisdivisblebythegenerator polynomialP(X).14Withthisdefinition,thesumoftwo codepolynomials isalsoacodepolynomial, forif FI(X)andF2(X)arepolynomialsofdegreelessthann, whicharedivisiblebyP(X),thenF,(X)+F2(X)isalso ofdegreelessthannanddivisiblebyP(X).Therefore, thesecodesareaspecialcaseofgroupcodes,asstudied bySlepian." IfP(X)hasXasafactor,theneverycodepolyno- mialhasXasafactorand,therefore,hasitszero-order coefficientequaltozero.Sincesuchasymbolwouldbe useless,wewillconsideronlycodesforwhichP(X)is notdivisiblebyX. Codepolynomials canbeformedbysimplymultiply- inganypolynomialofdegreelessthankbyP(X).The followingmethodhastheadvantage,however,thatit resultsinacodepolyniomial inwhichthehigh-order coefficients aremessagesymbolsandthelow-order coefficients arechecksymbols.Toencodeamessage polyrnomialG(X),wedivideXn-kG(X)byP(X)and thenaddtheremainderR(X)resultingfromthisdivi- SiolntoXn-kG(X)toformthecodepolynomial: XS-kG(X) =Q(X)P(X)+R(X), whereQ(X)isthequotientandR(X)theremainderre- sultingfromdividingX-kG(X)byP(X).Sincein modulotwoarithmetic,additionandsubtraction are thesame, F(X)=Xn-kG(X)+R(X)=Q(X)P(X), whichisamultipleofP(X)and,therefore,acode polynomial. Furthermore, R(X)hasdegreelessthan n-k,andXfl-kG(X)haszerocoefficientsinthen-k low-orderterms.Thusthekhighest-order coefficientsof F(X)arethesameasthecoefficienitsofG(X),whichare themessagesymbols.Thelowordern-kcoefficients ofF(X)arethecoefficientsofR(X),andthesearethe checksymbols. Example:Consideracodeforwhichn=15,k=10, anidn-k=5whichusesthegeneratorpolynomial P(X)=1-iX'+X4 +X5.Toencodethemnessage 1010010001corresponding tothepolynomialG(X)=1 +X2+X5+X9, wedivideX5G(X)byP(X)andfind theremainder.Bylongdivisionitcanibefoundthat X5+X7+XIO+X14=(1+X2+X4+X5) .(1+X+X2+X3+ X7+X8+X9)+(1+X). Thecodepolynomialisformedbyaddingtheremainder (1+X)toX5G(X): 14Accordingtotheusualdefinition,acycliccodeisagroupcodewiththeaddedpropertythatthecyclicshiftofacodevectorisalso acodevector.Codesobtainedbymakinganumberoftheleadinginformationsymbolsidenticallyzeroanddroppingthemarecalledshortenedcycliccodes.ThecodesdescribedinthispaperarecycliccodesifXm-1isevenlydivisiblebyP(X),andotherwiseareshort.einedcycliccodes.SeePrange,footnote1,andPeterson,footnote12. 15D.Slepian,"Aclassofbinarysignalingalphabets,"BellSys.Tech.J.,vol.35,pp.203-234;January,1956.1961 229 PROCEEDINGS OFTHIEIRE F(X)=(1+X)+(X5+X7+XIO+X14) II000 check symbols1010010001 information symbols PRINCIPLES OFERRORDETECTION AND ERRORCORRECTION Anencoded messagecontaining errorscaniberepre- sentedby H(X)=F(X)+E(X) whereF(X)isthecorrectencodedmessageandE(X)is apolynomial whichhasanonzerotermineacherrone- ousposition.Becausetheadditionismodulotwo, F(X)+E(X)isthetrueencoded messagewiththe erroneouspositionschanged. Ifthereceived messageH(X)isnotdivisibleby P(X),thenclearly anerrorhasoccurred.If,onthe otherhand,H(X)isdivisiblebyP(X),thenH(X)isa codepolynomial andwemustacceptitastheonewhich wastransmitted, eventhougherrorsmayhaveoccurred. SinceF(X)wasconstructed sothatitisdivisibleby P(X),H(X)isdivisiblebyP(X)ifandonlyifE(X)is also.Therefore, anerrorpatternE(X)isdetectable if andonlyifitisnotevenlydivisiblebyP(X).Toinsure aneffectivecheck,thegeneratorpolynomial P(X) mustbechosensothatnoerrorpatternE(X)which wewishtodetectisdivisiblebyP(X). Todetecterrors,wedividethereceived,possibly erroneous, messageH(X)byP(X)andtestthere- mainder.Iftheremainderisnonzero, anerrorhasbeen detected.Iftheremainder iszero,eithernoerrororan unidetectable errorhasoccurred. Example: F(X)=1+X+X5+X7+X10+X14 =110001010010001, E(X)X3+X6+X7 =000100110000000, H(X)F(X)+E(X) =1+X+X3+X5+X6+X10+ X14 =11010110001000 1. ThisF(X)wastakenfromthepreviousexample.The remainderafterH(X)isdividedbyP(X)=1+X2+X4 +X5isX2+X3+X4, andthefactthatthisisnotzero showsthatanerrormusthaveoccurred.Thesame remainder occursifE(X)isdividedbyP(X),since F(X)isdivisiblebyP(X). Theabilityofacodetocorrecterrorsisrelatedto itsabilitytodetecterrors.Forexample, anycode whichdetectsalldoubleerrorsiscapableofcorrecting anysingleerror.Thiscanbeseenbynotingthatifonly asingleerroroccurs,wecantrytocorrectitbytrying tochangeeachsymbol.Apolynomial withoneerrorandonesymbolchangedcanbeacodepolynomialonly iftheerroneoussymbolistheonewhichwaschanged, sinceallothercombinations areequivalenttodouble errorsand,therefore,aredetectable.Similarly,acode whichdetectsallcombinations of2terrorscancorrect anycombination ofterrors,sinceiftorfewererrors occur,changingallcombinations oftorfewerpositions resultsinacodepolynomial onlyifalltheerroneous positionlsarechaniged.Thesamneargumentshowsthat anycodecapableofdetectinganytwoerrorburstsof lengthborlesscancorrectainysinigleburstoflengthb orless.Finally,theconverseofthesestatementsisalso true;anyt-errorcorrectingcodecandetectanycombi- nationof2terrorsandanycodecapableofcorrecting anysingleburstoflengthbcanbeusedinsteadtodetect anlycombination oftwoburstsoflengthb. DETECTION OFSINGLEERRORS Theorem1:Acycliccodegeneratedbyanypolynlomial P(X)withmorethanonetermdetectsallsingleerrors. Proof:Asingleerrorintheithpositionofanenicoded message(countingfromtheleftandniumberingtheleft- mostpositionzero)corresponds toanerrorpolynomial Xi.Toassuredetectionofsingleerrors,itisnecessary onlytorequirethatP(X)doesnotdivideXievenly. Certainlynopolynomialwithmorethanonetermdi- videsXievenly.Q.E.D. Thesimplestpolynomialwithmorethanonetermis 1+X: Theorem2:Everypolynomialdivisibleby1+Xhas anevennumberofterms. Proof:LetF(X)=Xa+Xb+XC+.=(1+X)Q(X). Substituting X=1gives F(1)=1+1+1+(1+1)Q(1)=0. Thereisone"1"inF(1)foreachterm,andsincethe sumiszero,theremustbeanevennumberofterms. Q.E.D. ItfollowsthatthecodegeneratedbyP(X)=1+X detectsnotonlyanysingleerror,butalsoanlyoddnum- beroferrors.Infact,thechecksymbolmustsimnply beanover-allparitycheck,chosentomakethenumber ofonesinthecodepolynomialeven. Anypolynomialoftheform1+Xccontainsafactor 1+Xsince1+Xc=(1+X)(Xc-1+XC2+...+1) Therefore,ifP(X)containsafactor1lXc,anyodd numberoferrorswillbedetected. DOUBLEANDTRIPLEERRORDETECTING CODES(HAMMINGCODES) ApolynomialP(X)issaidtobelongtoanexponent eifeistheleastpositiveintegersuchthatP(X)evenly dividesXe-1(=Xe+1 mod2). Theorem3:AcodegeneratedbythepolynomialP(X) detectsallsingleanddoubleerrorsifthelengthnofthe codeisnogreaterthantheexponentetowhichP(X) belongs. Proof:Detectionofalldoubleerrorsrequiresthat230 January PetersonandBrown:CyclicCodesforErrorDetection P(X)doesnotevenlydivideXi+Xiforanyi,j<n. WecanfactorXi+Xi(assumingi<j)toX4(1+Xi-i). Itissufficient.torequirethatP(X)shouldnotdivide 1+Xi-i,sinceP(X)isassumednottobedivisiblebyX. Butj-i<n_e,anidtherefore,sinceP(X)belongstothe exponente,P(X)cannotdivide1+Xi-i.Thusthecode willdetectdoubleerrors.SinceP(X)isnotdivisibleby Xandcertainilycouldniotbejusttheconstant1,it musthavemorethanoneterm,andwill,byTheorem1, detectsingleerrorsalso.Q.E.D. Itcanbeshowinthatforanymthereexistsatleast onepolynomialP(X)ofdegreemthatbelonigsto e=2"-1.Thisisthemaximumpossiblevalueofe. Polynomials withthisproperty(usuallycalledprimnitive polynomials) arealwaysirreducible. Afewsuchpoly- nomialsarelistedinAppendixII,andmoreextensive tablesareavailable."2"6 Thusforanymthereisadouble- errordetectingcodeoflengthn=2m-1generatedbya polynomialP(X)ofdegreem,whichtherefore,hasm checksymbolsand2m_1-minformation symbols. Thesecodescanbeshowntobecompletelyequivalent toHammingsingle-errorcorrectingcodes.2312,17 Theorem4:AcodegeneratedbyP(X)=(1+X)P,(X) detectsallsingle,double,andtripleerrorsifthelength nofthecodeisnogreaterthantheexponentetowhich P,(X)belongs. Proof:Thesingleandtripleerrorsaredetectedbythe presenceofthefactor1+X,asisshownbyTheorem2, anddoubleerrorsaredetectedbecauseP,(X)belongs totheexponente.n,exactlyasinTheorem3.Q.E.D. CodesofmaximumlengthresultifP1(X)isaprimi- tivepolynomial, andthesecodesareequivalent to Hamminigsingle-errorcorrecting,double-errordetecting codes."2",15 DETECTION OFABURST-ERROR Aburst-erroroflengthbwillbedefinedasanypattern oferrorsforwhichthenumberofsymbolsbetweenthe firstandlasterrors,includingtheseerrors,isb. Example: TheE(X)=X3+X6+X7 =000100110000000 ofthepreviousexampleisaburstoflength5. Theorem5:Anycycliccodegeneratedbyapoly- nomialofdegreen-kdetectsanyburst-erroroflength n-korless. Proof:Clearly,anyburst-errorpolynomial canbe factoredintotheformE(X)=XiE,(X)whereE,(X)is ofdegreeb-1.ThisburstcanbedetectedifP(X)does notevenlydivideE(X).SinceP(X)isassumednotto 16A.A.Albert,"Fundamental ConceptsofHigherAlgebra,"UniversityofChicagoPress,Chicago,Ill.;1956.Thisbookcontains atableofirreduciblepolynomialsgivingtheexponentetowhichtheybelong(seep.161). 17N.M.Abramson,"Anoteonsingleerrorcorrectingbinarycodes,"IRETRANS.ONINFORMATION THEORY,Vol.IT-6,pp.502-503;September,1960.haveXasafactor,itcoulddivideE(X)onlyifitcould divideE,(X).Butifb.n-k,P(X)isofhigherdegree thanEI(X)and,therefore,certainlycouldnotdivide E,(X).Q.E.D. Ahighpercentageoflongerburstsaredetectedats well. Theorem6:Thefractioilofburstsoflenigthb>n-k thatareundetectedis 2-(7'-k)ifb>n-k+1,2-(nt-k-1)ifb=n-k+1. Proof:TheerrorpatterinisE(X)=XiE,(X)where E,(X)hasdegreeb-1.SinceE,(X)hastermsXOand Xb-1,thereareb-2termsXi,whereO<j<b-1, that canhaveeitherzerooronecoefficieints,anidsothereare 2b-2distinctpolynomials E,(X). Theerrorisundetected ifandonlyifEI(X)has P(X)asafactor. E1(X)=P(X)Q(X). SinceP(X)hasdegreen-k,Q(X)musthavedegree b-I-(n-k). Ifb-1=n-k, thenQ(X)=1,anidthere isonlyoneE,(X)whichresultsinoneundetectederror, namelyE1(X)=-P(X).Theratioofthenumberofuni- detectedburststothetotalnumberofburstsis,there- fore,1/2b-2=2-(tn-k-1)forthiscase.Ifb-1>n-k, Q(X)hastermsXOandXb-l-(n-k)andhasb-2-(n-k) arbitrarycoefficients. Thereare,therefore,2b-2-(n-k) choicesofQ(X)whichgiveundetectable errorpatternis. Theratioforthiscaseis2b-2-(n-k)/2b-2 =2-(n-k).Q.E.D. DETECTION OFTwoBURSTSOFERRORS(ABRAMSON ANDFIRECODES) Theorem7:ThecycliccodegeneratedbyP(X)=(1 +X)P1(X)detectsanycombination oftwoburst-errors oflenigthtwoorlessifthelengthofthecode,n,isn10 greaterthane,theexponenttowhichP1(X)belongs. Proof:Therearefourtypesoferrorpatterns. 1)E(X)=Xi+Xi 2)E(X)=(Xi+X'+')+Xi 3)E(X)=Xi+(Xi+Xi+') 4)E(X)=(Xi+Xi+')+(Xi+Xi+') 2)anid3)haveoddnumbersoferrorsandsotheyare detectedbythe1+XfactorinP(X).For4),E(X) =(1+X)(X'+Xi). The1+Xfactoriscancelledbythe 1+XfactorinP(X)sowewillrequireforboth1)and 4)thatXi+XiisnotevenlydivisiblebyP,(X). Xi+XjisnotevenlydivisiblebyP,(X)asisshownin theproofofTheorem3.Q.E.D. ThesecodesareequivalenttotheAbramsoncodes, whichcorrectsingleanddoubleadjacenterrors.2'1They arealsothesameastheHammingsinigle-errorcorrect- ing,double-errordetectingcodesofTheorem6. Theorem8:Thecycliccodegeneratedby P(X)=(Xc+1)Pi(X) willdetectanycombination oftwobursts1961 231 PROCEEDINGS OFTHEIRE E(X)=XiEl(X)+XiE2(X), providedc+1isequaltoorgreaterthanthesumofthe lengthsofthebursts,P,(X)isirreducibleandofdegree atleastasgreatasthelengthoftheshorterburst,and providedthelengthofthecodeisnogreaterthanthe leastcommonmultipleofcandtheexponentetowhich P,(X)belongs. Theproof,whichiselementarybutratherlong,is giveninAppendixIV.TheseareFirecodes.4"12 OTHERCYCLICCODES Thereareseveralimportantcycliccodeswhichhave notbeendiscussed.Burst-errorcorrectingcodeshave beentreatedalsobyMelas,5Meggitt,iandReiger.6 Codesforcorrectingindependent randomerrorshave beendiscoveredbyMelas.10Prange,'andBoseand Chaudhuri.9"2"8Anyofthesecodescanalsobeusedfor errordetection.TheBose-Chaudhuri codesarepar- ticularlyimportant. Foranychoiceofmandtthere existsaBose-Chaudhuri codeoflength2m-1whichis capableofcorrectinganycombination ofterrors(or alternatively, detectinganycombination of2terrors) andwhichrequiresageneratorpolynomialofdegreeno greaterthanmt.Thedescriptionofthestructureof thesecodesandthemethodsforchoosingthepolyno- mialsisbeyondthescopeofthispaper. IMPLEMENTATION Thusfar,analgebraicmethodhasbeengivenforen- codinganddecodingtodetectvarioustypesoferrors. Briefly,toencodeamessage,G(X),n-kzerosarean- nexed(i.e.,themultiplication Xn-kG(X)isperformed) andthenXn-kG(X)isdividedbyapolynomialP(X)of degreen-k.Theremainderisthensubtracted from Xn-kG(X).(Itreplacesthen-kzeroes.)Thisencoded messageisdivisiblebyP(X),butwehaveshownthat ifP(X)isproperlychosen,themessagewillnotbe evenlydivisibleifitcontainsdetectable errors.The onlynontrivialmanipulation tobeperformedforboth encodinganderrordetectionisdivisionbyafixed polynomial,P(X). Thefollowingisanexampleofdivisionunderaddi- tionmodulotwo: 1XI+1X2+0X+1 1X2+0X+1/1X5+1X4+1X3+0X2+1X+0 1XI+0X4+1XI 1X4+0X3+0X2+1X+0 1X4+0X3+1X2 0XI+1X2+1X+0 1X2+OX+1 1x+1 18W.W.Peterson,"Encodinganderror-correction proceduresfortheBose-Chaudhuri codes,"IRETRANS.ONINFORMATIONTHEORY,vol.IT-6,pp.459-470;September,1960.Wenowrepeatthisdivisionemployinigonilythecoef- ficientsofthepolynomials: 1101 1o/11010 I01 10010 101 0110 101 11 Itcanbeseenthatmodulotwoarithmetichassim- plifiedthedivisionconsiderably. Furthermore, wedo notrequirethequotient,sothedivisiontofindthere- maindercanbedescribedasfollows: 1)Alignthecoefficientofthehighestdegreetermof thedivisorandthecoefficientofthehighestdegree termofthedividendandsubtract(thesameas addition). 2)Alignthecoefficientofthehighestdegreeterm ofthedivisorandthecoefficientofthehighest degreetermofthedifferenceandsubtractagain. 3)Repeattheprocessuntilthedifferencehaslower degreethanthedivisor.Thedifferenceisthere- mainder. Thehardwaretoimplementthisalgorithmisashift registerandacollectionofmodulotwoadders.(A modulotwoadderisequivalenttothelogicaloperation EXCLUSIVE OR).Thenumberofshiftregisterposi- tionsisequaltothedegreeofthedivisor,P(X),andthe dividendisshiftedthroughhighorderfirstandleftto right.Asthefirstone(thecoefficientofthehigh-order termofthedividend)shiftsofftheendwesubtractthe divisorbythefollowingprocedure: 1)Inthesubtractionthehigh-ordertermsofthedivi- sorandthedividendalwayscancel.Asthehigh- ordertermofthedividendisshiftedofftheendof theregister,thispartofthesubtraction isdone automatically. 2)Modulotwoaddersareplacedsothatwhenaone shiftsofftheendoftheregister,thedivisor(except thehigh-ordertermwhichhasbeentakencareof) issubtractedfromthecontentsoftheregister. Theregisterthencontainsadifferencethatis shifteduntilanotheronecomesofftheendand thentheprocessisrepeated.Thiscontinuesuntil theentiredividendisshiftedintotheregister. Fig.1givesaregisterthatperformsadivisionby 1+X2+X4+X5. Notethatifalignmentofdivisorand dividendisconsideredtobeaccomplished whenthe high-ordertermofthedividendshiftsofftheend,then thedivisorisautomatically subtracted.232 January PetersonandBrown:CyclicCodesforErrorDetection TheshiftregistershowninFig.1has,ifusedforen- coding,onedrawbackthatcanbeovercomebyaslight modification. Recallthatwhenencodingamessage polynomial,G(X),wecalculatetheremainderofthe divisionofXn-kG(X)byP(X).Thestraightforward procedureistoshiftthemessagefollowedbyn-k zeroesintotheregister.Whenthelastzeroisinthe registerweobtaintheremainder.Becausethisre- mainderreplacesthen-kzerostoformtheencoded message,itisnecessarytodelaythemessagen-kshift timessothattheremaindercanbegatedinfromthe encoderregisteratthepropertime. Anexampleofthismethodofencodingisgivenin Fig.2.Initially,thegateG1isopenandthegateG2is shorted,allowingtheremainderondividingXn-kG(X) tobecalculated.Afterthemessageplusn-kzerosis shiftedin,G1isshortedandG2isopened.Thisallows theremainderwhichisnowintheregistertoreplace then-kzerosintheoutput.Errordetectionwiththis circuitrequiresthatgateG1beopenandgateG2be shorted.AfterH(X)hasbeenshiftedin,theregister SHIFTREGISTERPOSITION GEXCLUSIVEOR Fig.1-Ashiftregisterfordividingby1+X2+X4+X5. Fig.3-Amoreefficientcircuitforencodinganderrordetection.(Inthisexample,P(X) =1+X2+X4+X5.)containstheremainder.Ifthisisnonzero,anerrorhas occurred. Thedelayofn-kshiftscanbeavoidedifFig.2is modifiedtogivethecircuitofFig.3.InFig.3,instead ofshiftingthepolynomialintothelow-orderendofthe register,itistreatedasifitwereshiftingoutofthe high-orderend.Thisisequivalenttoadvancingevery terminthepolynomialbyn-kpositions,ormultiply- ingbyXn-k.Nowinencoding,assoonasG(X)hasbeen completelyshiftedintotheregister,theregistercon- tainstheremainderondividingXn-kG(X)byP(X). ThengateG1isshorted,gateG2isopened,andthere- mainderfollowstheundelayedG(X)outoftheenicoder toformF(X). Tominimizehardware,itisdesirabletousethesame registerforbothencodinganderrordetection,butif thecircuitofFig.3isusedforerrordetectionwewill gettheremainderondividingXn-kH(X)byP(X)in- steadoftheremainderondividingH(X)byP(X).It turnsoutthatthismakesnodifference,forifH(X)is evenlydivisiblebyP(X)thenobviouslyH(X)Xn-kis evenlydivisible,andifH(X)isnotevenlydivisibleby P(X)thenH(X)Xn-kwillnotbeevenlydivisibleeither, providedthedivisorP(X)doesnothaveafactorX. AnyusefulP(X)willsatisfythisrestriction.Thecir- cuitofFig.3can,then,beusedforbothencodingand errordetection. Errorcorrectionisbyitsnatureamuchmoredifficult taskthanerrordetection.Itcanbeshownthateach differentcorrectable errorpatternmustgiveadifferent remainderafterdivisionbyP(X).Therefore,errorcor- rectioncanbedoneasfollows: 1)DividethereceivedmessageH(X)=F(X)+E(X) byP(X)toobtaintheremainder. 2)ObtaintheE(X)-corresponding totheremainder fromatableorbysomecalculation. 3)SubtractE(X)fromH(X)toobtainthecorrect transmitted messageF(X). Boththeencodingandstep1ofthedecodingarethe sameforerrorcorrectionasforerrordetection.The error-correction equipmentismorecomplexinthatit requiresequipmentforthetablelook-uporcomputa- tionofstep2,anditrequiresthattheentirereceived messageH(X)bestoredtemporarilywhiletheremainder isbeingcalculatedandE(X)isbeingdetermined. The calculationrequiredinstep2canbedonesimplywith ashiftregisterforburst-error orsingle-errorcorrecting codes,butisquitecomplexforcodesthatcorrectmul- tiplerandomerrors.Detailsoferror-correction proce- duresarebeyondthescopeofthispaper,butcanbe foundinreferences.111217 CONCLUSION Asimplepresentation ofcycliccodeshasbeengiven intermsofpolynomials. Theattractivefeaturesofthese codesforerrordetection,boththeirhighefficiencyand theeaseofimplementation, havebeenemphasized.Fig.2-Onemethodofencodingondetectingerrors.(Inthisexample,P(X)=1+X2+X4+X5.)233 1961 PROCEEDINGS OFTHEIRE APPENDIXI NOTATION k=numberofbinarydigitsinthemessagebefore encoding, n=numberofbinarydigitsintheencodedmessage, n-k=numberofcheckdigits, b=lengthofaburstoferrors, G(X)=messagepolynomial(ofdegreek-1), P(X)=generatorpolynomial (ofdegreen-k), R(X)=remainder ondividingXn-kG(X)byP(X), R(X)isofdegreelessthann-k, F(X)=encodedmessagepolynomial, F(X)=Xn-kG(X)-R(X), E(X)=errorpolynomial, H(X)=receivedenicodedmiessagepolynomial, H(X)=F(X)+E(X). APPENDIXII ASHORTTABLEOFPRIMITIVE PrimitivePolynomial 1+X 1+X+X2 1+X+X31+X+X4 1+X2+X5 1+X+XI 1+X3+X7 1+X2+X3+X4+X8 1+X4+X9 1+X3+Xlo 1+X2+Xll 1+X-+X4A+X6+X'2 1+X+X3+X4+X13 1+X+X6+X1+X14 1+-X'4+X'5POLYNOMIALS e 1 3 7 15 31 63127 255511 10232047 4095 8191 1638332767 APPENDIXIII DATAFORSOMEREPRESENTATIVE CODES DetectionCapabilities Anyoddnumberoferrors Twoerrors,aburstoflength4orless,88percentof theburstsoflength5,94percentoflongerbursts*kinax anyvalue 11 Twoerrors,aburstof9orless,99.6percentofthe502 burstsoflength10,99.8percentoflongerbursts Twoburstsoflength2orless,anyoddnumberof10 errors,aburstof5orless,93.8percentofthebursts oflength6,96.9percentoflongerburstst Twoburstsofcombiniedlength12orless,anyodd22495numberoferrors,aburstof22orless,99.99996per centoftheburstsoflength23,99.99998percentoflongerbursts Anycombination of6orfewererrors,aburstoflength 11orless,99.9percentofburstsoflength12, 99.95percentoflongerburstsn-k 1 4 9 5 22 1211 I.-- 99231P(X) Reference 1+X Theorem2 1+X+XI Theorems3,5,6 1+X4+X9 Theorems3,5,6 (1+X+X4)(1+X)=1+X2 Theorems2,5,6,7+X4+X5 (I+X2+Xll)(1+Xll)=1+X2 Theorems2,5,6,8+X13+X22 1+X2+X4+X5+X6+X'O+Xll (1+X)( 1+X3+X'O) (1+X+X2+X3+X1O) (1+X2+X3+X8+XIO) *Note:1+X+X4belongstoe=15and11+4=15. tNote:Thisisthecodeusedinallexamples.Anycombination of7orfewererrors,anyoddnum- beroferrors,aburstoflength31orless,allbutabout 1in109oflongerburstsTheorems5,6,andfootnoteI Theorems2,5,6,andfoot-notes9,12,18234 January 235 PetersonandBrown:CyclicCodesforErrorDetection APPENDIXIV PROOFOFTHEOREM8 Theerrorpolynomialhastheform: E(X)=Xi[E,(X)+Xi-iE2(X)Z]. E1(X)hasdegreebi-1andE2(X)hasdegreeb2-1. ThegeneratorpolynomialP(X)cannothaveafactor XsoweneedonlycotisiderthefactorofE(X)inbrack- ets.Letj-i=d,assumeE'(X)=E1(X)+XdE2(X)is divisiblebyXc+1,andletd=cq+rwithr<c. Then, E'(X)=E1(X)+XcY+rE2(X) -E1(X)+XrE2(X)+[XrE2(X)j.[XCQ+11.(1) NowXc+IcontainsafactorXc+1for Xcq+1=(X''+1)(Xc(q-1)+Xc(q-2 +Xc.(q-3)+...+XO). Hencetherightmosttermin(1)isdivisiblebyXG+1. E'(X)wasassumeddivisiblebyXc+1anidsofrom(1), E1(X)+XTE2(X)mustbedivisiblebyXc+1.Usingthis result,wecanlet E1(X)+XTE2(X) =[xc+1I][Q(X)I E1(X)+XrE2(X)=Q(X)+XCQ(X). (2, WewillassumethatQ(X)$0.Letthedegreeof Q(X)beh.Thedegreeoftheright-handsideof(2)is c+handthedegreeoftheleft-handsideiseitherb1-1 orr+b2-1.Then,for(2)tobetruewemlusthave eitherc+h=bi-1 orc+h=r+b2-1. Sinceitwasas- sumedthatc>.bi+b2-1wemusthavethesecond relation. c+h=r+b2-1. Againusingc>b1+b2-1wehave bi+b2-1+h_r+b2-1 orb+hr. Fromthis,bi_rorb1-1<randasb1$0,h<r. Applyingtheseresultsto(2),weseethatbothE1(X) andQ(X)areoflowerdegreethananyofthetermsin XrE2(X).Itfollowsthen,giventheassumption thatQ(X)0,that XrE2(X)=XcQ(X). (3) AsE2(X)alwayscontainsanXOterm,thelowest orderterminXrE2(X)isofdegreer.Thelowestorder terminXcQ(X)isofdegreeatleastcbutr<cso(3)can neverbesatisfied.Therefore,theonlysolutionof(2)is withQ(X)=0givingE1(X)+XrE2(X) =0. AsE1(X)alwayscontainsanXOtermi,r=Oaind E1(X)=E2(X).Substituting in(1)gives E'(X)=E2(X)[XcQ+1]. Thisistheformoftheerrorpolynomialifitisevenily divisiblebyXC+1.Itissufficienttoshowthatthis polynomialisnotevenlydivisiblebyP1(X)toguarantee thatE(X)isneverevenlydivisiblebyP(X)=P(X),[Xc+].P1(X)isirreducible,sotodivideE'(X)=E2(X)[Xc-q+litmustdivideoneofthefactors.Forthis specialcase,E1(X)=E2(X) sobl=b2,andsiniceboth burstshavethesamelength,thisisthelenigthofthe shorterburst.ItwasspecifiedthatP1(X)isofdegreeno lessthanthelengthoftheshorterburstsoitisofhigher degreethanE2(X)andcannotdivideE2(X). ItremainstoshowthatP1(X)doesnotevenilydivide Xcq+1Makethesubstitution cq=ue+vwhereeisthe exponenttowhichP1(X)belonigsandv<e.NowvO0 becausecqislessthanorequaltothelengthofthe messageandthelengthofthemessageislessthanorequialtotheleastcommonmiiultipleofcande.Since cqisamnultipleofc,itcannotbeamultipleofe. xcq+1-X1te+V+1 Xct,+1=XV+1+XV(Xie+1). Aswasshownpreviously, Xue+1isdivisibleby Xe+1.Furthermore, P1(X),bydefiniitioni,divides Xe+1;therefore,P1(X)dividesXue+1.However,Xe+1 isthelowestdegreepolynomialofthisfornmthatP1(X) divides,soP1(X)doesnotdivideXv1-.Asv$0,we haveshownthatP1(X)doesnotdivideXI.+1,coni- pletingtheproof.1961