Codes with bounded synchronization delay. (English) Zbl 0202.50404

Authors’ summary: In this paper we study “bounded delay codes”, which have the property that every message can be uniquely decoded by examining a segment of bounded length, from any starting point. This class is shown to attain the upper bound on codebook size previously encountered (but not always attained) for the familiar subclass of “comma-free codes”.
The problem of determining the smallest message length \(s_0\) which guarantees unique decipherability for such codes is discussed. The bounded delay codes are classified according to the value of \(s_0\).
An extension is made to the case of variable length codes, in which the upper bound formula of the uniform word-length case is replaced by a system of inequalities.


94A45 Prefix, length-variable, comma-free codes
94B50 Synchronization error-correcting codes
Full Text: DOI