G7.3.2 A Controller from JK Flip-Flops

HardImplementIcarus · browser samples / server checksReview the topic

Design a three-state wash controller from JK flip-flop and gate cells within seven cells, so that its unused code returns to idle.

Hardware context: A snack machine that sells a 20-cent item with change, and a washing-machine controller built from two JK flip-flops. Build a three-state controller from JK flip-flop cells within seven cells, safe from its unused code.

A washing-machine board has two JK flip-flops left and room for five gates. The controller must fill the drum when started, spin it when filling is done, and go idle when spinning is done.

This is an Implement problem in cells. Build wash from the cell library only, with at most 7 cells in all, flip-flops included. The state codes are given. The unused code 11 must reach IDLE at the next clock edge.

The check runs streams of start and done, and sometimes upsets the board: every JK flip-flop is set to 1. It records the state in every cycle and counts your cells.

Signals in the Timeline

SignalWidthRole
script48input of each check
Full specification
The cell library (read-only)
// cells.sv: the cell library (read-only). Gates take 1 time unit.
// Every cell takes 1 time unit, whatever its fan-in. Ports are (y, inputs...): output first.
// Each cell adds 1 to the bench's cell counter when the simulation starts.
module INV   (output wire y, input wire a);                not #1 (y, a);             initial tb.cells++; endmodule
module AND2  (output wire y, input wire a, b);             and #1 (y, a, b);          initial tb.cells++; endmodule
module AND3  (output wire y, input wire a, b, c);          and #1 (y, a, b, c);       initial tb.cells++; endmodule
module OR2   (output wire y, input wire a, b);             or #1 (y, a, b);           initial tb.cells++; endmodule
module OR3   (output wire y, input wire a, b, c);          or #1 (y, a, b, c);        initial tb.cells++; endmodule
module NAND2 (output wire y, input wire a, b);             nand #1 (y, a, b);         initial tb.cells++; endmodule
module NOR2  (output wire y, input wire a, b);             nor #1 (y, a, b);          initial tb.cells++; endmodule
module JKFF       (output reg q, input wire j, k, clk, r);   // a JK flip-flop: rising edge, asynchronous reset r
  always @(posedge clk or posedge r) if (r) q <= 1'b0; else q <= (j & ~q) | (~k & q);
  always @(posedge tb.upset) q <= 1'b1;                       // the bench's upset sets every JK flip-flop to 1
  initial tb.cells++;
endmodule

The module (keep the name and the ports)
module wash (
  input  wire clk,
  input  wire rst,      // asynchronous reset, active high: IDLE
  input  wire start,
  input  wire done,
  output wire q1,       // the state: IDLE 00, FILL 01, SPIN 10
  output wire q0
);
  ...
endmodule
StateCode q1 q0Next state
IDLE00FILL if start = 1, else IDLE
FILL01SPIN if done = 1, else FILL
SPIN10IDLE if done = 1, else SPIN
unused11IDLE, whatever the inputs

Only cell instances and wires are allowed: no assign, no always block, no operators. An upset comes between edges and sets every JK flip-flop to 1.

Examples

Example 1

One Full Wash
Input
start/done per cycle: 10 00 00 01 00 01 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
Output
state_cycle0 = IDLE (0), state_cycle1 = FILL (1), state_cycle2 = FILL (1), state_cycle3 = FILL (1), state_cycle4 = SPIN (2), state_cycle5 = SPIN (2), state_cycle6 = IDLE (0), state_cycle7 = IDLE (0), state_cycle8 = IDLE (0), state_cycle9 = IDLE (0), state_cycle10 = IDLE (0), state_cycle11 = IDLE (0), state_cycle12 = IDLE (0), state_cycle13 = IDLE (0), state_cycle14 = IDLE (0), state_cycle15 = IDLE (0), state_cycle16 = IDLE (0), state_cycle17 = IDLE (0), state_cycle18 = IDLE (0), state_cycle19 = IDLE (0), state_cycle20 = IDLE (0), state_cycle21 = IDLE (0), state_cycle22 = IDLE (0), state_cycle23 = IDLE (0)

start in cycle 0 moves IDLE to FILL. done in cycle 3 moves FILL to SPIN, and done in cycle 5 moves SPIN back to IDLE.

Example 2

Start Held Down Through a Whole Wash
Input
start/done per cycle: 10 10 10 11 10 10 11 11 10 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
Output
state_cycle0 = IDLE (0), state_cycle1 = FILL (1), state_cycle2 = FILL (1), state_cycle3 = FILL (1), state_cycle4 = SPIN (2), state_cycle5 = SPIN (2), state_cycle6 = SPIN (2), state_cycle7 = IDLE (0), state_cycle8 = FILL (1), state_cycle9 = FILL (1), state_cycle10 = FILL (1), state_cycle11 = FILL (1), state_cycle12 = FILL (1), state_cycle13 = FILL (1), state_cycle14 = FILL (1), state_cycle15 = FILL (1), state_cycle16 = FILL (1), state_cycle17 = FILL (1), state_cycle18 = FILL (1), state_cycle19 = FILL (1), state_cycle20 = FILL (1), state_cycle21 = FILL (1), state_cycle22 = FILL (1), state_cycle23 = FILL (1)

start matters only in IDLE. Held high during FILL and SPIN, it changes nothing until the machine is idle again.

Example 3

An Upset While Idle, Done Low
Input
start/done per cycle: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00; upset to 11 at the start of cycle 2
Output
state_cycle0 = IDLE (0), state_cycle1 = IDLE (0), state_cycle2 = stray 11 (3), state_cycle3 = IDLE (0), state_cycle4 = IDLE (0), state_cycle5 = IDLE (0), state_cycle6 = IDLE (0), state_cycle7 = IDLE (0), state_cycle8 = IDLE (0), state_cycle9 = IDLE (0), state_cycle10 = IDLE (0), state_cycle11 = IDLE (0), state_cycle12 = IDLE (0), state_cycle13 = IDLE (0), state_cycle14 = IDLE (0), state_cycle15 = IDLE (0), state_cycle16 = IDLE (0), state_cycle17 = IDLE (0), state_cycle18 = IDLE (0), state_cycle19 = IDLE (0), state_cycle20 = IDLE (0), state_cycle21 = IDLE (0), state_cycle22 = IDLE (0), state_cycle23 = IDLE (0)

The upset puts the board in 11 during cycle 2. With done and start both 0, the next edge must still give IDLE.

Constraints and Contract

  • All inputs are known 0/1 values and change only between edges.
  • Use only cells from the library, at most 7 of them.

Hints

Hint 1

For each bit, fill a J map and a K map from the JK excitation table. When the bit is 0, K is a don't-care; when it is 1, J is.

Hint 2

The unused code is not a don't-care here. Its next state is 00, so in row 11 both K inputs must be 1.

Hint 3

Each J and K needs one gate at most. A J input that must ignore start in SPIN needs q1' in it.

What the grader checks: Seven directed and twelve seeded streams of 24 cycles, some with upsets to code 11. The state is compared with a JavaScript model in every cycle, and the cells are counted. Only library cells may be used.

20 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

One Full Wash

Input
start/done per cycle: 10 00 00 01 00 01 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
Expected output
state_cycle0 = IDLE (0), state_cycle1 = FILL (1), state_cycle2 = FILL (1), state_cycle3 = FILL (1), state_cycle4 = SPIN (2), state_cycle5 = SPIN (2), state_cycle6 = IDLE (0), state_cycle7 = IDLE (0), state_cycle8 = IDLE (0), state_cycle9 = IDLE (0), state_cycle10 = IDLE (0), state_cycle11 = IDLE (0), state_cycle12 = IDLE (0), state_cycle13 = IDLE (0), state_cycle14 = IDLE (0), state_cycle15 = IDLE (0), state_cycle16 = IDLE (0), state_cycle17 = IDLE (0), state_cycle18 = IDLE (0), state_cycle19 = IDLE (0), state_cycle20 = IDLE (0), state_cycle21 = IDLE (0), state_cycle22 = IDLE (0), state_cycle23 = IDLE (0)

start in cycle 0 moves IDLE to FILL. done in cycle 3 moves FILL to SPIN, and done in cycle 5 moves SPIN back to IDLE.

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

Icarus · browser samples / server checks