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

fYear

1992

fDate

7-10 Sep 1992

Firstpage

230

Lastpage

235

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;

fLanguage

English

Publisher

ieee

Conference_Titel

Design Automation Conference, 1992., EURO-VHDL '92, EURO-DAC '92. European

Conference_Location

Hamburg

Print_ISBN

0-8186-2780-8

Type

conf

DOI

10.1109/EURDAC.1992.246238

Filename

246238