Αλγόριθμοι Ελαχιστοποίησης Μη Πλήρως Ορισμένων Λογικών Συναρτήσεων

Abstract

Η συνεχής πρόοδος και οι αυξανόμενες απαιτήσεις στη σχεδίαση κυκλωμάτων πολύ μεγάλης κλίμακας ολοκλήρωσης (Very Large Scale Integration - VLSI) οδηγούν στην αποκλειστική χρήση εργαλείων σχεδίασης με τη βοήθεια υπολογιστή (Computer Aided Design - CAD) για την ελαχιστοποίηση λογικών συναρτήσεων. Στην παρούσα διδακτορική διατριβή εξετάζονται μέθοδοι ελαχιστοποίησης λογικών εκφράσεων σε μορφή αποκλειστικού-ή αθροίσματος από γινόμενα (Exclusive-or Sum Of Products - ESOP) και σε μορφή αποκλειστικού-ή αθροίσματος από σύνθετους όρους (Exclusive-or Sum of Complex Terms - ESCT). Οι συναρτήσεις που μελετώνται είναι μη πλήρως ορισμένες συναρτήσεις με πολλές εξόδους (multiple-output incompletely specified functions). Επίσης προτείνεται μια μέθοδος εύρεσης ακριβών (exact) ESOP εκφράσεων για μη πλήρως ορισμένες συναρτήσεις με 6 το πολύ εισόδους. Τέλος παρουσιάζεται ένας κβαντικός αλγόριθμος για την ESOP και ESCT ελαχιστοποίση, χρησιμοποιώντας κβαντικούς υπολογιστές (quantum computers). Οι αλγόριθμοι που παρουσιάζονται στην διατριβή δίνουν καλύτερα πειραματικά αποτελέσματα σε σχέση με παλαιότερους που αναφέρονται στη βιβλιογραφία.