Back close

Huffman Coding as a Nonlinear Dynamical System

Publication Type : Journal Article

Publisher : International Journal of Bifurcation and Chaos

Campus : Bengaluru

School : School of Engineering

Department : Electrical and Electronics

Year : 2011

Abstract : pIn this paper, source coding or data compression is viewed as a measurement problem. Given a measurement device with fewer states than the observable of a stochastic source, how can one capture their essential information? We propose modeling stochastic sources as piecewise-linear discrete chaotic dynamical systems known as Generalized Luröth Series (GLS) which has its roots in Georg Cantor's work in 1869. These GLS are special maps with the property that their Lyapunov exponent is equal to the Shannon's entropy of the source (up to a constant of proportionality). By successively approximating the source with GLS having fewer states (with the nearest Lyapunov exponent), we derive a binary coding algorithm which turns out to be a rediscovery of Huffman coding, the popular lossless compression algorithm used in the JPEG international standard for still image compression./p

Admissions Apply Now