Title :
A new approach to the decomposition of incompletely specified multi-output functions based on graph coloring and local transformations and its application to FPGA mapping
Author :
Wan, Wei ; Perkowski, Marek A.
Author_Institution :
Dept. of Electr. Eng., Portland State Univ., OR, USA
Abstract :
An approach to the decomposition of incompletely specified Boolean functions is introduced, and its application to lookup-table-based field programmable gate array (FPGA) mapping is described. Three methods are developed: fast graph coloring to perform a quasi-optimum `don´t care´ assignment; variable partitioning to quickly find the `best´ partitions; and local transformation to transform a nondecomposable function into several decomposable ones. The methods perform global optimization of the input function. A short description of a FPGA mapping program (TRADE) and an evaluation of its results are provided
Keywords :
Boolean functions; circuit layout CAD; graph colouring; logic CAD; logic arrays; table lookup; Boolean functions; FPGA mapping; TRADE; decomposition; graph coloring; incompletely specified multi-output functions; local transformations; lookup-table-based field programmable gate array; nondecomposable function; variable partitioning; Boolean functions; Circuits; Electronics packaging; Field programmable gate arrays; Input variables; Libraries; Logic; Network synthesis; Optimization methods; Table lookup;
Conference_Titel :
Design Automation Conference, 1992., EURO-VHDL '92, EURO-DAC '92. European
Conference_Location :
Hamburg
Print_ISBN :
0-8186-2780-8
DOI :
10.1109/EURDAC.1992.246238