# A New, Fast Pseudo-Random Pattern Generator for Advanced Logic Built-In Self-Test Structures
## 5 Pseudo-Random Pattern Generator DT-LFSR-TPG for LBIST Circuits with the STUMPS Architecture  
Let us denote \(\Psi_{min}\) as the minimum guaranteed phase shift between binary sequences produced at outputs of any TPG applicable for the STUMPS architecture. Results from Table 1 demonstrate that a single DT-LFSR register used as a pseudo-random TPG enables a pretty high level of phase shift that is much more than the one achieved by means of the methods disclosed in [13; 34; 35; 39]. The number of scan paths implemented in LBIST structures with the STUMPS architecture and incorporated into modern integrated circuits is as high as several thousand [25]. The implementation of a PRPG as such a long and single DT-LFSR register is a sophisticated engineering challenge. There are difficulties associated with development for the register topology as well as a network of interconnections between its cells and a network of interconnections between the register outputs and inputs of scan paths so as to achieve the desired operational frequency of such a TPG. The next problem is associated with seeking an appropriate \(\mathrm{D}^{k}\mathrm{T}^{t}\) structure associated with a primitive polynomial with the length of several thousand bits. The verification of whether the characteristic polynomial of such a register is really a primitive one can be carried out by means of the efficient algorithm \begin{table}
\begin{tabular}{c c c c c c} \hline
**No.** & \(t\) & \(n\) & \(\Omega\) & \(\Phi_{\mathbb{T}}\) & \(\Phi_{\mathbb{T}min}\) \\ \hline
17 & 65 & 81 & \(2.42\times 10^{24}\) & \(2.08\times 10^{24}\) & \(3.72\times 10^{22}\) \\
18 & 70 & 79 & \(6.04\times 10^{23}\) & \(3.20\times 10^{23}\) & \(8.64\times 10^{21}\) \\
19 & 71 & 84 & \(1.93\times 10^{25}\) & \(5.18\times 10^{24}\) & \(2.72\times 10^{23}\) \\
20 & 74 & 87 & \(1.55\times 10^{26}\) & \(1.88\times 10^{25}\) & \(2.09\times 10^{24}\) \\
21 & 78 & 95 & \(3.96\times 10^{28}\) & \(2.54\times 10^{27}\) & \(5.08\times 10^{26}\) \\
22 & 84 & 95 & \(3.96\times 10^{28}\) & \(1.93\times 10^{28}\) & \(4.72\times 10^{26}\) \\
23 & 85 & 97 & \(1.58\times 10^{29}\) & \(2.24\times 10^{28}\) & \(1.86\times 10^{27}\) \\
24 & 91 & 97 & \(1.58\times 10^{29}\) & \(1.04\times 10^{28}\) & \(1.74\times 10^{27}\) \\ \hline \end{tabular}
\end{table} 
Table 1: Cont. proposed in [39; 62]. However, such a solution needs prime factorization of a very large number expressed as \(2^{n}-1\), where \(n\) stands for the length of the DT-LFSR register. The aforementioned problems can be resolved by means of the original method and the innovative method outlined in this paper dedicated to the implementation of PRPG structures as a set of DT-LFSR registers operated in the parallel mode. The STUMPS architecture with a TPG designed according to the foregoing concept is depicted in Figure 12. All DT-LFSR registers of such a test pattern generator are of identical design and are synchronized by means of a common clock signal and their operation is controlled simultaneously by the same control signals. Outputs of T-type flip-flops incorporated into each single register deliver sequences of test vectors to a separate group of scan paths, whilst outputs of D-type flip-flops remain unused, which is indicated in the sketch below. A Test Pattern Generator with such a structure shall be further referred to as DT-LFSR-TPG. According to [34; 35], the minimum phase shift \(\Theta_{min}\) between binary sequences produced at any two outputs of a future TPG is imposed a priori before the engineering of a pseudo-random TPG for the STUMPS architecture is commenced. The sufficient level of that phase shift is deemed as a guarantee that a sequence of test vectors supplied to inputs of the CUT shall be of a pseudo-random nature. Any properly designed TPG must meet the condition that \(\Psi_{min}\geq\Theta_{min}\), i.e., the minimum phase shift between binary sequences appearing at outputs of such a TPG must be not less than the required limit imposed by the circuit designer.