Decomposition of Large-Scale Logic Functions

9.1分解系统：decomp本部分考虑一个逻辑函数的分解系统，采用三种方法：1)不相交双分解；2)少量有界集变量的简单不相交分解；3)使用雅可比矩阵分解。1)和2)是快速的，但只能找到有限的分解类，而3)需要花费更多的时间来找到所有简单的不相交分解。我们给出了3000多个函数的实验结果。我们还定义了一类新的函数：完全双可分解函数。实验结果表明，许多实际的逻辑函数具有不相交分解，有些是完全双分解的。9.2使用自动测试模式生成器和逻辑模拟器的分解系统由于该方法使用网络表而不是二元决策图来表示逻辑函数，因此可以分解更大的网络。利用网络表的信息，有效地求出f (X_1, X_2)=g （h (X_1), X_2）的分解，当…More re |X_1|【小于等于】k。计算时间与Gn^k成正比，其中n为主要输入变量的个数，G为门的个数。9.3算术三元决策图在算术三元决策图（arith_TDD）中，第三条边表示f_2=f_0+f_1，其中+为整数加法。arith_TDD表示扩展的权重函数，它是一个整数函数，显示立方体中真正的最小项的个数。算法tdd可用于检测功能分解、素数蕴涵和素数蕴涵。实验结果比较了基准函数的bdd和各种tdd的大小。9.4三参数查找功能分解本部分展示了一种启发式方法来查找输入变量的分区。9.5求不可分解函数的方法如果函数f表示为f(X_1, X_2)=g (h (X_1), X_2)，则函数f(X)有分解。本部分展示了一种检测不产生f(X)分解的分区（X_1, X_2）的方法。它通过对不可分解函数使用查找表来快速减少分解的搜索空间。提出了一种寻找分解的系统方法。该方法证明了随机生成函数在线性时间内的不可分解性。9.6对称函数的展开及其在非不交泛函分解中的应用本部分给出了对称函数的一种新的展开方法。它还显示了rd73， rd84和9sym的实现，分别只需要4个，6个和6个LUT。9.7使用伪kronecker决策图的FPGA设计这种方法既使用功能分解，又使用pkdd映射到LUT网络。该算法包括以下步骤：1)将给定函数f的BDD分解为几个更小的BDD；2)将每个BDD转换为PKDD；3)分区PKDD；4)将PKDD转换为LUT网络；5)简化得到的LUT网络。该方法具有以下特点：6)处理多输出函数；7) PKDD中的节点数为lut数的上界；8)对于没有函数分解的函数，该方法产生的网络比以前报道的要小得多。该系统的原型已经开发出来。9.8函数分解与两级逻辑最小化函数f可表示为f (X_1, X_2)=h_1 (X_1) h_2 (X_2)，是可与双分解的函数。在这种情况下，应用分配律，由h_1和h_2的最小SOP （MSOP）得到f的乘积和表达式SOP。如果结果是MSOP，那么最小化的复杂性就降低了。然而，将分配律应用于h_1和h_2的MSOP并不总是产生f的MSOP。在这一部分中，我们给出了一个n （n-1）个变量的不完全指定函数，其MSOP只有n个积，该函数在通过将分配律应用于分量函数的MSOP得到的SOP中产生2^<n-1>积。然后，我们引入了一类新的逻辑函数，称为正统函数，其中分配律对f的分量函数的MSOP的应用确实产生了MSOP。在正统函数中，MSOP中的产品数量等于最小项的最大独立集的大小。我们证明正统函数包括所有三个或三个以下变量的函数、所有对称函数、所有非对称函数、许多基准函数和少数具有许多变量的随机函数。9.9通过可重构硬件级联实现多输出函数。首先，多输出函数由非零输出（ECFN）的编码特征函数表示。然后，它由一系列查询表（lut）表示。最后，用一个大型LUT和一个定序器来模拟级联。我们通过lut级联表示基准函数的多个输出函数，并显示了lut的数量和网络的级别。少

9.1 Decomposition System : DECOMPThis part considers a decomposition system for logic functions using three methods : 1) Disjoint bi-decomposition ; 2) Simple disjoint decomposition with a few bound set variables ; and 3) Decomposition using Jacobian. 1) and 2) are quick, but find only limited classes of decompositions, while 3) finds all simple disjoint decompositions by spending more time. We show the experimental results for more than 3000 functions. We also define a new class of functions : complete bi-decomposable functions. Experimental results show that many practical logic functions have disjoint decompositions and some are completely bi-decomposable.9.2 Decomposition System using an Automatic Test Pattern Generator and a Logic SimulatorSince this method uses netlists rather than binary decision diagrams to represent logic functions, it can decompose larger networks. By using information of netlists, it efficiently finds decompositions of form f (X_1, X_2)=g (h (X_1), X_2), whe … More re |X_1|【less than or equal】k. The computation time is proportional to Gn^k, where n is the number of primary input variables, and G be the number of gates.9.3 Arithmetic Ternary Decision DiagramsIn the arithmetic ternary decision diagram (arith_TDD), the third edge denotes f_2=f_0+f_1, where + is an integer addition. The arith_TDD represents the extended weight function, an integer function showing the numbers of true minterms in the cubes. The arith_TDD is useful to detect functional decompositions, prime implicants and prime implicates. Experimental results compare the size of BDDs and various TDDs for benchmark functions.9.4 Three Parameters Find Functional DecompositionsThis part shows a heuristic method to find the partitions of input variables. We introduce three parameters to find bipartitions of input variables.9.5 Method to Find Undecomposable FunctionsA function f(X) has a decomposition if f is represented as f (X_1, X_2)=g (h (X_1), X_2). This part shows an method to detect partitions (X_1, X_2) that do not produce decompositions for f(X). It quickly reduces the search space for the decompositions by using look-up tables for undecomposable functions. A systematic method to find decompositions is presented. This method proves undecomposability of randomly generated functions in linear time.9.6 An Expansion of Symmetric Functions and Its Application to Non-Disjoint Functional DecompositionsThis part presents a new expansion method symmetric functions. It also shows the realizations of rd73, rd84, and 9sym, that require only 4, 6, and 6 LUTs, respectively.9.7 FPGA Design using Pseudo-Kronecker Decision DiagramsThis method uses both functional decomposition and a mapping to LUT network by using PKDDs. The algorithm consists of the following steps : 1) Decompose the BDD for the given function f into several smaller BDDs ; 2) Transform each BDD into a PKDD ; 3) Partition the PKDD ; and 4) Convert the PKDD into a LUT network ; 5)Simplify the resulting LUT network. This method has the following features : 6) It treats multiple-output function ; 7) The number of the nodes in the PKDD is the upper bound on the number of LUTs ; and 8) For the function without functional decompositions, this method produces much smaller networks than previously reported ones. A prototype of the system has been developed. Experimental results using benchmark functions show the encouraging results.9.8 Functional Decomposition and Two-level Logic MinimizationA function f is AND bi-decomposable if it can be written as f (X_1, X_2)=h_1 (X_1) h_2 (X_2). In this case, a sum-of-products expression (SOP) for f is obtained from minimum SOPs (MSOP) for h_1 and h_2 by applying distributive laws. If the result is an MSOP, then the complexity of minimization is reduced. However, the application of distributive laws to MSOPs for h_1 and h_2 does not always produce an MSOP for f. In this part, we show an incompletely specified function of n (n-1) variables with an MSOP of only n products, that produces 2^<n-1> Products in the SOP that is obtained by applying distributive laws to the MSOPs of the component functions.Then, we introduce a new class of logic functions, called orthodox functions, where the application of distributive laws to MSOPs for component functions of f does produce an MSOP.In an orthodox function, the number of products in an MSOP is equal to the size of the maximal independent set of minterms. We show that orthodox functions include all functions with three or fewer variables, all symmetric functions, all unate functions, many benchmark functions, and few random functions with many variables.9.9 Cascade Realization of Multiple-output Functions by Reconfigurable HardwareA realization of multiple-output logic function using a large look-up table (LUT) and a sequencer is presented. First, a multiple-out function is represented by an encoded characteristic function for non-zero outputs (ECFN). Then, it is represented by a cascade of look-up tables (LUTs). And finally, the cascade is simulated by a large LUT and a sequencer. We represent multiple-output functions for benchmark functions by cascades of LUTs, and show the number of LUTs and levels of networks. Less