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.
| Identifer | oai:union.ndltd.org:pdx.edu/oai:pdxscholar.library.pdx.edu:open_access_etds-6230 |
| Date | 11 December 1995 |
| Creators | Mohamedsadakathulla, Sanof |
| Publisher | PDXScholar |
| Source Sets | Portland State University |
| Detected Language | English |
| Type | text |
| Format | application/pdf |
| Source | Dissertations and Theses |
Page generated in 0.0017 seconds