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)


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 14:23
Last Modified: 15 Apr 2011 14:23

Actions (login required)

View Item View Item


Downloads per month over past year

View more statistics

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