A Research on the realization of three-level logic networks

点击翻译按钮获取中文摘要

(1) AND-OR-EXOR three-level networks.We considered design methods for AND-OR-EXOR three-level networks, where single two-input EXOR gate is used for each output. The network realizes an EXOR of two sum-of-products expressions (EX-SOP), F1 F2, where F1 and F2 are sum-of-products expressions (SOPs). The problem is to minimize the total number of different products in F1 and F2.(2)OR-AND-OR three-level networks.We considered the number of gates to realize logic functions by OR-AND-OR three-level networks under the condition that both true and complemented variables are available, and each gate has no fan-in and fan-out constraints. We show that an arbitrary n-variable function can be realized by an OR-AND-OR three-level network with at most 2^{r+1}+1 gates、where n=2r and r are integers. We developed a heuristic algorithm to design OR-AND-OR three-level networks, and compared the number of gates for three-level networks with two-level ones.(3) Bi-decomposition.A logic function f has a disjoint bi-decomposition iff f can be represented as f=h(g_1(X_1), g_2(X_2)), where X_1 and X_2 are disjoint set of variables, and h is an arbitrary two-variable logic function. We showed a fast method to find bi-decompositions without using decomnposition chart. Also, we enumerated the number of functions having bi-decompositions. When the function has a bi-decomposition, three-level network is easy to derive.(4)Generalized Reed-Muller expressionsA generalized Reed-Muller Expression (GRM) is obtained by negating some of the literals in a positive polarity Reed-Muller expression (PPRM).There are at most 2^{n{2^{n-1}} different GRMs for an n-variable function. A minimum GRM is one with the fewest products. We showed some properties and a minimization algorithm for GRMs. The minimization algorithm is based on binary decision diagrams. We also developed GRMIN2, heuristic minimization program for GRMs. We also developed an easily testable realization for GRMs.