First Advisor

Marek A. Perkowski

Date of Publication

10-17-1994

Document Type

Thesis

Degree Name

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

Department

Electrical Engineering

Language

English

Subjects

Computer algorithms, Logic circuits -- Design and construction, Kronecker products

DOI

10.15760/etd.6867

Physical Description

1 online resource (2, vii, 89 p.)

Abstract

Several classes of AND-EXOR circuit expressions have been defined and their relationship have been shown. A new class of AND-EXOR circuit, the Partially Mixed Polarity Reed-Muller Expression(PMPRM), which is a subclass of the Generalized Reed-Muller expression, is created, along with an efficient minimization algorithm. This new AND/EXOR circuit form has the following features: • Since this sub-family of ESOP (with a total of n2n-I22n-i - (n-1)2n forms which includes the 2n Fixed-Polarity Reed-Muller forms) is much larger than the Kronecker Reed-Muller(KRM) expansion(with 3n forms), generally the minimal form of this expansion will be much closer to the minimal ESOP than the minimal form of KRM expansion. • It is a sub-class of the Generalized Reed-Muller Expansion, thus has better testibility than other AND/EXOR circuits. Those design methods of easily testable GRM circuit networks[ 6] [35] can also be used for this new circuit form. • The exact solution to the minimization of this new expansion provides a upperbound for the minimization of ORM expansion. In this thesis, we prove that to calculate a PMPRM expansion from one of its adjacent polarity expansion , only one EXOR operation is needed. By calculating the adjacent polarity expansions one-by-one and searching all the PMPRM forms the minimum one can be found. A speedup approach allows us to find the exact minimum PMPRM without calculating all forms. The algorithm is explained by minimizing the 3-variable functions and is demonstrated by flow graphs. With the introduction of termwise complementary expansion diagram, a computerized algorithm for the calculation of any ORM expansion is presented. The exact minimum ORM form can be obtained by an exhaustive search through all ORM forms. A heuristic minimization algorithm, which is designed to decrease the time complexity of the exact one, is also presented in this thesis. Instead of depending on the number of input variables, the computation time of this quasi-minimum algorithm depends mainly on the complexity of the input functions, thus can solve much larger problems. The exact minimization algorithm for PMPRM and the quasi-minimum ORM minimization algorithm have been implemented in C programs and a set of benchmark functions has been tested. The results are compared to those from [16], [36], and Espresso's. In most cases our program gives the same or better solutions.

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/28939

Download

Share

COinS