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 *

Full-text access for editors Full-text access for subscribers Purchase this article Comment on this article