Exact and experimental algorithms for a Huffman-based error detecting code

Abstract

Even codes are binary pre fix codes, in which each encoding contains an even number of 1's. They are Huffman based codes with the additional property of being able to detect the ocurrence of an odd number of 1-bit errors in the message. They have been de ned motivated by a problem posed by Hamming in 1980. Even codes have been studied for the case in which the symbols have uniform probabilities. In the present work, it is considered the general situation of arbitrary probabilities. An exact algorithm for constructing an optimal even code is described. The algorithm has complexity O(n3), where n is the number of symbols. Further, two heuristics for constructing nearly optimal even codes are presented, which require O(n log n) time. The cost of the even code constructed by the second heuristics is at most 16,7% higher than the cost of a Huffman code, for the same probabilities. However, computer experiments suggest that, for practical purposes, this value seems to be much less: about 5% or less, for n large enough. This corresponds to the overhead in the size of the encoded message, for having the ability to detect errors. Concerning undetected errors, we obtain bounds on the probability of the trees to produce k consecutive wrong symbols, which suggest that such probability is small, for large messages.