Huffman Coding as a Non-linear Dynamical System

Abstract

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ö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.

7 pages, 5 figures

References in corpus (2)

• The B-Exponential Map: A Generalization of the Logistic Map, and Its Applications In Generating Pseudo-random Numbers
• Joint Entropy Coding and Encryption using Robust Chaos

Cited by in corpus (8)

• Increasing Average Period Lengths by Switching of Robust Chaos Maps in Finite Precision
• Application of Gray codes to the study of the theory of symbolic dynamics of unimodal maps
• One-Time Pad, Arithmetic Coding and Logic Gates: An unifying theme using Dynamical Systems
• Multiplexing of discrete chaotic signals in presence of noise
• A Neurochaos Learning Architecture for Genome Classification
• A Novel Chaos Theory Inspired Neuronal Architecture
• Separating a mixture of chaotic signals
• Hash function based on arithmetic coding and public-key cryptography