Schulman, Leonard J. and Zuckerman, David (1999) Asymptotically good codes correcting insertions, deletions, and transpositions. IEEE Transactions on Information Theory, 45 (7). pp. 2552-2557. ISSN 0018-9448 http://resolver.caltech.edu/CaltechAUTHORS:SCHUieeetit99
See Usage Policy.
Use this Persistent URL to link to this item: http://resolver.caltech.edu/CaltechAUTHORS:SCHUieeetit99
We present simple, polynomial time encodable and decodable 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.
|Additional Information:||© Copyright 1999 IEEE. Reprinted with permission. Manuscript received April 13, 1997; revised October 16, 1998. This work was supported in part by NSF NYI under Grant CCR-9457799, a David and Lucile Packard Fellowship for Science and Engineering, and an Alfred P. Sloan Research Fellowship. The authors wish to thank the anonymous referees for their helpful comments.|
|Subject Keywords:||Asymptotically good, asynchronous communication, deletion, edit distance, error-correcting codes, insertion, transposition|
|Usage Policy:||No commercial reproduction, distribution, display or performance rights in this work are provided.|
|Deposited By:||Archive Administrator|
|Deposited On:||19 Dec 2006|
|Last Modified:||26 Dec 2012 09:24|
Repository Staff Only: item control page