G7.2.1 Read the Machine from Its Gates

MediumImplementIcarus · browser samples / server checksReview the topic

Analyse a netlist with a JK and a D flip-flop: its excitation equations, its transition table and its run on a stream.

Hardware context: An undocumented two-flip-flop circuit on an old controller board, one JK and one D flip-flop. Write the transition table of a JK and D netlist and follow it on two streams.

An old controller board has a two-flip-flop circuit with no documentation. One flip-flop is a JK, the other a D. Before anyone reuses it, you must write down its transition table and output.

This is an Implement problem with no logic to write. Analyse the netlist and write each answer as a constant. The first three constants are worked examples and are already correct.

State codes are PQ read as a binary number: 2 means P = 1 and Q = 0. The check compares every constant with the right value and names the first wrong one.

Signals in the Timeline

SignalWidthRole
question8input of each check
Full specification
The netlist (inputs x; flip-flop outputs P and Q; output y)
// Flip-flop P is a JK flip-flop and Q is a D flip-flop. Both load at the rising clock edge.
// Each gate lists its output first, then its inputs.
not g1 (nq, Q);
not g2 (nx, x);
and g3 (jp, Q, x);       // J input of P
buf g4 (kp, nq);         // K input of P
xor g5 (dq, P, x);       // D input of Q
and g6 (y, P, nq, nx);   // the output y
ConstantWhat to write
JP_01_X1J of P when PQ = 01 and x = 1 (Q and x are both 1).
KP_01_X1K of P when PQ = 01 and x = 1 (it is Q', so 0).
NEXT_00_X0The next PQ from PQ = 00 with x = 0, as a number 0-3 (P is the high bit).
NEXT_00_X1The next PQ from PQ = 00 with x = 1, as a number 0-3 (P is the high bit).
NEXT_01_X0The next PQ from PQ = 01 with x = 0, as a number 0-3 (P is the high bit).
NEXT_01_X1The next PQ from PQ = 01 with x = 1, as a number 0-3 (P is the high bit).
NEXT_10_X0The next PQ from PQ = 10 with x = 0, as a number 0-3 (P is the high bit).
NEXT_10_X1The next PQ from PQ = 10 with x = 1, as a number 0-3 (P is the high bit).
NEXT_11_X0The next PQ from PQ = 11 with x = 0, as a number 0-3 (P is the high bit).
NEXT_11_X1The next PQ from PQ = 11 with x = 1, as a number 0-3 (P is the high bit).
Y_01_X0The output y in state PQ = 01 while x = 0.
Y_10_X0The output y in state PQ = 10 while x = 0.
Y_10_X1The output y in state PQ = 10 while x = 1.
Y_11_X0The output y in state PQ = 11 while x = 0.
AFTER_1011The state PQ (0-3) after reset to 00 and the inputs x = 1, 0, 1, 1 at four edges.
Y_ONESFrom reset (00) with x = 1, 1, 1, 0, 1, 1, 0: the number of cycles in which y = 1.
SELF_LOOPSHow many of the eight (state, x) pairs leave the state unchanged.

y is a Mealy output: it reads the present state and the present x, during the cycle. The flip-flops load together at the edge that ends the cycle.

Examples

Example 1

Worked Example: J of P
Input
J of P when PQ = 01 and x = 1 (Q and x are both 1)
Output
jp_01_x1 = 1

JP = Q·x. In state 01 with x = 1 both are 1, so JP = 1. This constant is already filled in.

Example 2

Worked Example: K of P
Input
K of P when PQ = 01 and x = 1 (it is Q', so 0)
Output
kp_01_x1 = 0

KP = Q'. With Q = 1 it is 0. So in state 01 with x = 1, P sets: J = 1, K = 0.

Example 3

Worked Example: One Table Entry
Input
the next PQ from PQ = 00 with x = 0, as a number 0-3 (P is the high bit)
Output
next_00_x0 = 0

From 00 with x = 0: JP = 0 and KP = 1, so P stays 0; DQ = P xor x = 0. The next state is 00, code 0.

Constraints and Contract

  • Keep the module name answer and the names of the constants.
  • State codes are 0 to 3, with P as the high bit.

Hints

Hint 1

Write the excitation equations first: JP, KP and DQ from the gates. Then the next-state equations: P+ = JP·P' + KP'·P and Q+ = DQ.

Hint 2

Fill one row at a time. Set P, Q and x, compute JP, KP and DQ, then P+ and Q+. Never use J alone as the next value of P.

Hint 3

For the stream questions, walk the table you built. y belongs to the cycle before each edge, so read it from the present state.

What the grader checks: The check reads each constant and compares it with a value computed in JavaScript from the netlist's equations. It cannot see how a value was found.

17 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 1 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

Worked Example: J of P

Input
J of P when PQ = 01 and x = 1 (Q and x are both 1)
Expected output
jp_01_x1 = 1

JP = Q·x. In state 01 with x = 1 both are 1, so JP = 1. This constant is already filled in.

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

Icarus · browser samples / server checks