Automated synthesis and optimization of multilevel logic circuits.

Wang, Lingli (2000) Automated synthesis and optimization of multilevel logic circuits. PhD thesis, Edinburgh Napier University.

Available under License Creative Commons Attribution Non-commercial.

Download (5MB) | Preview


    With the increased complexity of Very Large Scaled Integrated (VLSI) circuits, multilevel
    logic synthesis plays an even more important role due to its flexibility and compactness.
    The history of symbolic logic and some typical techniques for multilevel logic synthesis
    are reviewed. These methods include algorithmic approach; Rule-Based approach; Binary
    Decision Diagram (BDD) approach; Field Programmable Gate Array(FPGA) approach
    and several perturbation applications.
    One new kind of don't cares (DCs), called functional DCs has been proposed for multilevel
    logic synthesis. The conventional two-level cubes are generalized to multilevel cubes.
    Then functional DCs are generated based on the properties of containment. The concept
    of containment is more general than unateness which leads to the generation of new
    DCs. A separate C program has been developed to utilize the functional DCs generated
    as a Boolean function is decomposed for both single output and multiple output functions.
    The program can produce better results than script.rugged of SIS, developed by UC Berkeley,
    both in area and speed in less CPU time for a number of testcases from MCNC and
    IWLS'93 benchmarks.
    In certain applications ANDjXOR (Reed-Muller) logic has shown some attractive advantages
    over the standard Boolean logic based on AND JOR operations. A bidirectional
    conversion algorithm between these two paradigms is presented based on the concept of polarity
    for sum-of-products (SOP) Boolean functions, multiple segment and multiple pointer
    facilities. Experimental results show that the algorithm is much faster than the previously
    published programs for any fixed polarity. Based on this algorithm, a new technique called
    redundancy-removal is applied to generalize the idea to very large multiple output Boolean
    functions. Results for benchmarks with up to 199 inputs and 99 outputs are presented.
    Applying the preceding conversion program, any Boolean functions can be expressed
    by fixed polarity Reed-Muller forms. There are 2n polarities for an n-variable function and
    the number of product terms depends on these polarities. The problem of exact polarity
    minimization is computationally extensive and current programs are only suitable when
    n :::; 15. Based on the comparison of the concepts of polarity in the standard Boolean logic
    and Reed-Muller logic, a fast algorithm is developed and implemented in C language which
    can find the best polarity for multiple output functions. Benchmark examples of up to 25
    inputs and 29 outputs run on a personal computer are given.
    After the best polarity for a Boolean function is calculated, this function can be further
    simplified using mixed polarity methods by combining the adjacent product terms. Hence,
    an efficient program is developed based on decomposition strategy to implement mixed
    polarity minimization for both single output and very large multiple output Boolean functions.
    Experimental results show that the numbers of product terms are much less than
    the results produced by ESPRESSO for some categories of functions.

    Item Type: Thesis (PhD)
    Uncontrolled Keywords: Very Large Scaled Integrated (VLSI) circuits; symbolic logic; multilevel logic synthesis; Reed-Muller; polarity;
    University Divisions/Research Centres: Faculty of Engineering, Computing and Creative Industries > School of Engineering and the Built Environment
    Dewey Decimal Subjects: 600 Technology > 620 Engineering > 621 Electronic & mechanical engineering > 621.3 Electrical & electronic engineering
    Library of Congress Subjects: T Technology > TK Electrical engineering. Electronics Nuclear engineering
    Item ID: 4342
    Depositing User: Mrs Lyn Gibson
    Date Deposited: 15 Apr 2011 15:23
    Last Modified: 15 Apr 2011 15:23

    Actions (login required)

    View Item

    Document Downloads

    More statistics for this item...

    Edinburgh Napier University is a registered Scottish charity. Registration number SC018373