Binary Huffman equivalent codes with a short synchronizing codeword

作     者：Escott, AE Perkins, S 

作者机构：Univ Warwick Warwick Business Sch Operat Res & Syst Grp Coventry CV4 7AL W Midlands England Univ Glamorgan Div Math & Comp Pontypridd CF37 1DL M Glam Wales 

出 版 物：《IEEE TRANSACTIONS ON INFORMATION THEORY》 (IEEE Trans. Inf. Theory)

年 卷 期：1998年第44卷第1期

页      面：346-351页

核心收录：

学科分类：0808[工学-电气工程] 08[工学] 0701[理学-数学] 0812[工学-计算机科学与技术（可授工学、理学学位）] 

基　　金：Economic and Social Research Council  ESRC 

主　　题：Huffman codes synchronization synchronizing codewords variable-length codes 

摘      要：For a given set of codeword lengths, there are many different optimal variable-length codes, which are all Huffman 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 suggest the problem of finding, for a given set of codeword lengths, the binary Huffman equivalent code with the shortest synchronizing codeword. In this correspondence 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 m greater than or equal to 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.