loading...
 This Article 
   
 Share 
   
 Bibliographic References 
   
 Add to: 
 
Digg
Furl
Spurl
Blink
Simpy
Google
Del.icio.us
Y!MyWeb
 
 Search 
   
Data Compression Conference (DCC '95)
An efficient variable length coding scheme for an IID source
Snowbird, Utah
March 28-March 30
ISBN: 0-8186-7012-6
Kar-Ming Cheung, Jet Propulsion Lab., California Inst. of Technol., Pasadena, CA, USA
A. Kiely, Jet Propulsion Lab., California Inst. of Technol., Pasadena, CA, USA
In this article we examine a scheme that uses two alternating Huffman codes to encode a discrete independent and identically distributed source with a dominant symbol. One Huffman code encodes the length of runs of the dominant symbol, the other encodes the remaining symbols. We call this combined strategy alternating runlength Huffman (ARH) coding. This is a popular scheme, used for example in the efficient pyramid image coder (EPIC) subband coding algorithm. Since the runlengths of the dominant symbol are geometrically distributed, they can be encoded using the Huffman codes identified by Golomb (1966) and later generalized by Gallager and Van Voorhis (1975). This runlength encoding allows the most likely symbol to be encoded using less than one bit per sample, providing a simple method for overcoming a drawback of prefix codes-that the redundancy approaches one as the largest symbol probability P approaches one. For ARH coding, the redundancy approaches zero as P approaches one. Comparing the average code rate of ARH with direct Huffman coding we find that: 1. If P>1/3, ARH is less efficient than Huffman coding. 2. If 1/3/spl les/P>2/5, ARH is less than or equally efficient as Huffman coding, depending on the source distribution. 3. If 2/5/spl les/P/spl les/0.618, ARH and Huffman coding are equally efficient. 4. If P<0.618, ARH is more efficient than Huffman coding. We give examples of applying ARH coding to some specific sources.
Index Terms:
source coding; Huffman codes; runlength codes; variable length codes; redundancy; variable length coding scheme; IID source; Huffman codes; discrete independent and identically distributed source; dominant symbol; alternating runlength Huffman coding; runlength encoding; ARH coding; redundancy; average code rate; source distribution
Citation:
Kar-Ming Cheung, A. Kiely, "An efficient variable length coding scheme for an IID source," dcc, pp.182, Data Compression Conference (DCC '95), 1995
Usage of this product signifies your acceptance of the Terms of Use.