Back to search

National Technical University of Athens (NTUA)

Αλγόριθμοι ελαχιστοποίησης μη πλήρως ορισμένων λογικών συναρτήσεων

Abstract

dc:description

Various 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

Rights

Language dc:language
gre

Identifiers

dc:identifier.*
Identifier
10.12681/eadd/24780

Chain of custody

source
Harvested from
Greek National Archive of PhD Theses
Base URL
phdtheses.ekt.gr/eadd_oai/request
Last updated
2026-11-18
Source record
OAI-PMH GetRecord
citation

Kalathas, Marios; Καλαθάς, Μάριος. Αλγόριθμοι ελαχιστοποίησης μη πλήρως ορισμένων λογικών συναρτήσεων. National Technical University of Athens (NTUA), 2011. http://hdl.handle.net/10442/hedi/24780