Path-invariant comma-free codes

In this paper we define a subclass of comma-free codes which has a property called path invariance. The main advantage of codes in this subclass lies in the ease of establishing the positions of the divisions between words. Certain path-invariant comma-free dictionaries using symbols to form n-symbol words are developed and their properties are studied. The number of words in these dictionaries is determined to be where is a parameter which equals one when , and denotes the integral part of . That this is the maximum obtainable dictionary size is proved for a special case. The ability of these codes to correct registration (synchronization) errors when consecutive symbols are available (as opposed to the consecutive symbols required by general fixed-word-length comma-free codes) is demonstrated. A comparison of dictionary sizes is made for path-invariant comma-free codes, general fixed-word-length comma-free codes, and codes using one symbol as a comma. In the range and the path-invariant dictionaries are about to the size of the corresponding general comma-free dictionaries. Asymptotic dictionary sizes are obtained for and for .