Use este identificador para citar ou linkar para este item: http://hdl.handle.net/11422/1924
Tipo: Relatório
Título: Exact and experimental algorithms for a Huffman-based error detecting code
Autor(es)/Inventor(es): Pinto, Paulo Eustáquio Duarte
Protti, Fábio
Szwarcfiter, Jayme Luiz
Resumo : 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.
Palavras-chave: Compressão de dados (Ciência da computação)
Detecção de erros
Códigos de Huffman
Assunto CNPq: CNPQ::CIENCIAS EXATAS E DA TERRA::CIENCIA DA COMPUTACAO
Departamento: Instituto Tércio Pacitti de Aplicações e Pesquisas Computacionais
In: Relatório técnico NCE
Número: 0106
Data de publicação: 23-Fev-2006
País de publicação: Brasil
Idioma da publicação: eng
Tipo de acesso: Acesso Aberto
Citação: 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
Aparece nas coleções:Relatórios Técnicos e de Pesquisa

Arquivos associados a este item:
Arquivo Descrição TamanhoFormato 
01_06_000649951.pdf314,32 kBAdobe PDFVisualizar/Abrir


Os itens no repositório estão protegidos por copyright, com todos os direitos reservados, salvo quando é indicado o contrário.