zbMATH — the first resource for mathematics

Functional decomposition with application to FPGA synthesis. (English) Zbl 0989.94003
Boston: Kluwer Academic Publishers. xxiii, 263 p. (2001).
The book is about functional decomposition of Boolean functions, a very essential technique in logic synthesis for lookup table based field programmable gate arrays (FPGA), which have become increasingly important during the last years. Functional decomposition was already introduced in the late fifties. However, it has attracted a great deal of renewed attention as nowadays FPGAs offer millions of gates at low cost and considerable speed thanks to recent breakthroughs in technology. The increased capacities of today’s computers as well as the development of new methods have made the method applicable for large-scale problems.
The book, which is a revised version of the very excellent PhD Thesis of the author, consists of 2 parts. One part (Chapter 2) concentrates on “do not care” assignment with respect to BDD minimization of incompletely specified functions by exploiting symmetries. The methods proposed go far beyond the approach proposed by Chang, Cheng, and Marek-Sadowska. The second part handles functional decomposition of single-output Boolean functions (Chapter 3) of incompletely specified Boolean functions (Chapter 5), and of multi-output Boolean functions (Chapter 4). In particular, the book demonstrates how symmetries of Boolean functions can be exploited to increase the potential of sharing common decomposition functions of multi-output Boolean functions.
The book comprises both investigations on the computational complexity of the problems and efficient algorithms and heuristics that solve the problems. It is an excellent book. I suppose that it is of interest to researchers, advanced students, and professionals working in electronic design automation.
Reviewer: P.Molitor (Halle)

94-02 Research exposition (monographs, survey articles) pertaining to information and communication theory
94C10 Switching theory, application of Boolean algebra; Boolean functions (MSC2010)