Decomposition of Large-Scale Logic Functions

9.1分解系统：分解这一部分考虑使用三种方法的逻辑函数的分解系统：1)不相交的双分解；2)用几个有界集合变量的简单不相交分解；3)使用雅可比分解。1)和2)是快速的，但只找到有限类的分解，而3)通过花费更多的时间来找到所有简单的不相交分解。我们给出了3000多个函数的实验结果。我们还定义了一类新的函数：完全双可分解函数。实验结果表明，许多实际的逻辑函数都有不相交的分解，有些是完全二次分解的。9.2使用自动测试模式生成器和逻辑模拟器的分解系统。由于该方法使用网表而不是二叉决策图来表示逻辑函数，因此它可以分解更大的网络。它利用网表的信息，有效地找到了形式f(X_1，X_2)=g(h(X_1)，X_2)的分解，其中…更多Re|X_1|[小于或等于]k。计算时间与Gn^k成正比，其中n是主要输入变量的数量，G是门的数量。9.3算术三值决策图在算术三值决策图(Arith_Tdd)中，第三条边表示f_2=f_0+f_1，其中+是整数加法。Arith_tdd表示扩展的权重函数，这是一个整数函数，显示了立方体中的真最小项的数量。ARITH_TDD用于检测函数分解、素蕴涵和素蕴涵。实验结果比较了基准函数的BDD和不同TDDS的大小。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设计这种方法既使用了函数分解，又使用了PKDDS映射到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)，则它是双可分解的。在这种情况下，通过应用分配定律，从h1和h2的最小SOP(MSOP)得到f的乘积和表达式(SOP)。如果结果是MSOP，那么最小化的复杂性就降低了。然而，将分配定律应用于h_1和h_2的MSOP并不总是产生f的MSOP。在这一部分中，我们展示了一个由n(n-1)个变量组成的不完全指定的函数，它的MSOP只有n个乘积，它产生2^&lt；n-1&gt；通过将分配律应用于分量函数的MSOP而得到的SOP中的乘积。然后，我们引入了一类新的逻辑函数，称为纯正函数，其中将分配律应用于f的分量函数的MSOP确实产生了MSOP。在正统函数中，MSOP中的乘积的数目等于最小项的最大独立集的大小。证明了纯正函数包括三个或更少变量的所有函数、所有对称函数、所有单一函数、多个基准函数和少数多个变量的随机函数。9.9利用可重构硬件级联实现多输出函数提出了一种使用大查找表(LUT)和定序器实现多输出逻辑函数的方法。首先，多路输出函数由用于非零输出的编码特征函数(ECFN)表示。然后，它由级联的查找表(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