A Research on the realization of three-level logic networks

(1)AND-OR-EXOR三级网络。我们考虑了AND-OR-EXOR三级网络的设计方法，其中每个输出都使用一个两输入EXOR门。该网络实现了两个积和表达式(ex-SOP)的异或运算，其中F1和F2是积和表达式(SOP)。问题是最小化F1和F2中不同乘积的总数。(2)OR-AND-OR三级网络，在变量为真和可补且每个门都没有扇入和扇出约束的情况下，考虑了OR-AND-OR三级网络实现逻辑功能的门数。我们证明了任意n元函数可以由一个至多有2^{r1}1个门的或与或三级网络实现，其中n=2r和r是整数。(3)二分解：一个逻辑函数f有一个不相交的二次分解当且仅当f可以表示为f=h(g_1(X_1)，g_2(X_2))，其中X_1和X_2是不相交的变量集，h是任意两个变量的逻辑函数。我们给出了一种不使用分解图的快速求二重分解的方法。此外，我们还列举了具有二次分解的函数的数目。(4)广义Reed-Muller表达式通过对正极性Reed-Muller表达式(PPRM)中的一些文字取反得到广义Reed-Muller表达式(GRM)。对于n元函数，至多有2^{n{2^{n-1}个不同的GRM。最低GRM是具有最少产品的GRM。我们给出了GRMS的一些性质和最小化算法。最小化算法是基于二叉决策图的。我们还开发了GRMIN2启发式最小化程序。我们还为GRM开发了一个易于测试的实现。

(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.