资源描述：
《low density mds codes and factors of complete graphsnew》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、LowDensityMDSCodesandFactorsofCompleteGraphsLihaoXuVaskenBohossianJehoshuaBruckDavidG.WagnerCaliforniaInstituteofTechnologyUniversityofWaterlooMailCode136-93DepartmentofCombinatoricsandOptimizationPasadenaCA91125Waterloo,Ontario,CanadaN2L3G1Email:flihao,vincent,bruck
2、g@paradise.caltech.edudgwagner@math.uwaterloo.caAbstractWerevealanequivalencerelationbetweentheconstructionofanewclassoflowdensityMDSarraycodes,thatwecallB-Code,andacombinatorialproblemknownasperfectone-factorizationofcompletegraphs.Weuseknownperfectone-factorsofcompl
3、etegraphstocreateconstructionsanddecodingalgorithmsforbothB-Codeanditsdualcode.B-Codeanditsdualareoptimalinthesensethat(i)theyareMDS,(ii)theyhaveanoptimalencodingproperty,i.e.,thenumberoftheparitybitsthatarea ectedbychangeofasingleinformationbitisminimaland(iii)theyha
4、veoptimallength.Theexistenceofperfectone-factorizationsforeverycompletegraphwithanevennumberofnodesisa35yearslongconjectureingraphtheory.TheconstructionofB-codesofarbitraryoddlengthwillprovideanarmativeanswertotheconjecture.Keywords:MDSCodes,arraycodes,updatecomplexi
5、ty,lowdensity,perfectone-factorizationSupportedinpartbytheNSFYoungInvestigatorAwardCCR-9457811,byanIBMPartnershipAward,bytheSloanResearchFellowship,andbyDARPAthroughanagreementwithNASA/OSAT.11IntroductionArraycodeshaveimportantapplicationsincommunicationandstoragesys
6、tems[6][7],andhavebeenstudiedextensively[2][3][4][9].AcommonpropertyofthesecodesisthattheencodinganddecodingproceduresuseonlysimpleXOR(exclusiveOR)operationsandthusaremoreecientthanReed-Solomoncodesintermsofcomputationcomplexity[6].Inthispaper,wepresentanewclassoflin
7、earcode,calledB-Code,anMDS(MaximumDistanceSeparable)arraycodeofsizenloveranAbeliangroupG(q)withanadditionoperation+,wherel=2nor2n+1,andqissizenofthegroupG(q).Asusual,thedimensionofthecodeisde nedask=logN,whereNistheqnnumberofitscodewords.Itcanalsobeviewedasan(l;k)cod
8、eoverG(q),anditsdistanceisnalsode nedoverG(q),i.e.,overthecolumnsofthearray.Throughoutthispaper,forsimplicity,wewillassumeq=
