Asymptotically good codes correcting insertions, deletions, and transpositions
We present simple, polynomial-time encodable and deeodable codes which are asymptotically good for channels allowing insertions, deletions, and transpositions. As a corollary, they achieve exponential error probability in a stochastic model of insertion-deletion.
asymptotically good insertion deletion transposition asynchronous communication edit distance error-correcting codes