Research related to the design of logic circuits, both combinational and sequential, has been very productive. The variety of integrated chips (ICs) available to realize combinational functions is fairly large and ranges from basic gates to multiplexers, programmable logic arrays (PLAs), and so on. This variety has given rise to many computer-aided design algorithms, which are scattered in research journals but only sporadically described in textbooks.

The currently popular IC in logic synthesis is the field-programmable gate array (FPGA) with look-up table (LUT). A K-input 1-output LUT can realize any Boolean function of up to K variables. This feature has spurred research activity, resulting in a vast literature on LUT FPGA-based algorithms. The authors have made a major contribution to the literature by writing this survey paper, summarizing the work done until very recently.

The authors concentrate on combinational logic design, not the sequential logic design for which some references are given in the text. The basic techniques are described using a coherent theoretical framework.

The synthesis is described in two steps, which involve logic optimization (transforming a gate-level network to a more suitable form) and technology mapping (in which the network is transformed for a target technology).

The paper begins with a section devoted to summarizing problem formulation and representation, which makes substantial use of graph theory. The representations include sum-of products and binary-decision diagrams. The next section, on logic optimization, describes techniques to transform a multilevel logic network into a form more suitable for FPGA. Next comes a section on technology mapping, which describes how the network obtained using the methods in the previous section is transformed into LUT FPGAs. The criteria used to do this include area, depth, and delay minimizations. This detailed section encapsulates all of the techniques available.

I highly recommend this paper for research students and for the curious. People starting to work on a research problem often need a concise survey paper that lists relevant publications. This paper fits the bill. For those in industry, it may prove to be a source of useful algorithms. The paper also helps theoreticians and practitioners appreciate the state of the art. My only concern is that this paper is not necessarily a tutorial, since it assumes a certain background.