G7.6.3 Choose the State Codes

MediumOptimizeIcarus Verilog + Yosys · serverReview the topic

Choose 3-bit codes for a five-state machine so that its logic fits in 12 cells, using the adjacency rules.

Hardware context: A garage-door controller and a frame receiver that must survive a glitch in their state registers. Choose the state codes of a five-state controller so its logic fits a cell budget.

A small controller has five states and one input. Its arcs are fixed, and the review asks for less logic. Only the state codes may change.

This is an Optimize problem. The starter is correct but uses binary codes and takes 19 cells. Choose the codes of S1 to S4 so the design fits in 12 cells. S0 stays 000.

The check compares z with a model in every cycle and checks that st holds one code per state. Then the pinned flow counts the cells.

Signals in the Timeline

SignalWidthRole
xs24input of each check
Full specification
The module (keep the name and the ports)
module pick (
  input  logic       clk,
  input  logic       rst,    // synchronous reset, active high: S0
  input  logic       x,
  output logic       z,      // Moore output: 1 in S4 only
  output logic [2:0] st      // the state register itself; S0 must be 000
);
  ...
endmodule
Statenext if x = 0next if x = 1z
S0S0S10
S1S3S20
S2S4S20
S3S0S10
S4S0S11
RuleDetail
CodesFive different 3-bit codes; S0 is 000. st is the state register, so synthesis keeps your codes.
BudgetAt most 12 cells on the pinned flow (the starter: 19). A result equal to the limit passes.

Examples

Example 1

Every State, Then z
Input
x = 110010001100000000000000 (cycle 0 first)
Output
z_cycles = {3, 11}, codes_not_one_per_state = no

The stream visits all five states. z is 1 only in the cycles spent in S4, whatever its code.

Example 2

S1 To S3 and Back
Input
x = 101010101000000000000000 (cycle 0 first)
Output
z_cycles = {}, codes_not_one_per_state = no

Alternating bits move S0 to S1, S1 to S3 and S3 to S1. st must show the same code each time a state comes back.

Example 3

Ones Only
Input
x = 111111111111111111111111 (cycle 0 first)
Output
z_cycles = {}, codes_not_one_per_state = no

S0 goes to S1, then S2, which holds on 1. z stays 0.

Constraints and Contract

  • x is a known 0/1 value and changes only between edges.
  • Keep the module name and the ports. st is the only state register.

Hints

Hint 1

Rule 1: states with the same next state on the same input get adjacent codes. S0, S3 and S4 share both next states; S1 and S2 share one.

Hint 2

Three states cannot all be adjacent to each other. Pick two of S0, S3 and S4, then place S1 and S2 so the next states of one state are adjacent too.

Hint 3

The rules narrow the choice; they do not decide it. Several assignments that keep every rule pair adjacent still take 13 or 15 cells: measure a few.

What the grader checks: Five directed and ten seeded streams of 24 cycles after a reset. In every cycle z is compared with a JavaScript model, and st must hold one code per model state with S0 = 000. Then the design must fit in 12 cells on the pinned flow, with no latches.

The submitted design must synthesize with 0 latches and no combinational loop. It must use at most 12 cells; a result equal to the limit passes. Counts come from the pinned open-source synthesis flow. They are proxies for logic size and depth, not physical area or timing.

15 checks on Icarus Verilog + Yosys · server. 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

Every State, Then z

Input
x = 110010001100000000000000 (cycle 0 first)
Expected output
z_cycles = {3, 11}, codes_not_one_per_state = no

The stream visits all five states. z is 1 only in the cycles spent in S4, whatever its code.

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

Icarus Verilog + Yosys · server