Automatic Test Pattern Generation

Manufactured chips may have structural faults at certain places/nodes, which must be tested before being delivered to end users. These structural faults can be confirmed by testing logical faults which can represent the effects of the physical faults on the behavior of the system.

The two types of faults under consideration for this project are:

• SA0 : stuck-at-0, a fault where node is not able to attain value 1, irrespective of inputs
• SA1 : stuck-at-1, a fault where node is not able to attain value 0, irrespective of inputs

A logical fault can be tested by passing a test pattern or input vector and comparing the obtained result with the expected result. This project is conducted to design an algorithm to generate an input vector along with the expected result to test the above mentioned faults.

The algorithm is designed using the following 3 steps:

• Fault Sensitisation: Attempts to sensitize the fault site to a value opposite to the stuck fault.
• Propagation: Propagate the fault to a primary output.
• Justification: Justify the value at each node.

Detailed solution can be found in this document.

This project is the submission for Google Girl Hackathon 2023.

Algorithm

Flowchart

This link contains a detailed flowchart.

Pseudocode

The steps involved in the algorithm are:

Step 1:   Parse through the circuit file and store the circuit information in a structure.

Step 2:   Declare a global variable to store and access the node values throughout the algorithm.

Step 3:   Sensitize the faulty node (FAULT_AT) by assigning the value opposite to its stuck-at fault value (FAULT_TYPE). For example, to sensitize the SA0 (stuck-at 0) fault, the faulty node is assigned the opposite value 1.

Step 4:   Backtrack the inputs of the faulty node to justify the sensitized value assigned.

Step 5:   From the faulty node, propagate the fault to a primary output. The output should be the result of the sensitized value. This should be made sure by assigning a value to the second input (if any) of the output gate which ensures the output to be based on the sensitized value. The following 4 equations have been used in the algorithm to ensure this assignment, for

• NOT gate: ~1 = 0, ~0 = 1
• AND gate: 1 & ⍺ = ⍺
• OR gate: 0 | ⍺ = ⍺
• XOR gate: 0 ^ ⍺ = ⍺       where, ⍺ is a variable.

Step 6:   Keep track of the node to be justified (toJustify) after propagation. This is usually the second input (if any) of the output gate other than the faulty input.

Step 7:   Justify the node and input values by backtracking the inputs from the toJustify node and assigning them the values required to ensure the assigned value of toJustify.

Step 8:   In the output.txt file, write the resultant input vector, that is, the values assigned to inputs A, B, C and D and the expected value of output to confirm the fault, that is, the opposite of the value stored in Z.

Project Environment

Tools Used

• C++ - Programming Language
• Visual Studio Code - Integrated Development Environment (IDE)
• GCC/G++ with MinGW - C++ compiler
• Git, GitHub - Version History Control
• Markdown - Documentation Language

How to run the project

1. Clone the repository

git clone https://github.com/agarwalharshal/Automatic_Test_Pattern_Generation.git

2. Open the directory in Visual Studio Code
3. Launch a new terminal within the Automatic_Test_Pattern_Generation directory
4. Change the directory to the ./src directory.

cd .\src\

5. Compile the source files using the command:

g++ -o out *.cpp

6. Run the program:

./out

7. The output will be generated in the output.txt file.

Test Circuits

Test Circuit 1

circuit.txt

net_e = A & B
net_f = ~ net_e
net_g = C ^ D
Z = net_f | net_g
FAULT_AT = net_g
FAULT_TYPE = SA0

output.txt

[A, B, C, D] = [1, 1, 1, 0], Z = 0

Test Circuit 2

circuit.txt

net_e = ~ A
net_f = net_e | B
net_g = C ^ D
Z = net_f & net_g
FAULT_AT = net_e
FAULT_TYPE = SA1

output.txt

[A, B, C, D] = [1, 0, 1, 0], Z = 1

Test Circuit 3

circuit.txt

net_e = A & B
net_f = C | D
net_g = net_e ^ net_f
Z = ~ net_g
FAULT_AT = net_g
FAULT_TYPE = SA1

output.txt

[A, B, C, D] = [1, 0, 0, 0], Z = 0

Presentation

Presentation slides

Working Prototype