Genetic algorithm as self-test path and circular self-test path design method

Digital systems should provide services according to the specifications reliably. Impairments of dependability are associated with a large class of faults, errors and failures. These impairments may be caused by design, produce or rarely operational imperfections and improper use. There are lots of possible circuit failures: single stuck at 0 or 1 faults, delay and synchronization faults, bridging and open faults, in Metal Oxide Semiconductor technique (MOS) these faults consist in transistor stuck on or stuck off in a logical gates [1]. Some faults cannot be logically represented. Other class of faults can be connected with operational timing frequency and they are related to change impedance parameters, but in that case the built-in testing is one of the most resistant technique because of common silicon space. Faults that are stimulated may manifest itself as an error. For do that the fault have to be stimulated and propagated to one of internal (to memory module of sequential circuit) or external (primary) circuit output. The error, that is accessible from circuit output, is an information on detected fault and indicates that functional specification of circuit is violated. There is therefore a need for hardware testing.

For Very Large Scale Integration circuits (VLSI), the Built-In Self-Testing (BIST) concept is well used. Embedding the whole or major part of the tester into the circuit is considered as BIST. Production standard involves the use of Linear Feedback Shift Registers (LSFR) that are used as a Test Pattern Generators (TPG) and Test Response Compactors (TRC) in a signature analysis [2]. These LFSR registers can generate pseudo-random test vectors that may cover many faults. For the evaluation of the effectiveness of coating defects by sequence of test vectors, the Fault Coverage (FC) is applied. Multi-Input Signature Registers (MISR) and Single-Input Signature Registers (SISR) are mainly used as TRC registers [3]. These Compactors perform data compression generally lossy, but are known lossless Zero-Aliasing ones without faults masking phenomena.

There is also a non-linear technique with Self-Test Path (STP) or Circular STP (CSTP). Some modifications of these self-testing techniques are also known, e.g., Circular CSTP (C2STP) [4]. Contrary to linear technique, the Circuit Under Test (CUT) in non-linear technique is a feedback of STP or CSTP, thus posing a problem with parameter selection for these structures. These structures can be implemented in Field Programmable Gate Arrays (FPGA) [5], Application Specific Integrated Circuit (ASIC), System-on-Chip (SOC), which consist of many virtual Intellectual Property modules (IP Core). For SOC, the STP structures can also link IP modules [6].

Nevertheless, simulations presented in this paper show that it is possible to design such BIST, modeled as NLFSR, that achieve higher effectiveness than those of solutions reported in the literature and often are minimized. The minimization is related to the concept of external self-testing, where internal Memory Module (MM) of the circuit is disconnected during test, thus no additional conditions are imposed on its operation. It should be noted that both in linear and non-linear testing techniques, the circuit MM is typically included into self-testing structure registers as results from ability to improve testability and application of Design for Testability (DFT). An important observations was made in [7].

The properties of evolutionary algorithms make possible to solve a non-linear structures designing problem. The modeling of NLFSRs is important for the sake of correct representation of it. In this paper, many evolutionary models of non-linear register for evolutionary computer simulations are shown. In addition, many different design methods, often with the use of Genetic Algorithms (GATTO, GATTO\(+\), GATTO*, SELFISH GENE GA [8‐10]) and deterministic systems based, among other things, on Automatic Test Pattern Generation (ATPG) [11], Cellular Automata (CA) [12], Finite State Machines (FSM), and Binary Decision Diagrams (BDD) are used to built-in testing design. There are some solutions that can create a sequence of test vectors. In this paper, we are searching for not only a selection of sequences, but for structures that can generate these sequences with good FC parameter.

The paper is organized as follows. In Sect. 2, basic information on NLFSR as ATS, essentially STP and evolutionary are presented. Section 3 includes some description of the Genetic Algorithm and its using to create ATS structures. Next, in Sect. 4, some results of evolutionary searching for STP/CSTP structures are presented, and finally Sect. 5 concludes the paper.

The paper is an extended version of a previously published article titled “Genetic Algorithm for Self-Test Path and Circular Self-Test Path Design” that was presented at ACIIDS 2017 conference [7].

Self-Test Path, Circular Self-Test Path and Condensed Circular Self-Test Path (C2STP) and in general NLFSRs can be seen as realization of Autonomous Test Structure (ATS).

In Fig. 1, a schema of autonomous structure STP that works accordingly to (1) is presented.

In Fig. 1, \(V_{i}\) is an element of STP and it is mainly D-type flip-flop, t is a discrete time (clock time) and \(p=n+m-1\) is a length of STP (number of flip-flops).where \(\oplus \) denotes an addition operator over GF(2) andandis the Connection Matrix for D-type flip-flops which are used to create STP register. If some \(i\mathrm{th}\) flip-flop is a T-type one then \([T_{i,i}]=1\). The last element in the first row of the matrix \([T_{0,p-1}]=1\) for CSTP structure and in the rest of the paper ATS based on CSTP. The schema of CSTP is shown in Fig. 2.

Genetic algorithm (GA) has some useful features, such as the ability to deliver multiple point solutions, and so the lack of concentration of solutions around a certain subclass of STP/CSTP structure and configuration. The algorithm mimics natural evolutionary processes, and therefore there exists the possibility of self-control calculations in such a way that a solution better adapted to a greater extent affects the entire population of solutions (selective pressure).

The GA directs the search in the space of feasible solutions by environmental evaluation of the fitness function of each solution (individual). The course of the algorithm is presented in Fig. 10.

The process of STP/CSTP design creation is a complicated one, especially due to the difficulty of non-linear circuit feedback and BIST simulation time. Every individual has to be simulated and this process is a great time-consuming task. In [7], the stochastic model of pseudo-random testing, which significantly reduces this problem, was described. Using the stochastic model, the simulation of each solution is well reduced due to the conversion of exploration FC in search of a suitable length of sequence. Fitness function can be described as some optimization problem in which one is looking for such \(x^*\in V(p)\) that maximizes the following formula (27):where V(p) is a multidimensional vector of parameters. The fitness function is defined as follows (28):where \(x_{0}\) is a length of sequence, \(x_{1}\) is a number of ExORs used to create additional linear feedback, \(x_{2}\) is a number of T-type flip-flops used to design NLFSR and \(\sum _{i=0}^{n=2}w_{i}=1\).

The linear code of solution (chromosome) is a binary array of bit values that stores

In the initial stage of the genetic algorithm, essentially random \(P_{0}\) population base is created. The population is further assessed by the environment (fitness function). Based on the adaptation of individuals, their reproduction to temporary populations \(T_{i}\) is made. Then from \(T_{i}\) using genetic operators crossover and mutation with some probabilities, the descendant population (Offspring) \(O_{i}\) is created. Next evaluation of the newly established offspring population \(P_{i+1}\) takes place iteratively until the stopping criteria are fulfilled. This evolutionary process is common to all Genetic Algorithms. The ability to generate invalid connection matrices, i.e., not meeting the above conditions, was excluded by a particular type of chromosome encoding. With this approach, it is not necessary to use repair algorithms or penalty function for a faulty solution.

The criterion for stopping the algorithm is to reach an acceptable FC value or exceed a predetermined number of generations.

The experiments presented here were performed for a subset of ISCAS’89 sequential circuits presented in Table 1.

In Fig. 11b, one can notice a specific repeatability of FC 0.6–0.8 for STP/CSTP resulting from the presence of type 1 Long connection matrix (e.g., Seq. Id. 300–600, 1800–2100 and so on). This type of matrix can actually reduce the length of the ATS structure and thereby reduce the length of the test sequence (Fig. 11a). For other connection matrices, FC reaches the value of 1. However, the described phenomenon occurs for the s349, only.

Figure 12a shows that for the s382 within certain ATS structures, the focused values of FC of small discrepancies are obtained. Figure 12b for the same circuit can be noted that only a few configurations of ATS structure can be able to obtain the FC at around 0.9 (Seq. Id 2100–2300 for STP, 9700–9800 and 12800–12900 for CSTP). In these structures, matrices such as Input Matrix Free and Output Matrix Free are used. An interesting area is that identified by Id Seq. 10500 and 11700, there is ATS structure realized by a simple Shift Register (SR) generating short sequences, which, however, allow for the acquisition of a relatively high FC value. In this area, there is an additional CSTP feedback. The charts shown in Fig. 13 for the s444 are in some ways similar to the graph in Fig. 12 for the s382. Both test circuits are traffic light controllers and have the BCD counters (timers).

In Fig. 14 for the s820, it can be seen that almost independently of the ATS structure the FC is recovered in the range of 0.3–0.45. The best achieved result was FC \(=0.598\). The s820 circuit has only a few flip-flops but some portion of the state space which should be taken into account is fault dependent.

Statistical analysis of the results showed a correlation from low (below than 0.1) to strong (greater than 0.9), between the length of the sequences and FC for the specified ATS structures. For example, for s208.1, the correlation ranges between 0.19 and 0.914 (Table 2). Figure 15 shows the FC dependence on the length of test sequence for many ATS (more precisely STP) configurations. The correlation coefficient value is 0.7. Figure 16 can be seen that the vast majority of the structure ATS (sequence ID) generates test sequences of length 1000, except for a singularity identified by the 10500–11500th corresponds to the CSTP structure based on the Shift Register without the additional linear feedback. Interestingly, in

Fig. 16, there is a high correlation between the length of the generated sequence and the value of FC. Most ATS structures for this circuit cover from 0.7 to nearly 0.9 faults beyond the aforementioned singularity. The results of the study for s1238 in Fig. 17, with slightly less FC from 0.7 to 0.8, are quite similar. In Fig. 18, one can see that the FC depends on the structure of the ATS oscillates from about 0.35 to 0.5, with a maximum value of 0.530. There is also a singularity in the range of 10500–12000. Compared to the plots Figs. 16 and 18 there are more different sequence lengths, and the FC value is in the lower range. As with the circuit in Fig. 17 and smaller in Figs. 11, 12 and  13, there are ATS configurations that generate short cycles. In Fig. 19, almost all ATS structures have generated sequences longer than 1000 test vectors. Restricting the sequence length to 1000 vectors is too restrictive for medium-sized circuits (Table 1). Despite long sequences, FC values oscillate between 0.35 and 0.7 depending on the ATS structure. There is a very high dependency between ATS, exactly STP and FC (island areas, clusters in plots). Information about excessive limitation of 1000 sequence length vectors results from the developed stochastic faults model and the need to reduce the computer time-consuming circuit simulation, for example, for s1196 shown in Fig. 20. From Fig. 20, one needs to generate a long test sequence, for example, to get FC \(=0.95\) (Fig. 20d) probability of close 1 would generate a sequence of 10,000 vectors. This is obviously a necessary condition, but not sufficient due to the variety of ATS structures researched. Figures 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34 and 35 show in detail the effect of incremental including internal memory elements of a sequential circuit into STP structure on diagnostic performance of s298 circuit testing. With the increase in the number of included memory elements, STP increases the sequence length, but also increases FC. This incorporation of memory elements into STP allows one to convert a sequential circuit into a combinational circuit whose testing process is simplified. In a combinational circuit, the output depends entirely on the input and in the sequential circuit also on the state of the internal memory. The ability to disconnect system memory (MM) results from the use of special, e.g., BILBO multifunctional registers. Disconnecting the internal memory of the sequential system during testing is a standard and widely used approach.

In Table 3, the FC values obtained for a subset of ISCAS’89 are presented. In test simulation procedure, the block of sequential circuit memory is not disconnected. In other case, the greatest value of FC \(=0.997\) was calculated for the structure of the CSTP including all s298 circuit flip-flops (MM) (Fig. 35).

As mentioned earlier, to increase the circuit testability, all or some of circuit (MM) elements should be included into self-testing register (STP or CSTP) (Fig. 36). Disconnecting the (MM) elements, converts the sequential circuit (CUT) to a combinational one, that is easier to test. The effect of disconnecting memory elements from the sequential circuit s298 is shown in Figs. 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34 and 35.

Genetic algorithm was able to find appropriate solutions, i.e., the structures of ATS, which were able to generate adequate quality test sequences and the high value of FC was possible to obtain. The conducted experiments show that it is possible to identify ATS structures with a high correlation coefficient between the sequence length and FC. Finding a suitable ATS structure evolutionary with those properties requires the circuit test simulation without faults, and therefore significantly affects the efficiency of the search (exploration) of the solution space. Next, the diagnostic efficacy of ATS structure has to be finally confirmed by simulation circuits with faults, which is much more time complex task. The genetic algorithm used as the method of designing ATS structures was controlled by standard values of crossover and mutation operators. Crossover and mutation processes are specific for encoding connection matrices and exclude unacceptable forms. It should be noted that memory block of circuit operates in accordance with the specification and has not been disconnected, and so the same process of testing simulation was significantly complicated. As demonstrated in the research, the use of even a small subset of the internal memory of the sequential circuit as part of the STP/CSTP register allows for significant increase of fault coverage value. The results of sequential circuits testing even without disconnecting internal memory are comparable to other methods known from the literature. Including circuit memory elements into the STP/CSTP register radically increases the sequence length and FC, but imposes specific system solutions on the sequential circuit memory block, e.g., BILBO register. Research analysis has shown that there is a correlation between FC and the length of the test sequence. The value of the correlation coefficient reaches more than 0.9 for certain ATS structures, rarely reaching small values less than 2. The high correlation within specific ATS structures makes 

it possible to use deterministic local optimization algorithms or evolutionary exploitation process to select the appropriate connection matrices, additional linear feedback and type of flip-flops used to create STP/CSTP register.

In the future, research will be conducted on the classical testing structures such as independent test pattern generators (LFSRs) and test response compactors (MISRs, SISRs) or cellular automata. It is also very important to enrich used faults model by other types of faults such as open line, bridging and cross-talk faults. Other research related to the selection of other evolutionary algorithms for ATS design will also be made.