CaltechAUTHORS
  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. http://resolver.caltech.edu/CaltechAUTHORS:SCHUieeetit99

[img]
Preview
PDF
See Usage Policy.

188Kb

Use this Persistent URL to link to this item: http://resolver.caltech.edu/CaltechAUTHORS:SCHUieeetit99

Abstract

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
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
Record Number:CaltechAUTHORS:SCHUieeetit99
Persistent URL:http://resolver.caltech.edu/CaltechAUTHORS:SCHUieeetit99
Alternative URL:http://dx.doi.org/10.1109/18.796406
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:6720
Collection:CaltechAUTHORS
Deposited By: Archive Administrator
Deposited On:19 Dec 2006
Last Modified:26 Dec 2012 09:24

Repository Staff Only: item control page