A design method for look-up table type FPGA by pseudo-Kronecker expansion

Author

Sasao, Tsutomu ; Butler, Jon T.

Author_Institution

Kyushu Inst. of Technol., Iizuka, Japan

fYear

1994

fDate

25-27 May 1994

Firstpage

97

Lastpage

106

Abstract

In FPGA design, interconnections are often more expensive than logic. FPGAs using 3-input lookup tables (LUTs) require many logical levels and complex interconnections. On the other hand, FPGAs using 6-input LUTs require fewer interconnections and fewer logical levels. We show a method to represent logic functions by using pseudo-Kronecker diagrams (PKDD´s). Experimental results show that 2-valued PKDDs require 29% fewer nodes than BDDs, and 4-valued PKDDs require 23% fewer than QDDs, the 4-valued extension of BDDs. Thus, this method is useful for the design of FPGAs with 6-input LUTs. However, when LUTs have less than 6-inputs, this method is not applicable

Keywords

logic arrays; logic design; many-valued logics; table lookup; 2-valued PKDDs; 4-valued PKDDs; design method; interconnections; logic functions; logical levels; look-up table type FPGA; pseudo-Kronecker expansion; Delay effects; Design methodology; Field programmable gate arrays; Integrated circuit interconnections; Logic circuits; Logic functions; Propagation delay; Prototypes; Table lookup; Wiring;

fLanguage

English

Publisher

ieee

Conference_Titel

Multiple-Valued Logic, 1994. Proceedings., Twenty-Fourth International Symposium on

Conference_Location

Boston, MA

Print_ISBN

0-8186-5650-6

Type

conf

DOI

10.1109/ISMVL.1994.302215

Filename

302215