A synthesis approach for a set of Boolean functions on table-lookup-based field programmable gate arrays is proposed. Synthesis is considered as a global problem and, therefore, includes suitable factorization techniques as well as decomposition methods relying on the factored form. The factorization step looks for lexicographical expressions of Boolean functions. Some trade-offs between a strict input-driven decomposition and a maximal cell filling strategy are presented. The approach is applied to the Xilinx XC3000 and XC4000 series. Decomposition techniques both for area and speed optimization are detailed and their performance is compared to all available performance results.>

This paper proposes a new type of expression for Boolean functions called lexicographical expressions. The basic idea is to impose an input ordering for factoring logical expressions. Several algebraic properties are presented and relations with classical algebraic theory are established. The main result is that all elementary factorizations defined by (Cokernel, Kernel) pairs "compatible" with an input order are all "algebraically compatible," i.e., are all parts of a single factorization of the function. Thus for a given input order a unique factorization is defined. This leads to fast division procedures. Basic techniques for obtaining lexicographical factorizations are presented. First, a precedence matrix and an updating procedure are defined and used later to select an input order and a corresponding compatible factorization. Second, a factorization technique respecting a fixed order is detailed. This method is then applied to multilevel synthesis using standard cells which was the original motivation of this work. The goal is to reduce wiring complexity. A lexicographical factorization leads to a wiring area reduction due to the structuring of the logic into layers in which the inputs enter the layout in the order given by the factorization. Experimental results comparing this approach to classical ones are given. These results include routing ratio measurements, routing structure observation, global area measurement and critical path estimation. All these results are analyzed after place and route, using an industrial tool (COMPASS Design Automation tool).>

A multilevel logic synthesis method based on standard cells and aiming at reducing both gate and wiring areas is presented. The goal is to decrease the routing factor which is defined as a ratio between the routing area and the gate area. The wiring is taken into account during the synthesis steps (factorization and technology mapping). The approach is based on a lexicographical expression of a Boolean function controlling the input dependency and on a kernel filtering controlling the excessive factorizations responsible for wiring complexity increase. >

A novel method for optimized multilevel synthesis of CMOS circuitry in terms of compiled cells is presented. A compiled cell is the implementation on silicon of a lexicographical factorized Boolean expression. How a compiled cell is obtained automatically from the Boolean expression (layout synthesis) is recalled, and the rewriting of Boolean functions in terms of compiled cells is addressed. This approach leads to a dense and regular layout by abutment of compiled cells. The wiring channels are thus suppressed.>