Self-synchronizing Huffman codes (Corresp.)
T. Ferguson, Joshua H. Rabinowitz · IEEE Transactions on Information Theory · 1984
A problem associated with the use of variable-length source codes is that loss of synchronization may lead to extended errors in the decoded text. In this correspondence it is shown that some binary Huffman codes contain a codeword that resynchronizes the decoder regardless of the synchronization slippage preceding that codeword. Such codes are self-synchronizing in a probabilistic sense, yet require no additional system overhead. Some sufficient conditions are found for the existence or nonexistence of self-synchronizing Huffman codes for many classes of source probabilities. One of our results shows that many common languages can be encoded with self-synchronizing Huffman codes.