Title: The construction of binary Huffman equivalent codes with a greater number of synchronising codewords
Authors: Yuh-Ming Huang; Sheng-Chi Wu
Addresses: Department of Computer Science and Information Engineering, National Chi Nan University, Nantou, 545, Taiwan. ' Department of Computer Science and Information Engineering, National Chi Nan University, Nantou, 545, Taiwan
Abstract: An inherent problem with a Variable-Length Code (VLC) is that even a single bit error can cause a loss of synchronisation, and thus lead to error propagation. Codeword synchronisation has been extensively studied as a means to overcome this drawback and efficiently stop error propagation. In this paper, we first present the sufficient and necessary conditions for the existence of binary Huffman equivalent codes with the shortest, or at most two shortest, synchronising codeword(s) of length m + 1, where m (>1) is the shortest codeword length. Next, based on the results, we propose a unified approach for constructing each of these binary Huffman equivalent codes with the shortest, or at most two shortest, synchronising codeword(s) of length m + 1, if such a code exists for a given length vector.
Keywords: VLC; variable-length code; Huffman code; Huffman equivalent code; synchronous code; synchronising codewords; ad hoc computing; ubiquitous computing; codeword synchronisation.
DOI: 10.1504/IJAHUC.2012.045541
International Journal of Ad Hoc and Ubiquitous Computing, 2012 Vol.9 No.1, pp.54 - 65
Received: 29 Jun 2010
Accepted: 17 Aug 2010
Published online: 22 Feb 2012 *