Exact and approximation algorithms for error-detecting even codes

Even codes are prefix-free codes where every encoding contains an even number of 1’s, thus having ability of detecting the occurrence of an odd number of 1-bit errors in a 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 case of arbitrary probabilities. An exact algorithm for constructing an optimal even code is described with complexity O(n3), where n is the number of symbols. Further, two approximation algorithms for constructing nearly optimal even codes are presented, both requiring O(nlogn) time; in addition, the running time is O(n) if the symbols are given ordered by their probabilities. The cost of the even code constructed by the second approximation algorithm is at most 16.7% higher than the cost of a Huffman code, for the same probabilities. However, computational experiments suggest that, in practice, this difference is about 5%, for n large enough.