Ο όγκος των δεδομένων που απαιτούνται για τον έλεγχο της ορθής λειτουργίας ενός συστήματος που υλοποιείται σε ένα ολοκληρωμένο κύκλωμα είναι πάρα πολύ μεγάλος. Αυτό συνεπάγεται ότι ο χρόνος που απαιτείται για τον έλεγχο της ορθής λειτουργίας του ολοκληρωμένου κυκλώματος μπορεί να είναι απαγορευτικά μεγάλος. Για τη μείωση του απαιτούμενου χρόνου χρησιμοποιούνται διάφορες τεχνικές συμπίεσης των δεδομένων δοκιμής. Κάποιες από αυτές τις τεχνικές βασίζονται στην αποστολή κοινών δεδομένων δοκιμής ταυτόχρονα σε περισσότερες από μία μονάδες του ολοκληρωμένου κυκλώματος. Στην εργασία αυτή υλοποιούμε μια από αυτές τις τεχνικές που βασίζεται στην ύπαρξη μονοπατιών ολίσθησης (scan paths) στις μονάδες του ολοκληρωμένου κυκλώματος. Για την περαιτέρω μείωση του χρόνου που απαιτείται για τον έλεγχο της ορθής λειτουργίας του ολοκληρωμένου κυκλώματος γίνεται χρονοπρογραμματισμός της σειράς με την οποία θα ελεγχθεί η ορθή λειτουργία των διαφόρων μονάδων του ολοκληρωμένου κυκλώματος. / The volume of data that is required to test a SoC is too much big. This means that the time that is required for testing can be prohibitorily big. For the reduction of required time are used various techniques of data compaction.Some of these techniques are based on broadcasting the same value to all of the cores on a SoC.In this work we use one of these techniques that are based on the existence of scan chains in the core (broadcast scan).For further reduction of time that is required for testing a circuit we use a core testing schedule algorithm.

Στην εργασία, αυτή, εξετάζονται οι μέθοδοι συμπίεσης του συνόλου δοκιμής με τη χρήση πινάκων που έχουν ήδη προταθεί και προτείνεται μία νέα μέθοδος συμπίεσης δεδομένων δοκιμής για πυρήνες που ο έλεγχος ορθής λειτουργίας υλοποιείται μέσω μονοπατιών ολίσθησης. Η νέα μέθοδος επαναχρησιμοποιεί μπλοκ του πίνακα για τη σύνθεση διανυσμάτων δοκιμής. Δύο νέοι αλγόριθμοι παρουσιάζονται για επιλεκτική και πλήρη καταχώρηση τμημάτων του συνόλου δοκιμής σε πίνακα. Η προτεινόμενη μέθοδος συγκρίνεται με τις υπάρχουσες μεθόδους ως προς το ποσοστό συμπίεσης αλλά και ως προς το κόστος υλοποίησης. Για την αξιολόγηση της μεθόδου λαμβάνονται υπόψη σύνολα δοκιμής που έχουν παραχθεί για την ανίχνευση απλών σφαλμάτων μόνιμης τιμής, απλών σφαλμάτων μόνιμης τιμής με πολλαπλότητα ανίχνευσης Ν (Ν-detect) και σφαλμάτων καθυστέρησης μετάβασης. / In this work we refer to dictionary based test data compression methods. At first the already known dictionary based test data compression methods are comparably presented. Then we propose a new method and we show that the test data compression achieved by a dictionary based method can be improved significantly by suitably reusing parts of the dictionary entries. To this end two new algorithms are proposed, suitable for partial and complete dictionary coding respectively. For the evaluation of the proposed method, test sets have been generated and used based on the stuck-at fault model for single and N detection of each fault as well as on the transition fault model.

Η διατριβή ασχολείται με το αντικείμενο του ελέγχου ορθής λειτουργίας κυκλωμάτων κατά τον οποίο λαμβάνεται υπόψη και η συμπεριφορά ως προς την κατανάλωση ισχύος. Οι τεχνικές που προτείνονται αφορούν α) τη συμπίεση ενός συνόλου δοκιμής σε περιβάλλον ενσωματωμένου ελέγχου με χρήση εξωτερικών ελεγκτών, β) την εμφώλευση διανυσμάτων δοκιμής σε περιβάλλον ενσωματωμένου ελέγχου και γ) τη μείωση της κατανάλωση ισχύς και ενέργειας σε περιβάλλον εξωτερικού ελέγχου. Η συμπίεση των δεδομένων βασίζεται στην παρατήρηση ότι ένα διάνυσμα δοκιμής μπορεί να παραχθεί από το προηγούμενό του με την αντικατάσταση κάποιων τμημάτων του. Μεγαλύτερη συμπίεση επιτυγχάνεται όταν γίνει αναδιαταξή διανυσμάτων και αναδιάταξη των φλιπ-φλοπ της αλυσίδας ανίχνευσης. Αν η αναδιάταξη των φλιπ-φλοπ γίνει με βάση τη συχνότητα αλλαγών κατάστασης γειτονικών φλιπ-φλοπ τότε επιτυγχάνεται και μείωση της κατανάλωσης ισχύος. Όσον αφορά τις τεχνικές ενσωματωμένου αυτοελέγχου, μελετήθηκε το πρόβλημα της εμφώλευσης διανυσμάτων δοκιμής. Προτάθηκαν αποδοτικά κυκλώματα παραγωγής διανυσμάτων δοκιμής βασισμένα σε ολισθητές γραμμικής ανάδρασης και δέντρα πυλών XOR και σε ολισθητές συνδυασμένους με δέντρα πυλών OR. Όταν τα κυκλώματα υπό έλεγχο είναι κανονικής μορφής όπως είναι οι αθροιστές του αριθμητικού συστήματος υπολοίπων, προτείνονται κυκλώματα που εκμεταλεύονται την κανονική μορφή του συνόλου δοκιμής. Τέλος, σε περιβάλλον εξωτερικού ελέγχου, προτείνονται μέθοδοι αναδιάταξης διανυσμάτων δοκιμής με επανάληψη διανυσμάτων που μειώνουν την κατανάλωση. Οι μέθοδοι αυτές βασίζονται στην επιλογή των κατάλληλων ελάχιστων γεννητικών δέντρων και στη μετατροπή των κατάλληλων επαναλαμβανόμενων διανυσμάτων επιτυγχάνοντας σημαντική μείωση στην κατανάλωση ενέργειας, στη μέση και στη μέγιστη κατανάλωση ισχύος. / The dissertation is focused on VLSI testing while power dissipation is also taken into account. The techniques proposed are: a) test data compression in an embedded test environment, b) test set embedding in a built-in self test environment and c) reduction in test power dissipation in an external testing environment. Test data compression is based on the observation that a test vector can be produced from the previous one by replacing some parts of the previous vector with new parts of the current vector. The compression is even higher when the test vectors are ordered and scan cell reordering is also performed. If the scan cell reordering is based on a transition frequency approach then reduction in power dissipation is also achieved. In the case of built-in self test the problem of test set embedding was studied and efficient circuits based on linear feedback shift registers combined with XOR trees or shift registers combined with OR trees were proposed. If the circuits have a regular structure, such as the structure of residue number system adders, then a circuit taking advantage of the regular form of the test set can be derived. Finally, when external testing is considered, we proposed test vector ordering with vector repetition methods, which reduce power consumption. The methods are based on the selection of the appropriate minimum spanning trees and through the modification of the repeated vectors they achieve considerable savings in energy, average and peak power dissipation.

Το ερευνητικό αντικείμενο της συγκεκριμένης διατριβής αναφέρεται στην επεξεργασία έγχρωμης εικόνας με χρήση της θεωρίας γράφων, την ανάκτηση εικόνας καθώς και την οργάνωση / διαχείριση βάσεων δεδομένων με μεθόδους γραφημάτων και αναγνώρισης προτύπων, με εφαρμογή σε πολυμέσα. Τα συγκεκριμένα προβλήματα προσεγγίστηκαν διατηρώντας τη γενικότητά τους και επιλύθηκαν με βάση τα ακόλουθα σημεία: 1. Ανάπτυξη τεχνικών για την επιλογή χαρακτηριστικών από τις εικόνες βάσει χαρακτηριστικών χαμηλού επιπέδου (χρώματος και υφής), για χρήση τους σε εφαρμογές ομοιότητας και ανάκτησης εικόνας. 2. Υπολογισμός μετρικών και αποστάσεων στο χώρο των χαρακτηριστικών. 3. Μελέτη της πολυσχιδούς δομής των εικόνων μιας βάσης στο χώρο των χαρακτηριστικών. 4. Ελάττωση της διάστασης του χώρου και παραγωγή αναπαραστάσεων δύο διαστάσεων. 5. Εφαρμογή των μεθόδων αυτών σε υποκειμενικές αποστάσεις εικόνων. Η θεωρία γράφων και οι μέθοδοι αναγνώρισης προτύπων χρησιμοποιήθηκαν προκειμένου να παρουσιαστούν βέλτιστες λύσεις αφενός στο πρόβλημα της ανάκτησης εικόνων από βάσεις δεδομένων και αφετέρου στην οργάνωση και διαχείριση τέτοιων βάσεων εικόνων. Η διατριβή φέρνει πιο κοντά την επεξεργασία εικόνας με μεθόδους προερχόμενες από τη θεωρία γραφημάτων, τη στατιστική και την αναγνώριση προτύπων. Σε όλη τη διάρκεια της διατριβής, ιδιαίτερη έμφαση δόθηκε στο ζήτημα της εύρεσης του κατάλληλου συνδυασμού μεταξύ της αποτελεσματικότητας των συστημάτων και της αποδοτικότητας στα πλαίσια της εφαρμογής των προτεινόμενων αλγοριθμικών διαδικασιών. Τα αναλυτικά πειραματικά αποτελέσματα που πραγματοποιήθηκαν, αποδεικνύουν την βελτιωμένη απόδοση των προτεινόμενων μεθοδολογιών. / The subject of this doctoral thesis is related to color image processing using graph theoretic methods, image retrieval and image database management and organization in the reduced feature space, using pattern recognition analysis, with multimedia applications. The author attempted to approach the thesis subject by retaining its genericness and addressing the following points: 1. Development of techniques for extraction of image visual attributes based on low level features (color and texture information), to be used for image similarity and retrieval practices. 2. Calculation of metrics and distances in the feature space. 3. Study of the image manifolds created in the selected feature space. 4. Application of dimensionality reduction techniques and production of biplots. 5. Application of the proposed methodologies using perceptual image distances. Graph theory and pattern recognition methodologies were incorporated in order to provide novel solution to color image retrieval of image databases, as well as to image database management and organization. The current thesis brings closer image processing with graph theoretic methodologies, statistical analysis and pattern recognition. Throughout the thesis, consideration has been taken for finding the best trade off between effectiveness and efficiency when applying the proposed algorithmic procedures. The extended experimental results carried out in all stages of the projected studies reveal the enhanced performance of the proposed methodologies.