Exact and Experimental Algorithms for a Huffman-Based Error Detecting Code

摘要

Even codes are Huffman based codes in which every encoding contains an even number of 1's, thus having the ability of detecting the occurrence of an odd number of 1-bit errors in the message. The motivation for defining such codes comes from a problem posed by Hamming in 1980. Even codes have been studied for the case in which symbols have uniform probabilities. In this work, we consider the general situation of arbitrary probabilities. An exact algorithm for constructing an optimal even code is described with complexity O(n~3), where n is the number of symbols. Further, two heuristics for constructing nearly optimal even codes are presented, both requiring 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, computational experiments suggest that, for practical purposes, this value seems to be better: about 5% or less, for n large enough. This corresponds to the amount of redundancy to be added to the message in order to keep the ability of error detection. Concerning undetected errors, we obtain bounds on the probability of producing k consecutive erroneous symbols, suggesting that such a probability is small for large messages.