Implementation Of An ATPG Using PODEM Algorithm SACHIN DHINGRA Objective: Write a test pattern generation program using the PODEM algorithm.IMPLEMENTATION OF AN ATPG USING PODEM ALGORITHM SACHIN DHINGRA ELEC 7250: VLSI testingOBJECTIVE: Write a test pattern generation program using the PODEM algorithm. ABSTRACT: PODEM (Path-Oriented Decision Making) is an Automatic Test Pattern Generation (ATPG) algorithm which was created to overcome the inability of D-Algorithm (D-ALG) to generate test vectors for circuits involving Error Correction and Translation. The aim of this project is to implement the PODEM algorithm to generate test vectors for a given fault. External tools such as HITEC/PROOFS package are used to convert a netlist of a circuit into a levelized circuit description. HITEC/PROOFS package is also used to cal-culate the Testability Measures required for implementation of PODEM. A sample circuit is chosen for verification purposes. Various subroutines of the PODEM algorithm are individually verified. Finally the test vectors generated by the program are compared with manual implementation of the PODEM algorithm. I. INTRODUCTION: The D-ALG is proven to be ineffective in generation of test vectors for circuits that in-volve the XOR gates with re-convergent fan-outs. These kind of circuits are commonly found in applications requiring Error Correction and Translation (ECAT). Automatic Test Pattern Generators (ATPGs) using PODEM and D-ALG are complete i.e. they will gen-erate a vector for a fault if the fault is testable. D-ALG generates a decision structure to evaluate the value of every node in the circuit to obtain the test vectors. The drawback of this approach was discovered while generating test vectors for typical circuits like the ECAT. D-ALG takes extremely long time to generate tests for such circuits; PODEM on the other hand confines its search space only to the primary inputs. This technique proves to be much faster and efficient as compared to D-ALG In order to describe the circuit a five valued logic is used. The five values are 0, 1, X (un-known), D (Logic 1 in good circuit and 0 in the faulty circuit), D’ (Logic 0 for a good circuit and 1 for a faulty circuit). The algorithm examines all the possible input values till a test is found for a given fault. Initially all the primary inputs are unassigned, these in-puts are assigned values one by one depending on the fault location & fault type (sa0 or sa1), the path chosen for fault propagation also determine the input assignment. The im-plications of primary inputs are evaluated every time a new value is assigned to an input. These implications are used to determine testability of the faults. If any input does not contribute in fault detection then it is dropped from the input list. So the algorithm basi-cally assigns primary inputs with different values sequentially till a test vector for a given fault is found. HITEC/PROOFS is a package created in the University of Illinois, Urbana, capable of fault list generation, fault simulation and fault collapsing for stuck-at faults in sequen-tial/combinational circuits. The input to the package is a netlist which is converted into a circuit.lev file which describes the circuit in its levelized form along with the testabilitymeasures. The package generates a fault list of all the stuck-at faults in the circuit and if needed perform equivalent and dominance collapsing of the faults. Although the primary objective is perform fault simulation and test pattern generation, for the project, the pack-age is only used for levelization and calculation of the testability measures for the circuit under test. This helps us reduce the amount of coding required to implement the PODEM algorithm. In this project PODEM algorithm is implemented in ‘C’ programming language to gener-ate test vectors for stuck-at faults in a given circuit. The input to the program is a circuit netlist and its fault list. The netlist is parsed and stored as a data structure in the form of a levelized circuit. The faults are chosen one at a time from the fault list. PODEM algo-rithm is executed to determine a test vector which can detect the fault under consideration. The PODEM algorithm is explained in Section III. Section IV describes the implementa-tion of the algorithm in ‘C’ with the help of HITEC/PROOFS. The Results are presented in Section V, followed by conclusion. II. ALGORITHM: PODEM proves to be more efficient as compared to a D-ALG because it limits its search space only to Primary Inputs (PIs) of the circuits. D-ALG on the other hand has a search space comprising of all the internal nodes of the circuit along with the PIs. The first ob-jective of the algorithm is to sensitize the fault. After the fault is sensitized the objectives are changed in order to propagate the fault to a Primary Output (PO). Function OBJEC-TIVE is used to determine objectives for the program. Depending on the current objective, a function called BACKTRACE is used to determine the value of one of the PIs. For every PI assigned, logic simulation is performed to check for two conditions: desensitiza-tion of the fault and disappearance of fault propagation path (also known as X-PATH CHECK). If any one of the two conditions is violated, the program backtracks and changes the value assigned to the most recent PI. This process of assigning values to PIs is repeated till PIs form a test vector or no more combinations of PIs are possible. The latter case implies that the test is untestable. The simplified flowchart of the algorithm and its major functions (Backtrace, Forward Implication, X-Path Check and Objective) are shown in the following text.Podem:Objective: Is the Fault location unassignedSet the objective as the fault location and the value = V’Select a path to propagate the fault to the outputSelect an unassigned input of a node/gate on the propagation path as the objective Assign the non-controlling value as the objective value Selection possibleReturn ObjectiveTest not possible with current Input assignment. No objective assignedYesNoObjectiveInput fault location F and fault value VBacktrace: Forward Implication (IMPLY function): This function is used to perform a logic simulation of the circuit depending on the values of the Primary Inputs. The values of all the nodes/gates in the circuit are evaluated. These results are then used to determine the testability of