资源描述：
《边信息索引编码》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。
1、IndexCodingwithSideInformationZivBar-Yossef∗YitzhakBirk†T.S.Jayram‡TomerKol§Abstractsideinformationaboutx,beforeitissent.SourcecodingwithsideinformationaddressesencodingschemesthatMotivatedbyaproblemoftransmittingdataoverexploitthesideinformationinordertoreducethelengthbroadcastch
2、annels(BirkandKol,INFOCOM1998),weofthecode.Classicalresultsinthisarea[16,19,18]studythefollowingcodingproblem:asendercommuni-describehowtoachieveoptimalrateswithrespecttothecateswithnreceiversR1,...,Rn.Heholdsaninputjointentropyofthesourceandthesideinformation.x∈{0,1}nandwishestob
3、roadcastasinglemessageWitsenhausen[17]initiatedthestudyofthezero-sothateachreceiverRicanrecoverthebitxi.Eacherrorsideinformationproblem.ForeverysourceinputRihaspriorsideinformationaboutx,inducedbyadi-x∈X,thereceivergetsaninputy∈YthatgivessomerectedgraphGonnnodes;Riknowsthebitsofxi
4、ntheinformationaboutx.Thisiscapturedbyrestrictingthepositions{j
5、(i,j)isanedgeofG}.Wecallencodingpairs(x,y)tobelongtoafixedsetL⊆X×Y.BoththeschemesthatachievethisgoalINDEXcodesfor{0,1}nsenderandthereceiverknowL,andthuseachofthem,withsideinformationgraphG.givenhisowninput,hasinformati
6、onabouttheothersInthispaperweidentifyameasureongraphs,theinput.Witsenhausenshowedthatfixed-lengthsidein-minrank,whichweconjecturetoexactlycharacterizeformationcodeswereequivalenttocoloringsofarelatedtheminimumlengthofINDEXcodes.Weresolvetheobjectcalledtheconfusiongraph,andthusthelo
7、garithmconjectureforcertainnaturalclassesofgraphs.Forar-ofthechromaticnumberofthisgraphtightlycharac-bitrarygraphs,weshowthattheminrankboundistightterizestheminimumnumberofbitsneededtoencodeforbothlinearcodesandcertainclassesofnon-linearthesource.FurtherresultsbyAlonandOrlitsky[2]
8、andcodes.Forthegeneralproblem,weobtaina(weaker)Koulgietal.[12]showedthatgraph-theoreticinforma-lowerboundthatthelengthofanINDEXcodeforanytionmeasurescouldbeusedtocharacterizeboththeav-graphGisatleastthesizeofthemaximumacyclicin-eragelengthofvariable-lengthcodes,aswellasasymp-duced
9、subgraphofG.toticratesofcodesthat
