Please use this identifier to cite or link to this item: http://hdl.handle.net/11422/1924
Type: Relatório
Title: Exact and experimental algorithms for a Huffman-based error detecting code
Author(s)/Inventor(s): Pinto, Paulo Eustáquio Duarte
Protti, Fábio
Szwarcfiter, Jayme Luiz
Abstract: 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.
Keywords: Compressão de dados (Ciência da computação)
Detecção de erros
Códigos de Huffman
Subject CNPq: CNPQ::CIENCIAS EXATAS E DA TERRA::CIENCIA DA COMPUTACAO
Department : Instituto Tércio Pacitti de Aplicações e Pesquisas Computacionais
In: Relatório técnico NCE
Issue: 0106
Issue Date: 23-Feb-2006
Publisher country: Brasil
Language: eng
Right access: Acesso Aberto
Citation: 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)
URI: http://hdl.handle.net/11422/1924
Appears in Collections:Relatórios Técnicos e de Pesquisa

Files in This Item:
File Description SizeFormat 
01_06_000649951.pdf314,32 kBAdobe PDFView/Open


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.