# A New, Fast Pseudo-Random Pattern Generator for Advanced Logic Built-In Self-Test Structures
## 2 Motivation
#### Example 1
For such an illustration of test vectors, each \"0\" appearing at any output of the register is represented by a white dot, whilst black dots stand for high (\"1\") values of outputs. Figure 2(a) shows an example of a 20-bit type I LFSR associated with the primitive polynomial \(p(x)=1+x^{3}+x^{4}+x^{19}+x^{20}\), and a fragment of the STD graph for that register is depicted in Figure 2(b). The Q\({}_{0}\) output of the register corresponds to dots at the top of the graph, while the Q\({}_{19}\) output is associated with dots in the graph bottom. The time axis for the register operation extends horizontally. The register starts its operation from the state of <1000... 00>. The STD graph from Figure 2(b) features with pretty regular shape since it has the form of oblique white and black stripes. One can easily spot that sequences of bits appearing at subsequent outputs of the LFSR register are gradually shifted by only one bit. Likewise, subsequent vectors appearing at outputs of that register are also gradually shifted by only one bit (except for the bit number 0). These properties indicate a strong correlation both between binary sequences and between subsequent vectors appearing at outputs of the LFSR register [10; 12; 35]. As a consequence, sequences of test vectors produced by such a register must not be considered as fully pseudo-random ones, both for the test-per-scan and test-per-clock testing strategies [10; 40]. Similar observations are reported in [38] with respect to poor randomness of test vectors sequences delivered at outputs of a conventional LFSR. The strong correlation between sequences of test bits appearing at outputs of the type I LFSR is also confirmed by the graph plotted in Figure 4 for the correlation coefficient. The correlation coefficient \(C_{i,j}(\tau)\) for binary sequences is calculated from the formula [33]:  
\[C_{i,j}(\tau)=\frac{1}{T}\times\sum_{t=0}^{T-1}q_{i}(t)\times q_{j}(t+\tau), \tag{1}\]  
where \(q_{i}(t)\) and \(q_{j}(t)\) stand for the values of the corresponding \(i\)th and \(j\)th outputs of the register at the moment of \(t\), while \(i=0,1,[? ]n-1\), and \(T\) is the length of binary sequences used to calculate the correlation coefficient. The parameters of \(\tau\) represent the time offset (phase shift) between binary sequences at the outputs \(q_{i}\) and \(q_{j}\), where test sequences are observed and the difference between indexes and \(j-i\) is considered as the space distance between these two sequences. When \(j=i\), the function \(C_{i,j}(\tau)\) calculates the autocorrelation coefficient for the binary stream appearing at the \(q_{i}\) output. For all other cases, i.e., when \(i\
eq j\), the function \(C_{i,j}(\tau)\) calculates the coefficient of cross correlation between binary sequences produced at the outputs \(q_{i}\) and \(q_{j}\). That coefficient can be calculated either for the entire period of the register operation, in which \(T=2^{n}-1\) in Equation (1), or for the actual length of the test sequence. It must be also kept in mind that for computation of the correlation coefficient by means of the equation (1) all parameters \(q_{i}(t)=0\) shall be substituted with the values of \(\"-1\"\)[33]. In the graph depicted in Figure 4, the horizontal axes show the time offset \(\tau\) expressed in the number of clock cycles (the axis designated as \"time offset \(\tau\)\") as well as space distance, understood as the number of the register output (the axis designated as \"output no\"). In turn, the vertical axis (\"correlation coefficient\") is graduated with the values of correlation coefficients. The coefficient is calculated with respect to the binary sequence appearing at the \(q_{0}\) output with no time offset. The graph presented in Figure 4 demonstrates that in the case of a conventional type I LFSR register, the coefficient of correlation between the binary sequence appearing at the \(q_{i}\) output and the corresponding sequence at the \(q_{0}\) output but delayed by \(i\) clock cycles adopts the maximum value, i.e., equals 1.