Sponsor
Portland State University. Department of Electrical Engineering
First Advisor
Marek A. Perkowski
Term of Graduation
Spring 1997
Date of Publication
6-2-1997
Document Type
Thesis
Degree Name
Master of Science (M.S.) in Electrical and Computer Engineering
Department
Electrical Engineering
Language
English
Subjects
Decomposition method, Mappings (Mathematics), Map-coloring problem
DOI
10.15760/etd.7701
Physical Description
1 online resource (viii, 142 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 MVGUD which was developed at Portland State University. Extensive testing of MVGUD with these graph coloring and multi-coloring programs has been done in this thesis. MVGUD 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).
Persistent Identifier
https://archives.pdx.edu/ds/psu/36718
Recommended Citation
Malvi, Rahul, "The Column Multiplicity Problem in Decomposition of Functions and Relations" (1997). Dissertations and Theses. Paper 5830.
https://doi.org/10.15760/etd.7701
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.