SOME GENERAL RESULTS OF CODING THEORY WITH APPLICATIONS TO THE STUDY OF CODES FOR THE CORRECTION OF SYNCHRONIZATION ERRORS,
Abstract
Codes have been considered to combat different noise effects, e.g. substitution errors, synchronization errors, erasures, etc.. A unified theory treating arbitrary patterns of errors of any nature is sketched here by giving suitably general definitions of 'error-correcting', 'decodable with abounded delay', and 'error-limiting' (or synchronizable) codes; and by establishing the usual implications. As a by-product the essence of those notions is brought out with great clarity. Some auxiliary notions and results are used also for two interesting applications. One is a generalization of a previous result, giving sufficient conditions for a code to be decodable with bounded delay (and hence also error-correcting) with respect to certain patterns of up to e substitution or synchronization errors. The second is an extension of the basic Hamming Theorem and solves an open problem: a block code (of word length n) has Levenshtein distance = or > 2e + 1 between any two distinct words (with 2e < n) if and only if it can correct up to e substitution errors in every word or up to e substitution and synchronization errors in the whole message. (Author)
Document Details
- Document Type
- Technical Report
- Publication Date
- Nov 01, 1968
- Accession Number
- AD0684180
Entities
People
- L. Calabi
- W. E. Hartnett