A Design Method for Look-up Table Type FPGA by Pseudo-Kronecker Expansion

• Main Authors: Sasao, Tsutomu, Butler, Jon T
• Other Authors: NAVAL POSTGRADUATE SCHOOL MONTEREY CA DEPT OF ELECTRICAL AND COMPUTER ENGINEERING
• Format: Text
• Language: English
• Published: 1994
• Subjects: Electrical and Electronic Equipment; Mfg & Industrial Eng & Control of Product Sys; *ARRAYS; *GATES(CIRCUITS); *PROTOTYPES; CHIPS(ELECTRONICS); PRODUCTION; FPGA(FIELD PROGRAMMABLE GATE ARRAYS); Orca
• Online Access: http://www.dtic.mil/docs/citations/ADA593069; http://oai.dtic.mil/oai/oai?&verb=getRecord&metadataPrefix=html&identifier=ADA593069

Field programmable gate arrays (FPGA's) are very useful in rapid prototyping as well as small volume production [3]. A look-up table (LUT) type FPGA shown in Fig. 1.1 consists of LUT's and programmable interconnection. Both LUT's and programmable inter- connections are controlled by static RAMs. We assume that each FPGA has q LUT's, and each LUT can realize an arbitrary logic function of k binary variables. We also assume that interconnection resources are sufficient, i.e., any logical network with q LUT's can be realized. Note that wiring is implemented by pass transistors, and the delay time for interconnection will often be larger than for the LUT's. Consider the realization of a moderately complex function. If k is small, e.g., k = 2 or 3, the LUT's are efficiently used, but the interconnections will be complex. This will be especially inefficient since interconnections are often more expensive than logic. If k is large, e.g., k = 7 or 8, the interconnections will be simpler, but the LUT's are not efficiently used. Thus, there exists an optimum value for k between 3 and 7. One study [20] shows that when k = 3 or 4, FPGA's require the smallest chip area. However, these results have not been used by manufacturers. For example, for the XILINX 4000 Series FPGA's, k = 5, and for the AT&T ORCA FPGA's, k = 6 [1]. Various design methods for LUT-based FPGA's are known: (1) Technology mapping from AND-OR multi-level logic circuits; (2) Technology mapping from binary decision diagrams (BDD's); and (3) Functional decomposition.