# On Improving Reliability of SRAM-Based Physically Unclonable Functions
## 4 Analysis of the Proposed Counter Based Design
### Operation of the Proposed Voter as Random Walk  
Let \((U_{1},U_{2},\dots)\) be a sequence of independent random variables from the set \(\{1,-1\}\). Let the probability of value \(1\) from a trial be \(p\), where \(p\in[0,1]\). Then, the probability of value \(-1\) is \(1-p\). If \(X_{N}\) represents the sum of such sequence after \(N\)-trials, then  
\[X_{N}=\sum_{i=1}^{N}U_{i}\ ;\ \ \text{where}\ N\ \text{is the number of trials.} \tag{2}\]  
Figure 4: Modified Cell schematic and timing diagram. (**a**) modified SRAM cell for multiple evaluations; and (**b**) timing diagrams for bit evaluation.  
Figure 5: Error rate results from simulation.  
The path traced by \(X_{N}\) is called a simple random walk [28]. This is an elementary one-dimensional random walk on an integer number line. The properties of random walk and associated problems are well studied and are related to the Markov process.  
The UP/DOWN counter based scheme proposed above can be modeled and analyzed using random walk based models. For the purpose of analysis, without any loss in generality, let us assume that, in the absence of any noise, the PUF cell settles at _logic-1_ due to process variation. In the presence of noise, there is a possibility that the cell will settle at _logic-0_, which is opposite to the inherent process variation of the cell.  
In Table 1, we describe the notations used in our analysis of the UP/DOWN counter. In this analysis, we assume the noise experienced by the cell has zero mean; hence, for a statistical bias towards _logic-1_, \(p\) must be \(>\)0.5. If the cell has a strong bias towards _logic-1_, then \(p\gg 0.5\); otherwise, for a weak bias, \(p\) has a value slightly above 0.5.  
As mentioned earlier, the \(n\)-bit UP/DOWN counter is initialized at \(k=(2^{n}-2)/2\) and multiple trials are conducted. The state transition diagram to better illustrate this process is shown in Figure 6. If the PUF cell creates _logic-1_, it is symbolized by \(U_{i}=+1\) else, \(U_{i}=-1\) in Label (2). However, due to the absorbing saturation (decision) barrier at the end as shown in Figure 6, Label (2) cannot be used directly to model UP/DOWN counter. Nevertheless the UP/DOWN counter is related to the well-studied _Gambler's ruin_ problem [28] and, hence, the metrics of interest can be determined. For the proposed voter scheme, we are concerned with three probabilities: (i) probability of reaching the correct state, \(P_{s}\) (probability of success); (ii) probability for reaching the wrong state, \(P_{e}\) (probability of error); and (iii) probability of unresolved output \(1-(P_{e}+P_{s})\). If we consider our working example, as the cell is biased towards _logic-1_, the probability of reaching the end state (\(2^{n}-2\)) is the probability of success \(P_{s}\). Similarly, the probability of the trials leading to the end state 0 is the probability of error \(P_{e}\). The last probability case may arise when the counter has not reached a saturating state after a given number of trials. As the circuit is designed to resolve to a decision, we are concerned with \(P_{e}\) and \(P_{s}\) with a limited number of trials.  
\begin{table}
\begin{tabular}{c l} \hline \hline
**Symbols** & **Definitions** \\ \hline \(p\) & Probability of _logic-1_ from a PUF cell \\ \hline \(q=1-p\) & Probability of _logic-0_ from a PUF cell \\ \hline \(n\) & Length of the UP/DOWN counter \\ \hline \(T\) & Total number of trials \\ \hline \(k=\frac{(2^{n}-2)}{2}\) & Initialization state—it is also the number of steps from initialization to end states \\ \hline \(P_{s}\) & Probability of _logic-1_ from UP/DOWN counter (probability of success) \\ \hline \(P_{e}\) & Probability of _logic-0_ from UP/DOWN counter (probability of error) \\ \hline \hline \end{tabular}
\end{table}
Table 1: Definition of _symbols_.  
Figure 6: Markov Chain model for the voter scheme.