Ελαχιστοποίηση εκφράσεων αποκλειστικού Ή - κβαντικοί αλγόριθμοι

Abstract

The current era in computer engineering, is characterized by the continuously increasing incorporation of computers and embedded systems in the all aspects of our daily life. The integrated circuits continuously shrink, become faster, require less energy with the help of new materials and architectures. As a result, the electronic appliances find more and more applications in all the aspects of our life and, as the time passes, they become an invisible and essential layer of interface with the environment. The research object with which deals the present thesis is the minimization of logic “eΧclusive OR” or (XOR) expressions for an arbitrary logic function, and more particularly, with the reduction of number of terms that constitute this function, as well as with the mapping of such expressions in architectures of new technologies such as quantum computers. An integrated circuit is the practical realization of such a logic expression. Accordingly, there is great effort for the optimization of logic circuits. The most popular such category of expressions is the so-called ESOP (Exclusive or Sum Of Products) expressions, where a logic function is expressed as XOR sum of products. Another more general category are the ESCT (Exclusive or Sum of Complex Terms) expressions, that can be considered as an extension of ESOPs, since the terms are now complex (complex terms) and do not include only the logic function AND between the variables, but also any logic function (of two inputs and one output). The importance of the above expressions is also stressed by the fact that they can, in a trivial manner, be mapped in reversible architectures. A reversible logic circuit has smaller losses of energy in comparison to a conventional circuit and for this reason the composition of reversible circuits is considered the future in the logic design. Another important advantage, is that they can be also used for the composition of quantum circuits. The minimization of these expressions as well as their quantum extensions are the main object of research in this thesis. This work deals firstly, with the theoretical background of the minimization of such expressions. Theorems are proved, which indicate a methodology for finding a minimal ESCT expression for any completely specified single output logic function, with the restriction of the number of terms in its minimal expression or with the restriction of the number of its input variables. Moreover, it is studied how the above conclusions can be used for heuristic minimisation of functions that do not fall in the above restrictions. Later on, the above conclusions are extended, heuristically, for incompletely specified multi-output logic functions. The above theoretical study of the problem of “exclusive or” minimization, is used for the realization of conventional and quantum algorithms which, as it appears also from the experimental results, give better results than the corresponding of the international bibliography. More specifically, the quantum algorithms that can be used for the exact minimization of “exclusive or” expressions, indicate the explicit supremacy of quantum computers against the conventional ones. Finally, we apply the above results in the field of encryption and secure computation. More specifically, the ESCT minimization algorithms are used to achieve up to 39% less cost of communication against the related corresponding efforts of bibliography.

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