A Low-Cost Decoder for Arbitrary Binary Variable-Length Codes

Encoders and decoders for variable-length codes such as Huffman Codes can be costly to implement. This paper describes low-cost encoder and decoder for binary variable-length codes that is simple to implement when decoding speed is not an issue. Keywords: encoder, decoder, variable-length code, Huffman code, tree 1. Introduction Variable-length Huffman codes [1] are widely used in data compression, e.g., in the Unix pack command or as a low-level part of the popular JPEG image data compression scheme. Encoding and decoding variable-length codes presents an important problem in an environment dominated by the fixed word length data representation in modern computers. For a given variable-length code, an encoder must thus convert some fixed-length input into its variable-length representation, and vice-versa, a decoder converts variable-length input into its corresponding fixed-length output. Little interest, if any, seems to be paid to variable-length encoders in literature, perhaps ..