A Huffman-based error detecting code

Even codes are Huffman based prefix codes with the additional property of being able to detect the occurrence of an odd number of 1-bit errors in the message. They have been defined 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, we consider the general situation of arbitrary probabilities. We describe an exact algorithm for constructing an optimal even code. The algorithm has complexity O(n(3)log n), where n is the number of symbols. Further we describe an heuristics for constructing a nearly optimal even code, which requires O(n log n) time. The cost of an even code constructed by the heuristics is at most 50% higher than the cost of a Huffman code, for the same probabilities. That is, less than 50% higher than the cost of the corresponding optimal even code. However, computer experiments have shown that, for practical purposes, this value seems to be much less: at most 5%, for n large enough. This corresponds to the overhead in the size of the encoded message, for having the ability to detect an odd number of 1-bit errors.