First Advisor

Rolf Schaumann

Term of Graduation

Spring 1997

Date of Publication

6-1997

Document Type

Thesis

Degree Name

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

Department

Electrical Engineering

Language

English

Subjects

Decomposition method, Mapping (Mathematics), Map-coloring problem

Physical Description

online resource (vii, 140 pages)

Abstract

Finding the column multiplicity in Functional Decomposition has been known to be one of the most important problems to be solved in the process of functional decomposition of discrete functions. A lot of research has been done in this field with many new heuristics generated to find the column multiplicity, but there has not been an evaluation of the algorithms on the kinds of graphs that occur in decomposition and whether having an exact method to calculate the column multiplicity is useful from the overall design goals. The intent of this thesis was to investigate the column multiplicity problem, in order to find out how different heuristic algorithms compare with an exact algorithm for finding the column multiplicity, and to find out if an exact graph coloring is actually required or not. In order to investigate this problem of column multiplicity in functional decomposition, two graph coloring programs, and a multi-coloring program were written: one of the graph coloring programs is an exact graph coloring, the other graph coloring program and the multi-coloring program are both based on heuristic algorithms. The two graph coloring programs have been compared in this thesis on randomly generated graphs. These programs were incorporated into the multi-valued decomposer of functions and relations MVG UD which was developed at Portland State University. Extensive testing of MVG UD with these graph coloring and multi-coloring programs has been done in this thesis. MVG UD was tested on both circuit benchmarks and on machine learning benchmarks.

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

Share

COinS