Αλγόριθμοι ελαχιστοποίησης μη πλήρως ορισμένων λογικών συναρτήσεων
Authors: Καλαθάς Μάριος 
Published: January 2014

Στην παρούσα διδακτορική διατριβή εξετάζονται μέθοδοι ανάλυσης και βελτιστοποίησης λογικών εκφράσεων σε μορφή αποκλειστικού-ή αθροίσματος από γινόμενα (Exclusive-Or Sum of Products - ESOP) και αποκλειστικού-ή αθροίσματος από σύνθετους όρους (Exclusive-or Sum of Complex Terms - ESCT). Οι συναρτήσεις που μελετώνται περιέχουν αδιάφορους όρους (don’t cares), πρόκειται δηλαδή για μη πλήρως ορισμένες συναρτήσεις (incompletely specified functions). Η βελτιστοποίησή τους έγκειται στην εύρεση ελάχιστων εκφράσεων, δηλαδή εκφράσεων με όσο το δυνατόν λιγότερους όρους. Αξίζει να σημειωθεί ότι τα προβλήματα της ελαχιστοποίησης εκφράσεων ESOP και ESCT είναι από τη φύση τους εξαιρετικά δύσκολα, καθώς στη γενική μορφή τους είναι NP-hard. Η ύπαρξη αδιάφορων όρων δυσχεραίνει ακόμα περισσότερο την εύρεση ελάχιστων εκφράσεων. Καταρχήν μας ενδιαφέρει η ελαχιστοποίηση εκφράσεων ESOP. Αρχικά προτείνεται ένας ευριστικός αλγόριθμος για την παραγωγή και την ελαχιστοποίηση τέτοιων εκφράσεων για τυχαίες μη πλήρως ορισμένες λογικές συναρτήσεις πολλών εξόδων. Αυτός ο αλγόριθμος χρησιμοποιεί αποσύνθεση συναρτήσεων και λογική πολλαπλών τιμών και η αποτελεσματικότητά του μετράται χρησιμοποιώντας συγκεκριμένες μετροσυναρτήσεις (benchmark functions). ΄Οπως μπορούμε να δούμε από τα πειραματικά αποτελέσματα, παρουσιάζει καλύτερη απόδοση από προηγούμενους αλγόριθμους. Στη συνέχεια της διατριβής, προτείνεται μια μέθοδος για την εύρεση μιας ακριβούς έκφρασης ESOP για τυχαίες μη πλήρως ορισμένες συναρτήσεις με 6 το πολύ μεταβλητές. Για να το επιτύχουμε αυτό, αποθηκεύουμε σε ένα συμπιεσμένο πίνακα το βάρος όλων των συναρτήσεων 5 μεταβλητών. Στην προσέγγισή μας χρησιμοποιούμε εκτεταμένα αυτόν τον πίνακα, ώστε να επιταχύνουμε το χρόνο εκτέλεσης. Με βάση όσα γνωρίζουμε, αυτός είναι ο πρώτος αλγόριθμος που αντιμετωπίζει αυτό το πρόβλημα. Στη συνέχεια, παρουσιάζεται η δυνατότητα χρησιμοποίησης σύνθετων όρων (complex terms), για την παραγωγή εκφράσεων που είναι πιο συμπαγείς από τις αντίστοιχες ESOP (δηλαδή αποτελούνται από μικρότερο αριθμό όρων). Σε αυτή την περίπτωση δεν επιτρέπεται μόνο η πράξη AND μεταξύ δύο μεταβλητών, αλλά οποιαδήποτε λογική συνάρτηση. Οι εκφράσεις που παράγονται είναι οι προαναφερόμενες εκφράσεις ESCT. Ερευνάται, έπειτα, το πρόβλημα της αποσύνθεσης, απεικόνισης και ελαχιστοποίησης των λογικών συναρτήσεων πολλών εξόδων, σε μορφή εκφράσεων ESCT. Πρώτα παρουσιάζεται ένας μαθηματικός φορμαλισμός για τις λογικές συναρτήσεις μιας εξόδου και έπειτα επεκτείνεται για συναρτήσεις πολλών εξόδων. Επίσης, παρουσιάζεται ένας καινούριος ευριστικός αλγόριθμος για την ελαχιστοποίηση εκφράσεων ESCT για μη πλήρως ορισμένες συναρτήσεις πολλών εξόδων. Ο αλγόριθμος αυτός αποτελεί επέκταση του προηγούμενου για τις εκφράσεις ESOP. Δίνονται πειραματικά αποτελέσματα, που υποδεικνύουν την ανωτερότητα αυτού του αλγορίθμου, όταν συγκρίνεται με προηγούμενους, για μη πλήρως ορισμένες συναρτήσεις και την εκμετάλλευση των αδιάφορων όρων που επιτυγχάνεται. Τέλος, η παρούσα διδακτορική διατριβή παρουσιάζει έναν κβαντικό αλγόριθμο για την εύρεση ελάχιστων εκφράσεων ESOP ή ESCT για τυχαίες μη πλήρως ορισμένες συναρτήσεις. Ο προτεινόμενος αλγόριθμος εκμεταλλεύεται τον έμφυτο μαζικό παραλληλισμό των κβαντικών κυκλωμάτων, ώστε να επιτύχει καλύτερη πολυπλοκότητα από τους συμβατικούς αλγόριθμους. Οι προτεινόμενες εκφράσεις αποκλειστικού-ή (XOR), όπως οι ESOP και οι ESCT, μπορούν να χρησιμοποιηθούν για να υλοποιήσουν μια τυχαία λογική συνάρτηση σε ένα αντιστρέψιμο ή ακόμα και σε ένα κβαντικό κύκλωμα.