Abstract-Kulkarni och Kiyavash införde nyligen en ny metod för att fastställa övre gränser för storleken på raderingskorrigering koder. Denna metod är baserad på verktyg från hypergrafteori. Radering kanalen representeras av en hypergraf vars kanter är radering bollar (eller sfärer), så att en radering-korrigering kod blir en matchning i denna hypergraf. Följaktligen kan en bunden på storleken av en sådan kod erhållas från gränser på motsvarande nummer av en hypergraf. Klassiska resultat i hypergrafteorin åberopas sedan för att beräkna en övre gräns på matchningstalet som en lösning på ett linjärt programmeringsproblem: problemet med att hitta fraktionerade transversaler. Metoden med Kulkarni och Kiyavash kan användas inte bara för borttagningskanalen utan även för andra felkanaler. I detta dokument studeras denna metod i dess mest allmänna upplägg. För det första, det visas att om felkanalen är regelbunden och symmetrisk då den övre bunden av denna metod sammanfaller med den välkända sfär packning bundna och därmed kallas här den generaliserade sfär packning bundna. Även om denna gräns uttryckligen ges av en linjär programmering problem, att hitta dess exakta värde kan fortfarande vara en utmanande uppgift. Konsten att hitta den exakta övre gränsen (eller något svagare) är tilldelningen av vikter till hypergrafens hörn på ett sätt att de uppfyller begränsningarna i det linjära programmeringsproblemet. För att förenkla komplexiteten i den linjära programmeringen presenterar vi en teknik baserad på diagram automorfismer som i många fall avsevärt minskar antalet variabler och begränsningar i problemet. Vi tillämpar sedan denna metod på specifika exempel på felkanaler. Vi börjar med Z-kanalen och visar hur man exakt hittar den generaliserade sfären packning bundna till denna installation. Därefter studeras den icke-binära magnitudkanalen både för symmetriska och asymmetriska fel, där vi fokuserar på singelterrorfallet. Vi följer upp borttagningskanalen, som var den ursprungliga motivationen för arbetet av Kulkarni och Kiyavash, och visar hur man kan förbättra på sina övre gränser för enkel-deletionkorrigerande koder. Eftersom raderings- och kornterrorkanalerna har en liknande struktur för ett enda fel, förbättrar vi också de befintliga övre gränserna för en-korns felkorrigerande koder. Slutligen använder vi denna metod för projektiva utrymmen och finner dess generaliserade sfär packning bunden till singel-terror fallet.
I REF har detta förfarande analyserats och generaliserats till andra felmodeller, såsom Z-kanalen, korn-terrorkanalen och projektiva utrymmen.
Generalized Sphere Packing Bound
{'venue': 'IEEE Transactions on Information Theory', 'journal': 'IEEE Transactions on Information Theory', 'mag_field_of_study': ['Mathematics', 'Computer Science']}