Binary Huffman equivalent codes with a short synchronizing codeword

摘要

For a given set of codeword lengths, there are many different optimal variable-length codes, which are all Huffman (1952) equivalent codes. Some of these codes may contain a synchronizing codeword which resynchronizes the code whenever it is transmitted. The shorter the synchronizing codeword, the quicker the code will resynchronize. Ferguson and Rabinowitz (1984) suggest the problem of finding, for a given set of codeword lengths, the binary Huffman equivalent code with the shortest synchronizing codeword. We consider binary Huffman equivalent codes whose shortest codeword has length m<1 and which contain a synchronizing codeword of length m+1, the shortest possible in this case. We provide an algorithm for constructing these codes for a given set of codeword lengths, if such a code exists. We study further properties of these codes and show that when in m/spl ges/3 the codes contain more than one synchronizing codeword. Finally, we suggest ways of improving the synchronization properties of the codes and provide some example codes.