National Technical University of Athens (NTUA)
Αλγόριθμοι ελαχιστοποίησης μη πλήρως ορισμένων λογικών συναρτήσεων
Abstract
dc:descriptionVarious 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.
Degree
thesis:*- Grantor dc:publisher
- National Technical University of Athens (NTUA)
- Year dc:date
- 2011
Author and committee
dc:creator, dc:contributor.*- Authors dc:creator
-
- Kalathas, Marios
- Καλαθάς, Μάριος
Subjects
dc:subject × 16- Ακριβής ελαχιστοποίηση
- Ευριστική ελαχιστοποίηση
- Εκφράσεις αποκλειστικού ή αθροίσματος γινομένων
- Εκφράσεις αποκλειστικού ή αθροίσματος σύνθετων όρων
- Κβαντικοί αλγόριθμοι
- Κβαντικοί υπολογιστές
- Exact minimization
- Heuristic minimization
- ESOP expressions
- ESCT expressions
- Quantum algorithms
- Quantum computers
- Επιστήμες Μηχανικού και Τεχνολογία
- Επιστήμη Ηλεκτρολόγου Μηχανικού, Ηλεκτρονικού Μηχανικού, Μηχανικού Η/Υ
- Engineering and Technology
- Electrical Engineering, Electronic Engineering, Information Engineering
Rights
- Language dc:language
- gre
Identifiers
dc:identifier.*- Identifier
- 10.12681/eadd/24780