1 Introduction

Multistage analog-to-digital converters (ADCs) such as pipelined, algorithmic (cyclic), and successive approximation register (SAR) are widely used in medium-to-high-resolution and bandwidth applications. In these architectures, the analog-to-digital conversion is performed by using one or several successive simple stages in a way that makes it possible to compromise between speed, power consumption, resolution, and circuit area. Among all kinds of ADCs, algorithmic converter, due to the cyclic nature of its conversion process, needs smaller area and lower power and is preferred for some applications [14, 17].

One of the very important issues in analog-to-digital converters is the quantization noise theory. Based on this theory, if an ADC is modeled as a uniform quantizer, without considering its internal structure, the output quantization noise is almost white with uniform distribution [27, 31]. Few studies have been carried out on the analysis of quantization noise specified for multistage converters. In [8, 16], it has been shown that with the passage of signal from different stages of a full-bit and half-bit redundant pipelined converter, the residue probability density function (pdf) and the residue joint pdf at different times converge to uniformity. The obtained results reveal that in a redundant pipeline ADC, the last-stage residue distribution is uniform but does not cover the full converter dynamic range. The same feature exists for the algorithmic converters with full-bit and half-bit redundant structures. These properties allow us to use them as random number generators (RNGs) and produce independent and identically distributed random bit sequences.

Random number generators have numerous applications in symmetric- and public-key cryptography algorithms [1, 7], communication systems [6] as well as calibration of algorithmic and pipelined ADCs by dither injection [13]. RNGs can be divided into two categories: pseudorandom number generators (PRNGs) and true random number generators (TRNGs) [10, 23]. PRNGs have high throughput and because of their intrinsic nature can be easily embedded in any digital circuit or system. However, because of their deterministic and finite memory algorithms, they have periodic behavior and are far from the ideal features required in some important applications such as information security and cryptography [12, 28]. Accordingly, TRNGs which are called physical generators are preferred to be used for high-end security applications [12]. They are usually implemented with a combination of three blocks: entropy source, harvesting mechanism, and postprocessing, and physical random processes are used as their entropy sources [21, 32].

Low throughput [4] and high cost of embedding physical RNGs in digital circuits [1, 7] have led the attention of recent researches to the sources that have both features of the physical RNGs and the simplicity of digital sources simultaneously. Therefore, chaos-based RNGs which use chaotic maps have found widespread applications [18, 21, 29]. Some of these chaotic maps are very similar to the building blocks of practical electronic circuits. For instance, the input–output characteristic of the half-bit redundant stage which has been exploited in designing pipelined ADC in [26] is fully equivalent to the chaotic map that has been used in [6, 29]. For this reason, in [1, 21], this 1.5-bit stage was employed to implement an ADC- based chaotic RNG. Although today this characteristic is not commonly used in multistage ADCs, it is shown that popular used full-bit and half-bit redundant stages are also efficient to design chaotic maps. Since the ADCs are mixed-signal integrated circuits and can be used in high speeds [11], the ADC-based random number generator has high throughput and is easily embeddable in all analog and digital circuits.

In this paper, the input–output characteristics of the various stages of the algorithmic ADC are compared with some of the common chaotic maps that are used in chaos-based RNGs. It is shown that they are fully similar to each other. One of these chaotic maps is Bernoulli map [3, 12, 30], which fully matches with the characteristic of the ideal 1-bit stage. The characteristic of the full k-bit stage is also fully identical to the N-way Bernoulli shift map with \(N=2^{k}\) [25], which is the more general form of the Bernoulli map. Furthermore, using the fundamental theorem for function of a random variable [20], a new approach to analyze the output of chaotic maps as well as the different cycle residues of algorithmic ADC is presented. To this end, the propagation of the output pdf of the chaotic maps in different cycles of the algorithmic ADC is studied. It is demonstrated that regarding the random nature and the uniform distribution of the nonredundant algorithmic ADC output bits, this converter can be used to implement N-way Bernoulli shift map and generate random sequences. For the half-bit redundant algorithmic ADC, the residue pdf converges to uniformity in the center half of the stage full-scale range and out of it converges to zero. Thus, after a sufficiently large number of cycles, each stage will be fully equivalent to the common chaotic map which has been used in [6, 29]. The performance of the proposed ADC-based RNG is evaluated by using the US National Institute for Standards and Technology (NIST) randomness test suite [24]. Since analog-to-digital converters are sensitive to device parameters’ variations [5, 11, 22], these nonidealities are also considered. Test results show that algorithmic-based RNG successfully passes all NIST 800-22 statistical tests in the presence of mismatches.

The rest of the paper is organized as follows. In Sect. 2, some of the common chaotic maps that are very similar to the characteristic of ADC building blocks are investigated. Section 3 introduces the algorithmic ADC architecture. In Sect. 4, the use of full-bit algorithmic ADC, and in Sect. 5, the application of half-bit redundant converter in random bit generation is explored. Section 6 evaluates the performance of the proposed RNG using the NIST statistical test suite, and a brief conclusion is drawn in Sect. 7.

2 Chaos-Based RNGs

Random sequence generation can be modeled by the toss of an ideal coin, which the probability of each side is 1/2. Such tosses are independent from each other, and seeing each toss does not affect the probability of the next tosses observations. That is, the system state cannot be predicted. This behavior can be described as the two-state Markov chain of Fig. 1, which is a special kind of Markov processes. Several chaotic maps were presented for this Markov chain. One of them is Bernoulli map which is expressed as follows [12, 30]:

$$\begin{aligned} M:[-1,1]\rightarrow [-1,1],\quad M(x)=\mu x\hbox { mod }2-1 \end{aligned}$$
(1)

where \(0<\mu \le 2\) is the chaos control parameter and the maximum entropy of the source is obtained by \(\mu =2\). Equation (1) can be expressed as follows:

$$\begin{aligned} M:[-1,1]\rightarrow [-1,1],\quad M(x)=\left\{ \begin{array}{ll} {\mu x+1}&{} \quad {-1<x<0} \\ {\mu x-1}&{} \quad {0<x<1.} \end{array}\right. \end{aligned}$$
(2)

Assuming \(\mu =2\), Bernoulli shift map fully matches with the 1-bit stage input–output characteristic of algorithmic converter. In Sect. 4, it will be shown that after sufficient iterations of this map, the distribution of the x-samples becomes uniform over [\(-1, 1\)]. In this way, the Bernoulli map and 1-bit stage of algorithmic ADC are exactly equivalent to Markov chain of Fig. 1 and knowing the previous sequences reveals no information about its future values. Also, since the probability of being in each of two states equals 1/2, the entropy of the source is one bit.

Fig. 1
figure 1

Markov chain of the fair coin toss

Full size image

The more general form of (1) and (2) is N-way Bernoulli shift map [25], which can be expressed as

$$\begin{aligned} M:[-1,1]\rightarrow [-1,1],\quad M(x)=Nx\hbox { mod }2-1. \end{aligned}$$
(3)

The N-way Bernoulli shift map that is widely used in signal- processing tasks is shown in Fig. 2 for different values of N. Since this map can be modeled by two-state Markov chain of Fig. 1 [1, 21], knowing the previous sequences reveals no information about its future values.

Fig. 2
figure 2

N-way Bernoulli shift map for different values of N

Full size image

Another chaotic map that has been found to have a good performance in RNGs is according to the following expression [6, 29]:

$$\begin{aligned} M:[-1,1]\rightarrow [-1,1],\quad M(x)=(2x+1)\hbox { mod }2-1. \end{aligned}$$
(4)

This map that is shown in Fig. 3 can be expressed as:

$$\begin{aligned} M:[-1,1]\rightarrow [-1,1],\quad M(x)=\left\{ \begin{array}{ll} {2x+2}&{} \quad \displaystyle {-1<x<-\frac{1}{2}} \\ {2x}&{} \quad \displaystyle {-\frac{1}{2}<x<\frac{1}{2}} \\ {2x-2}&{} \quad \displaystyle {\frac{1}{2}<x<1.} \end{array}\right. \end{aligned}$$
(5)

This chaotic map is identical to the characteristic of the 1.5-bit stage employed in [26] for pipelined ADC which uses the half-bit redundancy in order to achieve the related advantages. An important feature of this map compared with Bernoulli map is its flexibility against noise and nonideality impacts on electronic circuits in a way that it has all the necessary conditions for a piecewise affine Markov chaotic map [21]. In this map, the distribution of x-samples over [\(-1, 1\)] converges to uniformity. It can be shown that from the statistical point of view and after sufficient iterations, the behavior of the map can be illustrated exactly as the Bernoulli process and two-state Markov chain of Fig. 1 [1].

Fig. 3
figure 3

The chaotic map (5)

Full size image

3 Algorithmic ADC Architecture

The architecture of an algorithmic analog-to-digital converter is shown in Fig. 4. This ADC consists of an input sample-and-hold amplifier (SHA) and one or several number of successive simple stages. All signals are normalized to \(V_\mathrm{ref}\), so the converter dynamic range is \([-1, 1]\). The SHA converts the continuous-time input signal \(x_\mathrm{in} \) into a sampled sequence \(x( k )=x_\mathrm{in}\) (\(kT_\mathrm{s}\) ), where \(T_\mathrm{s}\) denotes the sampling period. Each algorithmic stage consists of a flash sub-ADC, a sub-DAC, a subtractor, and an interstage amplifier. In the ith stage, the flash sub-ADC generates an \(m_{i}\)-bit digital estimation \(D_{i}\) of the stage input \(x_{i}\) and the sub-DAC converts this digital word to an analog signal. Then, the difference between the sampled signal \(x_i \) and its quantized version \((Q_i )\) is amplified with the interstage gain \(G_{i}\) to produce a residue signal \(y_{i}\) which is used as the input \(x_{i+1}\) to the next stage. The algorithmic converter extracts the required number of bits in several clock cycles and by returning back to a sequential approach.

Fig. 4
figure 4

Algorithmic ADC architecture

Full size image

In the algorithmic converter, input–output characteristic of each stage is according to the following expression:

$$\begin{aligned} x_i =\frac{1}{G_i }x_{i+1} +Q_i. \end{aligned}$$
(6)

Assuming the input signal is passed sequentially through N cycles, it can be written as [13, 16]

$$\begin{aligned} x=\sum _{i=1}^N {\left( \, {\prod _{j=1}^{i-1} {\frac{1}{G_j }} } \right) } Q_i +e, \end{aligned}$$
(7)

where e is the quantization error and

$$\begin{aligned} e=\left( \, {\prod _{i=1}^{N-1} {\frac{1}{G_i }} } \right) x_N. \end{aligned}$$
(8)

If there are no other error sources than the quantization noise, the converter signal-to-quantization-noise ratio (SQNR) is obtained by:

$$\begin{aligned} \hbox {SQNR}=10\log \left( {\frac{\overline{x^{2}} }{\overline{\hbox {e}^{2}} }} \right) =10\log \left( {\overline{x^{2}} } \right) -10\log \left( {\overline{\hbox {e}^{2}} } \right) . \end{aligned}$$
(9)

By applying a full-scale sinusoidal input, the converter effective number of bits (ENOBs) can be calculated by [19]:

$$\begin{aligned} \hbox {ENOB}=\frac{\hbox {SQNR}-1.76}{6.02}. \end{aligned}$$
(10)

In terms of the structure and function of the algorithmic ADC and according to (8), by increasing the number of cycles, the quantization error can be reduced to any desired level. Thus, the SQNR and ENOB of this converter can be theoretically increased to any arbitrary level. But, in an analog circuit, the initial conditions cannot be determined with infinite precision and the impact of noise is inevitable. By applying one initial condition to the circuit, and after too many cycles that the high significant bits are extracted, the low significant bits indicate the noise value, which affects the initial conditions, and thus, the output bits become quite random. So, it is sufficient to throw away the extracted bits of the first cycles to see an exactly unpredictable behavior in the circuit of Fig. 4.

One important property of the algorithmic ADC is converting analog to digital by the aid of a series redundant or nonredundant successive simple stages. This property makes it possible to map each stage input pdf to its output pdf and use this feature for easier analysis of the noise distribution. To this end, the fundamental theorem for function of a random variable [20] can be exploited and the propagation of the residual pdf in successive stages with full-bit and half-bit redundant architectures can be shown [8]. In the algorithmic ADC architecture (Fig. 4), each stage might be redundant or nonredundant. Firstly, the analysis of the residue pdf in ideal nonredundant stages is investigated. This is exactly the same as analysis of the Bernoulli shift chaotic map. It will be shown that after sufficient iterations the system will be fully equivalent to the Markov chain of Fig. 1. This fact indicates that the system can be used as a chaos-based RNG.

4 RNG Using Full-Bit Algorithmic ADC Structure

In 1-bit/stage algorithmic ADC, \(G_{i}=2\) and (6) can be expressed as

$$\begin{aligned} x_{i+1} =y_i =\left\{ \begin{array}{lll} \displaystyle {2\left( {x_i +\frac{1}{2}} \right) }&{} \quad {-1<x_i <0}&{} {\left( {D_i =0} \right) } \\ \displaystyle {2\left( {x_i -\frac{1}{2}} \right) }&{} \quad {0<x_i <1}&{} {\left( {D_i =1} \right) .} \end{array}\right. \end{aligned}$$
(11)

This characteristic is fully matched to the Bernoulli map with \(\mu =2\), which was described in (2) and depicted in Fig. 2a. Thus, the algorithmic ADC structure can be used to implement and iterate the Bernoulli shift map.

Fig. 5
figure 5

The different cycle residues in a 1-bit/cycle algorithmic converter

Full size image

The residue transfer characteristic of the different cycles in a 1-bit/cycle converter is shown in Fig. 5. Comparing Figs. 2 and 5 shows that two cycles of the converter is same as the four-way Bernoulli shift map and, in general, N cycles of the algorithmic ADC are exactly identical to M-way Bernoulli shift map where \(M=2^{N}\).

In [8], using the fundamental theorem for function of a random variable, it has been shown that for the input pdf \(f_x \left( x \right) \), the converter Nth cycle output pdf is obtained by

$$\begin{aligned} f_{y_N } =\left\{ \begin{array}{ll} \displaystyle {\frac{1}{M}\mathop \sum \limits _{m=0}^{M-1} {f_x \left( {\frac{y-(2m+1-M)}{M}} \right) } }&{} \quad {-1<y<+1} \\ \displaystyle 0&{} \quad {\hbox {otherwise},} \end{array}\right. \end{aligned}$$
(12)

where \(M=2^{N}\). It is clear that if the input pdf is uniform over [\(-1, 1\)], then the first cycle output pdf and, as a result, the output distributions of all the subsequent cycles are uniform. Therefore, N-way Bernoulli shift map does not change the pdf of an input with uniform density.

Since \(f_x \left( x \right) \) and \(f_{y_N } \left( y \right) \) are nonzero only over [\(-1, +1\)], they can be extended into periodic signals \(\tilde{f}_x \left( x \right) \) and \(\tilde{f}_{y_N } \left( y \right) \) with period 2 and Fourier series coefficients \(a_k \) and \(b_k \), respectively. The Fourier series representation of these periodic signals can be written as

$$\begin{aligned} \tilde{f}_x (x)=\sum _{k=-\infty }^{+\infty } {a_k \hbox {e}^{j\pi kx}} \Leftrightarrow a_k =\frac{1}{2}\int _{-1}^{+1} {f_x (x)\hbox {e}^{-j\pi kx}\hbox {d}x} \end{aligned}$$
(13)

and

$$\begin{aligned} \tilde{f}_{y_N } (y)=\sum _{k=-\infty }^{+\infty } {b_k \hbox {e}^{j\pi ky}} \Leftrightarrow b_k =\frac{1}{2}\int _{-1}^{+1} {f_{y_N } (y)\hbox {e}^{-j\pi ky}\hbox {d}y} . \end{aligned}$$
(14)

By substituting (12) in (14), \(b_k \) can be calculated as

$$\begin{aligned} b_k= & {} \frac{1}{2M}\int _{-1}^{+1} {\sum _{m=0}^{M-1} {f_x \left( {\frac{y-(2m+1-M)}{M}} \right) \hbox {e}^{-j\pi ky}\hbox {d}y} }\nonumber \\= & {} \frac{1}{2}\sum _{m=0}^{M-1} {\left( \int _{1-\frac{2(m+1)}{M}}^{1-\frac{2m}{M}} {f_x (x)} \hbox {e}^{-j\pi Mkx}\hbox {d}x\right) \hbox {e}^{-j\pi k(2m+1-M)}} . \end{aligned}$$
(15)

As regards \(\hbox {e}^{-j\pi k\left( {2m+1-M} \right) }=\left( {-1} \right) ^{k}\)

$$\begin{aligned} b_k= & {} \frac{(-1)^{k}}{2}\sum _{m=0}^{M-1} {\int _{1-\frac{2(m+1)}{M}}^{1-\frac{2m}{M}} {f_x (x)} \hbox {e}^{-j\pi Mkx}\hbox {d}x}\nonumber \\= & {} \frac{(-1)^{k}}{2}\int _{-1}^{+1} {f_x (x)} \hbox {e}^{-j\pi Mkx}\hbox {d}x. \end{aligned}$$
(16)

Comparing (13) and (16) reveals that

$$\begin{aligned} b_k =(-1)^{k}a_{Mk} . \end{aligned}$$
(17)

It can be observed that kth Fourier coefficient of \(\tilde{f}_{y_N } \left( y \right) \) is equal to (Mk)th harmonic of \(\tilde{f}_x \left( x \right) \). Hence, the last-stage residue pdf retains only the Fourier series coefficients which are integer multiples of M. So, after propagating through a sufficient number of stages, only the DC component

$$\begin{aligned} b_0 =a_0 =\frac{1}{2}\int _{-1}^{+1} {f_x (x)\hbox {d}x=\frac{1}{2}} \end{aligned}$$
(18)

is preserved and all harmonics are weeded out. It is clear that with increasing the total number of bits of the ADC (N), the last-stage residue pdf converges to the uniform distribution:

$$\begin{aligned} f_{y_N } (y)=\left\{ \begin{array}{ll} \displaystyle {\frac{1}{2}}&{} \quad {-1<y<+1} \\ \displaystyle 0&{} \quad {\hbox {otherwise}}. \\ \end{array}\right. \end{aligned}$$
(19)

In this way, the probability of the Nth stage output bit is \(\hbox {Pr}\left( {D_N =0} \right) =\hbox {Pr}\left( {D_N =1} \right) =1/2\), which indicates the uniform distribution of the output streams. After this, each stage of the generator acts like the Markov chain of Fig. 1, which can be directly used to implement ideal RNG. In order to implement this RNG, it is enough to consider a 1-bit/cycle algorithmic ADC without its digital correction logic according to Fig. 6, and let it run for infinite number of bits. This is equivalent to iterate the Bernoulli chaotic map \(x_{n+1} =M\left( {x_n } \right) \) that the output bit determines the RNG output and the circuit state.

Fig. 6
figure 6

RNG using 1-bit/cycle algorithmic ADC

Full size image

To illustrate the results, a simulation was performed for the 1-bit/cycle algorithmic ADC of Fig. 6. Initial condition was set to 0.25\(V_\mathrm{FS}\) and noise to 0.001\(V_\mathrm{FS}\). The converter residual pdfs after different cycles are shown in Fig. 7. It can be seen that after many cycles, residue pdf converges to uniformity. So, after passing less than 18 cycles, the system will be exactly equivalent to the Markov chain of Fig. 1. Two runs of the system starting at the same initial condition with a 0.1-mV noise floor, which has led to different trajectories, are shown in Fig. 8. It can be observed that by throwing less than 18 first samples of the output sequence, the system will have a quite random and unpredictable output bitstream. Running this system for a thousand sequences of length 10,000 at different times, the entropy of the output sequences is shown in Fig. 9. As it is expected, this RNG has one bit of entropy.

Fig. 7
figure 7

The 1-bit/cycle converter residue pdfs after different cycles. Initial condition was set to 0.25\(V_\mathrm{FS}\) and noise floor to 0.001\(V_\mathrm{FS}\)

Full size image
Fig. 8
figure 8

Twice running the RNG of Fig. 6. a Residue cycles. b Output streams

Full size image

The input–output characteristic of a k-bit stage algorithmic ADC is identical to \(k\times 1\)-bit stages (Fig. 6). This characteristic is equivalent to the \( 2^{k}\)-way Bernoulli shift map and can be used to implement this map. In [8, 16], it has been shown that the impact of each k-bit stage on input pdf is the same as to \(k\times 1\)-bit stages. Consequently, in an algorithmic converter with a k-bit stage, every cycle is exactly identical to one run of \(2^{k}\)-way Bernoulli shift map. Thus, by increasing the number of converter cycles, residue probability density function converges to uniform distribution of (19).

Small variations in Bernoulli map parameters can bring about stable equilibrium points in the system; thus, this map is not suitable for the electronic implementation [21]. In fact, the impact of noise and nonidealities of the electronic circuits on Bernoulli map is similar to the nonidealities impacts on the algorithmic full-bit stage characteristic, which there is not enough safety against them. So, redundancy is employed in such stages.

5 RNG Using Half-Bit Redundant Algorithmic ADC

Half-bit redundancy is widely used in the structure of multistage converters. Using redundancy in multistage ADCs, in addition to increasing the speed and decreasing the circuit power [15], can make converters less sensitive against the elements nonidealities impacts and environmental mismatches [2, 9].

Fig. 9
figure 9

The output sequence entropy of Fig. 6

Full size image

For an ideal 1.5-bit/cycle algorithmic ADC, the stage input–output characteristic is according to the following expression:

$$\begin{aligned} x_{i+1} =y_i =\left\{ \begin{array}{lll} \displaystyle 2\left( {x_i +\frac{1}{2}} \right) &{} \quad \displaystyle -1<x_i <-\frac{1}{4}&{} \quad \left( {d_{i_1 } d_{i_2 } =00} \right) \\ \displaystyle {2x_i }&{} \quad \displaystyle {-\frac{1}{4}<x_i <\frac{1}{4}}&{} \quad {\left( {d_{i_1 } d_{i_2 } =01} \right) } \\ \displaystyle {2\left( {x_i -\frac{1}{2}} \right) }&{} \quad \displaystyle {\frac{1}{4}<x_i <1}&{} \quad {\left( {d_{i_1 } d_{i_2 } =10} \right) .} \\ \end{array}\right. \end{aligned}$$
(20)

In [18], it has been shown that for the input pdf \(f_x \left( x \right) \), the converter Nth cycle output pdf is obtained by:

$$\begin{aligned} f_{y_N } =\left\{ \begin{array}{ll} \displaystyle {\frac{1}{2^{N}}f_x \left( {\frac{y-(2^{N}-1)}{2^{N}}} \right) }&{} \quad \displaystyle {-1<y<-\frac{1}{2}} \\ \displaystyle {\frac{1}{2^{N}}\sum _{m=-(2^{N}-1)}^{(2^{N}-1)} {f_x \left( {\frac{y-m}{2^{N}}} \right) } }&{} \quad \displaystyle {-\frac{1}{2}<y<\frac{1}{2}} \\ \displaystyle {\frac{1}{2^{N}}f_x \left( {\frac{y+(2^{N}-1)}{2^{N}}} \right) }&{} \quad \displaystyle {\frac{1}{2}<y<1.} \\ \end{array}\right. \end{aligned}$$
(21)

It is observed that with increasing the total number of bits (N), the output pdf is more concentrated in center half of the stage full-scale range. Since after a sufficient number of stages, \(f_{y_N } \left( y \right) \) is fully concentrated over \(\left[ {-1/2,1/2} \right] \), by repeating the middle half of the last-stage full-scale range it can be extended into a periodic signal \(\hat{f} _{y_N } \left( y \right) \) with period 1 and Fourier series coefficients \(c_k \)

$$\begin{aligned} \hat{{f}}_{y_N } (y)=\sum _{k=-\infty }^{+\infty } {c_k \hbox {e}^{j2\pi ky}} \Leftrightarrow c_k =\int _{-1/2}^{+1/2} {f_{y_N } (y)\hbox {e}^{-j2\pi ky}\hbox {d}y} . \end{aligned}$$
(22)

By substituting (21) in (22), \(c_k \) can be calculated as

$$\begin{aligned} c_k= & {} \frac{1}{M}\int _{-1/2}^{+1/2} {\sum _{m=-(M-1)}^{M-1} {f_x \left( {\frac{y-m}{M}} \right) \hbox {e}^{-j2\pi ky}\hbox {d}y} }\nonumber \\= & {} \sum _{m=-(M-1)}^{M-1} {\left( \int _{-\frac{m}{M}-\frac{1}{2M}}^{-\frac{m}{M}+\frac{1}{2M}} {f_x (x)} \hbox {e}^{-j2\pi Mkx}\hbox {d}x\right) \hbox {e}^{-j2\pi mk}} \end{aligned}$$
(23)

where \(M=2^{N}\). As regards \(\hbox {e}^{-j2\pi mk}=1\)

$$\begin{aligned} c_k =\int _{-1+\frac{1}{2M}}^{+1-\frac{1}{2M}} {f_x (x)} \hbox {e}^{-j2\pi Mkx}\hbox {d}x. \end{aligned}$$
(24)

Comparing (13) and (24) reveals that with increasing the total number of bits of the converter (N), \(c_k \) converges to \(2a_{2Mk} \). It means that the last-stage residue pdf retains only the Fourier series coefficients which are integer multiples of 2M. So, after propagating through a sufficient number of stages, only the DC component

$$\begin{aligned} c_0 =2a_0 =\int _{-1}^{+1} {f_x (x)\hbox {d}x=1} \end{aligned}$$
(25)

is preserved and all harmonics are weeded out. Therefore, after many number of cycles, residue pdf converges to the uniform distribution:

$$\begin{aligned} f_{y_N } =\left\{ \begin{array}{ll} 1&{} \quad \displaystyle {-\frac{1}{2}<y<\frac{1}{2}} \\ 0&{} \quad {\hbox {otherwise}} \end{array}.\right. \end{aligned}$$
(26)

In order to study whether the characteristic of (20) can be used for RNG, the interval partition \(X_0 =\left[ {-1,-1/2} \right) \), \(X_1 =\left[ {-1/2,-1/4} \right) \), \(X_2 =\left[ {-1/4,0} \right) \), \(X_3 =\left[ {0,1/4} \right) \), \(X_4 =\left[ {1/4,1/2} \right) \), \(X_5 =\left[ {1/2,1} \right] \) of [\(-1, 1\)] is considered and the state \(x_{i}\) is defined as \(x\in X_i \). Since the distribution of the x-samples, after passing sufficient cycles becomes uniform and limited over [\(-1/2, 1/2\)], the probability of the \(x_{0 }\) and \(x_{5}\) is 0 and other states have the probability 1/4. So, after sufficient cycles, the system will be fully equivalent to the chaotic map shown in Fig. 3. In [21], it has been shown that the evolution of this process can be expressed by the Markov chain of Fig. 10a. Since this chain has memory and its different states are not independent, it is not suitable for direct implementation of the RNG. To eliminate this drawback, the state aggregations of Fig. 10b can be exploited and an easier Markov chain with two macrostates \(S_{0}\) and \(S_{1}\) be obtained [7, 21]. It is evident that the new Markov chain is equivalent to the two-state Markov chain of Fig. 1. By considering the thermometric digital coding for the 1.5-bit stage:

$$\begin{aligned} x_{i+1} =y_i =M(x_i )=\left\{ \begin{array}{lll} \displaystyle {2\left( {x_i +\frac{1}{2}} \right) }&{} \quad \displaystyle {-1<x_i <-\frac{1}{4}}&{} \quad {\left( {d_{i_1 } d_{i_2 } =00} \right) } \\ {2x_i }&{} \quad \displaystyle {-\frac{1}{4}<x_i <\frac{1}{4}}&{} \quad {\left( {d_{i_1 } d_{i_2 } =01} \right) } \\ \displaystyle {2\left( {x_i -\frac{1}{2}} \right) }&{} \quad \displaystyle {\frac{1}{4}<x_i <1}&{} \quad {\left( {d_{i_1 } d_{i_2 } =11} \right) } \end{array} \right. \end{aligned}$$
(27)

it is sufficient to calculate XOR of \(d_{i _1} \) and \(d_{i _2} \) to determine whether the system is in \(S_{0 }\) or \(S_{1}\) [21].

Fig. 10
figure 10

a Markov chain of 1.5-bit stage, b related state aggregation

Full size image
Fig. 11
figure 11

RNG using 1.5-bit/cycle algorithmic ADC structure

Full size image

To clarify the obtained results, a simulation was performed for the algorithmic converter of Fig. 11 including an ideal 1.5-bit stage. The converter residue pdfs after different cycles are shown in Fig. 12. It can be observed that after many cycles, the residue probability density function over [\(-1/2, 1/2\)] converges to uniformity. So, after passing less than 15 cycles, the system will be exactly equivalent to the Markov chain of Fig. 1. Two runs of the system starting at the same initial condition with a 0.1-mV noise floor, which has led to different trajectories, are shown in Fig. 13. It can be seen that by throwing away less than 15 first samples of the output bitstream, a quite random and unpredictable sequence appears in the output. This system was run for a thousand sequences of length 10,000 at different times, which the output sequence entropies are shown in Fig. 14. As it is expected, this RNG has one bit of entropy.

Fig. 12
figure 12

The 1.5-bit/stage converter residue pdfs after different cycles. Initial condition was set to zero and noise floor to 0.001\(V_\mathrm{FS}\)

Full size image
Fig. 13
figure 13

Twice running RNG of Fig. 13. a Residue cycles. b Output streams

Full size image

6 Randomness Test Results

To evaluate the randomness of the proposed ADC-based RNG output bitstream using 1.5-bit stage of pipelined converter, the NIST test suit [24] is applied to the RNG output bit stream of Fig. 11. The statistical test suite v2.1.2, July 2014, which is the latest version available at the time of this study, is used for evaluation of the captured data. \(\alpha =0.01\) gives the set of p values as shown in Table 1. p value \(\ge \)0.01 means the test is passed and p value \(\ge \)0.01 is interpreted as the test is failed [24]. The test results show that output random bitstream successfully passes all NIST 800-22 statistical tests without any postprocessing.

Fig. 14
figure 14

The output sequence entropy of Fig. 13

Full size image
Table 1 NIST test results for the ideal 1.5 bit/cycle
Full size table

Since all ADCs are sensitive to device parameters variations, we take into account the inevitable circuit nonidealities such as comparator offset errors, capacitor mismatches and gain error that may go along with the ADC-based RNG of Fig. 11. Assuming these nonidealities, the RNG of Fig. 11 output bit stream was evaluated. A Monte Carlo simulation model was run for 1,000,000 length sequences. The NIST statistical test results are shown in Table 2. Test results show that algorithmic-based RNG successfully passes all NIST 800-22 statistical tests.

Table 2 NIST test results in the presence of nonidealities
Full size table

7 Conclusion

A new approach to analysis and design of chaos-based RNGs using ADC building blocks has been presented. Regarding the fact that multistage converters have theoretically infinite precision, the structure of algorithmic ADC was used to design random number generators. The input–output characteristics of the full-bit and half-bit redundant stages of algorithmic ADC were compared with different chaotic maps. It was found that 1-bit stage of this converter can be used to implement the Bernoulli map, and also the \(2^{k}\)-way Bernoulli shift map can be implemented using \(k\times 1\)-bit stages or one k-bit stage. It was revealed that in the half-bit redundant algorithmic ADC, after a sufficiently large number of cycles, residue pdf becomes concentrated in the center half of the stage full-scale range. In this way, the 1.5-bit stage characteristic will be fully equivalent to the common chaotic map that is employed to generate random number sequences. Therefore, this stage is suitable to implement chaotic RNG. With regard to the uniformly distributed and statistically independent residue signals of this converter at different times, it was found that the structure of multistage algorithmic converter is suitable to implement multi-bit chaos-based RNGs and is capable of being embedded to high-speed analog and digital circuits.