Information Technology Reference
In-Depth Information
4.4
Redundancy Removal
Redundancies may exist in the preliminary majority expression network and the
circuit can be further simplified by removing them. This process is explained through
an example shown in Eq. (
16
). The following network has three inputs a, b and c, and
one output f as shown in Eq. (
16
), where [3], [4], [5] and [6] are internal nodes.
ð
16
Þ
The repeated nodes have to be removed. By selecting each node and comparing its
original form and complementary form with the rest of the nodes, it can be found that
[4] and [6] are identical while [4] and [5] are complementary to each other. By
substituting [5] and [6] with [4]
0
and [4], Eq. (
17
) is obtained.
ð
17
Þ
Then the inverters have to be optimized. In this network, one of the inputs in node
[3] has doubled inverters and can be eliminated out. The last step is to simplify the
nodes with duplicated inputs. Two inputs to the majority function node [3] are [4],
therefore [3] will be identical to the logic value of [4]. By substituting [3] = [4],it
can be seen that f now has two same inputs and can be simplified. The optimized
output is as shown in Eq. (
18
). Note that, the redundancy removal process should be
carried out for multiple iterations until no more changes can be made to the network.
f
¼
b
ð
18
Þ
The simplified function after taking redundancies into consideration requires no
majority gate as compared to 3 levels and 5 majority gates in the original network.
5
Results and Comparisons
The proposed method has been applied to MCNC benchmark circuits and compared
to other synthesis approaches. The circuit ''mux'' in MCNC benchmark suite is used
to explain the process in detail. The original circuit equations are shown in Eq. (
19
).
It has 1 primary output, v, which is in curly brackets, and 21 primary inputs a, b, c,
d, e, f, g, h, i, j, k, l, m, n, o, p, q, r, s, t, u. The rest of the variables are the internal
nodes.
Search WWH ::
Custom Search