The Graph Structure of the Generalized Discrete Arnold's Cat Map

Chaotic dynamics is an important source for generating pseudorandom binary sequences (PRBS). Much efforts have been devoted to obtaining period distribution of the generalized discrete Arnold's Cat map in various domains using all kinds of theoretical methods, including Hensel's lifting approach. Diagonalizing the transform matrix of the map, this article gives the explicit formulation of any iteration of the generalized Cat map. Then, its real graph (cycle) structure in any binary arithmetic domain is disclosed. The subtle rules on how the cycles (itself and its distribution) change with the arithmetic precision e are elaborately investigated and proved. The regular and beautiful patterns of Cat map demonstrated in a computer adopting fixed-point arithmetics are rigorously proved and experimentally verified. The results can serve as a benchmark for studying the dynamics of the variants of the Cat map in any domain. In addition, the used methodology can be used to evaluate randomness of PRBS generated by iterating any other maps.

Automated summary

This article investigates the period distribution and cycle structure of the generalized Cat map in various binary arithmetic domains. The rules of how the cycles change with arithmetic precision are studied and proven. The regular and beautiful patterns of the Cat map are rigorously proved and experimentally verified using fixed-point arithmetic. The results provide a benchmark for studying the dynamics of Cat map variants in any domain and can be used to evaluate the randomness of PRBS generated by other maps.