Edinburgh Napier University

  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.