On Optimal Binary One-Error-Correcting

OnOptimalBinaryOne-Error-CorrectingCodesofLengthsand

DenisS.Krotov,PatricR.J.Östergård,andOlliPottonen

Abstract—BestandBrouwer[2]provedthattriply-shortened

anddoubly-shortenedbinaryHammingcodes(whichhavelength

and,respectively)areoptimal.Propertiesof

suchcodesareherestudied,determiningamongotherthingsparametersofcertainsubcodes.Autilizationofthesepropertiesmakesacomputer-aidedclassi cationoftheoptimalbinaryone-error-correctingcodesoflengths12and13possible;thereare237610and117823suchcodes,respectively(with27375and17513inequivalentextensions).Thiscompletestheclassi cationofoptimalbinaryone-error-correctingcodesforalllengthsupto15.Somepropertiesoftheclassi edcodesarefurtherinvestigated.Finally,itisprovedthatforany,thereareoptimalbinary

andthatone-error-correctingcodesofcannotbelengthenedtoperfectcodesoflength.IndexTerms—Automorphismgroup,classi cation,clique,error-correctingcode,MacWilliamstransform.

Abinarycodeoflength,size,andminimumdistanceissaidtobeancode.Sinceacodewithminimumdistanceisabletocorrectuptoerrors,suchacodeissaidtobe-error-correcting.Ifeverywordintheambientspaceisatdistanceatmostfromsomecodewordofa-error-correctingcode,thenthecodeiscalledperfect.

Themaximumsizeofabinarycodeoflengthandminimumdistanceisdenotedby;thecorrespondingcodesaresaidtobeoptimal.Forbinarycodesthereisadirectconnectionbetweenoptimalerror-correctingcodeswithoddandevenmin-imumdistance:

(1)

Onegetsfromtheoddcasetotheevencasebyextendingthecodewithaparitybit,andfromtheevencasetotheoddcasebyremovinganarbitrarycoordinate,calledpuncturing.Othertransformationsofcodesincludeshortening,whereacoordinateisdeletedandallcodewordsbutthosewithagivenvalueinthedeletedcoordinateareremoved,andlengtheningwhichisthereverseoperationofshortening.See[1]forthebasictheoryoferror-correctingcodes.

Whenstudyingoptimalerror-correctingcodes—orsubop-timalforthatsake—itisreasonabletorestrictthestudytocodesthatareessentiallydifferentinthefollowingsense.Twobinarycodesaresaidtobeequivalentifthecodewordsofoneofthecodescanbemappedontothoseoftheotherbytheadditionofavectorfollowedbyapermutationofthecoordinates.Suchamappingfromacodeontoitselfisanautomorphismofthecode;thesetofallautomorphismsofacodeformstheautomorphismgroupof,denotedby.

Acodewithonlyeven-weightcodewordsissaidtobeeven.Codesequivalenttoevencodesareofcentralimportanceinthecurrentwork;thesecodeshaveonlyeven-weightcodewordsoronlyodd-weightcodewords,andtheyarecharacterizedbythefactthatthedistancebetweenanytwocodewordsiseven.Wethereforecallsuchcodeseven-distancecodes(nottobecon-fusedwithcodesthathaveevenminimumdistance).

Hammingcodesareperfect(andtherebyoptimal)one-error-correctingcodes:

I.INTRODUCTION

BINARYcodeoflengthisaset,where

isthe eldoforder2.The(Hamming)distancebe-tweenelements,calledwords(orcodewordswhentheybelongtoacode),isthenumberofcoordinatesinwhichtheydifferandisdenotedby.Theminimumdistanceofacodeisthesmallestpairwisedistanceamongdistinctcode-words:

A

The(Hamming)weightofnonzerocoordinates.

ofawordisthenumber

ManuscriptreceivedFebruary18,2011;acceptedApril07,2011.DateofpublicationMay19,2011;dateofcurrentversionOctober07,2011.TheworkofD.S.KrotovwassupportedbytheFederalTargetProgram“Scienti candEdu-cationalPersonnelofInnovationRussia”for2009–2013(GovernmentContract02.740.11.0429)andbytheRussianFoundationforBasicResearchunderGrant10-01-00424.TheworkofP.R.J.ÖstergårdwassupportedbytheAcademyofFinlandunderGrants130142and132122.TheworkofO.Pottonenwassup-portedbytheAcademyofFinlandGrant128823,theHelsinkiInstituteofIn-formationTechnologyHIITproject“AlgorithmicSystems,”andbytheFinnishCulturalFoundation.

D.S.KrotoviswiththeSobolevInstituteofMathematicsandtheMechanicsandMathematicsDepartment,NovosibirskStateUniversity,630090Novosi-birsk,Russia.

P.R.J.ÖstergårdiswiththeDepartmentofCommunicationsandNet-working,AaltoUniversitySchoolofElectricalEngineering,00076Aalto,Finland,andalsowithLehrstuhlfürMathematikII,UniversitätBayreuth,95440Bayreuth,Germany(e-mail:patric.ostergard@tkk. ).

O.PottonenwaswiththeDepartmentofInformationandComputerScience,AaltoUniversitySchoolofScience,00076Aalto,Finland.HeisnowwiththeDepartamentdeLlenguatgesiSistemesInformàtics,UniversitatPolitècnicadeCatalunya,08034Barcelona,Spain.

CommunicatedbyM.Blaum,AssociateEditorforCodingTheory.DigitalObjectIdenti er10.1109/TIT.2011.2147758

BestandBrouwer[2]showedthatbyshorteningHammingcodesone,two,orthreetimes,onestillgetsoptimalcodes:

(2)

0018-9448/$26.00©2011IEEE

Forallbuttheverysmallestparameters,therearemanyin-equivalentcodeswiththeparametersin(2).Ingeneral,acom-pletecharacterizationorclassi cationofsuchcodesdoesnotseemfeasible,buttheclassi cationproblemcanbeaddressedforsmallparametersandgeneralpropertiesofthesecodescanbestudied.Forexample,theissuewhethercodeswiththesepa-rameterscanbelengthenedtoperfectcodeshasattractedsomeinterestintheliterature[3]–[6].For,everycode(2)canbelengthenedtoaperfectcodeandthiscanbedoneinauniquewayuptoequivalence[3].Consequently,codeswithsuchpa-rametersareinadirectrelationshiptotheperfectcodes,soourmaininterestisinthecodeswithand.

Oneaimofthecurrentworkistostudypropertiesofcodeswiththeparametersofdoubly-shortenedandtriply-shortenedperfectbinaryone-error-correctingcodes.ThisstudyisstartedinSectionIIbyconsideringcertainpropertiesofsubcodes,whichcanbeutilizedinacomputer-aidedclassi cationofoptimalbinaryone-error-correctingcodesoflength12and13,consideredinSectionIII.Itturnsoutthatthenumberofequivalenceclassesofandcodesis237610and117823,respectively.Somecentralpropertiesoftheclassi edcodesareanalyzedinSectionIV.Finally,in nitefamiliesofoptimalone-error-correctingcodesoflengthandthatcannotbelengthenedtoperfectone-error-cor-rectingcodesoflengtharepresentedinSectionV.Apreliminaryversionofsomeoftheresultsinthisworkcanbefoundin[6].

Asonlybinarycodesareconsideredinthecurrentwork,thewordbinaryisomittedinthesequel.

II.PROPERTIESOFSUBCODES

Somepropertiesrelatedtosubcodesofthecodesunderstudyareconvenientlyinvestigatedintheframeworkoforthogonalarrays.Anorthogonalarrayofindex,strength,degree,andorderisaarraywithentriesfrom

andthepropertythateverycolumnvector

appearsexactlytimesineverysubarray;necessarily

.Thedistancedistributionofancodeisde nedby

WewillneedthefollowingtheorembyDelsarte[7];formoreinformationabouttheMacWilliamstransform,seealso[1,Ch.5].

Theorem1:AnarrayisanorthogonalarrayofstrengthifandonlyiftheMacWilliamstransformofthedistancedistribu-tionofthecodeformedbythecolumnsofthearrayhasentries

,.

Wearenowreadytoproveacentralresult,essentiallyfol-lowingtheargumentsof[2,Th.6.1](where,however,thecase

ratherthanisconsidered).Theorem2:Every

codeisaneven-distancecodeandformsan

with,

,and

.

Proof:We rstshowthataneven-distance

codeformsanorthogonalarraywith

thegivenparameters.Letbethedistancedistributionof,andletbetheMacWilliamstransformof,thatis

(3)

where

isaKrawtchoukpolynomial.Itiswellknownthatand

for[7].

Asisaneven-distancecode,forodd,and,since

,wehave

(4)

Let

.Direct

calculationsnowshowthat

(5)

From(5)and

wederive

(6)

andforanyotherinteger.Wehave,

,and,sincehasminimumdistance4,.Utilizing(4),

wethenget

(7)

andthereby

Weknowthatinfact,sowehaveequal-itiesin(7).Thisimpliesthat,

thatis,for.By(6)andthecommentthereafter,itfollowsthatfor(and

).ApplicationofTheorem1showsthat

wehaveanorthogonalarraywiththegivenparameters.Toshowthatanycodeisindeedaneven-distancecode,weassumethatthereisacodewhichisnot,tolaterarriveatacontradiction.Thecodecanbeparti-tionedintosetsofeven-weightandodd-weightcodewords,de-notedbyand,respectively.Thatis,

KROTOVetal.:ONOPTIMALBINARYONE-ERROR-CORRECTINGCODESOFLENGTHSAND6773

,withand

.Foranycodewords,,,wehave

(asthedistanceis

oddandgreaterthan4).Let

whereistheweight-onevectorwiththe1incoordinate.We

nowknowthatisaneven-distancecodeforany.Wenextprovethatisanorthogonalarraywiththesamestrength(seetheearlypartoftheproof)asthedifferenteven-distancecodes.Theproofthatthesameholdsforisanalogous.W.l.o.g.,itsuf cestoconsiderthelastcoordinatesandtwo-tuplesthatdifferonlyinone(wechoosethelast)coordinate—inductionthenshowsthatthisholdsforanypairs—andshowthatthesetwo-tuplesoccurinequallymanycodewordsof.

Wedenotethesetofwordsinacodethathavevalueinthelastcoordinatesby.Then

Sinceand

bothformorthogonalarrayswith

strength

,,anditfollowsthat

.

Asisaneven-distancecodethatformsanorthogonalarraywithstrength,http://wendang.chazidian.comly,wenowhaveexceptforand,andcancarryoutcalculationscloselyre-latedto(7):

so

Butsimilarlyonegets

,andthereby

when

,acontradiction.

Corollary1:Acodehasauniquedis-tancedistribution.

Proof:Itsuf cestoprovethattheMacWilliamstransformofthedistancedistributionisunique.BytheproofofTheorem2,foracodewehaveforeveryexceptforandtheunknownvalues

and.Equation(3)givesapairofequationswhichdeterminestheunknownvalues.Consequently,theremarkattheendof[2]aboutthedistancedistributionofcertaincodesnotbeinguniqueappliesonlytotriply-shortenedperfectcodesandnottotriply-shortenedex-tendedperfectcodes.

Corollary2:Everycodewith

isaneven-distancecode.

Proof:Fromacodewiththegivenparametersthatisnotaneven-distancecode,onecangetasubcodeforwhichthesameholds.Thiscanbedonebyshorteninginacoordinatewheretwocodewordsthatareatoddmutualdistancehavethesamevalue.ThisisnotpossiblebyTheorem2.

Thedistance-graphofacodeisagraphwithonevertexforeachcodewordandedgesbetweenverticeswhosecorre-spondingcodewordsareatmutualdistance.

Corollary3:Every

codewithhasaconnecteddistance-3graph.Proof:Ifthedistance-3graphofancodeisnotconnected,thentherearemorethanonewayofextendingthecodetoancode;cf.[8,p.230].Inparticular,itcanthenbeextendedtoacodethatisnotaneven-distancecode.ThisisnotpossiblebyCorollary2.

Corollary4:Shorteningacodetimeswithgivesacodethatisaneven-distancecode.Inparticular,withand,wealwaysgeta

subcodeaftershorteningacodefour

times.

However,notallcodeswith

aresubcodesofsome

code.WeshallnowstrengthenthenecessaryconditioninCorol-lary4foracodetobeasubcodeofa

code.Sincetheresultisofinterestspeci callyfortheclassi -cationinSectionIII,forclarityitispresentedonlyforsubcodesofcodes.Forthegeneralcase,similarconditionscanalternativelybeobtainedusingresultsbyVasil’eva[9]andconnectionsbetweencodesand1-perfectcodesoflength[10,Cor.4].Theorem3:Letbeobtainedfromacodebyshorteningtimes,,andletdenotethenumberofcodewordsofweightin.Ifisanevencode,then

,andifisacodewithonlyodd-weight

codewords,then.

Proof:Withoutlossofgenerality,weassumethatshort-eningiscarriedoutbyextractingcodewordswithzerosingivencoordinates(afterwhichthecoordinatesaredeleted).We rstconsiderthecasegivenanevencode.Considerallsubcodesobtainedbylookingatalldif-ferentsetsoffourandshorteningwithrespecttozerosinthesecoordinates.ByCorollary4,everysuchsubcodehascardinality16,sothesumoftheircardinalitiesis

.Inthissum,everycodeword(intheofweight0isconsidered;similarlyforeach

6774IEEETRANSACTIONSONINFORMATIONTHEORY,VOL.57,NO.10,OCTOBER2011

codewordofweight2,4,6,and8,wegetthecounts330,126,35,and5,respectively.

Afterrepeatingthesecalculationswithrespecttoshorteningsin3,2,1,and0coordinates,wearriveatthefollowingsystemofequations:

Whentheseequationsarecombinedwiththecoef cients,

,,,,andwiththecoef -cients,,,,,one

getstheequationsand

,respectively.Sinceand,weget

and.Fromthelatterin-equality,wegetforodd-weightcodesafter

addingtheall-onewordtoallcodewords.Thiscompletestheprooffor.Theinequalitymeansthatwehaveeither

or(orboth).Intheformercase,wewillhave

onecodewordofweight0afteranyshortening.Inthelattercase,ontheotherhand,thecodewordsofweight2musthavedisjointsupports,soatmostofthemarelostwhenshorteningtimes.Itfollowsthataftershorteningtimes.Thisprovesthe rstpartofthetheorem.

Forthesecondpartofthetheorem,weuseinductionandletbeacodeobtainedbyshorteninganevencodetimes.Moreover,let,soandareobtainedaftershorteningthecodetimes;isobviouslyevenandhasonlyodd-weightcodewords.Wealsode nethecode(whichisobviouslyequivalentto).Theweightdistributionsofthecodes,,,andaredenotedby,,,and,respectively,so

and.From

and

wenowobtain

Thiscompletestheproof.

ItcouldbepossibletosharpenTheorem3,but,asweshalllatersee,itful llsourneedsinthecurrentstudy.

III.CLASSIFICATIONOFONE-ERROR-CORRECTINGCODESBeforedescribingtheclassi cationapproachusedinthecur-rentwork,wegiveashortreviewofsomeoldrelatedclassi -cationresults.

A.SurveyofOldResults

Asurveyofclassi cationresultsforoptimalerror-correctingcodescanbefoundin[8,Sec.7.1.4],wherecataloguesofop-timalcodescanalsobeobtainedinelectronicform.Inthecurrentstudy,weconsideroptimalcodeswith—thatis,optimalone-error-correctingcodes—and.Zaremba[11]provedthatthecodeattainingisunique(uptoequivalence)andsoisthereforeitsextension;itisnotdif culttoshowthatalloptimalcodeswithshorterlengthsarealsounique.BaichevaandKolev[12]provedthatthereare5equivalenceclassesofcodesattaining,andthesehave3extensions.LitsynandVardy[13]proveduniquenessofthecodeattaining

anditsextension.ThesecondauthorofthispapertogetherwithBaichevaandKolevclassi edthecodesattainingand;thereare562equivalenceclasses(with96extensions)and7398equivalencesclasses(with1041exten-sions)ofsuchcodes,respectively.

Knowingthesizesoftheoptimalone-error-correctingcodesuptolength11,oneinfactknowsthesizesofsuchcodesuptolength15by(2).

Theperfectcodesattainingwereclassi- edbythesecondandthethirdauthor[14];thenumberofequivalenceclassesofsuchcodesis5983,http://wendang.chazidian.comingaresultbyBlackmore[3],thisclassi cationcanbeusedtogetthenumberofequivalenceclassesofcodesattaining

,whichis38408;thesehave5983extensions.

Alltheseresultsstillleavetheclassi cationproblemopenforlengths12and13.Itisknown[5]thatnotallsuchcodescanbeobtainedbyshorteningcodesoflength14or15.B.Classi cationApproach

Thegeneralideaunderlyingthecurrentworkistoclas-sifycodesinaniterativemannerbyutilizingthefactthatan

codehasansubcodewith.

Thisidea—withvariousvariations—hasbeenusedearlierin[15]andelsewhere.However,itiseasytoarguewhyitisnotfeasibletoclassifytheandcodesdirectlyinsuchamanner.Aclassi cationoftheandcodesviaaclassi cationofthecodeswithwouldleadtoaprohibitivenumberofcodesoflength11.Toseethis,itsuf cestoobtainaroughboundonthenumberofequivalenceclassesofcodes.Everyoptimalcodehasdifferentsubsetsof128codewords,andanysuchsetofcanbeequivalenttoatmostsetsintotal.There-fore,thereareatleast

equivalenceclassesofcodes.Similar(rough)boundscanbeobtainedforthenumberofcodeswith.

KROTOVetal.:ONOPTIMALBINARYONE-ERROR-CORRECTINGCODESOFLENGTHSAND6775

Sofarinthissection,wehaveconsideredthecase.Ofcourse,by(1),wemightaswellconsiderthecase.Infact,weshalldosointhesequel,togetasmallernumberofequivalenceclassesofsubcodesineachstage.

Tomaketheclassi cationfeasible,weshallmakeuseofCorollary4,whichshowsthatnotonlydoallsub-codesoftheandcodeshave,butwehavethemuchstrongerresultthatallsubcodesoftheandcodeshavesizeandareeven-distancecodes.Moreover,thenumberofsubcodestobeconsideredcanbereducedconsiderablybyTheorem3.Allinall,byCorollary4theandcodescanbeobtainedasfollows:

(8)

Theeven-distance

codesareclassi editerativelyfromsmallercodes,withoutanyassumptionsonthesizesofsub-codes.

Asdescribedin[8,Sec.7.1.1],lengtheningiscarriedoutbyusingacliquealgorithm.Foreachsetofparametersinthese-quence(8),thenumberofcodesisfurtherreducedbyisomorphrejectionandbydiscardingcodesthatdonotful llCorollary4andTheorem3.Detailsregardingtheimplementationofsomeofthesepartswillbediscussednext.C.ImplementationandResults

Beforepresentingtheresultsofthecomputations,weshallconsidersomedetailsregardingtheimplementationofvariouspartsofthealgorithm.

Themethodoflengtheningcodesby ndingcliquesinacertaincompatibilitygraph—consistingofonevertexforeach(even)wordthatcanbeaddedandwithedgesbetweenverticeswhosecorrespondingwordsareatmutualdistanceatleast—iswellknown,cf.[8,Sec.7.1.1].However,weareherefacingthechallengeof ndingratherlargecliques—uptosize256,inthelaststepof(8).Thiscliquesearchcanbespedupasfollowsinthelastthreestepsof(8),againrelyingonthetheoreticalresults.

Considerthestepoflengtheningancodewith

,byincludingacoordinatewithzerosforthese

codewordsandaddingcodewordsoflengthwith1sinthenew(say, rst)coordinate.Thecandidatesforthenewcode-wordscanbepartitionedintosetsdependingonthevaluesinthe rstcoordinates(recallthatthevalueinthe rstcoordinateis1forallofthese).Letbethesubgraphoftheoriginalcompatibilitygraphinducedbytheverticescorre-spondingtothecodewordsin.Wenowconstructanewgraphwithonevertexforallcliquesofsize32inforany,andwithedgesbetweenverticeswheneverthecorrespondingcodespairwiseful lltheminimumdistancecriterion.Thecliquesofsizeingivethedesiredcodes.TheprogramCliquer[16]wasusedinthisworktosolvecliqueinstances.

Isomorphrejection,thatis,detectingandremovingcopiesofequivalentcodes,iscarriedoutviaatransformationintoagraph[15]andusingthegraphisomorphism

programnauty[17].Thegraphconsideredhastwoverticesforeachcoordinate,onefor

TABLEI

NUMBEROFINTERMEDIATE(EVEN-DISTANCE)CODES

eachvalueofthecoordinate.Theprogramnautycanbeaskedtogiveacanonicallabelingofthevertices;weusetheideaofcanonicalaugmentation[18]andrequirethatthevertexcorre-spondingtothenewcoordinateandthevaluegiventotheoldcodewordshavethesmallestlabel.(See[19]forananalogousapproachforconstantweightcodes.)Codesthatpassthistestmuststillbecomparedwiththeothercodesobtainedfromthesamesubcode.

Forthe rstfewsetsofparametersin(8),nautyprocessesthegraphsinasuf cientlyfastmanner.However,thelargerthecodes,thegreateristheneedforenhancingsuchadi-rectapproach,cf.[14].Inthecurrentwork,aninvariantwasusedthatisbasedonsetsoffourcodewordswiththesamevalueinallbutsixcoordinates,wheretheyformthestructure{000000,111100,110011,001111}[14],[20].

Thesearchstartsfromthe343566equivalenceclassesofeven-distancecodes,whichinturnwereclassi edit-erativelyfromsmallercodes.InTableI,thenumberofequiva-lenceclassesofcodesaftereachlengtheningandapplicationofthenecessaryconditionsisshown.

TableIshowsthatthereare27375equivalenceclassesof

codesaswellas17513equivalenceclassesofcodes.Puncturingthecodesinallpossibleways

andcarryingoutfurtherisomorphrejectionrevealsthatthereare237610equivalenceclassesofcodesand117823equivalenceclassesofcodes.AtotaloflessthanonemonthofCPU-timeusingonecoreofa2.8-GHzpersonalcomputerwasneededforthewholesearch.

Beforepresentingthemainpropertiesoftheclassi edcodes,weshallbrie ydiscussvalidationofthesecomputer-aidedresults.

D.ValidationofClassi cation

Datafromtheclassi cationstepscanbeusedtovalidatetheresultsbyusingadouble-countingargument.Morespeci cally,thetotalnumberofeven-distancecodes(thatis,labeledcodesdisregardingequivalence)withcanbecountedintwoways.Thisisawell-knowntechnique,see[8,Ch.10]and[19].

Theorbit-stabilizertheoremgivesthenumberoflabeledeven-distancecodesas

(9)

whereisasetwithonecodefromeachequivalenceclassofsuchcodes.

Letbeasetofrepresentativesfromallequivalenceclassesofeven-distancecodesandthenumberof nalcodes(beforeisomorphrejection)thatareobtainedin