Some General Results of Coding Theory with Applications to the Study of Codes for the Correction of Synchronization Errors

摘要

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