A Caltech Library Service

Asymptotically good codes correcting insertions, deletions, and transpositions

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. doi:10.1109/18.796406.

See Usage Policy.


Use this Persistent URL to link to this item:


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.

Item Type:Article
Related URLs:
URLURL TypeDescription
Schulman, Leonard J.0000-0001-9901-2797
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
Issue or Number:7
Record Number:CaltechAUTHORS:SCHUieeetit99
Persistent URL:
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:6720
Deposited By: Archive Administrator
Deposited On:19 Dec 2006
Last Modified:08 Nov 2021 20:36

Repository Staff Only: item control page