Data Compression and Error Detection Integration

Abstract

Hamming [4] proposed, in 1980, the Hamming HuffmanTrees, structures for data compression, which can combinethe Huffman encoding with the noise protection of Hammingencoding. Those structures can detect 1 bit-errorsintroduced during transmission of compressed data. Thiswork extends that proposal and discusses the Odd DetectionTress (ODT), whose basic property is to detect any oddnumber of wrong bits introduced in a message. It is presentedthe special case where the frequencies are constantand the Optimal ODT are caracterized for this situation. Itis highlighted the low cost for the addition of that feature,related to Huffman. It is also discussed one algorithm to thegeneral case.