1Neural Network Automatic Test Pattern GeneratorPriyanka SinhaDepartment of Electrical and Computer Engineering, Auburn University200 Broun Hall, [email protected]—This paper discusses the technique for modelinga test generation problem using neural networks. Throughexamples, it illustrates the representation of a digital circuit asa hopfield network; the translation of faults to the same andthe generation of test vectors for it. The results that have beenreported, clearly indicate the advantage in using it as a meansof parallelizing the test generation process.Further, faster waysof implementing the energy minimization using quadratic 0-1programming are discussed.I. INTRODUCTIONAutomatic test pattern generation for a large combinationalcircuits testing is frequent for VLSI circuits. Therefore, par-allelizing the process would helps in reducing the time fortesting. In order to truly do so, the testing problem has tobe mapped to a parallel computation model. Neural networksare useful represent complex non-linear functions. A hopfieldnetwork is a kind of neural network that has been used here.They are an attempt to model the vastly parallel collection ofneurons in our brain. The neurons are depicted as a set ofnodes related by bidirectional weighted edges of weight Tij.Each node has an activation state V associated with it and athreshold I. The network is in an excited state if upon randomlyupdating a neuron, according to the update rule given asVi= 1 if ΣNj=1TijVj< 0= 0 if ΣNj=1TijVj> 0= Viotherwise, its state changes depending on the state of its neighbours.Where N is the number of nodes in the network and the energyE is given byE = −12ΣNi=1ΣNj=1TijV iV j − ΣNi=1IiV i + K, K being a constant.If the state does not change with the update rule, then thenetwork is in stable state. Hopfield has proved that in thestable state the energy is the minimum. Hence, such a neuralnetwork can be used to model an optimization problem bydefining the energy function appropriately and allowing thenetwork to stabilize by randomly updating the nodes. This isthe inherent parallelization in the model.The weights of the hopfield network are determined by thetraining vector sequences that are fed to the network, which inthe case of AND,OR,NOT,NAND and NOR gate are simplefunctions given by• ANDTij= (1 − δ (i, j)) ×((A + B) × connected (i, j) − B × inputs (i, j))Ii= − (2A + B) × output (i)K = 0• ORTij= (1 − δ (i, j)) ×((A + B) × connected (i, j) − B × inputs (i, j))Ii= −B × output (i) − A × input (i)K = 0• NANDTij= (1 − δ (i, j)) ×((−A − B) × connected (i, j) − B × inputs (i, j))Ii= −B × output (i) − A × input (i)K = 0• NORTij= (1 − δ (i, j)) ×((−A − B) × connected (i, j) − B × inputs (i, j))Ii= BK = B• NOTTij= −2J × (1 − δ (i, j))Ii= − (2A + B) × output (i)K = 0where the functions are as follows:inputs (i, j) = 1 if i and j areinput neurons for the same gate0 otherwiseconnected (i, j) = 1 − inputs (i, j)δ (i, j) = 1 if i = j0 otherwiseoutput (i) = 1 if i is an output neuron f or the gate0 otherwiseinput (i) = 1 if i is an input neuron f or the same gate0 otherwise2This idea of representation to be used for an ATPG isdefined by [1]. Section I presents the history of the ideaof neural networks being used for automatic test patterngeneration. Section II illustrates an example of how a neuralnetwork can be used to generate tests. Section III depicts theand Section IV concludes.II. BACKGROUNDNeural networks have been an object of study since the1940’s. The Hopfield network has been around since 1982.Its uniqueness is in the fact that it is a recurrent network,i.e., it has feedback loops from the output to its input whichgathers the associative nature of the neurons in the brain closerthan back propagation . Hopfield had solved the problem ofdefining a recurrent neural network that would surely stabilize.By 1985, it was known that these Hopfield networks couldbe used to solve combinatorial optimization problems. Thechallenge lay in modelling such a problem in terms of aHopfield network.Figure ??Fig. 1. A hopfield networkIn the area of testing, in the attempt to reduce the time totest massive circuits, which VLSI would end up with, a majoreffort would be underway to parallelize the test generationproblem in order to reduce that time. The technical report,”Automatic Test Generation using Neural Networks” , 1988’is the earliest I could find that had a mention of using neuralnetworks for test generation. The following publications [?],[2], [3], [8] are compiled into the book [1]. The initial use ofa gradient descent technique to minimize the energy functioncleared the validity of the model for stuck-at faults. Later on,the minimization was made faster using the idea of implicationgraphs. Transitive closure and path sensitization could detectredundant faults and also model delay tests. The latest point ofinterest is in [?] and [11]. Further interest in the implicationgraphs were presented by VD Agrawal.III. ANALYSIS AND ALGORITHMSIn order to use neural networks for test generation, thecircuit under test has to be represented as a neural network.After this novel step, the fault in the circuit is modeled.If possible, nodes with equal threshold, inputs and outputare merged in the step of neural pruning. Then, the energyminimization would generate a test for the faulty circuit. Afterall of this, the optimizations are made to expend minimumeffort in generating the test. In the following sections we goover these steps taking the example circuit to be Figure 2, i.e.,a = NOT (b)c = AND(a, b)d = OR(a, c)Fig. 2. Example CircuitThis circuit has a total of 16 stuck at faults of whichm-s-a-0 and c-s-a-0 are redundant and (b-s-a-0, a-s-a-1,l-s-a-1, m-s-a-1, c-s-a-1, d-s-a-1) and (b-s-a-1, a-s-a-0, l-s-a-0,d-s-a-0) are equivalent.States NoFault b-s-a-0 b-s-a-1 a-s-a-0 a-s-a-1 l-s-a-0 l-s-a-1m-s-a-0 m-s-a-1 c-s-a-0 c-s-a-1 d-s-a-0 d-s-a-1b=0 1 1 0 0 1 0 1 1 1 1 1 0 1b=1 0 1 0 0 1 0 1 0 1 0 1 0 1A. Represent a digital circuit as a neural networkUsing the functions for thresholds and activation valuesgiven above, and taking the circuit Figure 2 as a sample circuit,the weights and thresholds have been calculated and shown in3.IV. REPRESENT A FAULT IN A CIRCUITUsing the same circuit, the fault l-s-a-1 is represented asFigure 4. For the faulty node, a dual node a“ is created. Allnodes related to ’a” as output of the