Accession Number : AD0684180

Title :   SOME GENERAL RESULTS OF CODING THEORY WITH APPLICATIONS TO THE STUDY OF CODES FOR THE CORRECTION OF SYNCHRONIZATION ERRORS,

Corporate Author : PARKE MATHEMATICAL LABS INC CARLISLE MASS

Personal Author(s) : Calabi,L. ; Hartnett,W. E.

Report Date : NOV 1968

Pagination or Media Count : 30

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)

Descriptors :   (*SYNCHRONIZATION(ELECTRONICS), ERRORS), (*CODING, ERRORS), DECODING, SEQUENCES(MATHEMATICS), SET THEORY, THEOREMS

Subject Categories : Cybernetics

Distribution Statement : APPROVED FOR PUBLIC RELEASE