Completion Optimization for Partially Defined Boolean Functions

1. Introduction

Logic synthesis has traditionally focused on optimizing implementations of completely specified Boolean functions. For such functions, the Boolean relation between the inputs and outputs is fixed, and the objective is to minimize implementation cost while preserving functionality.

Many practical engineering specifications, however, are naturally represented by Partially Defined Boolean Functions. In a PDBF, the output values are specified only for a subset of the input combinations, while the remaining combinations are don't-care conditions. Consequently, a PDBF represents not a single Boolean function but a family of Fully Defined Boolean Functions.

The choice of completion can have a significant effect on the complexity of the synthesized circuit. Nevertheless, conventional synthesis flows typically select one completion before logic optimization and optimize only the resulting Fully Defined Boolean Function.

This paper introduces Completion Optimization, a synthesis methodology that treats the selection of a Legal Completion as an optimization problem in its own right. Rather than optimizing only the implementation of a fixed Fully Defined Boolean Function, the proposed approach operates directly on the PDBF, selecting a Legal Completion according to the chosen optimization objective before conventional logic synthesis begins.

Experimental results demonstrate that Completion Optimization and conventional logic synthesis perform complementary optimization tasks. Completion Optimization selects a favorable Fully Defined Boolean Function from the Opportunity Space represented by the PDBF, while conventional logic synthesis optimizes the implementation of the selected function. Together, they produce substantially smaller and shallower implementations than those obtained by applying conventional logic synthesis directly to the original specification for the benchmarks considered in this paper.

The remainder of the paper introduces the theoretical framework underlying Completion Optimization, presents the proposed methodology, and evaluates it using illustrative examples, practical synthesis benchmarks, an application-derived Partially Defined Boolean Function, and scalability experiments.

2. The Importance of Completion

A partially defined Boolean function specifies the required output only for a subset of its input combinations. The remaining combinations are left unspecified and may be assigned either logic value without violating the original specification. Consequently, a PDBF represents not a single Boolean function, but a family of legal Boolean functions.

Table 1 presents a simple example.

The unspecified value x may be assigned either 0 or 1. Both assignments satisfy the original specification and therefore produce Legal Completions of the PDBF.

Assigning x = 0 produces the exclusive-OR function. Assigning x = 1 produces the logical OR function. Although both completed Boolean functions satisfy the original PDBF, their implementations differ significantly in area and logic depth. In this example, the OR function admits a substantially simpler implementation than the XOR function.

The quality of the final implementation depends not only on logic optimization, but also on the selected completion.

To illustrate this point, the example was synthesized using the ABC logic synthesis system. The resulting implementation is functionally equivalent to the XOR completion. Applying additional optimization scripts, including deepsyn and transtoch, did not reduce either the area or the logic depth. This experiment indicates that conventional logic optimization can improve only the completed Boolean function it receives; it does not explore alternative Legal Completions that may lead to superior implementations.

There is generally no universally optimal completion. A completion that minimizes gate count may differ from one that minimizes logic depth, fan-out, area, or power. The desirable completion therefore depends on the optimization objective.

This observation changes the role of completion in logic synthesis. Completion is not merely a preprocessing step—it is itself an optimization problem.

3. Completion Optimization

3.1 From Don't-Cares to Optimization Opportunities

A partially defined Boolean function contains one or more don't-care values. Traditionally, these values are regarded as unspecified outputs that may be assigned either logic value without violating the original specification.

Every don't-care is an Optimization Opportunity.

Each don't-care provides the freedom to choose between two legal logic values. This choice may influence gate count, logic depth, fan-out, area, power consumption, or other implementation characteristics. Consequently, selecting a completion is itself an optimization problem.

3.2 Opportunity Space

Each Optimization Opportunity represents one binary decision. Collectively, the Optimization Opportunities defined by a PDBF constitute its Opportunity Space. Every complete assignment of the Opportunity Space determines one Legal Completion. Therefore, a PDBF containing n Optimization Opportunities defines up to 2ⁿ Legal Completions.

Even relatively small benchmark functions generate trillions of Legal Completions, while large industrial examples define Opportunity Spaces far beyond exhaustive exploration.

3.3 Completion Optimization

Completion Optimization explores the Opportunity Space according to one or more implementation objectives. Unlike conventional logic optimization, which optimizes a fixed Boolean function, Completion Optimization determines the assignment of Optimization Opportunities before or during implementation construction.

Different objectives—including gate count, logic depth, fan-out, area, power, or combinations thereof—may favor different assignments. Consequently, there is generally no universally optimal completion.

3.4 GT

The GT system implements the Completion Optimization methodology. Rather than explicitly constructing a completed Boolean function, GT operates within the Opportunity Space while directly constructing circuit implementations corresponding to selected assignments of the Optimization Opportunities.

Completion Optimization does not replace conventional logic synthesis. It extends the synthesis flow by introducing a new optimization stage. The circuit implementations produced by GT can be used directly or further optimized using existing synthesis tools.

4. Experimental Evaluation

The experiments evaluate different completion trade-offs, compatibility with conventional synthesis, medium-scale performance, an application-derived PDBF, and scalability.

4.1 7SDD Benchmark

The Seven-Segment Display Decoder is naturally a PDBF because only decimal input values 0–9 are defined. Different synthesis systems implicitly select different FDBFs and therefore produce different area-depth trade-offs.

The GT platform generated multiple Legal Completions optimized for different objectives. The minimum-area implementation contains 14 AIG AND nodes, whereas the minimum-depth implementation requires 18 nodes but only 4 logic levels.

4.2 Compatibility with Conventional Logic Synthesis

Completion Optimization determines the Boolean function to be implemented, whereas conventional logic synthesis improves the implementation of that selected function.

4.3 Medium-Scale Benchmark

The benchmark Example_250_1_2000 contains 250 input variables and one output. GT generated 317 candidate implementations. The smallest contained 393 AIG AND nodes with 32 logic levels.

Despite more than two hundred optimization iterations, ABC reduced the GT implementation by only one AIG AND node while improving logic depth by three levels.

4.4 Application-Derived PDBF

An ASCII 5×7 alphanumeric character recognizer accepts a 35-bit bitmap and produces a 7-bit ASCII code plus a validity signal. For invalid patterns, only the validity output is specified; the ASCII outputs are irrelevant. The recognizer is therefore naturally a PDBF.

4.5 Scalability

Completion Optimization was applied to example_10000_1000_5000, containing 10,000 input variables, 1,000 outputs, and 5,000 Optimization Opportunities.

A sparse benchmark with 1,000,000 input variables and 100 specified terms was processed in a web browser, producing an implementation with 6 AIG AND nodes and 4 logic levels in approximately 13 seconds per Search Strategy.

5. Discussion

5.1 Completion Optimization as a New Optimization Stage

Conventional logic synthesis assumes the FDBF has already been determined. Completion Optimization operates one stage earlier, while the specification is still represented as a PDBF. It selects a Legal Completion that best satisfies the chosen objective before conventional synthesis begins.

5.2 Relationship to Conventional Logic Synthesis

The two approaches address different optimization problems. Completion Optimization determines what Boolean function should be implemented, whereas conventional logic synthesis determines how that selected function should be implemented most efficiently.

5.3 Engineering Significance

PDBFs are not merely mathematical abstractions. The ASCII character recognizer demonstrates that partially defined specifications arise naturally in engineering. Whenever such freedom exists, selecting a Legal Completion becomes an optimization problem in its own right.

6. Conclusions

This paper introduced Completion Optimization, a new optimization stage operating directly on PDBFs before conventional logic synthesis begins. The methodology is based on Optimization Opportunities, Opportunity Spaces, and Legal Completions.

Experimental results demonstrated that different Legal Completions lead to different implementation trade-offs and that Completion Optimization and conventional synthesis perform complementary roles. The application-derived ASCII recognizer showed that PDBFs arise naturally in practical engineering specifications, while scalability experiments demonstrated practicality for extremely large Opportunity Spaces and high-dimensional sparse specifications.

Completion Optimization extends the conventional digital design flow by optimizing the functional specification before implementation optimization begins.