First Advisor

Marek A. Perkowski

Date of Publication

12-11-1995

Document Type

Thesis

Degree Name

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

Department

Electrical Engineering

Language

English

Subjects

Computer algorithms

DOI

10.15760/etd.7034

Physical Description

1 online resource (2, ix, 99 p.)

Abstract

In order to achieve superior speed in sequencer designs over competing PLD devices, Cypress brought to market an innovative architecture, CY7C361. This architecture introduced a new kind of universal logic gate, the CONDITION DECODER (CDEC). Because there are only 32 macrocells in the chip, saving only one CDEC gate can be quite important (the well-known "fit/no-fit problem"). A problem that is related to the fitting problem of the Cypress CY7C361 chip is the SOC Minimization. Due to the limited low number of macrocells in CY7C361, a high quality logic minimization to reduce the number of macrocells is very important. The goal of this thesis is, however, more general, since we believe that CDEC can be used as a generalpurpose gate for standard cell structures with few levels, and also for new PLD structures. We depart, therefore, from the Cypress chip as a sole motivation of our work, and we present a generic logic synthesis problem of SOC minimization. In this thesis, we formulate the SOC minimization problem and present a new kind of approach using graph coloring to solve it. A Cube Splitting algorithm is also presented, whereby the input cubes are split in such a way, that the generated cubes are lower in number than the minterms, and when these cubes are used as nodes in graph coloring algorithm, gives near exact solutions. The algorithms used in the SOC minimization program, SOCMIN, have been designed for Strongly Unspecified functions, defined by ON and OFF sets, and hence finds important applications for Machine Learning and Pattern theory, where there is a high percent of don't cares. The approach to solving the covering problem, the Conditional Graph Coloring, can be used in other similar problems such as PLA minimization, or Column Minimization Problem in Curtis-like decomposition of Multi-valued Relations. We found also the Muller method very efficient for ON,OFF data representation: it can be used to extend any other single-output minimizer for incomplete functions to a multi-output one.

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

Download

Share

COinS