National Technical University of Athens (NTUA)
Ελαχιστοποίηση εκφράσεων "αποκλειστικού ή"
Abstract
dc:descriptionOur 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.
Degree
thesis:*- Grantor dc:publisher
- National Technical University of Athens (NTUA)
- Year dc:date
- 2008
Author and committee
dc:creator, dc:contributor.*- Authors dc:creator
-
- Voudouris, D.
- Βουδούρης, Δημήτριος
Subjects
dc:subject × 14- Ελαχιστοποίηση
- Σύνθετος όρος
- Αλγόριθμοι, Κβαντικοί
- MAITRA
- ESCT
- ESOP
- Complex term
- Reversible
- Quantum
- Wave cascade
- Επιστήμες Μηχανικού και Τεχνολογία
- Επιστήμη Ηλεκτρολόγου Μηχανικού, Ηλεκτρονικού Μηχανικού, Μηχανικού Η/Υ
- Engineering and Technology
- Electrical Engineering, Electronic Engineering, Information Engineering
Rights
- Language dc:language
- gre
Identifiers
dc:identifier.*- Identifier
- 10.12681/eadd/17014