Title :
On the cost of worst case coding length constraints
Author :
Baron, Dror ; Singer, Andrew C.
Author_Institution :
Coordinated Sci. Lab., Illinois Univ., Urbana, IL, USA
fDate :
11/1/2001 12:00:00 AM
Abstract :
We investigate the redundancy that arises from adding a worst case length constraint to uniquely decodable fixed-to-variable codes over achievable Huffman (1952) codes. This is in contrast to the traditional metric of the redundancy over the entropy. We show that the cost for adding constraints on the worst case coding length is small, and that the resulting bound is related to the Fibonacci numbers
Keywords :
Huffman codes; decoding; entropy; source coding; Fibonacci numbers; Huffman codes; entropy; lossless source coding; redundancy; uniquely decodable fixed-to-variable codes; worst case coding expansion; worst case coding length constraints; Computer aided software engineering; Costs; Decoding; Entropy; Huffman coding; Random variables; Source coding;
Journal_Title :
Information Theory, IEEE Transactions on
