Motivated by a problem posed by Hamming in 1980, we define even codes. They are Huffman type prefix codes with the additional property of being able to detect the occurrence of an odd number of 1-bit errors in the message. We characterize optimal even codes and describe a simple method for constructing the optimal codes. Further, we compare optimal even codes with Huffman codes for equal frequencies. We show that the maximum encoding in an optimal even code is at most two bits larger than the maximum encoding in a Huffman tree. Moreover, it is always possible to choose an optimal even code such that this difference drops to 1 bit. We compare average sizes and show that the average size of an encoding in a optimal even tree is at least and at most of a bit larger than that of a Huffman tree. These values represent the overhead in the encoding sizes for having the ability to detect an odd number of errors in the message. Finally, we discuss the case of arbitrary frequencies and describe some results for this situation.
@article{ITA_2005__39_1_263_0,
author = {Pinto, Paulo E. D. and Protti, F\'abio and Szwarcfiter, Jayme L.},
title = {Parity codes},
journal = {RAIRO - Theoretical Informatics and Applications - Informatique Th\'eorique et Applications},
volume = {39},
year = {2005},
pages = {263-278},
doi = {10.1051/ita:2005015},
mrnumber = {2132591},
zbl = {1086.94036},
language = {en},
url = {http://dml.mathdoc.fr/item/ITA_2005__39_1_263_0}
}
Pinto, Paulo E. D.; Protti, Fábio; Szwarcfiter, Jayme L. Parity codes. RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 39 (2005) pp. 263-278. doi : 10.1051/ita:2005015. http://gdmltest.u-ga.fr/item/ITA_2005__39_1_263_0/
[1] , An adaptive Method for Data Compression, in Record of the 7th Asilomar Conference on Circuits, Systems and Computers, Naval Postgraduate School, Monterrey, Ca. (1973) 593-597. | Zbl 0304.68038
[2] , Variations on a Theme by Huffman. IEEE Trans. Inform. Theory 24 (1978) 668-674. | Zbl 0399.94012
[3] , Coding And Information Theory. Prentice Hall (1980). | MR 555735 | Zbl 0431.94001
[4] , A Method for the Construction of Minimum Redundancy Codes, in Proc. of the IRE 40 (1951) 1098-1101.
[5] , The Art of Computer Programming. Addison Wesley (1973). | MR 378456 | Zbl 1127.68068
[6] , Dynamic Huffman Coding. J. Algorithms 6 (1985) 163-180. | Zbl 0606.94007
[7] , Um algoritmo eficiente para construção de códigos de prefixo com restrição de comprimento. Master Thesis, PUC-RJ, Rio de Janeiro (1997).
[8] and, A fast algorithm for optimal length-limited Huffman codes. JACM 37 (1990) 464-473. | Zbl 0699.68070
[9] , and, Improved Analysis of the FGK Algorithm. J. Algorithms 28 (1999) 195-211. | Zbl 1111.94328
[10] and, The Warm-up Algorithm: A Lagrangean Construction of Length Restricted Huffman Codes. SIAM J. Comput. 30 (2000) 1405-1426. | Zbl 0987.94020
[11] and, Improved Bounds on the Inefficiency of Length Restricted Codes. Algorithmica 31 (2001) 513-529. | Zbl 1012.94008
[12] and, Practical length-limited coding for large alphabets. Comput. J. 38 (1995) 339-347.
[13] , and, A Huffman-Based Error Detection Code, in Proc. of the Third International Workshop on Experimental and Efficient Algorithms (WEA 2004), Angra dos Reis, Brazil, 2004. Lect. Notes Comput. Sci. 3059 (2004) 446-457.
[14] , An Optimum Encoding with Minimal Longest Code and Total Number of Digits. Inform. Control 7 (1964) 37-44. | Zbl 0116.35303