Arithmetic coding as a non-linear dynamical system

DOI10.1142/S0218127411029392zbMATH Open1221.94037arXiv0906.3575OpenAlexW2020767010MaRDI QIDQ716619FDOQ716619

Authors: Nithin Nagaraj, P. G. Vaidya, Kishor G. Bhat 

Publication date: 30 September 2011

Published in: Communications in Nonlinear Science and Numerical Simulation, International Journal of Bifurcation and Chaos in Applied Sciences and Engineering (Search for Journal in Brave)

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"{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.

Full work available at URL: https://arxiv.org/abs/0906.3575

Recommendations

• Arithmetic coding as a non-linear dynamical system
• Comments on ``Arithmetic coding as a non-linear dynamical system
• Generalized arithmetic coding using discrete chaotic maps
• An efficient coding system for long source sequences
• A secure and efficient entropy coding based on arithmetic coding

zbMATH Keywords

data compressionarithmetic codingchaotic mapencryptionHuffman codingsource codinggeneralized Lüroth series

Mathematics Subject Classification ID

Strange attractors, chaotic dynamics of systems with hyperbolic behavior (37D45) Information theory (general) (94A15) Coding theorems (Shannon theory) (94A24) Source coding (94A29) Stability of topological dynamical systems (37B25) Dynamical systems involving maps of the interval (37E05)

Cites Work

• A Mathematical Theory of Communication
• Title not available (Why is that?)
• Ergodic theory of chaos and strange attractors
• Title not available (Why is that?)
• Title not available (Why is that?)
• Communication Theory of Secrecy Systems*
• Title not available (Why is that?)
• A Method for the Construction of Minimum-Redundancy Codes
• Arithmetic Coding
• Chaos
• Arithmetic coding as a non-linear dynamical system
• SOME BASIC CRYPTOGRAPHIC REQUIREMENTS FOR CHAOS-BASED CRYPTOSYSTEMS
• Robust Chaos
• Title not available (Why is that?)
• Cantor's Series for Vectors
• DESIGN OF ONE-DIMENSIONAL CHAOTIC MAPS WITH PRESCRIBED STATISTICAL PROPERTIES
• Probability density functions of some skew tent maps
• On grammars, complexity, and information measures of biological macromolecules
• Piecewise linear maps, Lyapunov exponents and entropy
• Title not available (Why is that?)

Cited In (18)

• An application of the Hopfield model to Huffman codes
• Joint compression and encryption using chaotically mutated Huffman trees
• A novel block-based scheme for arithmetic coding
• Application of Gray codes to the study of the theory of symbolic dynamics of unimodal maps
• When noise meets chaos: stochastic resonance in neurochaos learning
• One-time pad as a nonlinear dynamical system
• Arithmetic coding as a non-linear dynamical system
• Chaosnet: a chaos based artificial neural network architecture for classification
• An efficient coding system for long source sequences
• A secure and efficient entropy coding based on arithmetic coding
• Comments on ``Arithmetic coding as a non-linear dynamical system
• A dynamical systems proof of Kraft-McMillan inequality and its converse for prefix-free codes
• Distributed source coding using chaos-based cryptosystem
• GLS coding based security solution to JPEG with the structure of aggregated compression and encryption
• Multiplexing of discrete chaotic signals in presence of noise
• Generalized arithmetic coding using discrete chaotic maps
• Generalized smooth transition map between tent and logistic maps
• The problem of the inverse Lyapunov exponent and its applications

This page was built for publication: Arithmetic coding as a non-linear dynamical system

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q716619)