Please use this identifier to cite or link to this item:
|Exact and experimental algorithms for a Huffman-based error detecting code
|Pinto, Paulo Eustáquio Duarte
Szwarcfiter, Jayme Luiz
|Even codes are binary pre fix codes, in which each encoding contains an even number of 1's. They are Huffman based codes with the additional property of being able to detect the ocurrence of an odd number of 1-bit errors in the message. They have been de ned motivated by a problem posed by Hamming in 1980. Even codes have been studied for the case in which the symbols have uniform probabilities. In the present work, it is considered the general situation of arbitrary probabilities. An exact algorithm for constructing an optimal even code is described. The algorithm has complexity O(n3), where n is the number of symbols. Further, two heuristics for constructing nearly optimal even codes are presented, which require 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, computer experiments suggest that, for practical purposes, this value seems to be much less: about 5% or less, for n large enough. This corresponds to the overhead in the size of the encoded message, for having the ability to detect errors. Concerning undetected errors, we obtain bounds on the probability of the trees to produce k consecutive wrong symbols, which suggest that such probability is small, for large messages.
|Compressão de dados (Ciência da computação)
Detecção de erros
Códigos de Huffman
|CNPQ::CIENCIAS EXATAS E DA TERRA::CIENCIA DA COMPUTACAO
|Instituto Tércio Pacitti de Aplicações e Pesquisas Computacionais
|Relatório técnico NCE
|PINTO, P. E.D. ; PROTTI, F. SZWARCFITER, J. L. Exact and experimental algorithms for a Huffman-based error detecting code. Rio de Janeiro: NCE, UFRJ, 2006. 25 p. (Relatório Técnico, 01/06)
|Appears in Collections:
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.