Variable-Length Binary Encodings

Abstract

This paper gives a theoretical treatment of several properties which describe certain variable-length binary encodings of the sort which could be used for the storage or transmission of information. Some of these, such as the prefix and finite delay properties, deal with the time delay with which circuits can be built to decipher the encodings. The self-synchronizing property deals with the ability of the deciphering circuits to get in phase automatically with the enciphering circuits. Exhaustive encodings have the property that all possible sequences of binary digits can occur as messages. Alphabetical-order encodings are those for which the alphabetical order of the letters is preserved as the numerical order of the binary codes, and would be of possible value for sorting of data or consultation of files or dictionaries. Various theorems are proved about the relationships between these properties, and also about their relationship to the average number of binary digits used to encode each letter of the original message.