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. doi:10.1109/18.796406. https://resolver.caltech.edu/CaltechAUTHORS:SCHUieeetit99

[img]
Preview
PDF
See Usage Policy.

193kB

Use this Persistent URL to link to this item: https://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
Related URLs:
URLURL TypeDescription
https://doi.org/10.1109/18.796406DOIUNSPECIFIED
ORCID:
AuthorORCID
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
DOI:10.1109/18.796406
Record Number:CaltechAUTHORS:SCHUieeetit99
Persistent URL:https://resolver.caltech.edu/CaltechAUTHORS:SCHUieeetit99
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:08 Nov 2021 20:36

Repository Staff Only: item control page