Aristotle University Of Thessaloniki (AUTH)
Μέθοδοι ελέγχου ολοκληρωμένων ψηφιακών κυκλωμάτων
Abstract
dc:descriptionAs 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.
Degree
thesis:*- Grantor dc:publisher
- Aristotle University Of Thessaloniki (AUTH)
- Year dc:date
- 2004
Author and committee
dc:creator, dc:contributor.*- Authors dc:creator
-
- Dimopoulos, Michael
- Δημόπουλος, Μιχαήλ
Subjects
dc:subject × 20- Έλεγχος σφαλμάτων ψηφιακών κυκλωμάτων
- Παραγωγή διανυσμάτων ελέγχου σφαλμάτων
- Παράλληλος αλγόριθμος παραγωγής διανυσμάτων
- Σαμαροειδές σημείο
- Αλγόριθμοι, Γενετικοί
- Πυκνότητα σφαλμάτων
- Κανόνες ελαχιστοποίησης
- Συμπίεση διανυσμάτων ελέγχου σφαλμάτων
- Testing digital circuits
- Test generation
- Parallel ATPG algorithm
- Saddle point
- Algorithms, Genetic
- Fault density
- Reduction rules
- Test sequence compaction
- Φυσικές Επιστήμες
- Επιστήμη Ηλεκτρονικών Υπολογιστών και Πληροφορική
- Natural Sciences
- Computer and Information Sciences
Rights
- Language dc:language
- gre
Identifiers
dc:identifier.*- Identifier
- 10.12681/eadd/14664