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

Abstract

Various methods of analysis and optimization of logic expressions in the form of Exclusive-Or Sum of Products (ESOP) and Exclusive-or Sum of Complex Terms (ESCT) are presented in this PhD thesis. The functions considered contain don’t care terms, namely they are incompletely specified functions. Their optimization concerns the finding of minimal expressions, by that means expressions with the least possible number of terms. It should be highlighted that the problems of minimizing ESOP and ESCT expressions are by default extremely complex, since they are NP-hard. The existence of don’t care terms complicates even more the finding of exact expressions. Initially, we are interested in the minimization of ESOP expressions. First of all, we propose a heuristic algorithm for the generation and the minimization of such expressions for arbitrary multiple-output incompletely specified logic functions. This algorithm uses functional decomposition and multiple-valued logic and its efficiency is measured using standard benchmark functions. As we can observe from the experimental results, our algorithm presents with better performance compared to previous ones. Afterwards, we propose a method which finds an exact ESOP expression for arbitrary incompletely specified functions of up to 6 variables. To achieve that, we store the weight of all functions of 5 variables in a compressed table. In our approach, we use this table extensively, in order to decrease the execution time. To the best of our knowledge, this is the first algorithm dealing with this problem. Moreover, we present the possibility of using complex terms to generate more compact expressions (which are consisted of fewer terms) than the respective ESOP ones. In this case, not only the AND operation is permitted between two variables, but also any logic function. The produced expressions are the previously mentioned ESCT expressions. Additionally, we examine the problem of decomposition, mapping and minimization of multiple-output logic functions, in the form of ESCT expressions. Initially, a mathematical formulation for single output logic functions is presented, which is extended for multiple-output functions. Furthermore, we propose a naive heuristic algorithm to minimize ESCT expressions for multiple-output incompletely specified functions. This algorithm is an extension of the previous one for ESOP expressions. The experimental results presented indicate both the superiority of our algorithm compared to previous ones for completely specified functions, as well as the exploitation of the presence of don’t care terms achieved. Finally, this PhD thesis presents a quantum algorithm to find exact ESOP or ESCT expressions for arbitrary incompletely specified functions. The proposed algorithm exploits the inherent massive parallelism of quantum circuits, in order to achieve better complexity than the conventional ones. The suggested XOR expressions, such as ESOP and ESCT, might be used to implement an arbitrary logic function in a reversible, or even in a quantum circuit.

Στην παρούσα διδακτορική διατριβή εξετάζονται μέθοδοι ανάλυσης και βελτιστοποίησης λογικών εκφράσεων σε μορφή αποκλειστικού-ή αθροίσματος από γινόμενα (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, μπορούν να χρησιμοποιηθούν για να υλοποιήσουν μια τυχαία λογική συνάρτηση σε ένα αντιστρέψιμο ή ακόμα και σε ένα κβαντικό κύκλωμα.