During the last few years Field Programmable Gate Arrays (FPGAs) have
become increasingly important. Thanks to recent breakthroughs in
technology, FPGAs offer millions of system gates at low cost and
considerable speed.
Functional decomposition has emerged as an essential technique in
automatic logic synthesis for FPGAs. Functional decomposition as a
technique to find realizations for Boolean functions was already
introduced in the late fifties and early sixties by Ashenhurst, Curtis,
Roth and Karp. In recent years, however, it has attracted a great deal
of renewed attention, for several reasons. First, it is especially well
suited for the synthesis of lookup-table based FPGAs. Also, the
increased capacities of today's computers as well as the development of
new methods have made the method applicable to larger-scale problems.
Modern techniques for functional decomposition profit from the success
of Reduced Ordered Binary Decision Diagrams (ROBDDs), data structures
that provide compact representations for many Boolean functions
occurring in practical applications. We have now seen the development of
algorithms for functional decomposition which work directly based on
ROBDDs, so that the decomposition algorithm works based on compact
representations and not on function tables or decomposition matrices as
in previous approaches.
The book presents, in a consistent manner, a comprehensive presentation
of a multitude of results stemming from the author's as well as various
researchers' work in the field. Apart from the basic method, it also
covers functional decomposition for incompletely specified functions,
decomposition for multi-output functions and non-disjoint
decomposition.
Functional Decomposition with Application to FPGA Synthesis will be of
interest both to researchers and advanced students in logic synthesis,
VLSI CAD, and Design Automation as well as professionals working in FPGA
design and the development of algorithms for FPGA synthesis.