Exact and approximation algorithms for error-detecting even codes

详细信息	查看全文 | 推荐本文 |

• 作者：Paulo E.D. Pinto^a ; ^{pauloedp@ime.uerj.br} ; Fá ; bio Protti^b ; ^{fabio@ic.uff.br} ; Jayme L. Szwarcfiter^c ; ^{jayme@nce.ufrj.br}
• 关键词：Data compression ; Error detection ; Hamming codes ; Huffman codes
• 刊名：Theoretical Computer Science
• 出版年：2012
• 期刊代码：114_03043975
• 类别：cp
• 出版时间：6 July, 2012
• 卷：440-441
• 期：Complete
• 页码：60-72
• 文件大小：325 K

摘要

Even codes are prefix-free codes where every encoding contains an even number of 1鈥檚, 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 , where is the number of symbols. Further, two approximation algorithms for constructing nearly optimal even codes are presented, both requiring time; in addition, the running time is 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 large enough.