Synthesis of power and delay optimized NIG structures

Padmanabhan Balasubramanian, D. A. Edwards

    Research output: Chapter in Book/Report/Conference proceedingConference contribution


    Structuring and mapping of a Boolean function is an important problem in the design of digital combinatorial circuits. Library aware constructive decomposition offers a solution to this problem. Compact multi-level representation of binary networks, based on simple circuit structures, such as AND-Inverter Graphs (AIG) [1] [5], NAND graphs, OR-Inverter Graphs (OIG), AND-XOR-Inverter graphs, Reduced Boolean Circuits [8] does exist in literature. In this work, we discuss a novel efficient synthesis method for combinational logic circuits, represented using a NAND-Inverter Graph (NIG), which is composed of only two-input NAND (NAND2) and inverter (INV) cells. The networks are constructed on the basis of irredundant disjunctive normal forms, comprising terms with minimal cardinality. Construction of a NIG for a non-regenerative function in normal form would be straightforward, whereas for the opposite phase, it would be developed by considering a virtual instance of the function. However, the choice of best NIG for a given function would be based upon node count and cell count needed for actual implementation at the technology independent stage. We compare the power efficiency and delay improvement achieved by optimal NIGs over minimal AIGs and OIGs for some case studies. In comparison with functionally equivalent and redundant AIGs, NIGs report mean savings in power and delay of 33.76% and 18.57% respectively, after technology mapping with a 0.35 micron TSMC CMOS process. For a similar comparison with OIGs, NIGs demonstrate average savings in power and delay of 45.67% and 20.92% respectively. ©2007 IEEE.
    Original languageEnglish
    Title of host publicationCanadian Conference on Electrical and Computer Engineering|Can Conf Electr Comput Eng
    Number of pages3
    ISBN (Print)1424410215, 9781424410217
    Publication statusPublished - 2007
    Event2007 Canadian Conference on Electrical and Computer Engineering, CCECD - Vancouver, BC
    Duration: 1 Jul 2007 → …


    Conference2007 Canadian Conference on Electrical and Computer Engineering, CCECD
    CityVancouver, BC
    Period1/07/07 → …


    • AIG
    • Boolean function
    • Delay optimization
    • Low power design
    • NAND-Invert graph (NIG)


    Dive into the research topics of 'Synthesis of power and delay optimized NIG structures'. Together they form a unique fingerprint.

    Cite this