Μέθοδοι ελέγχου ολοκληρωμένων ψηφιακών κυκλωμάτων
Creators: name: Δημόπουλος, Μιχαήλ Γ.
Publisher: name: Aristotle University of Thessaloniki
Year: 2004
Subjects: Ελεγχος σφαλμάτων ψηφιακών κυκλωμάτων
Γενετικοί αλγόριθμοι
Παράλληλος αλγόριθμος παραγωγής διανυσμάτων ελέγχου σφαλμάτων
Συμπίεση διανυσμάτων ελέγχου σφαλμάτων
Testing digital circuits
Parallel ATPG
Genetic algorithms
TPG methods

description: Αντικείμενο της διατριβής αποτελεί η εύρεση μεθόδων Αυτόματης Παραγωγής Διανυσμάτων Ελέγχου σφαλμάτων(ATPG πρόβλημα) για ψηφιακά κυκλώματα. Για τα συνδυαστικά ψηφιακά κυκλώματα το ATPG πρόβλημα διατυπώνεται(δομή κυκλώματος, συνθήκες ελεγξιμότητας) σαν ένα νευρωνικό δίκτυο(ΝΔ) του οποίου η ελάχιστη τιμή της συνάρτησης ενέργειας(συντεταγμένες ελαχίστου) παριστά και την λύση του ATPG προβλήματος. Για την ελαχιστοποίηση της συνάρτησης ενέργειας του ΝΔ εφαρμόζονται η μέθοδος της καθοδικής κλίσεως(gradient descent) όπου διαπιστώνεται ότι η επιφάνεια ενεργείας του ΝΔ παρουσιάζει ένα σαμαροειδές σημείο και μελετάται η περίπτωση της έναρξης της αναζήτησης της λύσης από το σημείο αυτό. Επιπλέον, αναπτύσσεται ένας παράλληλος ATPG αλγόριθμος που υλοποιείται σε ένα δίκτυο από Transputers. Για τα ακολουθιακά κυκλώματα, αναπτύσσονται γενετικές μέθοδοι ATPG που : α)για τη διατήρηση, όσο γίνεται, της κληρονομικότητας χρησιμοποιείται ένας τελεστής διασταύρωσης με μη ομοιόμορφη κατανομή πιθανότητας στην επιλογή του σηεμίου τομής, β) για την ταχύτητη αύξηση του ποσοστού κάλυψης σφαλμάτων αναγνωρίζονται και αξιοποιούνται υποακολουθίες που υπάρχουν στον γενετικό πληθυσμό(μπορεί να έχουν μικρή τιμλη καταλληλότητας) και έχουν μερικά ιδιαίτερα χαρακτηριστικά(ουσιώδεις υποακολουθίες, ακολουθίες USS, DFS). Επιπλέον, για την παραγωγή μικρών σε μήκος ακολουθιών προτείνονται(και ενσωματώνονται στην κύρια γενετική μέθοδο) συστηματικοί τρόποι συνδυασμού και δυναμικής συμπίεσης κατάλληλων τμημάτων τους(υποακολουθίες) για να προκύψουν γρήγορα νέες συμπαγείς ακολουθίες που καλύπτουν περισσότερα σφάλματα. Τέλος, αναπτύσσονται μέθοδοι στατικής συμπίεσης για σύνολα ανεξάρτητων ακολουθιών ελέγχου που δεν βασίζονται στη προσομοίωση σφαλμάτων(χρονοβόρα διαδικασία) για την επαλήθευση της κάλυψης του αρχικού συνόλου σφαλμάτων. Σε κάθε περίπτωση, η αποδοτικότητα των μεθόδων που προτείνονται συγκρίνεται με καθιερωμένες μεθόδους από την βιβλιογραφία και σχολιάζονται τα αποτελέσματα
description: In this dissertation we elaborate on efficient Automatic Test pattern generation methods for digital circuit. For combinational circuits, the circuit under test(CUT) with all the ATPG constraints is representes by a neural network which is characterized by an energy function E. The ATPG problem is formulated as an energy minimization problem where we attempt to find the global minimum of the energy function E. 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 method of gradient descent search. Furthermore, a parallel ATPG is developed which use Genetic Algorithms(GAs) for simulation-based test generation. These methods : a) Employ a crossover operator with a non-uniform probability distribution for the cutpoint selection in order to preserve, as much as posible, the inheritance of the "good" genes, b)Exploit, in order to speed up the fault coverage, certain special subsequeces 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. Finally, efficient methods are developed that statically compact sets of independents test sequences