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

Abstract

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