IBM®
Skip to main content
    Country/region [change]    Terms of use
 
 
 
    Home    Products    Services & solutions    Support & downloads    My account    

IBM Technical Journals
Special report: Celebrating 50 years of the IBM Journals
All topics > Computing Methodologies >

Generalized Kraft inequality and arithmetic coding

 Award plaque by J. J. Rissanen

Algorithms for encoding and decoding finite strings over a finite alphabet are described. The coding operations are arithmetic involving rational numbers li as parameters such that ∑i 2−li ≤ 2−ε. This coding technique requires no blocking, and the per-symbol length of the encoded string approaches the associated entropy within ε. The coding speed is comparable to that of conventional coding methods.

Originally published:

IBM Journal of Research and Development, Volume 20, Issue 3, pp. 198-203 (1976).

Significance:

In this seminal paper Rissanen introduces arithmetic coding, a new form of entropy encoding that improved on the Huffman coding and eventually replaced it as the primary method for performing data compression. The idea was further generalized in the related paper J. J. Rissanen and G. G. Langdon, Jr., “Arithmetic coding,” Journal of Research and Development 23, No. 2, 149-162 (1979).

Comments:

Related paper: Arithmetic coding (JRD 1979) by J. J. Rissanen and G. G. Langdon, Jr.

    About IBM    Privacy    Contact