Arithmetic coding as a non-linear dynamical system. (English) Zbl 1221.94037
Summary: In order to perform source coding (data compression), we treat messages emitted by independent and identically distributed sources as imprecise measurements (symbolic sequence) of a chaotic, ergodic, Lebesgue measure preserving, non-linear dynamical system known as generalized Lüroth series (GLS). GLS achieves Shannon’s entropy bound and turns out to be a generalization of arithmetic coding, a popular source coding algorithm, used in international compression standards such as JPEG2000 and H.264. We further generalize GLS to piecewise non-linear maps (skewed-nGLS). We motivate the use of skewed-nGLS as a framework for joint source coding and encryption.
MSC:
| 94A29 | Source coding |
| 37D45 | Strange attractors, chaotic dynamics of systems with hyperbolic behavior |
| 37E05 | Dynamical systems involving maps of the interval |
References:
| [1] | Alvarez, G.; Li, S., Some basic cryptographic requirements for chaos-based cryptosystems, Int J Bifurcat Chaos, 16, 8, 2129-2151 (2006) · Zbl 1192.94088 |
| [2] | Sayood, K., Introduction to data compression (1996), Morgan Kaufmann · Zbl 0858.94009 |
| [3] | Grangetto M, Grosso A, Magli E. Selective encryption of JPEG2000 images by means of randomized arithmetic coding. In: IEEE 6th workshop on multimedia signal processing, Sienam, Italy; 2004. p. 347-50.; Grangetto M, Grosso A, Magli E. Selective encryption of JPEG2000 images by means of randomized arithmetic coding. In: IEEE 6th workshop on multimedia signal processing, Sienam, Italy; 2004. p. 347-50. |
| [4] | Shannon, C. E., A mathematical theory of communication, Bell Sys Tech J, 27, 379-423 (1948) · Zbl 1154.94303 |
| [5] | Salomon, D., Data compression: the complete reference (2000), Springer-Verlag: Springer-Verlag New York · Zbl 0960.68040 |
| [6] | Huffman, D. A., A method for the construction of minimum-redundancy codes, Proc IRE, 1098-1102 (1952) · Zbl 0137.13605 |
| [7] | Alligood, K. T.; Sauer, T. D.; Yorke, J. A., Chaos: an introduction to dynamical systems (1996), Springer: Springer New York · Zbl 0867.58043 |
| [8] | Vaidya PG, Nagaraj N. Foundational issues of chaos and randomness: “God or Devil, Do We Have A Choice?”. In: Proceedings of foundations of sciences, project of history of Indian science, philosophy and culture, New Delhi; 2006.; Vaidya PG, Nagaraj N. Foundational issues of chaos and randomness: “God or Devil, Do We Have A Choice?”. In: Proceedings of foundations of sciences, project of history of Indian science, philosophy and culture, New Delhi; 2006. |
| [9] | Dajani, K.; Kraaikamp, C., Ergodic theory of numbers, vol. 29 (2002), Mathematical Association of America: Mathematical Association of America Washington, DC · Zbl 1033.11040 |
| [10] | Rissanen, J. J.; Langdon, G. G., Arithmetic coding, IBM J Res Dev, 23, 2, 146-162 (1979) · Zbl 0404.94005 |
| [11] | ISO/IEC FCD 15444-1, JPEG2000 Image compression standard; 1999.; ISO/IEC FCD 15444-1, JPEG2000 Image compression standard; 1999. |
| [12] | Joint Video Team JVT of ISO/IEC MPEG and ITU-T VCEG, Joint Committee Draft (CD); 2002.; Joint Video Team JVT of ISO/IEC MPEG and ITU-T VCEG, Joint Committee Draft (CD); 2002. |
| [13] | Luca MB, Serbanescu A, Azou S, Burel G. A new compression method using a chaotic symbolic approach, <www.univ-brest.fr/lest/tst/publications/pdf/comm04_compression_chaos.pdf>; Luca MB, Serbanescu A, Azou S, Burel G. A new compression method using a chaotic symbolic approach, <www.univ-brest.fr/lest/tst/publications/pdf/comm04_compression_chaos.pdf> |
| [14] | Shannon, C. E., Communication theory of secrecy systems, Bell System Tech J, 28, 656-715 (1949) · Zbl 1200.94005 |
| [15] | Wen, J. G.; Kim, H.; Vilasenor, J. D., Binary arithmetic coding using key-based interval splitting, IEEE Signal Process Lett, 13, 2, 69-72 (2006) |
| [16] | Nagaraj N, Vaidya PG, Bhat KG. Joint entropy coding and encryption using robust chaos; 2006.arXiv.org:nlin.CD/0608051.; Nagaraj N, Vaidya PG, Bhat KG. Joint entropy coding and encryption using robust chaos; 2006.arXiv.org:nlin.CD/0608051. |
| [17] | Banerjee, S.; Yorke, J. A.; Grebogi, C., Robust chaos, Phys Rev Lett, 80, 3049-3052 (1998) · Zbl 1122.37308 |
| [18] | Shastry MC, Nagaraj N, Vaidya PG. The B-exponential map: a generalization of the logistic map, and its applications in generating pseudo-random numbers; 2006. arXiv.org:cs/0607069.; Shastry MC, Nagaraj N, Vaidya PG. The B-exponential map: a generalization of the logistic map, and its applications in generating pseudo-random numbers; 2006. arXiv.org:cs/0607069. |
| [19] | The National Institute of Standards and Technology, <http://www.csrc.nist.gov/rng/SP800-22b.pdf>; The National Institute of Standards and Technology, <http://www.csrc.nist.gov/rng/SP800-22b.pdf> |
| [20] | Marsaglia G.<http://www.csis.hku.hk diehard/index.html>; Marsaglia G.<http://www.csis.hku.hk diehard/index.html> |
| [21] | Walker J. ENT: a psuedorandom number sequence test program, <http://www.fourmilab.ch/random/>; Walker J. ENT: a psuedorandom number sequence test program, <http://www.fourmilab.ch/random/> |
| [22] | Boyd, C.; Cleary, J. G.; Irvine, S. A.; Rinsma-Melchert, I.; Witten, I. H., Integrating error detection into arithmetic coding, IEEE Trans Commun, 45, 1-3 (1997) |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
