TL;DR
This paper introduces a novel lookup-table-based algorithm for minimizing generalized k-variable-mixed-polarity Reed-Muller (GPMPRM) expansions. This method offers a more efficient way to represent and simplify complex Boolean functions, outperforming existing techniques, especially for systems of multiple output functions.
What Problem Does This Paper Address?
Boolean functions are fundamental to digital circuit design. While traditional methods use Boolean algebra, alternative representations like Reed-Muller (RM) expansions, particularly those using exclusive-OR (XOR) gates, are gaining traction due to their efficiency in certain circuit types and improved testability. However, finding the minimal representation (i.e., the one with the fewest product terms or literals) for these expansions is a computationally challenging problem.
Existing RM expansions include Fixed Polarity Reed-Muller (FPRM) and Kronecker Reed-Muller (KRM). A more general form, the Generalized Reed-Muller (GRM) expansion, offers more flexibility but is computationally infeasible to minimize exhaustively. The paper focuses on a subset of GRM called Generalized Partially Mixed-Polarity Reed-Muller (GPMPRM) expansions, which offer a good balance between expressiveness and manageability. The core problem is to efficiently find the optimal GPMPRM expansion for a given Boolean function, especially when dealing with multiple output functions, where simply minimizing each output independently doesn't guarantee an overall optimal solution.
Methods
The paper proposes a lookup-table-based approach to minimize GPMPRM expansions. The core idea is to leverage a decomposition technique that breaks down the problem into smaller, manageable subproblems.
- Decomposition: The polarity coefficient matrix of a Boolean function is recursively partitioned. This allows the problem of minimizing an n-variable function to be reduced to minimizing several k-variable subfunctions.
- Lookup Tables: Precomputed lookup tables store optimal solutions (minimizing product terms and literals) for k-variable subfunctions. This avoids recomputing solutions for common subproblems.
- Heuristic for Mixed Polarity Variable Selection: To further improve efficiency, a heuristic based on the "exclusion rule" is employed to intelligently select the k variables that will have mixed polarities. This is crucial because the choice of these variables significantly impacts the final minimized form.
- Multiple Output Minimization: For systems of multiple output functions, the algorithm is extended to find common product terms across different outputs, leading to a more globally optimal solution than independent minimization.
Datasets
The paper evaluates its algorithm using benchmark functions from the MCNC (Microelectronics Center of North Carolina) suite, which are commonly used in circuit design research. These benchmarks are provided in PLA (Programmable Logic Array) format. The paper also refers to results from previous works on similar benchmarks. No new datasets were introduced.
Key Insights and Ideas
- GPMPRM as a Sweet Spot: GPMPRM expansions offer a powerful representation that is more expressive than FPRM but more computationally tractable for minimization than general GRM expansions.
- Lookup Tables for Efficiency: The use of precomputed lookup tables is a key enabler for efficiently finding optimal GPMPRM expansions, trading storage for computation time.
- Heuristic Variable Selection Matters: The choice of which variables are allowed to have mixed polarities is critical. The proposed heuristic based on the exclusion rule significantly improves the quality of the minimized solutions.
- Global Minimization for Multi-Output Functions: The algorithm's ability to find common terms across multiple outputs is a significant advantage over independent minimization, leading to more compact overall circuit implementations.
Key Results
- Improved Minimization Quality: The proposed GPMPRM minimization algorithm, especially with k=3 mixed polarity variables, consistently outperforms exact FPRM minimizers and previous GPMPRM approaches (with only one mixed polarity variable) in terms of the number of product terms and literals.
- Faster Execution Time: The GPMPRM algorithm demonstrates significantly lower execution times compared to exact FPRM minimizers, making it practical for larger and more complex functions.
- Effective for Multiple Outputs: The algorithm achieves better results for multiple output functions by identifying shared product terms, leading to more compact designs.
- Adaptable Cost Functions: The algorithm can be adapted to different cost criteria (e.g., minimizing product terms, literals, or a weighted combination), offering flexibility to designers.
Limitations and Future Work
- Computational Complexity: While significantly improved, the complexity of the algorithm still grows exponentially with the number of variables (n) and the number of mixed polarity variables (k). The lookup table size can become prohibitive for very large k.
- Heuristic Nature: The selection of mixed polarity variables is heuristic, meaning it doesn't guarantee the absolute global optimum in all cases, though it performs very well in practice.
- Future Research: The authors suggest further research into comparing GPMPRM expansions with other generalized RM forms like GRM and pseudo-Kronecker expansions. They also note that the current algorithm is highly efficient for up to ten input variables with k=3, implying that exploring larger k or n might require further algorithmic refinements. The NP-completeness of the underlying problem suggests that exact solutions for very large instances will remain challenging.
Summary updated