Abstract
Conventional sequential logic synthesis assumes that the next-state and output functions of a finite-state machine are completely specified before optimization. In practice, sequential specifications inherently contain unreachable states and unreachable state/input combinations whose behavior is never observed during correct operation. Consequently, sequential devices are naturally represented as Sequential Device Partially Defined Boolean Functions consisting of a specified reachable region and an unspecified unreachable region.
This paper introduces GT AND Sequential Synthesis, a methodology that exploits optimization freedom in the unreachable region before conventional synthesis. A three-state controller demonstrates that only two unreachable state/input combinations allow GT to reduce the complete implementation from seven to four gates while also reducing depth and wiring.
Keywords: sequential logic synthesis, PDBF, reachability, Completion Optimization, finite-state machine, GT Synthesis.
1. Introduction
Logic synthesis has traditionally been formulated as the optimization of completely specified Boolean functions derived from a sequential specification. Once the state encoding and transition functions have been determined, conventional synthesis algorithms seek an implementation with reduced area, delay, or power while preserving specified behavior.
This formulation implicitly assumes that every combination of current state and primary inputs defines meaningful behavior. Sequential systems fundamentally differ: only a subset of all mathematically possible state/input combinations is ever reachable. The remaining combinations do not contribute to observable behavior and therefore do not constrain implementation.
Sequential logic is inherently partially defined.
GT AND Sequential Synthesis exploits this intrinsic property. Instead of immediately assigning values to unreachable behavior and optimizing one completed Boolean function, GT searches Legal Completions that preserve all reachable behavior. Conventional synthesis is then applied to the selected completion.
2. Native Sequential Device PDBFs
2.1 Sequential Specifications
A deterministic sequential device is described by a finite set of states, primary inputs, a next-state function, and an output function. Only a subset of the Cartesian state/input space is reachable during correct execution.
2.2 Reachable and Unreachable Regions
Behavior over R determines observable functionality. Behavior over U is never exercised and therefore remains unspecified.
3. Reachability Reveals the Sequential Device PDBF
Conventional reachability analysis is commonly used to eliminate unreachable states, simplify state encodings, compute sequential don’t-cares, or reduce verification complexity. GT gives reachability a broader role: it exposes the partial definition already present in the specification.
ONLY reachable behavior defines correctness.
Unreachable behavior defines optimization freedom.
4. GT AND Sequential Synthesis
- Reachability Analysis: compute R from the specification, initial conditions, and permitted environment.
- Sequential Device PDBF Construction: preserve next-state and output behavior over R; represent U as unspecified.
- Completion Optimization: search SOS(SP) for Legal Completions satisfying structural objectives.
- Logic Synthesis: optimize the selected completed Boolean representation.
- Technology Mapping: map the optimized network to gates, standard cells, or FPGA resources.
5. Illustrative Example
5.1 Three-State Controller
The controller uses present-state bits A and B, primary input I, next-state bits Anext and Bnext, and Moore output Y. State 11 is unused and unreachable.
5.2 PLA Representation
.i 3 .o 3 .ilb A B I .ob A_next B_next Y .type fr .p 8 000 000 001 010 010 001 011 100 100 000 101 100 110 --- 111 --- .e
5.3 Functional Interpretation
On every reachable combination, Y=B. GT can therefore complete the unreachable rows so that Y is implemented as a direct state-bit connection. A favorable completion for Anext is consistent with Anext=I(A+B), while Bnext=IĀB̄ over reachable behavior.
5.4 Results
| Method | Gates | Maximum Levels | Wires |
|---|---|---|---|
| ABC + deepsyn | 7 | 3 | 17 |
| ABC + transtoch | 6 | 4 | 15 |
| GT Completion Optimization | 4 | 2 | 11 |
Relative to deepsyn, GT reduces gates by 42.9%, depth by 33.3%, and wires by 35.3%. Relative to transtoch, GT reduces gates by 33.3%, depth by 50.0%, and wires by 26.7%.
6. Relationship to Completion Optimization
Once reachability partitions the sequential state/input space into R and U, the optimization problem becomes a multi-output Completion Optimization problem. Paper I provides the optimization engine. Paper II demonstrates contextual extraction in combinational RTL. Paper III establishes that sequential specifications inherently provide their own Native Sequential Device PDBFs.
Optimize a PDBF
Reveal contextual PDBFs
Recognize native sequential PDBFs
7. Discussion
The central contribution is conceptual rather than merely algorithmic. Partial definition is intrinsic to sequential specifications. The Sequential Device PDBF is not generated by GT and is not an approximation; it is the exact specification restricted to behavior that can occur.
GT modifies only the completion stage. Existing synthesis engines, verification tools, and technology mappers require no change. Larger systems may use symbolic simulation, SAT, BDDs, formal model checking, abstraction, or compositional reachability.
Future Research
- Standard FSM and sequential benchmark suites.
- Protocol-aware optimization for AXI, PCIe, USB, Ethernet, UART, SPI, I²C, CAN, and DDR.
- Joint optimization of state assignment, next-state logic, output logic, and U.
- Integration with the PDBF Passport Library.
- FPGA and ASIC evaluation using mapped area, delay, power, fan-out, and wiring.
8. Conclusions
GT AND Sequential Synthesis exploits optimization freedom naturally present within sequential specifications. Reachability reveals the specified region R and the unspecified region U; Completion Optimization searches the resulting Sequential Opportunity Space while preserving all observable behavior.
Sequential logic is inherently partially defined.
ONLY reachable behavior defines correctness.
Unreachable behavior defines optimization freedom.