On the Redundancy of Two-Dimensional Balanced Code

OntheRedundancyofTwo-DimensionalBalancedCodesErikOrdentlich,RonM.Roth*ComputerSystemsLaboratoryHPL-97-143December,1997E-mail:[e-mail]@cs.technion.ac.ilbalancedarrays,DC-freecodes,two-dimensionalcodingLetcn×mbethesetofbinaryn×marraysinwhicheachrow,andrespectivelyeachcolumn,hasthesamenumberof0'sand1's.Weprovethelowerboundlog2|cn×m|≥nm–1/2(nlog2(2m)+mlog2(2n)).WealsoshowthatthisboundistightuptoanadditivetermO(n+logm).*OnsabbaticalleavefromHPLaboratoriesIsrael,ComputerScienceDepartment,Technion,Haifa32000,Israel.WorksupportedinpartbygrantNo.95-00522fromtheUnited–States–IsraelBinationalSciencesFoundation(BSF),Jerusalem,Israel.©CopyrightHewlett-PackardCompany19971IntroductionInthiswork,weconsidertheenumerationproblemoftwo-dimensionalbalancedbinarynmarrays,inwhicheachrow,andrespectivelyeachcolumn,hasthesamenumberof0’sand1’s(nandmareeven).Byabinaryn-vectorwerefertoavectorinIRnwithentriesrestrictedtof0;1g.Abinaryn-vectorviscalledbalancedifnisevenandhalfoftheentriesofvare1’s.Muchisknownaboutcodesthatmapunconstrainedinputsequencestoone-dimensionalbalancedbinaryn-vectors.ThosecodesgoalsobythenamesDC-freeorzero-disparitycodes[10].Wedenotethesetofallbalancedbinaryn-vectorsbyAn;clearly,jAnj=nn=2!:TheratiojAnj=2n=2nnn=2willbedenotedbyn.TheredundancyofasetCf0;1gnisdenedbynlog2jCj.TheredundancyofAn,denotedn,isgivenbyn=nlog2jAnj=log2n:(1)Itisknownthat1p2nn1q2n(2)(see[5],[8,p.309]).AveryecientencodingalgorithmduetoKnuth[5]mapsunconstrainedbinarywordsintoAnwithredundancydlog2ne.SeealsoimprovementsbyAl-BassamandBose[1],andTallini,Capocelli,andBose[12].Lesshasbeenknownabouttheredundancyoftwo-dimensionalbalancedarrays.Byabinarynmarraywemeanannmarraywhosecolumnsarebinaryn-vectors.Abinarynmarrayiscalledbalancedifnandmarebothevenandeachoneoftherowsandcolumnsofisbalanced.WedenotebyAnmtheset(orthecode)ofallbalancednmarrays.TheredundancyofAnm,denotednm,isgivenbynm=nmlog2jAnmj:AnecientcodingalgorithmintoasubsetofAnmispresentedin[11]thathasredundancynlog2m+mlog2n+O(n+mloglogn).Initssimplerversion,thealgorithmin[11]balancestherowsusingoneofthealgorithmsin[1],[5],or[12];bytradingthosealgorithmswiththe(morecomputationallycomplex)enumerativecodingofAm,theredundancycanbereducedto12(nlog2m)+mlog2n+O(n+mloglogn).InSection2weprovetheupperboundnmnm+mn12nlog2(2m)+mlog2(2n);1andinSection3weshowthatthisboundistightuptoanadditivetermO(n+logm).Thisboundimpliesthatrequiringbalancedrowsinabinaryarraydoesnot\interferewithrequiringbalancedcolumns.Note,however,thatthoserequirementsarenotindependent:forinstance,ifallnrowsinabinarynmarrayarebalanced,andm1ofthecolumnsarebalancedaswell,thensomustbetheremainingcolumn.Thecomputationoftheredundancyoftwo-dimensionalbalancedarrayscanberelevanttothecodingapplicationthatweoutlinenext.Incurrently-availablemagneticandopticalmemorydevices,dataisrecordedalongtracks,thustreatingtherecordingdeviceasone-dimensional.Recentproposalsforthedesignofopticalstorage|inparticularholographicmemory|trytotakeadvantageofthefactthattherecordingdeviceistwo-dimensional(oreventhree-dimensional),therebyincreasingtherecordingdensity[4],[9].Thenewapproach,however,introducesnewtypesofconstraintsonthedata|thoseconstraintsnowbecomemulti-dimensionalinnature,ratherthanone-dimensional.Thespecicconstraintstobeusedintherecentlysuggestedrecordingtechniquesareyettobecrystallized.Nevertheless,experimentsreportedonholographicmemory,andexperiencegatheredinotherexistingopticaldevices,suggestthat0’sand1’sintherecordeddataneedtobebalancedwithincertainareasorpatterns.ThesetAnmmayturnouttobeusefulforthatpurpose.2UpperboundontheredundancyofAnmInthissectionweprovethefollowingupperboundonnm.Proposition2.1Foreveryevenpositiveintegersnandm,nmnm+mn12nlog2(2m)+mlog2(2n):Proposition2.1isadirectcorollaryofthefollowinglowerboundonthesizeofAnm,combinedwith(1)and(2).Proposition2.2Foreveryevenpositiveintegersnandm,jAnmj2nmnmmn:Proposition2.2isaspecialcaseofLemma2.4whichwestateandprovebelow.Weintroducesomenotationsthatwillbeusedhereafterinthiswork.Letbeabinarynmarray(notnecessarilybalanced).Therowtypeofisanintegern-vectorw=(w1;:::;wn)wherewiisthesumoftheentriesoftheithrowof.2Foranintegern-vectorw=(w1;:::;wn),deneRm(w)tobethesetofallbinarynmarrayswhoserowtypeisw.Clearly,jRm(w)j=nYi=1mwi!(wedenemw=0ifw0orwm).Forevennandanintegern-vectorw,denotebyUm(w)thesetofallarraysinRm(w)whosecolumnsarebalanced.ForevenmwehaveAnm=Um((m=2)1n),where1ndenotestheall-onevectorinIRn.Forarealvectory,wedenotebykyk=kyk1thesumoftheabsolutevaluesoftheentriesofyandbykyk1thelargestabsolutevalueofanyentryofy.Thesupportofywillbedenotedbysupp(y).Notethatwheny1andy2arebinarym-vectors,thenky1y2kisthenumberofpositionsonwhichtheydier.Thesetf1;2;:::;ngwillbedenotedbyhni.Lemma2.3LetX1;:::;XnbeindependentBernoullirandomvariablestakingonf0;1gwithprobabilitiesProbfXi=1g=pi,i2hni,andsupposethatPni=1pi=n=2.Then,ProbnnXi=1Xi=n=2on;withequalityholdingifandonlyifpi=12foralli.Lemma2.3followsfromaresultduetoHoeding[7].Forthesakeofcomp