ISIT2007,Nice,France,June24-June29,2007OnTheGeneralizationofError-CorrectingWOMCodesAnxiao(Andrew)JiangComputerScienceDept.,TexasA&MUniversity,CollegeStation,TX77843,USAEmail:[email protected](WriteOnceMemory)codesarecodesforefficientlystoringandupdatingdatainamemorywhosestatetransitionisirreversible.StoragemediathatcanbeclassifiedasWOMincludesflashmemories,opticaldisksandpunchcards.Error-correctingWOMcodescancorrecterrorsbesidesitsregulardataupdatingcapability.TheyareincreasinglyimportantforelectronicmemoriesusingMLCs(multi-levelcells),wherethestoreddataarepronetoerrors.Inthispaper,westudyerror-correctingWOMcodesthatgeneralizetheclassicmodels.Inparticular,westudycodesforjointlystoringandupdatingmultiplevariables-insteadofonevariable-inWOMswithmulti-levelcells.Theerror-correctingcodeswestudyherearealsoanaturalextensionoftherecentlyproposedfoatingcodes[7].Weanalyzetheperformanceofthegeneralizederror-correctingWOMcodesandpresentseveralbounds.Thenumberofvalidstatesforacodeisanimportantmeasureofitscomplexity.Wepresentthreeoptimalcodesforstoringtwobinaryvariablesinnq-arycells,wheren=1,2,3,respectively.Weprovethatamongallthecodeswiththeminimumnumberofvalidstates,thethreecodesmaximizethetotalnumberoftimesthevariablescanbeupdated.I.INTRODUCTIONTheWriteOnceMemory(WOM)wasfirstintroducedbyRivestandShamir[10]tomodelthosememorieswhereeachbasicstorageelementcantransitfroma0-statetoa1-statebutnotviceversa.EarlyexamplesofWOMincludepunchcardsandopticaldisks.Inrecentyears,flashmemories,whichusefloatinggatesasstoragecells,haveemergedasanimportantfamilyofmemoriesthatcanbemodelledasWOMs.Inflashmemories,everymemorycellhasathresholdvoltagethatisoneofqpossiblevalues:0,1,..,q-1.Thethresholdvoltageisthestateofthecell.Movingthecellfromalowerstatetoahigherstatecanberealizedefficientlyusingeitherthehot-electroninjectionmechanismortheFowler-Nordheimtunnelingmechanism.However,movingthecellfromahigherstatetoalowerstateismuchmoreexpensive,becauseitrequireserasingandre-writingallthedatainamemoryblock,whichtypicallyconsistsofabout128kilobytes.Theerasureandrewritingofablockarenotonlyveryslow,butalsodegradethecells'qualityandshortenthememory'slifetime.Currently,aflashmemory'slifetimeisboundedbyaround105program-erasecycles.Forthisreason,theoperationofloweringacell'sstateshouldbedelayedasmuchaspossible.Whenweconsiderthetimeperiodbetweentwoblockerasureoperations,acell'sstatecanonlymoveupwardinitsqstates.Whenq>2,thecelliscalledamulti-levelcell(MLC).Thedatainmemoriesoftenneedtobeupdated,especiallyforapplicationssuchasfilesystems,programs,etc.SinceaWOM'sstatetransitionisirreversible,thenumberofupdatesitallowsislimited.ManyresearchershavestudiedWOMcodes,whereasinglevariableisstoredinaWOM,andtheWOMcodeaimsatmaximizingthenumberof timesthevariablecanberewritten(i.e.,updated)[2], [3],[6],[8],[11].MultiplefamiliesofWOMcodes,includinglinearcodes[1],[10],tabularcodes[10],codesbasedonprojectivegeometries[9],etc.,havebeeninvented.WOMcodesthatcancorrecterrorshavealsobeenexplored[4],[12].Thecapabilityoferrorcorrectionisespeciallyimportantforelectronicmemoriesusingmulti-levelcells.UsingMLCisafundamentalapproachforincreasingthedatadensity.Inflashmemories,q-arycellswhereq=4upto256havebeenimplemented.It,however,bringsreliabilityissues.Variousreasonscanmakethestateofacellbereadincorrectly,especiallyforadjacentstates.Wemodeltheproblemwestudyasfollows.Thememoryconsistsofncells,whereeachcellhasqstates:0,1,..,q-1.Acellcanchangefromstateitostatejifandonlyifi<j.(0<i,jq-1.)kvariablesarestoredinthememory,whereeachvariabletakesitsvaluefromanalphabetofsize1:{0,1,...,I-1}.Bydefault,initially,allthecellsareinstate0,andallthevariableshavethevalue0.Everywritechangesthevalueofexactlyonevariable.Weusettodenotethemaximumnumberofwritesallowedbythememoryintheworstcase.Specifically,foranysequenceofwrites,thefirsttofthemareguaranteedtobeimplementable.Weuse(cl,c2,...,c)-calledthecellstatevector-todenotethestatesofthencells,wherecie[0,q-1]isthestateofthei-thcell.ThevalueofEn1Ciiscalledtheweightofthecellstatevector.ForanytwocellstatevectorsA=(c,c2,,cn)andB=(c,C,..,c'),theirL1distanceisdefinedtobedL(A,B)=EnIci-c'.Weuse(vl,V2,....,v)-calledthevariablevector-todenotethevaluesofthekvariables,whereviC[0,1-1]isthevalueofthei-thvariable.Ourerrormodelhasthreeparameters:A+,A-,andE.Here,A+(resp.,A-)isthemaximummagnitudeofasingle-cellerrorintheupwarddirection(resp.,inthedownwarddi-rection),andEisthemaximumtotalmagnitudeoftheerrors.(Naturally,E>A+>0andE>A->0.)Specifically,let'suse(el,e2,...,en)-calledtheerrorvector-todenotethenadditiveerrorsinthencells.Fori=1,2,,n,itmakesthestateofthei-thcell,ci,tobemistakenlyreadas1-4244-1429-6/07/$25.00©2007IEEE1391Authorized licensed use limited to: Texas A M University. Downloaded on June 28,2010 at 21:47:02 UTC from IEEE Xplore. Restrictions