# True Random Number Generator Based on Fibonacci-Galois Ring Oscillators for FPGA
## 2 All-Digital True Random Number Generators
### Digital TRNGs
#### 2.2.3 Fibonacci and Galois Ring Oscillators  
Before presenting Fibonacci and Galois Ring Oscillators, it is worthwhile to introduce concepts about Linear Feedback Shift Registers, whose structures inspired these True-Random Bit Generators (TRBGs). A Linear Feedback Shift Register (LPSR) is a shift register with a feedback network, usually a XOR tree, which feeds the input with a linear function of the current internal state. The degree m of the LFSR equals the length of shift register itself. Two different architectures of LFSR, Fibonacci and Galois, are pictured in Figures 3 and 4. In the former, the outputs of the D flip-flop (DFF), which are closed in retro-action by  
Figure 1: Transition-Effect Ring Oscillator. Figure 2: Metastable Ring Oscillator. the switches, are XORed together and connected to the serial input of the shift register. The latter presents a different concept: if \(f_{r-i}\) is 0 (switch opened), DFFi feeds DFFi+1 as in a normal shift register operation; on the contrary, if \(f_{r-i}\) is 1 (switch closed), the output of DFFi is XORed with the serial output of the shift register to create the input for DFFi+1. In both cases, the feedback function is controlled by the switches \(f_{i}\), that are conventionally closed if \(f_{i}=1\) or opened if \(f_{i}=0\). These values can be seen as coefficients of a polynomial: the characteristic polynomial of the LFSR. \[P(x)=1+f_{1}x+f_{2}x^{2}+\dot{+}f_{m}x^{m} \tag{4}\]  
Since the new state depends only on the previous one and the number of states is finite (they are, in fact, bounded by the length of the Shift Register), every LFSR outputs a periodic pattern. It is possible to generate pseudo-random sequences with an LFSR that has a much bigger period than the length of the output sequence. Nevertheless, no entropy is ever generated inside an all-deterministic circuit like this one and it is simple to prove that LFSRs show neither prediction nor backtracking resistance. A change in these two architectures was introduced in [24], where two new TRNG architectures were presented: Fibonacci Ring Oscillators (FiROs) and Galois Ring Oscillators (GaROs). FiRO is derived from its homonym LFSR architecture, substituting all D flip-flops with inverters, as shown in Figure 5. Since all synchronous elements are removed, the circuit is fully asynchronous and evolves in a stochastic fashion. Randomness is introduced by the dependency of the delay of the inverter from temperature and supply voltage: as these parameters vary, both for noise and environmental changes, the ring evolves with different output patterns, resulting in a chaotic and unpredictable signal. Additional randomness can be acquired during the sampling phase: the violation of setup and hold times can lead to metastability of the sampling unit. FiRO is made up by r inverter elements cascaded so that everyone (except the last one) creates the input for the next inverter. Feedback  
Figure 4: Galois Linear Feedback Shift Register. Figure 3: Fibonacci Linear Feedback Shift Registers. function is defined, as in LFSR, by the coefficients fi, which can be represented with the characteristic polynomial:  
\[P(x)=\sum_{i=0}^{r}f_{i}x^{i}\ \ \ \ \ with\ \ \ f_{0}=f_{r}=1 \tag{5}\]  
To ensure enough randomness, it is important to avoid fixed points, so that oscillation never stops. No fixed-points are present if these two conditions are satisfied1:  
\[ \begin{cases}P(x)=(x+1)h(x)\\ h(1)=1\end{cases}  \tag{6}\]  
GaRO is derived from Galois LFSR structure, again substituting all D flip-flops with inverters, as shown in Figure 6. The same considerations made with FiRO on the stochastic evolution of this circuit hold. GaROs are made up by \(r\) inverters cascaded so that each inverter output is the input of a XOR gate which forms the input of the next inverter. The feedback function can be represented with the characteristic polynomial:  
\[P(x)=\sum_{i=0}^{r}f_{i}x^{i}\ \ \ \ \ with\ \ \ f_{0}=f_{r}=1 \tag{7}\]  
The conditions for GaROs not to have fixed points are the following:  
\[