Decomposition of Large-Scale Logic Functions

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

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