Title :
Asymptotically good codes correcting insertions, deletions, and transpositions
Author :
Schulman, Leonard J. ; Zuckerman, David
Author_Institution :
Coll. of Comput., Georgia Inst. of Technol., Atlanta, GA, USA
fDate :
11/1/1999 12:00:00 AM
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
Keywords :
channel coding; decoding; error correction codes; error statistics; exponential distribution; polynomials; asymptotically good codes; asynchronous noisy channel; deletions correction; exponential error probability; insertion-deletion; insertions correction; polynomial time decodable codes; polynomial time encodable codes; stochastic model; transpositions correction; Binary codes; Decoding; Difference equations; Encoding; Error correction codes; Information security; Information theory; Notice of Violation; Privacy; Redundancy;
Journal_Title :
Information Theory, IEEE Transactions on
