Voir la notice de l'article provenant de la source Numdam
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},
pages = {263--278},
publisher = {EDP-Sciences},
volume = {39},
number = {1},
year = {2005},
doi = {10.1051/ita:2005015},
mrnumber = {2132591},
zbl = {1086.94036},
language = {en},
url = {http://geodesic.mathdoc.fr/articles/10.1051/ita:2005015/}
}
TY - JOUR AU - Pinto, Paulo E. D. AU - Protti, Fábio AU - Szwarcfiter, Jayme L. TI - Parity codes JO - RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications PY - 2005 SP - 263 EP - 278 VL - 39 IS - 1 PB - EDP-Sciences UR - http://geodesic.mathdoc.fr/articles/10.1051/ita:2005015/ DO - 10.1051/ita:2005015 LA - en ID - ITA_2005__39_1_263_0 ER -
%0 Journal Article %A Pinto, Paulo E. D. %A Protti, Fábio %A Szwarcfiter, Jayme L. %T Parity codes %J RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications %D 2005 %P 263-278 %V 39 %N 1 %I EDP-Sciences %U http://geodesic.mathdoc.fr/articles/10.1051/ita:2005015/ %R 10.1051/ita:2005015 %G en %F 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) no. 1, pp. 263-278. doi: 10.1051/ita:2005015
Cité par Sources :