| With the growing complexity of VLSI circuits, automatic synthesis of digital circuits has gained increasing importance. The synthesis process transforms an abstract representation of a circuit into an implementation in a target technology optimizing some objective function. One of the key steps in this process is logic synthesis, which produces an optimal gate level design from a register-transfer level description.; In this thesis, we describe a multi-level logic synthesis approach based on function decomposition. In particular, we present Boolean methods for extracting common subfunctions from multiple-output Boolean functions under different objectives including area, delay, energy, and energy-delay product. The extraction problem is cast as an encoding problem and a number of encoding methods are proposed. These methods include column encoding, shared subfunction encoding, and a graph-based approach for extracting logic with a large number of supporting variables. We use ordered binary decision diagrams to represent Boolean functions so that this approach can be implemented more efficiently.; Application of these methods to the synthesis of look-up table (LUT)-based field programmable gate arrays (FPGAs) is presented next. In many instances, we had to adapt the proposed extraction techniques to the FPGA architecture. For example, we used a two-layer decomposition technique to map to Xilinx XC4000 device and used variable input-size decomposition to map to Xilinx XC5000 device. These techniques produce results which are much better than state-of-the-art techniques in terms of area, delay, and power. |
