PaperlayerView exact revision on arXiv

Source-linked AI summary

Dynamic Analysis of Digital Chaotic Maps via State-Mapping Networks

Chengqing Li, Bingbing Feng, Shujun Li, Juergen Kurths, Guanrong Chen

arXiv:1410.7694v5cs.CRnlin.CD

TL;DR

The paper asks how chaotic-map dynamics change under finite-precision digital implementation, where conventional output tests may not reveal the full state structure. It models all representable states and transitions as state-mapping networks, analyzes Logistic and Tent maps across arithmetic domains, and proves scale-free properties for the Logistic map’s SMN. The framework also supports coarse PRNG-randomness evaluation and identifies structures relevant to mitigating digital dynamics degradation.

  • Problem

    Finite-precision implementations degrade chaotic dynamics, while output-based randomness tests do not expose the complete structural behavior of digital maps.

  • Method

    The paper constructs SMNs whose nodes are digital states and whose directed edges represent map transitions, then analyzes Logistic and Tent maps in fixed- and floating-point domains.

  • Results

    The Logistic map’s SMN has proved scale-free properties, while the framework reveals structural properties of digital chaotic maps.

  • Takeaways & Limitations

    SMNs can classify digital chaotic-map structure and coarsely verify PRNG randomness, while helping identify undesirable finite-precision dynamics.

Abstract

from arXiv · show

Chaotic dynamics is widely used to design pseudo-random number generators and for other applications such as secure communications and encryption. This paper aims to study the dynamics of discrete-time chaotic maps in the digital (i.e., finite-precision) domain. Differing from the traditional approaches treating a digital chaotic map as a black box with different explanations according to the test results of the output, the dynamical properties of such chaotic maps are first explored with a fixed-point arithmetic, using the Logistic map and the Tent map as two representative examples, from a new perspective with the corresponding state-mapping networks (SMNs). In an SMN, every possible value in the digital domain is considered as a node and the mapping relationship between any pair of nodes is a directed edge. The scale-free properties of the Logistic map's SMN are proved. The analytic results are further extended to the scenario of floating-point arithmetic and for other chaotic maps. Understanding the network structure of a chaotic map's SMN in digital computers can facilitate counteracting the undesirable degeneration of chaotic dynamics in finite-precision domains, helping also classify and improve the randomness of pseudo-random number sequences generated by iterating chaotic maps.

I. INTRODUCTION

Digital implementations degrade the dynamics of ideal chaotic maps because finite precision introduces round-off and truncation errors. The paper addresses this limitation by analyzing complete state-mapping networks rather than relying only on output statistics.

  • Finite-precision round-off and truncation errors cause digital chaotic orbits to diverge from theoretical trajectories.
  • Digital chaotic maps inevitably undergo dynamics degradation, limiting their ability to attain ideal chaotic behavior.
  • Randomness test suites can miss rare structural details because they sample outputs rather than reveal the complete state relationships.
  • An SMN represents every digital state as a node and each map transition as a directed edge, enabling direct structural analysis.
  • The paper analyzes Logistic and Tent map SMNs in fixed-point and floating-point arithmetic and applies SMNs to PRNG evaluation.

II. STATE-MAPPING NETWORK OF DIGITAL CHAOTIC MAPS IN THE FIXED-POINT ARITHMETIC DOMAIN

The paper studies digital chaotic-map dynamics through complex-network methodology, beginning with general SMN properties and then examining Logistic and Tent map structures.

  • The study defines state-mapping networks for chaotic maps implemented with fixed-point arithmetic.
  • It proves general properties of fixed-point SMNs before analyzing special structures of the Logistic and Tent maps.
  • The Logistic and Tent maps serve as representative cases for examining digital chaotic-map dynamics.

A. Basic properties of chaotic maps implemented in the fixed-point arithmetic precision

A fixed-point SMN discretizes a map's domain and range into representable states, then connects states according to quantized map transitions. The section establishes structural relationships across precisions and specifies the quantization convention.

  • Basic SMN construction: For precision n, the map domain and range are discretized into 2^n + 1 representable states.
  • Basic SMN construction: The SMN contains one node per state and a directed edge when the quantized map sends one state label to another.
  • Quantization: Round, floor, and ceil are possible integer quantization functions, but the paper uses round quantization throughout.
  • Cross-precision relationships: Properties 1–3 characterize how node labels at precision n correspond to labels 2i, 2i + 1, and 2i − 1 at precision n + 1.

B. SMN of the digital Logistic map

The digital Logistic map is represented as a state-mapping network whose structure reveals connected components, cycles, transient paths, and scale-free in-degree distributions. These properties can be derived analytically under fixed-point arithmetic and approach limiting distributions as precision increases.

  • SMN construction: Each possible digital state is a node, and the Logistic-map mapping between states forms directed edges in the SMN.The analysis uses fixed-point precision n and examines how the network changes with arithmetic precision.
  • Network structure: The whole SMN consists of weakly connected components, each containing exactly one self-loop or cycle, with every node reaching its component's cycle through a transient process.These properties characterize the functional-graph structure of the digital map.
  • Network structure: One weakly connected component contains more than half of all network nodes and dominates the remaining components in size.The components also follow a clear decreasing size order.
  • In-degree structure: Quantization changes in-degree monotonicity mainly where degrees are relatively small, while the degree of F*_n(2^n−1) is derived analytically.The in-degree generally increases with the output value because the Logistic map's derivative decreases on [0, 1/2].
  • In-degree structure: The Logistic map's symmetry makes most node in-degrees even, except for the node corresponding to the critical point f(1/2).In-degree counts the number of directed edges entering a node.

C. SMN of the digital Tent map

The digital Tent map’s SMN has a restricted degree structure and expands incrementally as implementation precision increases. Unlike the Logistic map, its edges do not accumulate with increasing precision, and convexity is sufficient but not necessary for power-law degree distributions.

  • Precision effects: The Tent-map SMN incrementally expands as fixed-point precision increases, as illustrated for µ = 31/25 at 5-bit and 6-bit precision.The 5-bit and 6-bit networks are shown in separate panels.
  • Analytical setup: For the Tent map, the domain’s symmetry permits analysis using only its left half, where the map increases monotonically with x.The inverse-function analysis is performed on [0, 1/2], with the case y ≠ µ treated separately.
  • Precision effects: The Tent map’s edges do not accumulate as implementation precision increases, unlike those of the Logistic map.This distinction follows from the Tent map’s restricted degree values.
  • Degree distributions: Convexity throughout the domain is sufficient but not necessary for the associated SMN to follow a power-law distribution.Thus, the Logistic map’s convexity-based condition does not characterize all maps with power-law SMNs.

A. Influence caused by floating-point arithmetic

Floating-point arithmetic alters complement operations and produces map-specific finite-precision behavior. For the digital Tent map, iterations can nevertheless be carried out exactly through bit shifting and converge to zero after a bounded number of steps.

  • Representation formats: Floating-point arithmetic represents real numbers with variable precision, while fixed-point arithmetic uses a fixed precision, creating different finite-precision behavior.The paper distinguishes the two formats as a trade-off between numerical range and precision.
  • Floating-point complement: In floating-point arithmetic, equality between x and 1 − fl(1 − fl(x)) does not generally hold because of final quantization differences.For x ≤ 0.5 the complement operation is evaluated through floating-point rounding; for x > 0.5, the complement is fixed in the represented domain.
  • Floating-point complement: The difference between 1 − (1 − x) and x decreases monotonically within each selected floating-point interval.The two initial interval segments connect smoothly at e1 = −14, and the resulting Logistic-map difference is shown in Fig. 12.
  • Tent-map dynamics: The digital Tent map reaches zero exactly because its chaotic iterations use left bit shifting without quantization error.For a nonzero initial state, x(L−1) = (0.1)2, then x(L) = 1 and x(L+1) = 0.
  • Tent-map dynamics: Nr = L+1 iterations are required for a nonzero digital Tent-map state to converge to zero, while Nr = 0 for the zero state.Across 10,000 initial conditions, average Nr values for three arithmetic domains were about 11.95, 24.97, and 54.01, matching theoretical expectations.

B. Relationship between the SMNs obtained in two arithmetic domains

The paper establishes a strong correspondence between floating-point and fixed-point state-mapping networks when their minimum representable intervals match. Floating-point networks can then be understood as rewired versions of corresponding fixed-point subnetworks, with similar in-degree distributions.

  • Theoretical relationship: Matching the floating-point minimum interval to fixed-point precision n requires n = m + 2l−1 − 2, yielding strong correlation between the two SMNs.The correspondence is characterized by Theorem 2.
  • Theoretical relationship: Theorem 2 maps nodes with the same label between floating-point and fixed-point SMNs through piecewise relations determined by exponent intervals.The mapping distinguishes low-valued nodes from nodes in ranges [2n−j−1, 2n−j).
  • Examples: Figures 15–17 and Tables II–III illustrate and validate the correspondence across selected Logistic- and Tent-map arithmetic domains.The examples include µ = 121/25, µ = 62/24, and µ = 15/24.
  • Network construction: Floating-point SMNs can be generated from corresponding fixed-point SMNs by redirecting links according to the floating-point quantization intervals.This makes the floating-point network a rewired version of a fixed-point subnetwork.
  • Network structure: The cumulative and ordinary in-degree distributions of Logistic-map floating-point SMNs approximate those of corresponding fixed-point SMNs.The paper verifies this correspondence by comparing Figs. 5 and 18 with Figs. 6 and 19.

IV. TESTING THE RANDOMNESS OF VARIOUS PRNGS BASED ON ITERATING A CHAOTIC MAP VIA SMN

State-mapping networks provide a structural tool for classifying chaotic-map PRNGs and coarsely evaluating their randomness. The paper examines how precision, state and parameter selection, perturbation, switching, and cascading alter SMN structure.

  • SMN-based evaluation: SMNs can classify structures of PRNGs based on iterating chaotic maps and provide a coarse visual complement to standard randomness test suites.The paper specifically mentions NIST SP 800-22 and TestU01 as complementary test suites.
  • Selecting states and parameters: Nodes labeled 0 and 2n are pathological seeds and should be excluded from PRNGs.The Tent-map control parameter determines the selected SMN under a fixed implementation environment.
  • Increasing precision: Increasing arithmetic precision can enlarge average SMN orbit length and complexity but cannot change the overall network structure.The paper also notes that higher precision does not always enlarge the average path period.
  • Perturbation methods: State perturbation rewires SMN linking edges, whereas control-parameter perturbation walks between SMNs associated with different parameters.The examples use bit-wise XOR state perturbation and parameter switching between Logistic-map SMNs.
  • Switching and cascading: Switching walks on different chaotic-map SMNs and can give some final-SMN nodes out-degree greater than one, bounded by the number of maps.Cascading connects walks across multiple SMNs, potentially joining previously isolated connected components.
  • SMN-based evaluation: SMN analysis can evaluate dynamical complexity after enhancement methods are applied to an existing chaotic map.The paper presents this as an application of SMN-based evaluation.

V. CONCLUSIONS

The paper uses complex-network methodology to reveal microscopic and macroscopic structure in digital chaotic maps. SMNs classify map structures and coarsely verify randomness, with possible extension to higher-dimensional systems.

  • Conclusions: SMN analysis reveals subtle dynamical properties of digital Logistic and Tent maps at microscopic and macroscopic scales.The conclusion presents the study as a complex-network analysis of digital chaotic maps.
  • Conclusions: Small-precision SMNs can classify digital-map structure and coarsely verify the randomness of generated sequences.The conclusion frames this as an efficient tool rather than a replacement for all randomness testing.
  • Conclusions: The analysis can be extended to higher-dimensional chaotic systems.This extension is stated as a future scope of the methodology.
Loading 1410.7694v5…