What Determines the Implementation Size of Partially Defined Boolean Functions?

1. Introduction

For a PDBF, behavior is required only on a care domain. A PLA can therefore declare a large input space even when a much smaller subset of coordinates is sufficient to distinguish all care situations that require different output values.

The central question is therefore not simply how many primary inputs are declared, but how many must survive in a valid realization and how much logic is then required over that selected support.

2. PDBF Model and Effective Support

Let D be the care domain of a PDBF F. A circuit N is valid when it agrees with F for every assignment in D; behavior outside the care domain is unrestricted.

For output N_j, let Supp(N_j) denote the original primary inputs in its transitive support. The network effective support is the union of these sets, and PI_eff is its cardinality. Two valid implementations of the same PDBF may therefore use different subsets of the declared inputs.

3. Care Separation and MCS

Consider two PLA cubes that require opposite values for the same output. Their separator set contains every input coordinate fixed to complementary values, 0/1 or 1/0, in the two cubes. At least one such coordinate must survive in the support of any implementation that distinguishes the two care regions.

A care-separating support H intersects the separator set of every opposite-care cube pair. MCS is the minimum cardinality of such a set.

Computationally, this is a minimum hitting-set problem. Exact MCS is used in this paper only where an exact optimum was obtained.

4. MCS Lower-Bound Theorem

Proof. Take an output and two cubes requiring opposite values. If the output support contained no variable from their separator set, the projections of the two cubes onto that support would be compatible. Two assignments—one from each cube—could then agree on the entire support. Because the implemented output depends only on that support, it would produce the same value for both assignments, contradicting the opposite required care values. Thus the output support must intersect every corresponding separator set. The union of all output supports is therefore a feasible care-separating support, so its cardinality cannot be smaller than MCS. □

5. Experimental Methodology

GT implementations are represented as gate-level BLIF networks. Effective PI is measured by tracing the transitive support of all primary outputs back to the original primary inputs. The exact-support experiment includes only benchmarks for which both an exact optimal MCS and a GT support measurement are available, avoiding any mixture of exact and sampled quantities.

For large IPv6 semantic PDBFs, exact MCS is not yet available. These cases are reported separately using declared PI, CSPI, GT effective PI, gates, and levels. CSPI counts the union of PIs capable of separating at least one opposite-care pair; it is not a minimum-support quantity.

6. Exact-MCS Results

All eight implementations satisfy MCS≤PI_eff. Five attain equality, so GT has provably minimum effective-support cardinality for those five PDBFs. Across the eight exact cases, the median PI_eff/MCS ratio is 1.0.

7. Support Complexity Does Not Fully Determine Gate Count

Minimum support does not imply minimum gate count. Even among support-optimal cases, the amount of logic per effective input varies. This motivates a two-stage interpretation:

The expression is conceptual rather than an additive cost equation. Care structure constrains the support that must survive; the Boolean relationships over that support then determine the gates and depth required by a particular realization.

8. Large IPv6 Semantic PDBFs

The reductions in effective input dimension are substantial: 1,408→197 for the SRv6 classifier, 946→120 for the service-chain policy, 1,024→97 for VXLAN, and 806→41 for the firewall classifier. These are support-reduction results; exact support optimality is not yet claimed for these large cases.

9. What Determines PDBF Implementation Size?

The experiments suggest that nominal PI count describes the coordinate space in which the PDBF is written, but not how many coordinates must survive in a valid realization. Cube count describes specified regions but not how they can be separated. MCS addresses the minimum care-separation requirement, while PI_eff records the support selected by a particular synthesis result.

Support optimality and logic optimality should therefore be evaluated separately. When GT reaches MCS, support cardinality is solved optimally for that benchmark, while gate or depth optimization may still continue over the same support.

10. Discussion

Benchmark design

PDBF benchmarks should report more than PI, PO, and cube count. Where practical, exact MCS—or certified MCS bounds—adds a specification-side quantity with direct implementation meaning. Reporting PI_eff then distinguishes support reduction from gate-level optimization.

Tool comparison

MCS is tool-independent. Any synthesis system may process the same PLA and report a valid implementation. If PI_eff=MCS, support cardinality is optimal regardless of the synthesis method. Gates, depth, wiring, fan-out, mapping, and runtime remain separate comparison dimensions.

Limitations

The exact experiment currently contains eight benchmarks. Large IPv6 examples demonstrate support reduction but not exact support optimality. MCS is a lower bound on effective support and is not claimed to equal minimum gate count or minimum depth.

11. Reproducibility and Verification

A synthesized result is validated by checking that it satisfies every required care value represented by the PLA. Behavior on don't-care assignments is unrestricted. Effective PI is determined from the transitive support of all outputs.

Independent tools may process the same PLA, produce their own networks, validate care-domain compatibility, and report effective PI, gate count, and depth. The benchmark inputs are available from the GT Synthesis benchmark page.

12. Conclusion

Declared primary-input count alone is not a sufficient measure of PDBF implementation complexity. MCS provides a specification-side lower bound on the effective support of every valid implementation, and equality PI_eff=MCS certifies globally minimum effective-support cardinality.

Five of the eight current exact-MCS GT implementations attain this bound. Larger IPv6 semantic PDBFs demonstrate substantial reductions from declared PI to effective PI. The resulting framework separates two questions: which primary inputs must survive the care constraints, and how much logic is required to realize the behavior over the selected support?