Abstract-The buller modell av raderingar innebär betydande utmaningar i kodning teori, med grundläggande frågor som kapaciteten i binära radering kanalen fortfarande är öppen. I det här dokumentet studerar vi den svårare modellen med de värsta fallens raderingar, med fokus på att konstruera effektivt decodable-koder för de två extrema systemen med hög bullernivå och hög ljudnivå. Specifikt konstruerar vi polynom-tid decodable koder med följande avräkningar (för alla ε > 0): 1) koder som kan korrigera ett bråk 1 − ε av raderingar med hastighet poly(ε) över ett alfabet av storlek poly(1/ε); 2) binära koder för hastighet 1‐Õ ( ε) som kan korrigera ett bråk ε av raderingar; och 3) binära koder som kan listas-avkodas från ett bråk (1/2 − ε) av raderingar med hastighet poly(ε). Detta dokument ger de första effektiva konstruktioner som uppfyller de kvalitativa målen att korrigera en radering bråk närmar sig 1 över avgränsade alfabet, och korrigera en konstant bråkdel av bit raderingar med hastighet närmar sig 1 över ett fast alfabet. Ovannämnda resultat för vår förståelse av radering av kodkonstruktioner i dessa system till en liknande nivå som värsta fall fel.
Guruswami och Wang REF visade att det för ε > 0 finns polynomiska tidskoder med alfabetstorleken poly(1/ε) som korrigerar 1 – ε-fraktionen av raderingar med skattesats (ε 2 ) och koder med alfabetstorleken poly(1/ε) som korrigerar ε-fraktionen av raderingar med skattesatsen 1 −Õ( ε).
Deletion Codes in the High-Noise and High-Rate Regimes
{'venue': 'IEEE Transactions on Information Theory', 'journal': 'IEEE Transactions on Information Theory', 'mag_field_of_study': ['Computer Science', 'Mathematics']}