Ελαχιστοποίηση εκφράσεων "αποκλειστικού ή"

Abstract

Our times are characterized by the invasion of computers and the embedded systems in our life. Electronic devices are shrinking, they become faster and require smaller amounts of power for their operation. This situation leads to the reduction of the size of integrated circuits which form the basic parts for building electric devices. This thesis deals with minimizing logic expressions using the eXclusive OR logical operation (XOR). More specifically it deals with minimizing the number of terms inside these expressions. A logic circuit is a practical implementation of such an expression. This way, this thesis tries to contribute to the problem of improving logic circuits. The most famous of those expressions is the so called ESOP expression (Exclusive or Sum Of Products), where a logic function is expressed as an Exclusive OR sum of logic products. The main contribution of this thesis lies in minimizing ESCT expressions (Exclusive or Sum of Complex Terms). These expressions are a superset of ESOP, since their terms are called complex and can include not only the logic AND function but logic OR and XOR as well, between the variable literals. The importance of the aforementioned expressions is enhanced by the fact that they can be, trivially, mapped to reversible architectures. A reversible circuit has smaller thermal dissipation than its conventional counterpart since it loses no power due to information loss. That is the reason they are thought to be the future in logic design. One additional important advantage is that they can be used to synthesize quantum circuits. This thesis deals with the theoretical background of minimizing ESOP and ESCT expressions. Theorems are presented which indicate a methodology for finding minimal ESCT and ESCT expressions for any fully defined single output Boolean function but with restrictions on the number of its input variables or the number or terms in its minimal expressions. Those conclusions are, also, used for heuristic minimization for functions that do not conform to the previous limitations. They are also extended for incompletely specified multi output Boolean functions. The practical algorithms that are implemented as a result of this research are compared to algorithms from the international bibliography and their results indicate their effectiveness. Lastly, some of the theoretical results are extended in the field of quantum computations. We propose quantum algorithms for exact ESOP and ESCT minimization and these algorithms show the advantage of a quantum computer over its classical counterpart for difficult computational problems.

Η σημερινή εποχή χαρακτηρίζεται από την εισβολή των ηλεκτρονικών υπολογιστών και των ενσωματωμένων συστημάτων σε κάθε πτυχή της ζωής μας. Οι ηλεκτρονικές συσκευές, συνεχώς, συρρικνώνονται, γίνονται ταχύτερες ενώ απαιτούν όλο και μικρότερα ποσά ενέργειας για τη λειτουργία τους. Η κατάσταση αυτή οδηγεί, μοιραία, και στη μείωση του μεγέθους των ολοκληρωμένων κυκλωμάτων των βασικών, δηλαδή, δομικών στοιχείων των σύγχρονων ηλεκτρονικών συσκευών. Η παρούσα διδακτορική διατριβή ασχολείται με την ελαχιστοποίηση λογικών εκφράσεων “αποκλειστικού ή” (XOR) για τυχαία λογική συνάρτηση, και πιο συγκεκριμένα με τη μείωση των όρων από τους οποίους αυτή αποτελείται. Ένα ολοκληρωμένο κύκλωμα αποτελεί την πρακτική υλοποίηση μιας τέτοιας λογικής έκφρασης. Κατά συνέπεια η διατριβή αυτή προσπαθεί να προσφέρει στο πρόβλημα της βελτιστοποίησης των λογικών κυκλωμάτων. Η πιο γνωστή τέτοια κατηγορία εκφράσεων είναι οι λεγάμενες εκφράσεις ESOP (Exclusive or Sum Of Products), όπου μια λογική συνάρτηση εκφράζεται ως άθροισμα XOR από λογικά γινόμενα. O κύριος στόχος της διατριβής είναι η ελαχιστοποίηση εκφράσεων ESCT (Exclusive or Sum of Complex Terms), οι οποίες μπορούν να θεωρηθούν ως επέκταση των ESOP, αφού πλέον οι όροι ονομάζονται σύνθετοι (complex terms) και δεν περιλαμβάνουν μόνο τη λογική πράξη ΚΑΙ ανάμεσα στις μεταβλητές αλλά εν γένει οποιαδήποτε λογική πράξη (συνάρτηση δύο εισόδων μιας εξόδου). Η σημασία των παραπάνω εκφράσεων τονίζεται και από το γεγονός ότι μπορούν, με τετριμμένο τρόπο, να απεικονισθούν σε αντιστρέψιμες αρχιτεκτονικές. Ένα αντιστρέψιμο λογικό κύκλωμα έχει μικρότερες απώλειες ενέργειας σε σχέση με ένα τυπικό λογικό κύκλωμα και για το λόγο αυτό η σύνθεση αντιστρέψιμων κυκλωμάτων θεωρείται το μέλλον στη λογική σχεδίαση. Ένα ακόμα σημαντικό τους πλεονέκτημα είναι ότι μπορούν να χρησιμοποιηθούν και για τη σύνθεση κβαντικών κυκλωμάτων. Η διατριβή ασχολείται, καταρχήν, με το θεωρητικό υπόβαθρο της ελαχιστοποίησης τέτοιων εκφράσεων. Αποδεικνύονται θεωρήματα τα οποία υποδεικνύουν μια μεθοδολογία για την εύρεση ελάχιστης ESOP ή ESCT έκφρασης για οποιαδήποτε πλήρως ορισμένη λογική συνάρτηση μοναδικής εξόδου αλλά με περιορισμό ως προς τον αριθμό των όρων σε μια ελάχιστη έκφρασή της ή με περιορισμό ως προς τον αριθμό των μεταβλητών εισόδου της. Γίνεται επιπλέον μελέτη πως τα παραπάνω συμπεράσματα μπορούν να χρησιμοποιηθούν για ευριστική ελαχιστοποίηση συναρτήσεων που δεν εμπίπτουν στους παραπάνω περιορισμούς. Στη συνέχεια τα παραπάνω πορίσματα επεκτείνονται, ευριστικά, για ατελώς ορισμένες λογικές συναρτήσεις πολλών εξόδων. Η παραπάνω θεωρητική μελέτη του προβλήματος ελαχιστοποίησης εκφράσεων αποκλειστικού ή χρησιμοποιείται για την υλοποίηση πρακτικών αλγορίθμων οι οποίοι, όπως φαίνεται και από τα πειραματικά αποτελέσματα, δίνουν καλύτερα αποτελέσματα από τους αντίστοιχους της διεθνούς βιβλιογραφίας. Τέλος κάποια από τα παραπάνω θεωρητικά πορίσματα επεκτείνονται στο χώρο των κβαντικών υπολογισμών. Προτείνονται κβαντικοί αλγόριθμοι που μπορούν να χρησιμοποιηθούν για την ακριβή ελαχιστοποίηση εκφράσεων “αποκλειστικού ή” και καταδεικνύουν τη σαφή υπεροχή των κβαντικών υπολογιστών έναντι των κλασικών τους αναλόγων.