A9.2.2 Make the Proof Finish

MediumDebugIcarus · browser samples / server checksReview the topic

A safe decade counter gives an unknown proof. Say which helper assertions close it, which do not, and which only seem to.

Hardware context: A decade counter whose safety proof does not close by induction. Pick a true helper invariant that closes the proof, and reject false or assumed ones.

A decade counter never reaches 12, but prove reports UNKNOWN: induction starts from unreachable states such as 11. A helper assertion can rule them out.

Write answer(q). For questions 3 to 7 return the verdict of one formal run: 1 for PASS, 0 for FAIL, 2 for UNKNOWN.

Questions 0 to 2 are worked examples on a free-running counter. Questions 3 to 7 are graded only by the full check.

Signals in the Timeline

SignalWidthRole
question4input of each check
Full specification
The decade counter, questions 3 to 7
module top(input clk, input en, output reg [3:0] cnt = 0);
  // A decade counter: 0 to 9, then back to 0.
  always @(posedge clk) if (en) cnt <= (cnt == 4'd9) ? 4'd0 : cnt + 4'd1;
endmodule
q=3: No helper. Mode prove, depth 8, smtbmc yices. props.sv:
never12: assert property (@(posedge clk) cnt != 4'd12);
q=4: Helper: assert cnt <= 9. Mode prove, depth 2, smtbmc yices. props.sv:
never12: assert property (@(posedge clk) cnt != 4'd12);
helper: assert property (@(posedge clk) cnt <= 4'd9);
q=5: Helper: assert cnt != 11. Mode prove, depth 2, smtbmc yices. props.sv:
never12: assert property (@(posedge clk) cnt != 4'd12);
helper: assert property (@(posedge clk) cnt != 4'd11);
q=6: A false helper: assert cnt <= 8, bmc. Mode bmc, depth 20, smtbmc yices. props.sv:
never12: assert property (@(posedge clk) cnt != 4'd12);
helper: assert property (@(posedge clk) cnt <= 4'd8);
q=7: The helper as an assumption: assume cnt <= 9. Mode prove, depth 2, smtbmc yices. props.sv:
never12: assert property (@(posedge clk) cnt != 4'd12);
helper: assume property (@(posedge clk) cnt <= 4'd9);
The free-running counter, questions 0 to 2
module top(input clk, output reg [3:0] cnt = 0);
  always @(posedge clk) cnt <= cnt + 4'd1;     // 0, 1, ..., 15, 0, ...
endmodule
q=0: Free counter, prove. Mode prove, depth 4, smtbmc yices. props.sv:
never12: assert property (@(posedge clk) cnt != 4'd12);
q=1: Free counter, bmc depth 20. Mode bmc, depth 20, smtbmc yices. props.sv:
never12: assert property (@(posedge clk) cnt != 4'd12);
q=2: Free counter, bmc depth 10. Mode bmc, depth 10, smtbmc yices. props.sv:
never12: assert property (@(posedge clk) cnt != 4'd12);

Simulator note: Every key was measured with the formal engine v1 (smtbmc yices). Your answer function is checked by a small bench on Icarus 12.

Examples

Example 1

Free Counter, Prove
Input
answer(0)
Output
answer = 2

The counter does reach 12, so no proof exists; induction alone cannot decide at depth 4.

Example 2

Free Counter, Bmc Depth 20
Input
answer(1)
Output
answer = 0

Twenty steps reach the count of 12.

Example 3

Free Counter, Bmc Depth 10
Input
answer(2)
Output
answer = 1

Ten steps are too few: a bounded PASS.

Constraints and Contract

  • Return one value per question from answer(q).
  • Keep the function header.

Hints

Hint 1

Induction asks: from any state where the properties held for a few steps, can the next step break them? Unreachable states count too.

Hint 2

A helper closes the proof when it is true, and it rules out every bad unreachable state.

Hint 3

An assumption is never checked. What does a PASS with an assumed helper prove?

What the grader checks: Eight constant answers: three worked examples and five graded questions, each the verdict of one real formal run.

8 checks on Icarus · browser samples / server checks. Run the examples first, then check the full regression. Full checks use the server judge. Downloads contain public samples only. A passing result establishes the tested cases, not a proof for all possible inputs.

See all 3 steps and the final capstone

Report a problem with this page

Your code SystemVerilogSaved locally
Ln 1, Col 1Tab indents · Ctrl/⌘ + Enter runs samples
Not run yet

Free Counter, Prove

Input
answer(0)
Expected output
answer = 2

The counter does reach 12, so no proof exists; induction alone cannot decide at depth 4.

Run samples executes all 3 public checks. Check all tests runs 8 checks on the server.

Icarus · browser samples / server checks