Title :
Using decision diagrams to design ULMs for FPGAs
Author :
Zilic, Zeljko ; Vranesic, Zvonko G.
Author_Institution :
Dept. of Electr. & Comput. Eng., McGill Univ., Montreal, Que., Canada
fDate :
9/1/1998 12:00:00 AM
Abstract :
Many modern field programmable logic arrays (FPGAs) use lookup table (LUT) logic blocks which can be programmed to realize any function of a fixed number of inputs. It is possible to employ logic blocks that realize only a subset of all functions, while the rest can be obtained by permuting and negating the inputs such blocks, known as Universal Logic Modules (ULMs), have already been considered for application in FPGAs; we propose a new class of ULMs which is more useful in the FPGA environment. Methodology for systematic development of such blocks is presented, based on the BDD description of logic functions. We give an explicit construction of a three-input LUT replacement that requires only five programming bits, which is the optimum for such ULMs. A realistic size four-input LUT replacement is obtained which uses 13 programming bits
Keywords :
decision theory; field programmable gate arrays; formal logic; table lookup; BDD description; FPGAs; ULMs; Universal Logic Modules; decision diagrams; explicit construction; field programmable logic arrays; four-input LUT replacement; logic functions; lookup table logic blocks; programming bits; systematic development; three-input LUT replacement; Binary decision diagrams; Field programmable gate arrays; Helium; Logic arrays; Logic design; Logic functions; Pins; Programmable logic arrays; Routing; Table lookup;
Journal_Title :
Computers, IEEE Transactions on