求可处理多输出的通用多级逻辑最小化算法

This algorithm optimizes multi-output Boolean systems by extracting and reusing common subexpressions to minimize total logic gate count. Below is a step-by-step implementation framework:

1. Preprocess Input Expressions #

• Convert all output Boolean functions to a standardized form (e.g., sum-of-products (SOP) or product-of-sums (POS)) to enable consistent term comparison across functions.
• Example input (already in SOP form):

  F1 = AB + AC + AD
  F2 = A'B + A'C + A'E
  

2. Identify Candidate Common Subexpressions #

• Scan all terms across all outputs to find shared components, including:
  • Exact term matches (e.g., B + C emerges when factoring AB+AC and A'B+A'C).
  • Algebraically factored forms that can be extracted as reusable intermediates.
• Track subexpression frequency with a map to prioritize high-occurrence candidates.

3. Calculate Cost-Benefit of Reuse #

For each candidate subexpression P:

• Compute the gate cost of implementing P independently (e.g., B + C uses 1 OR gate).
• Compare original vs. reused cost:
  • Original cost: Sum of gate counts for all duplicated instances of the subexpression.
  • New cost: Cost of P + cost of referencing P in each output function.
• Only proceed if the new cost is lower than the original.

In the example:

• Original cost for AB+AC (F1) and A'B+A'C (F2): (2 AND gates + 1 OR gate) × 2 = 6 gates.
• Reusing P = B + C: 1 OR gate (for P) + 1 AND gate (AP) + 1 AND gate (A'P) = 3 gates, saving 3 gates total.

4. Select Optimal Subexpressions #

• Use a greedy approach to prioritize subexpressions with the highest cost reduction per gate added. For global optimization (computationally heavier), use dynamic programming to explore all possible combinations.
• Avoid over-factoring that creates redundant intermediates which negate cost savings.

5. Rewrite Functions with Intermediate Variables #

• Replace all instances of selected subexpressions with new intermediate variables, then update the function set to include both intermediates and rewritten outputs:

  P = B + C
  F1 = AP + AD
  F2 = A'P + A'E
  

6. Iterate for Further Minimization #

• Repeat steps 2-5 on the rewritten function set. New common subexpressions may emerge after introducing intermediates, enabling additional gate savings.
• Stop when no cost-effective subexpressions can be extracted.

Key Considerations #

• Canonical Form Choice: Experiment with SOP and POS forms—each may reveal different reusable subexpressions.
• Computational Efficiency: For large systems, use heuristic methods (e.g., extended Espresso minimizer) to balance optimization quality and runtime.
• Gate Library Constraints: Adjust cost calculations to match target gate types (e.g., NAND-only libraries) for accurate real-world results.

内容的提问来源于stack exchange，提问作者Hexaneat