1 Introduction

Random numbers play an important role in nowadays digital systems, and they can be found in many digital systems. As digital computers dominate data processing fields today, random number generators implemented in digital computers are known as pseudo-random number generators (PRNGs). The deterministic nature of the process leads to the term pseudo-random. PRNGs algorithms are widely used today thanks to their simplicity of implementation in both software and hardware. They are capable of generating sequences of numbers which appear random-like from many aspects.

Though they are necessarily periodic and their periods are very long, they pass many statistical tests and can be easily implemented with simple software routines (Elsherbeny and Rahal 2012). PRNGs have been widely used in Monte Carlo simulations, test pattern generation, cryptography, and telecommunication systems (Liu and Miao 2015). A good PRNG should have characteristics of: (1) long-period random number sequence; (2) a fit in statistical properties; (3) a high throughput rate; and (4) an unpredictability (Li et al. 2012). Finding all aforementioned characteristics together in one PRNG is a big challenge, due to their fixed linear structure, and most known pseudo-random generators (Linear Feedback Shift Registers, Linear congruential generators, etc.) are not secure enough, especially when used for information security.

Not long ago, many researchers have focused on chaotic signals as a source of randomness because of their attractive proprieties (Oishi and Inoue 1982; Lin and Chua 1993; Bernstein and Lieberman 1991; Kolesov et al. 2001; Stojanovski et al. 2001; Andrecut 1998). A chaotic system by nature is a dynamical system that provides some characteristics such as noise-like behavior, sensitive dependence on initial conditions, unpredictability, aperiodicity and ergodicity. These characteristics are very useful making chaotic systems good alternatives to many conventional PRNGs and cryptosystems.

Unfortunately, chaos dynamics proprieties are more significant when these systems are studied in their original continuous state. The digital implementation of such systems using finite arithmetic precision leads to significant degradations on its dynamical behavior. These degradations are in fact a serious problem that detracts from importance of chaotic systems application.

Therefore, in order to benefit from the chaotic dynamic properties using finite precision computations, the dynamical degradations arising from digitization process should be taken into account and solved as much as possible. Many researchers have been highlighted theses degradation problems with some proposed solutions (Binder and Jensen 1986; Beck and Roepstorff 1987; Palmore and Herring 1990; Fryska and Zohdy 1992; Li et al. 2001a, 2003; Hu et al. 2014; Liu et al. 2014, 2017; Deng et al. 2015a, b).

The digitized chaotic systems are often known as pseudo-chaotic generators (PCGs), like PRNGs, and PCG suitable for cryptography should provide good statistical proprieties and should be unpredictable. Technically, unpredictability can be interpreted as cycle length of the chaotic generator. In other words, due to the computation finite precision; although chaotic generators seem random, they have a finite period that when the generator reaches; then, it will repeat the same orbit. The process of dealing with dynamical degradations of digital chaotic system can be considered as making a periodic system “chaotic”, which is known as “chaotification” or “anti-control” of chaos (Hu et al. 2014).

This paper is organized as follows. Section 2 deals with dynamical degradations arisen from digitizing process of chaotic systems. Sect. 3 describes some proposals on the context of overcoming dynamical degradations in digital chaotic signals. Section 4 is devoted to represent our proposed idea for extending cycle length of digital chaotic systems, in which enough details and evaluation of the proposed scheme are presented. The FPGA-based hardware implementation of the proposed scheme is the subject of Sect. 5. Section 6 concludes the paper.

2 Dynamical Degradations in Digital Chaotic Systems

The digital implementation of chaotic systems on computers has the same concept of analog-to-digital conversion process in electronics. Depending on the computing arithmetic precision provided by the computer, the implemented chaotic function generates time series with values rounded to the nearest continuous value. The difference between the rounded value and the real one represents the quantification error. Following the analytic idea used in Li et al. (2003), consider a one-dimensional chaotic system \(T :X \rightarrow X\), defined on [0, 1]:

$$\begin{aligned} X(n+1) = F(x(n)) \end{aligned}$$
(1)

Assume that the fixed-point arithmetic precision is adopted; the chaotic iterations will be confined in the following discrete set:

$$\begin{aligned} S=[x_n\in [0,1]|x_n=n\times 2^{-L}, n=0,1,.,2^L-1] \end{aligned}$$

where L represents the word size (Largest precision). Hence, any quantity of the digital chaotic system (1) (initial condition, control parameter or generated output) can never take a value out of the specified set S. The digital chaotic system (1) can be represented as follows:

$$\begin{aligned} \tilde{X}(n+1)=F_L (\tilde{X}(n))=D_L o F(\tilde{X}n)) \end{aligned}$$
(2)

where \(\tilde{X}(n)\) represents the digital state vector and \(D_L\) the quantization function. Three quantization functions are used in almost today's computers: floor function, ceil function and round function.

Fig. 1
figure 1

The chaotic attractor studied in Fryska and Zohdy (1992), a implemented using single-precision floating-point arithmetic (32 bits), b using extended double-precision floating-point arithmetic (80 bits) and c obtained from the exact solution

2.1 Quantization Error in Digital Chaotic Systems

\(D_L\) will introduce the quantization error to the digital sequence generated by the system (1); consequently, due to the high sensitivity of the chaotic systems to the initial parameters, the quantification error quickly propagates into the mainstream of the generated sequence and changes the topology of the systems attractor. The pseudo-orbits (which designate the digitized chaotic orbits) represented in finite precision arithmetic can be entirely different from the theoretical ones (Li et al. 2005).

Some computation precisions lead to different and unexpected chaotic and non-chaotic structures. As an example, Fryska and Zohdy (1992) have implemented a 3-D piecewise linear chaotic system using single-precision floating-point arithmetic (32 bits) and extended double-precision floating-point arithmetic (80 bits). The first case gave a two-scroll chaotic attractor that is highly instable. The surprising results were in the second case, even though the used parameters were kept unchanged, unexpected results were obtained: a periodic attractor (Fig. 1).

The influence of the arithmetic precision (quantization error) on chaotic dynamics has also been studied in depth in Palmore and Herring (1990), where the authors concluded that quantization errors using floating-point arithmetic can propagate into the mainstream of a chaotic system and, within 30–50 steps, destroy all the accuracy of the result.

2.2 Cycle Length in Digital Chaotic Systems

A very important issue related to digitization of chaotic systems is their long-term dynamics. Numerous studies have mentioned the direct relationship between digitized chaotic systems cycle length and the used arithmetic precision. Accordingly, the digital chaotic systems are considered as periodic and its longest orbit can never exceed \(2^L\). In accordance with Li et al. (2003), a typical orbit of a computerized chaotic system has a limited length n, where \(n \ll 2^L\) in most cases . The orbit length has two main parts (Fig. 2), transient length (l) from \(x_0\) to \(x_l\) and cycle length (n) from \(x_l\) to \(x_n\), and consequently the orbit length \(= l + n\). Numeric simulations have found that maximal length of computerized chaotic orbits is \(O(2^{\varepsilon L})\), where \(0<\varepsilon <1\) and \(1/\varepsilon >> 1\) is right for many chaotic systems (Li et al. 2003).

Fig. 2
figure 2

Digitized chaotic systems typical orbit

3 Purifying Digital Chaotic Systems from Degradations

The agreed issue is that digital chaotic systems are periodic and their cycle lengths may be rather short (despite the existence of long ones). This sensitive issue makes the usefulness of applying chaos in cryptography meaningless.

Thus, to counteract degradations resulting from digitizing continuous chaotic systems, extensive research has been done recently from both theoretical and experimental points of views. The proposed solutions can be classified into 3 main categories, using higher arithmetic precision, cascading multiples chaotic systems and randomly perturbing the digital chaotic orbits. The efficiency evaluation of theses remedies can be found in Li et al. (2005).

3.1 Using Higher Arithmetic Precision

By increasing the computation arithmetic size, the cycle length of the digitized chaotic system can be effectively extended. The average cycle length will be prolonged exponentially as the precision increases (Hu et al. 2014), but, however, the computation arithmetic is still finite and there still exist plenty of short chaotic orbits; consequently, due to the computation power available today, it is unreasonable to trust this idea and confirm its efficiency.

Some weak control parameters lead to a worse distribution and produce chaotic sequences with short cycles; in this case, increasing arithmetic precision has no effect which implies that this idea is still vulnerable.

3.2 Cascading Multiples Chaotic Systems

This idea is based on using multiple chaotic generators and then combines their outputs together for producing the whole chaotic sequence. In Heidari-Bateni and McGillem (1994), the authors have cascaded two chaotic systems in a spread spectrum communication system, one for generating the chaotic sequence and the other for generating the initial conditions for the other system. After N iterations for the second chaotic system, the first system generates a new initial condition to initiate the second one.

Although this idea can effectively prolong the period of the generated chaotic sequence; Li et al. (2005) and Binder and Jensen (1986) assumed that the distribution of output sequence of digital chaotic system for the proposed idea is not uniform in discrete phase space even though the input sequence is uniformly distributed.

Another important issue related to the cascading multiple chaotic systems technique is the hardware cost and performance. In fact, what we can benefit from this technique in terms of cycle extension may be lost in the cost of hardware implementation of such designs, and consequently, reduces its performance in general.

3.3 Perturbing the Chaotic System Orbit

The basic idea of this method consists of using either random or pseudo-random sequence to perturb the digital chaotic orbits. This technique is more efficient compared to the other two and was supported and adopted by many theorists and practitioners (Černák 1996; Li et al. 2001b, 2005; Fryska and Zohdy 1992; Hu et al. 2014; Merah et al. 2015; Blank 1994; Hasimoto-Beltrán and Ramírez-Ramírez 2011; Tao et al. 1998; Shu-Bo et al. 2009; Tong 2013). Experiments have shown that such a simple remedy can improve the dynamical properties of computerized (digital) chaos to some extent (Li et al. 2003). Perturbation techniques can be classified into three main categories: perturbing the orbits of a given digital chaotic system, perturbing the control parameters, and perturbing both orbits and control parameters; the first two methods are mostly used.

Tao et al. (1998) had easily deduced that the new cycle length of the perturbed schemes is \(T^{'}=\sigma \varDelta (2^{L}-1)\), where \(\sigma\) is a positive integer, \(\varDelta\) is the perturbation period, and \((2^{L}-1)= T\) is the cycle length of the perturbing signal. Assuming perturbing system uses the same finite precision as the digital chaotic system and has a maximum length of \(2^L\), the lower bound of the system cycle length is \(T^{'}_{\mathrm{min}}=\varDelta 2^{L}\) which is greater than the cycle length \(2^L\).

Fig. 3
figure 3

The proposed scheme for extending cycle length of digital chaotic systems

4 The Proposed Perturbation Mechanism (PPM)

In this section, the proposed idea for perturbing a given chaotic system orbits and extending its cycle length is described. As mentioned previously, the proposed circuit is self-perturbation; that is, our digital chaotic system does not need an external perturbation source; it provides a self-generator for perturbing its orbits.

As shown in Fig. 3, the proposed scheme has 4 main parts: the chaotic system, a counter, a shift register of m memory cells, and slice blocks, each part has its own function as follows:

  • The chaotic system It has the role of generating the chaotic sequence x(n) which has L bits of length.

  • Slice block 1 This block divides the binary sequence of the chaotic output x(n) into two parts: the sequence \(S_1\) that represents the l upper bits of x(n) and the sequence \(S_2\) that represents the m lower bits of x(n); note that \(L = l + m\) where L is the largest computation precision used to implement the chaotic system.

  • Slice block 2 This block extracts the LSB (low significant bit) from the chaotic output x(n) at each clock cycle.

  • Shift register It has m bits of size; this block has the role of loading the LSB generated from the slice block 2 and shifts it to the right at each clock cycle. The shifting operation works continuously, when the register cells are full; the register excludes the right bit to accept new bit on its left side (Fig. 3).

  • Counter It has the most important role in the circuit because it defines the perturbation periods \(T_{\mathrm{p}}\). The counter is controlled by a flip-flop, and this last has an initial integer value N (12 bits) which represents the maximum that the counter can reach. When the counter reaches the maximum N, two signals named \({\hbox {Cnt}}_{\mathrm{out}}\) and C change their states from ’0’ to ’1’, for the signal C, when activated; it tells the flip-flop to load new data (D) from the shift register. The signal \({\hbox {Cnt}}_{\mathrm{out}}\) controls a multiplexer that outputs either a sequence of zeros (m bits of length) or the shift register content (of m bits of length bits of length).

  • Bit basher block It has the role of collecting the signals \(S_1\) and \(S_3\) (perturbed version of the signal \(S_2\)) to produce the new perturbed sequence \(x^{'}(n)\).

Roughly speaking, we can understand from what have been said above that the chaotic signal x(n) is perturbed during variable periods \(T_{\mathrm{p}}=N\times T\) (where T represents the system clock period). During the counting process, \(S_1\) is XORed with zeros which means that it is kept unchanged (\(S_3 = S_1\) ) and obviously \(x(n)= x^{'}(n)\). If the counter reaches its maximum, the signal \({\hbox {Cnt}}_{\mathrm{out}}\) will be changed from ’0’ to ’1’ and then \(S_2\) is XORed with the shift register content (output of the multiplexer); in this case, \(x^{'}(n)\) becomes a perturbed version of x(n) .

4.1 Experimental Evaluation of the Proposed Perturbation Mechanism

The PPM has been evaluated by applying it on the logistic chaotic map given by:

$$\begin{aligned} x(n+1)=rx(n)(1-x(n)) \end{aligned}$$
(3)

where r is the control parameter. Before applying our PPM, we will try to evaluate the original chaotic system given above by using low arithmetic precision. So, by using a largest arithmetic precision \(2^{16} (L = 16)\), and fixing r to 3.9 (chaotic behavior), we have randomly selected a set of initial conditions and for each one we have computed the transient length and cycle length of the logistic map output. Table 1 summarizes the obtained results.

It is clear from the given results that the logistic map provides very short cycle lengths using the adopted arithmetic precision. In this case, the chaotic properties of the logistic map are meaningless. The system is no longer chaotic, and it is purely periodic. The auto-correlation function can also help to detect periodicities on the logistic map output. The result of the auto-correlation function performed on the logistic map is given in Fig. 4 in which a strong correlation is observed on the output sequence.

Table 1 Computed transient length and cycle length of the logistic map output for different initial conditions

The PPM is now applied to the original system of the logistic chaotic map, by fixing \(m = 15\) bits and \(l = L-m = 1\). The output of the new logistic map is shown in Fig. 5. Figure 6 shows the auto-correlation function result performed on the modified logistic chaotic map for more than 70 million samples. It is clear that the modified logistic map provides good independence between samples compared to the original one.

It should be noted that the available computing configuration did not allow us to process more than 100 millions samples ( i5-2500K CPU with 8Gb of RAM). Thus, we have confirmed that no periodic orbits have been detected for a sequence of 100 millions samples and less.

Fig. 4
figure 4

The auto-correlation function of the chaotic sequence generated from the original digital chaotic system of the logistic map

Fig. 5
figure 5

The output sequence of the modified digital logistic chaotic map with largest precision \(L=2^{16}\)

Fig. 6
figure 6

Auto-correlation function result performed on the modified digital logistic chaotic map with the largest precision \(L=2^{16}\) and for more than 70 million samples

4.1.1 Evaluation of the PPM by Detecting Eventual Cycles

In this case, a simple test is performed on the modified logistic map, and it consists of detecting repeated samples in the chaotic sequence and try to see whether there is a repeated orbits or not. If there are no similar orbits and even there are repeated samples, we can say that the PPM works well.

Experimentally, we tried to detect equal samples and then define their kth positions. We plotted chaotic subsequences starting from the defined kth positions. Thus, experimental results given in Fig. 7 showed (for 106 samples) the detected repeated sample \(x_k=\) 0.94372558550 (for example) and the \(k^th\) positions where \(x_k\) is repeated; \(k = 263\), \(k = 247{,}041\), \(k = 498{,}476\), \(k = 533{,}784\), \(k = 610{,}577\).

It is clear from Fig. 7 that even though the detected samples are identical, the perturbation circuit forces the system to diverge to another different orbit.

Fig. 7
figure 7

Superposition of chaotic sub-sequences from the defined kth positions, \(x_1\) from \(k = 263\), \(x_2\) from \(k = 247{,}041\), \(x_3\) from \(k = 498{,}476\) and \(x_4\) from \(k = 610{,}577\)

4.1.2 Evaluation of the PPM in Terms of Uniformity

Another important criterion that should be provided by good PRNGs is uniformity; this means that numbers generated from a given PRNG should be uniformly distributed. We have evaluated uniformity of the modified logistic map using our PPM and compared the results with the original logistic map. Figures 8 and 9 present the results of the histogram for both logistic maps.

It is clear from the obtained results that the modified logistic map using the PPM provides good distribution and its output is uniformly distributed compared with the original logistic map.

Fig. 8
figure 8

Histogram of the output of the original logistic map

Fig. 9
figure 9

Histogram of the output of the modified logistic map using the PPM

4.1.3 Evaluation of the PPM Using the Approximate Entropy Test

The modified chaotic map has been also evaluated using the approximate entropy test (ApEn). This test has been proposed first by Pincus (1991) for the purpose of detecting similar patterns in time series, and time series containing many repetitive patterns has relatively small ApEn; a complicated process has higher ApEn and therefore is less predictable.

The algorithm of the ApEn works as follows: for a given time series \(\lbrace u(i),i=1,2,.,N \rbrace\), reconstruct this series as:

$$\begin{aligned} X(i)=\,& {u(i),u(i+1),\ldots ,u(i+m-1)},i=1,2,\ldots n,\\ n=\,& N-m+1 . \end{aligned}$$

Now, the m-dimensional sequence X(i) is used to construct \(C^m_i(r)\) = (the number of X(j) such that \(d[X(i),X(j)] \leqslant (r)/(N-m-1)\) , where m (= 2 in our case) is an integer which represents the length of compared run of data, r (range from 0.1 to 0.3) specifies a filtering threshold, and d represents the distance between the vectors X(i) and X(j) : \(d[X(i),X(j)] = {\hbox {max}} |u(i+j)-u(j+k)|, k=0,1,\ldots m-1\). Now we define:

$$\begin{aligned} \phi ^m (r)=(N-m-1)^{-1}\sum \limits _{i=1}^{N-m+1} {\hbox {log}}(C_i^m (r)) \end{aligned}$$

Finally, the ApEn is given by:

$$\begin{aligned} ApEn = \phi ^m (r) - \phi ^{m+1} (r) \end{aligned}$$
(4)

The results of the ApAn test performed on the modified digital chaotic system, the original system, and white noise sequence (as reference) are shown in Fig. 10. It is clear that the modified system has an ApAn much greater than the original system. This result proves the randomness quality of the modified system; we can say that the ApAn for the modified system is relatively equal to the ApAn of white noise. Table 2 contains a comparison between ApAn obtained for our modified system and other proposal (Liu and Miao 2015).

Table 2 Approximate entropy comparison between the modified logistic map and other proposal
Fig. 10
figure 10

The approximate entropy of the sequence of the modified logistic map compared to the original one and white noise

4.1.4 Statistical Proprities of Chaotic Sequence of the Modified Chaotic Map

This section is attended to evaluate our modified logistic map in terms of statistical proprieties of its output, for this purpose; two well-known statistical tests batteries are used: NIST and Diehard, and for each test a \(p\_value\) (significant level) is computed and should greater than 0.01 to say that the test is passed successfully. The results (for \(X(0)= 0.55\)) of the statistical tests performed both on the original logistic map and the modified one are given in Tables 3 and 4, the underlined results mean that the test is fail.

Table 3 NIST statistical tests results performed on the modified logistic map output
Table 4 Diehard statistical tests results performed on the modified logistic map output

It is clear from the obtained results that the modified logistic map provides good statistical proprieties of randomness compared to the original one, and more than 90% of the performed tests are passed successfully.

To affirm the good statistical properties of the modified logistic map, we have evaluated its output for different (randomly chosen) seeds (initial conditions) using both NIST and Diehard statistical tests. Figures 11 and 12 represent the obtained results for \(X_{0}= 0\), \(X_{1}= 0.1\), \(X_{2}= 1.2\), \(X_{3}= 0.25\), \(X_{4}= 0.30\), \(X_{5}= 0.43\), \(X_{6}= 0.58\), \(X_{7}= 0.67\), \(X_{8}= 0.78\), \(X_{9}= 0.85\) and \(X_{10}= 0.95\).

Fig. 11
figure 11

NIST statistical tests results performed on the modified logistic map output for different seeds

Fig. 12
figure 12

Diehard statistical tests results performed on the modified logistic map output for different seeds

The obtained results showed that more than \(87.5 \%\) of the NIST statistical tests have been passed successfully \((p\_value > 0.01)\) and more than \(89.47\%\) of Diehard statistical tests have been passed successfully \((0.01 \leqslant p\_value < 1 )\). George Marsaglia (Diehard statistical tests developer) has pointed out that we should not be surprised with occasional \(p\_values\) near 0 or 1, such as 0.0012 or 0.9983. When a bit stream really FAILS BIG, we will get \(p\_values\) of 0 or 1 to six or more places. By all means, do not, as a statistician might, think that a \(p\_value < 0.025\) or \(p\_value > 0.975\) means that the RNG has “failed the test at the 0.05 level”. Such \(p\_value\) happens among the hundreds that Diehard produces, even with good RNGs.

Thus, from all given results, we can say that the modified logistic map using PPM provides good statistical properties.

5 FPGA-Based Implementation of the Modified Logistic Chaotic Map Using the PPM

This section is devoted to present the results of the FPGA-based implementation of our system in terms of performance and hardware resource consumption. In fact, we have implemented two chaotic systems of the logistic map: the original logistic map and the modified one only for comparison purpose in real-time.

The system was designed using Xilinx System Generator tool (XSG), after some steps needed for implementation, the system was implemented on Xilinx Artix XC7A100T FPGA device (embedded on Digilent Nexys 4 board). In order to visualize the real-time FPGA output, we have used two digital-to-analog converters of National Semiconductor DAC121S101 of 12 bits of resolution (embedded on the Digilent PmodDA2 board). It is worth noting that in addition to the main VHDL code of the chaotic systems, another VHDL component is added to drive signals between the chaotic generator and the PmodDA2 board.

Fig. 13
figure 13

Block diagram of real-time analog outputs of FPGA-based chaotic logistic maps [original logistic map and the modified one using the PPM (orange)]

The DAC component (Fig. 13) receives the parallel data of 12 bits of length (DATA1 from the original logistic map and DATA2 from the modified logistic map), and a START command tells the component to begin the conversion process. The DAC component then converts the data signals from parallel to serial (SD1, SD2) and sends them to the PmodDA2. Another commands, CLK_OUT and NSYNS are also sent to the Pmod and represent, respectively, the clock signal needed for driving the DACs (25 MHz) and the signal used to latch the data inside the PmodDA2 after the data have been shifted out.

Figure 14 represents the hardware components used for the real-time implementation and visualization of both original logistic map and the modified logistic map using the PPM. Real-time outputs of the implemented design shown on oscilloscope are presented in Fig. 15.

Fig. 14
figure 14

Components used for real-time implementation of the design

Fig. 15
figure 15

Real-time outputs of FPGA-based implementation of both original logistic map (blue) and modified logistic map using the PPM (orange)

The results of the achieved performance and consumed resources are given in Table 5 with the largest precision of \(L=2^{16}\). The obtained results have been compared with other modified logistic map; in fact, we have also implemented the proposed method in Liu and Miao (2015).

It is clear from the achieved results that our system provides the higher performance with fewer resources compared to the modified logistic map proposed in Liu and Miao (2015).

Table 5 Timing and resource consumption reports

6 Conclusion

New, simple, and efficient method for extending cycle length of digital chaotic systems is presented in this paper. Our proposed idea does not need any external generator of perturbing the orbit of the chaotic system; it contains a self-mechanism for ensuring perturbation, and this directly reflected on the performance of the design. The cycle length of the new modified chaotic system using our PPM has been extremely increased.

The results obtained from the evaluation of our proposed method prove its efficiency; the new chaotic sequence provides good uniform distribution and the higher approximate entropy compared to other proposals with good results in terms of auto-correlation function. (No repeated patterns are detected.) The statistical tests performed on the proposed system showed clearly the good randomness of its output compared with the original system.

The comparison between our proposed method with other proposals in terms of randomness, approximate entropy, and FPGA hardware implementation performance confirms its efficiency.