Pattern Generator Using Genetic Algorithm Biology Essay

Published: Last Edited:

This essay has been submitted by a student. This is not an example of the work written by our professional essay writers.

This paper presents a genetic algorithm based test vector compaction technique. Genetic algorithm has been used for optimizing the test vectors generated by a test pattern generator. The digital circuits in VLSI system are increasing in complexity. In order to ensure their reliability these circuits are tested using test vectors generated by Automatic Test Pattern Generator. The generation of test vectors with high fault coverage is a expensive process for large circuits. An efficient ATPG algorithm reduces the test pattern generation time and cost, beside the high fault coverage. The aim of the algorithm is to reduce the number of test patterns and hence decreasing the test application time and to reduce the test power. Experimental results showed that the number of test patterns applied to test any combinational circuit is reduced by approximately 50% by using the proposed algorithm. Hence the test application time is reduced without sacrificing the fault coverage.

Keywords- Automatic Test Pattern Generation (ATPG), Genetic Algorithm (GA), very large scale integrated (VLSI), system-on-chip (SOC), Linear Feedback Shift Register (LFSR), circuit under test (CUT), Automatic Test Equipment (ATE).


With the advance of semiconductor manufacturing technology, the requirements of digital VLSI circuits which are composed of millions of gates, have led to many challenges during testing. Moreover, design complexity and the gigahertz range of operating frequencies make the testing of SOC designs a most demanding challenge. This is because the large chips require a huge amount of test data and dissipate a large amount of power during testing, which greatly increases the system cost. There are many parameters that should be improved in order to reduce the test cost. That includes the test power, test length (test application time), test fault coverage, and test hardware area overhead. This work mainly deals with reducing the number of test patterns (test compaction) used to test VLSI circuits, which reduces the test application time and hence the test power.

Test compaction is the process of reducing the length of a test sequence (or the total length of a set of test sequences) for the circuit. Test compaction is important for reducing the test application time and the volume of test data. Test compaction procedures can be classified into two categories. Dynamic compaction [6] procedure is incorporate into the test generation procedure heuristics which aimed at reducing the test length. Thus, they attempt to avoid the generation of extra test vectors. Static compaction [6] procedures perform test compaction as a post processing step, independent of the test generation process. Static compaction has two advantages, 1. Unlike dynamic compaction, static compaction does not require any modifications to the test generation procedure. 2. Since dynamic compaction is based on heuristics and is not guaranteed to achieve the minimum test length, static compaction is useful, even after dynamic compaction is applied during test generation, to further reduce the length of the test sequence. In this work static test compaction technique is used. Genetic algorithm is used for test vector compaction technique.

testing of vlsi circuits

Testing of VLSI circuits is performed using Automatic Test Equipment. ATE applies input stimulus to the circuit under test and measure the output response. If the ATE observes a response different from the expected response, the CUT fails that test. Three components of the VLSI testing are input patterns, CUT, and stored response as shown in Fig. 1. In VLSI circuits, the stimuli are called test patterns or test vectors. Testing typically consists of

Set of test stimuli

Circuit Under Test (CUT)

Analysing output responses

If incorrect (fail), CUT assumed to be faulty

If correct (pass), CUT assumed to be fault-free

ATPG is a method used to find an input (or test vectors) sequence that, when applied to a digital circuit, enables tester to distinguish between the correct behavior and the faulty circuit behavior caused by defects. The efficiency of this method is measured by using fault coverage, computational time and the length of test set.

Kanad Basu and Prabhat Mishra [4] had developed a bitmask selection technique for test data compression in order to create maximum matching patterns; also they developed a dictionary selection method which takes into account the bitmask based compression. Subsets of primary input vectors of limited sizes were used [5] during testing for target faults. Chia-Yi Lin, Hsiu-Chuan Lin, and Hung-Ming Chen [2] proposed a technique for sequential circuit testing based on the selective test pattern compression. This method can reduce considerable shift-in power by skipping the switching signal passing through long scan chains. Irith Pomeranz and Sudhakar M. Reddy [1] had proposed static Test Data Volume Reduction algorithm in which the compacted test vectors were obtained fault simulating each fault and removing the redundant test vectors which is a complex process for large circuits.

Input Test Stimuli

Circuit under test

Output Response Analysis


Pass/ Fail



Fig 1 VLSI circuit testing

Genetic algorithm proposed by Goldberg [13] is specially suited to solve large scale combination optimization problem. GA has been successfully applied in different areas of VLSI design, especially in testing such as test pattern generation [5].

Genetic Approach for Test Pattern Generation

Test generation using deterministic & fault oriented algorithm is highly complex and time consuming. New approaches are needed to reduce execution time. GA was used for fault simulation based test generation with conditional execution of test vector under 2 phase scheme in [7] which is used for sequential circuits. Several approaches to test generation have been proposed. In [8], [9] the fitness evaluation and population scoring is low cost and only based on the fault coverage of each test vector. The disadvantage of the technique is that if a dropping fault simulation is used, experimentally after almost 10 generation, the generated vectors stop detecting remaining faults. This method has resulted in better final test set, but it is very expensive. A new operator is used in [8], in which, after each generation, the best vector in population is put on the final test set and then rescored with a new decreasing fitness.

Genetic Algorithm Introduction

The most popular technique in evolutionary computation is the genetic algorithm. Holland proposed GA as a heuristic method based on "Survival of the fittest". GA was discovered as a useful tool for search and optimization problem. Space of all feasible solutions (the set of solutions among which the desired solution resides) is called search space. Each and every point in the search space represents one possible solution. Therefore each possible solution can be "marked" by its fitness value, depending on the problem definition. With Genetic Algorithm one looks for the best solution among a number of possible solutions represented by one point in the search space.

Basics of Genetic Algorithm

GA starts by generating an initial population of chromosomes. Generally, the initial population is generated randomly. Then, the genetic algorithm loops over an iteration process to produce the population [11]. Each iteration consists of the following four steps:

Selection: The first step is selecting individuals for reproduction. This selection is based on the relative fitness of the individuals so that best ones are often chosen for reproduction.

Reproduction: This is the second step where offspring's are produced from the selected individuals. For the next generation new chromosomes are produced by either crossover or mutation or both.

Evaluation: In this step the fitness of the new individuals (chromosomes or offspring's) is evaluated.

Replacement: In this last step, individuals from the old population are replaced by the new ones.

The algorithm is stopped when the population converges toward the optimal solution.

Genetic Algorithm for Test Pattern Generation

In this paper, genetic algorithm is used for test pattern generation. The test vectors or test patterns form the population or set of solution for GA. This algorithm is used to find the optimal solution with high fault coverage. A random population of n test vectors or chromosome is first generated and fitness of each individual in the population is evaluated based their fault coverage. By repeating selection, crossover, mutation and replacement, new population of chromosomes is created for next generation. The compacted or optimal test vectors generated by this algorithm had detected all the faults in the VLSI circuits. Results show that the test set size has been reduced without any degradation in the fault coverage for the benchmark circuits.

Flowchart for the genetic algorithm used in this paper is shown in the fig 2.

The steps involved in the algorithm are

1. Initial population: Random population of n chromosomes (suitable solutions for the problem) was created. Population size for each generation is chosen to be large enough in order to ensure adequate diversity. Here the individuals of the population are the test vectors for each circuit. The length of each chromosome or individual is equal to the number of primary inputs of the CUT. There is always a trade off between the convergence rate and the search space. The population size increases with increase in the length of the test vector. The table 1 shows the approximate population size for different test vectors.


population size

Test Vector Length

Population size








Generate initial population of test vectors

Evaluate the fitness of each individual by performing fault simulation with fault dropping

Optimization criteria met?


Best Individuals obtained






Generate new population

Fig 2 Flow chart of Genetic Algorithm

2. Fitness Function Evaluation: In this step the fitness function for each chromosome (test vector) in the population is evaluated. This is given by f(x). Fitness function provides a measurement for the quality of the test vector. A test vector that detects the maximum number of faults is chosen as the best test vector. When fault dropping is included then a test vector that detects maximum number of new faults is considered to be the best test vector. Based on this fitness function value the chromosomes (test vectors) were selected by the selection process for reproduction. The fitness function is problem specific. In this paper it is based on the fault coverage. The fitness function is given by

F(x) = No of faults detected by test vector

Total number of faults

The optimum solution is obtained for the maximum value of F(x).

3. Creation of New Population: New population is created by repeating the following steps selection, crossover and mutation.

Selection: In selection process two parent chromosomes from the population is selected for producing offspring's. Selection of parent chromosomes is based on their fitness value, better fitness, the bigger chance to get selected. The selected chromosomes were used in the crossover process.

There are different types of selection process. In this paper Tournament Selection scheme is used.

Tournament Selection: Tournament selects each parent by choosing individuals at random, the number of which we can specify by Tournament size, and then choosing the best individual out of that set to be a parent. The best individual from the tournament is the one with the highest fitness, which is the winner. Tournament competitions and the winner are then inserted into the mating pool. The tournament competition is repeated until the mating pool for generating new offspring is filled. The mating pool comprising of the tournament winner has higher average population fitness. This method is more efficient and leads to an optimal solution.

Crossover: Crossover is the process of considering two parents and producing offspring's from them. With a cross probability, cross over of the parents selected by the selection process is performed to produce new offspring (children). If no crossover was performed, offspring is the exact copy of parents. After the selection process, the population consists of better individuals. The three steps of the crossover operator are:

i. The reproduction operator selects at random a pair of two individual strings for the mating.

ii. A cross site is selected at random along the string length.

iii. Finally, the position values are swapped between the two strings following the cross site.

In this paper single point crossover is performed which converges much faster. In single point crossover two mating chromosomes are cut once at corresponding points and the sections after the cuts is exchanged between them to form new offspring's. Here, a cross-site or crossover point is selected randomly along the length of the parent chromosomes and bits next to the cross-sites are exchanged. Single point crossover is shown in the Fig 3.

Fig 3 Single point crossover

Mutation: After crossover, mutation is performed on the offspring's that were obtained from the crossover. Mutation prevents the algorithm from reaching the local minimum. Mutation is viewed as a background operator to maintain genetic diversity in the population. It introduces new genetic structures in the population by randomly modifying some of its building blocks. The mutation varies for different kinds of representation. For binary representation, mutation inverts the bits from '0' to '1' and '1' to '0' with a small mutation probability. The mutation is shown in fig 4.

Fig 4 Mutation

Optimization Criteria: The condition for the algorithm to stop is called the optimization or stopping criteria. In this paper the stopping criteria is the total number of faults detected, which is the sum of the faults detected by each test vector. Fault simulation is performed for each fault considered and then each test vector is evaluated based on the faults detected.

Results and discussion

The combinational circuits were taken as the CUT. These circuits were simulated in Matlab for fault coverage. The number of faults detected by each test vector to the total number of faults injected in the circuit gives the fault coverage for each test vector. 20 faults were introduced to the ISCAS'85 combinational benchmark circuit c17. Since it is a 5 input circuit, the total number of test vectors was 32. The Genetic algorithm was applied and found that out of 32 test vectors only 5 test vectors were enough to detect all the injected faults. For the 1 bit adder which is 3 input circuit, has 8 test vectors. 22 faults were introduced to this circuit. GA was applied and found that only 4 test vectors were enough to detect all the faults.

1. Experimental result shows that the test pattern size has been reduced up to 58% in comparison with other methods static TDVR algorithm as shown in table II.

Fig 5 Circuit under Test benchmark Circuit - c17


Result test set compaction


Number Of Inputs And Patterns Applied

Fault Model Considered And Number of Faults Introduced

Number Of Test vectors for 100% Fault coverage

% Reduction Of Number Of Test Vector




5 input

32 test vectors

Stuck at fault model

20 faults




1 bit adder

3 input

8 test vectors

Stuck at fault model

22 faults





Genetic algorithm has been used for test pattern generation which has reduced the test set size without any degradation in the fault coverage. This algorithm has been applied to various combinational benchmark circuits like c17, 1 bit full adder and found that the percentage reduction in the test pattern was found to be approximately 50% when compared to the other test compaction technique like TDVR. The compacted test set has achieved the same fault coverage as the original test set. This reduction in the test vectors in turn reduces the test application time and hence the test power. In future GA can be applied for the sequential circuits in order to obtain the reduced test set.