Definition
Completeness analysis determines whether every possible input scenario of a design—described as a transaction sequence—can be covered by a chain of properties that predicts the values of states and outputs at every point in time. A property suite that passes this analysis is considered complete in the sense that any two designs satisfying all properties in the suite are formally equivalent. [C1]
Core checks
The analysis is described as reducing to checks at the end state of each property. For each property, the method checks that:
- there is always a successor property whose assumptions match;
- the successor property is uniquely determined; and
- each property uniquely describes the outputs and states of the design under verification (DUV). [C2]
Together, these checks ensure that the property suite does not leave unspecified transitions, ambiguous successor behavior, or multiple possible values for the DUV state and outputs. [C2]
Role in formal verification
Completeness analysis is used with property-based formal verification. In the cited work, the surrounding verification flow uses interval property checking (IPC), a SAT-based methodology for verifying safety properties. IPC uses arbitrary starting states rather than only initial states; properties that hold from arbitrary states also hold from reachable states, while false negatives from unreachable states may be removed using invariants. [C3]
The same source states that completeness analysis integrated within an IPC verification environment was commercially available, and that detailed methodology was referenced in prior work. [C4]
Complete property suites as design models
When verification completes successfully and the property suite is complete, the suite forms a model of the verified design: the properties describe the design transitions and output behavior in a unique way. [C5]
This model property is important because it can be exploited to derive an executable model. In the cited instruction-set-simulator work, the authors state that the fact that the properties form a model, together with abstraction used in verification, can be used to obtain a simulator that captures the entire behavior of the design. [C6]
Example application: instruction-set simulator generation
In the cited processor case study, a property suite written in ITL was checked for completeness against the processor design and was therefore treated as a correct and complete specification. The paper reports that the processor core source comprised about 10,000 lines of VHDL, while the final reformulated property suite comprised about 2,000 lines of ITL. [C7]
The same work used the complete property suite as the basis for generating an instruction set simulator (ISS). For an industrial design, the generated ISS reached 1.2 MIPS, while a commercial just-in-time compiled simulator reached 2.5 MIPS; the authors concluded that the generated ISS showed performance comparable to modern custom-made instruction set simulators. [C8]
Verification-language context
The properties in the cited work are written in ITL. ITL uses temporal-logic expressions to describe the behavior of a synchronous sequential system, with discrete time steps corresponding to clock cycles. [C9]