First Advisor

Marek A. Perkowski

Date of Publication

8-10-1992

Document Type

Thesis

Degree Name

Master of Science (M.S.) in Electrical and Computer Engineering

Department

Electrical Engineering

Language

English

Subjects

Functions -- Computer programs, Computer algorithms, Computer programs

DOI

10.15760/etd.6568

Physical Description

1 online resource (3, xii, 103 p.)

Abstract

In recent years, there is an increased interest in the design of logic circuits which use EXOR gates. Particular interest is in the minimization of arbitrary Exclusive Sums Of Products (ESOPs). Functions realized by such circuits can have fewer gates, fewer connections, and take up less area in VLSI and especially, FPGA realizations. They are also easily testable. So far, the ESOPs are not as popular as their Sum of Products (SOP) counterparts. One of the main reasons it that the problem of the minimization of ESOP circuits was traditionally an extremely difficult one. Since exact solutions can be practically found only for functions with not more than 5 variables the interest is in approximate solutions. Two approaches to generate s~b optimal solutions can be found in the literature. One approach is to minimize sub-families of ESOPs. Another approach is to minimize ESOPs using heuristic algorithms. The method we introduced in this thesis belongs to the second approach, which normally generates better results than the first approach. In the second approach, two general methods are used. One method is to minimize the coefficients of Reed-Muller forms. Another method is to perform a set of cube operations iteratively on a given ESOP. So far, this method has achieved better results than other methods. In this method (we call it cube operation approach), the quality of the results depends on the quality of the cube operations. Different cube operations have been invented in the past a few years. All these cube operations can be applied only when some conditions are satisfied. This is due to the limitations of the operations. These limitations reduce the opportunity to get a high quality solution and reduce the efficiency of the algorithm as well. The efforts of removing these limitations led to the invention of our new cube operation, exorlink, which is introduced in this thesis. Exorlink can be applied on any two cubes in the array without condition. All the existing cube operations in this approach are included in it. So this is the most general operation in this approach. Another key issue in the cube operation approach is the efficiency of the algorithm. Existing algorithms perform all possible cube operations, and give litter guide to select the operations. Our new algorithm selectively performs some of the possible operations. Experimental results show that this algorithm is more efficient than existing ones. New algorithms to minimize multiple output functions and especially incompletely specified ESOPs are also presented. The algorithms are included in the program EXORCISM-MV -2, which is a new version of EXORCISM-MY. EXORCISM-MV -2 was tested on many benchmark functions and compared to the results from literature. The program in most cases gives the same or better solutions on binary and 4-valued completely specified functions. More importantly, it is able to efficiently minimize arbitrary-valued and incompletely specified functions, while the programs from literature are either for completely specified functions, or for binary variables. Additionally, as in Espresso, the number of variables in our program is unlimited and the only constraint is the number of input cubes that are read, so very large functions can be minimized. Based on our new cube operation and new algorithms, in the thesis, we present a solution to a problem that has not yet been practically solved in the literature: efficient minimization of arbitrary ESOP expressions for multiple-output multiple-valued input incompletely specified functions.

Rights

In Copyright. URI: http://rightsstatements.org/vocab/InC/1.0/ This Item is protected by copyright and/or related rights. You are free to use this Item in any way that is permitted by the copyright and related rights legislation that applies to your use. For other uses you need to obtain permission from the rights-holder(s).

Comments

If you are the rightful copyright holder of this dissertation or thesis and wish to have it removed from the Open Access Collection, please submit a request to pdxscholar@pdx.edu and include clear identification of the work, preferably with URL

Persistent Identifier

https://archives.pdx.edu/ds/psu/27319

Download

Share

COinS