Huffman Coding as a Non-linear Dynamical System

Details Huffman Coding as a Non-linear Dynamical System Huffman Coding as a Non-linear Dynamical System

2009-06-19

arxiv.org/abs/0906.3575v1

Nonlinear Sciences

Chaotic Dynamics

7 pages, 5 figures

Scientific paper

In 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 the essential information? We propose modeling stochastic sources as piecewise linear discrete chaotic dynamical systems known as Generalized Lur\"{o}th Series (GLS) which dates back to Georg Cantor's work in 1869. The Lyapunov exponent of GLS 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 closest Lyapunov exponent), we derive a binary coding algorithm which exhibits minimum redundancy (the least average codeword length with integer codeword lengths). This turns out to be a re-discovery of Huffman coding, the popular lossless compression algorithm used in the JPEG international standard for still image compression.

Affiliated with

Also associated with

No associations

Rating

Huffman Coding as a Non-linear Dynamical System does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Huffman Coding as a Non-linear Dynamical System, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Huffman Coding as a Non-linear Dynamical System will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-400858