Vi introducerar synkronisering strängar, som ger ett nytt sätt att eektivt hantera synkroniseringsfel, dvs. tillägg och raderingar. Synkroniseringsfel är strikt mer allmänna och mycket svårare att hantera än mer allmänt anses halv-fel, dvs symbol korruption och raderingar. För varje ε > 0, synkronisering strängar tillåter att indexera en sekvens med en ε − O (1) storlek alfabet så att man kan eektivt omvandla k synkronisering fel till (1 + ε)k halv-fel. Denna kraftfulla nya teknik har många tillämpningar. I detta dokument fokuserar vi på att utforma insdelkoder, dvs. felkorrigering av blockkoder (ECC) för in- och utmatningskanaler. Medan ECC för både halv-fel och synkronisering fel har studerats intensivt, har den senare i stort sett motsatt framsteg. Som Mitzenmacher uttrycker det i sin 2009 undersökning: "Channels med synkroniseringsfel. ... är helt enkelt inte tillräckligt förstådda av nuvarande teori. Med tanke på den nästan fullständiga kunskap vi har om kanaler med raderingar och fel är vår brist på förståelse om kanaler med synkroniseringsfel verkligen anmärkningsvärd." Det tog faktiskt fram till 1999 för de första insdelkoder med konstant hastighet, konstant avstånd och konstant alfabetsstorlek att konstrueras och först sedan 2016 finns det konstruktioner av konstant hastighet insdel koder för asymptotiskt stora bullerhastigheter. Även i asymptotiskt stora eller små buller regim dessa koder är polynomiskt långt från den optimala hastighet distans handelo. Detta gör förståelsen av insdelkoder upp till detta arbete likvärdig med vad som var känt för vanliga ECCs efter att Forney infört consctenated codes i sin doktorsavhandling för 50 år sedan. En direkt tillämpning av vår synkroniseringssträng baserad indexeringsmetod ger en enkel svart-box konstruktion som omvandlar alla ECC till en lika effektiv insdelkod med endast en liten ökning av alfabetets storlek. Detta överför omedelbart mycket av den högt utvecklade förståelsen för regelbundna ECC till området för insdelkoder. Framför allt, för det fullständiga bullerspektrumet får vi e e cient "nära-MDS" insdel koder som kommer godtyckligt nära den optimala hastighets-distans handel som ges av * Singleton bundna. Framför allt ger vi insdelkoder som ger en hastighet på 1−δ −ε över ett alfabet med konstant storlek som effektivt korrigerar en ε-fraktion av infogningar eller raderingar.
I denna inställning state of the art koder över stora ändliga alfabet är synkronisering sträng baserade koder från REF som uppnår en hastighet godtyckligt nära Singleton av 1−δ för alla δ  till (0, 1).
Synchronization strings: codes for insertions and deletions approaching the Singleton bound
{'venue': 'STOC 2017', 'journal': None, 'mag_field_of_study': ['Computer Science', 'Mathematics']}