Μέθοδοι ελέγχου ολοκληρωμένων ψηφιακών κυκλωμάτων

Abstract

As circuit size grows, the need of correct circuit functioning imposes a testing methodology to be applied to ensure proper behavior of that circuit after manufacturing. Towards that direction, Test Pattern Generation procedures are devised to validate the circuit function. These procedures produce sets of input vectors (test sets) that when applied to circuit inputs produce output responses that enable one to check the "correct" circuit functioning. In this dissertation we elaborate on efficient Automatic Test pattern generation methods for digital circuits. Test pattern generation methods differentiate between those that operate on a combinational circuit and those operating on sequential circuits. For combinational circuits, the circuit under test (CUT) with all the ATPG constraints is represented here by a neural network. This neural network is characterized by an energy function E that has global minimum (=0) only at the neuron states consistent with circuit’s logic function. With the help of the energy function E the ATPG problem for combinational circuits is formulated, in this work, as an energy minimization problem where we attempt to find the global minimum of the energy function. For this purpose, are developed: a) a method of gradient descent search where the studying of the surface of the energy function revealed a saddle point and the research focused on the use of saddle point as a starting point of the search process. b) A method that tries to find the solution (test vector) by using the transitive closure of the implication graph based on the energy function constraints. Furthermore, a parallel ATPG which is based on method b) is developed and implemented on a Network of Transputers. For sequential circuits, where a sequence of input vectors (test sequence) is required to detect a single fault the complexity of sequential circuit test generation is much higher than for combinational circuits. To cope with the complexity of sequential circuit test generation ATPG methods are developed which use Genetic Algorithms (GAs) for simulation-based test generation. In this work, it is ascertained that the current GA-based sequential test generators don’t take into consideration the following remarks: In a sequential circuit: a) it is very difficult, if not impossible, to identify the good "genes" of the circuit. b) Crossover operator which is responsible for the inheritance of good genes acts as a mutation operator. c) During the evolutionary process, "good" sequences survive while "weak" sequences are discarded though certain "weak" sequences may carry useful information about faults and/or states. States reached by "weak" sequences may be difficult for the "good" ones to reach and certain faults detected by them may be difficult to be detected in latter passes. Taking into consideration the above remarks, GA-based ATPG algorithms are devised that: a) Employ (GATPG algorithm) a crossover operator with a non-uniform probability distribution for the cut-point selection in order to preserve, as much as possible, the inheritance of the "good" genes, b) Exploit (GIFT algorithm), in order to speed up the fault coverage, certain special subsequences that exist in the GA population (essential subsequences, USS, DFS), which, although may have low fitness value ("weak" sequences), detect faults (usually non-common faults) that are not present in the "good" test sequences. Also, with the aim of producing short test sets of high quality, the main GA method incorporates techniques that properly select and dynamically compact subsequences. Branch & Bound method exploiting "previous" knowledge in order to speed up the process. Finally, experimental results are presented to evaluate the efficiency of the proposed methods.

O ?λεγχος των ψηφιακ?ν κυκλωμ?των επιτυγχ?νεται μ?σω της σ?γκρισης της θεωρητικ?ς αναμεν?μενης και της πραγματικ?ς απ?κρισης (τιμ?ς εξ?δων) των δοθ?ντων κυκλωμ?των μετ? την εφαρμογ? κατ?λληλων διανυσμ?των ελ?γχου (τιμ?ς εισ?δων). Αντικε?μενο της παρο?σας εργασ?ας αποτελε? η ε?ρεση μεθ?δων Αυτ?ματης Παραγωγ?ς Διανυσμ?των Ελ?γχου σφαλμ?των (ATPG πρ?βλημα) για ψηφιακ? κυκλ?ματα. Η παραγωγ? των διανυσμ?των ελ?γχου σφαλμ?των (ATPG πρ?βλημα) διαφοροποιε?ται αν?λογα με το υπ? ?λεγχο κ?κλωμα (συνδυαστικ? ? ακολουθιακ?). Τα βασικ? ζητο?μενα των μεθ?δων ATPG ε?ναι η παραγωγ? εν?ς συν?λου διανυσμ?των ελ?γχου που, κατ? σειρ?ν προτεραι?τητας, (α) παρουσι?ζουν υψηλ? ποσοστ? κ?λυψης σφαλμ?των, (β) το πλ?θος τους ε?ναι μικρ? (κ?στος ελ?γχου) και (γ) παρ?γονται με μικρ? υπολογιστικ? κ?στος. Για τα συνδυαστικ? ψηφιακ? κυκλ?ματα το ATPG πρ?βλημα διατυπ?νεται εδ? (δομ? κυκλ?ματος, συνθ?κες ελεγξιμ?τητας) σαν ?να νευρωνικ? δ?κτυο (NΔ) του οπο?ου η ελ?χιστη τιμ? της συν?ρτησης εν?ργειας του (συντεταγμ?νες ελαχ?στου) παριστ? και την λ?ση του ATPG προβλ?ματος. Για την ελαχιστοπο?ηση της συν?ρτησης εν?ργειας του NΔ εφαρμ?ζονται: α) η μ?θοδος της καθοδικ?ς κλ?σεως (gradient descent) ?που διαπιστ?νεται ?τι η επιφ?νεια ενεργε?ας του NΔ παρουσι?ζει ?να σαμαροειδ?ς σημε?ο και μελετ?ται η περ?πτωση της ?ναρξης της αναζ?τησης της λ?σης απ? το σημε?ο αυτ?, β) μια μ?θοδος που βασ?ζεται στη θεωρ?α γραφημ?των και χρησιμοποιε? το μεταβατικ? γρ?φημα. Επιπλ?ον, η μ?θοδος που βασ?ζεται στο μεταβατικ? γρ?φημα αναπτ?σσεται σε παρ?λληλο ATPG αλγ?ριθμο (PARTEGEN) που υλοποιε?ται σε ?να δ?κτυο απ? Transputers. Για την περ?πτωση των ακολουθιακ?ν κυκλωμ?των, λ?γω της πολ? μεγαλ?τερης πολυπλοκ?τητας τους, αναπτ?σσονται εδ? ATPG μ?θοδοι που αν?κουν στην κατηγορ?α των γενετικ?ν μεθ?δων ελ?γχου και βασ?ζονται στην προσομο?ωση. Στα ακολουθιακ? κυκλ?ματα, ?που ζητο?μενο ε?ναι η παραγωγ? ακολουθι?ν διανυσμ?των, διαπιστ?νεται ?τι η εφαρμογ? των γενετικ?ν μεθ?δων ?πως γ?νεται μ?χρι σ?μερα δεν λαμβ?νει υπ?ψη ?τι: α) ε?ναι δυσδι?κριτος ο εντοπισμ?ς #«µZ#¶N‹#των