Essential Hazards, the C-Element and Handshakes

Find the hazard no logic cover can remove, build the Muller C-element, and use it to join four-phase handshakes.

You Will Be Able To

  • Find an essential hazard with the three-change test on a flow table.
  • Explain why it shows when feedback is faster than an input, and fix it with feedback delay.
  • Describe the Muller C-element and build it from gates.
  • Follow a four-phase handshake and join two acknowledgements with a C-element.
Lesson
G7.11
Time
35 min
Runs on
Your browser
Check
5 questions

A sender must know that two receivers have both taken its data, but the receivers answer at different times. One small gate joins the answers. Here it is in a four-phase handshake.

Two Acknowledgements, One JoinOne column per change, from the lab run. ack is the C-element output.
0123456789101112reqack_aack_backrequestboth answeredboth reset
Scroll horizontally ↔
  1. Change 1

    req rises. Receiver A answers first; ack stays 0, because B has not answered.

  2. Change 3

    B answers too. Only now does ack rise.

  3. Change 4

    The sender drops req. B resets first, A later: ack holds 1 until both are 0.

  4. Change 6

    Both acks are 0, so ack falls. The sender may start the next request.

Measured: the lab below, on Icarus Verilog 12. Each column is one line of the run, at the time shown there.

Essential Hazards

Some hazards live in the flow table itself. The test: from a stable state, change one input once, and separately change it three times. If the two end states differ, the table has an essential hazard.

G7.10's table, from A at ab = 11b changesEnds in
Once11 to 10B
Three times11 to 10 to 11 to 10C

Read from the merged flow table of G7.10. One change leads to B; three lead to C.

In a circuit the danger is real when one gate gets the input change late. The new state variable comes round the loop. Then that gate sees the new state with the old input, as if b had changed three times.

The Feedback Outruns the Input
The Feedback Outruns the Inputg1 · NOTnr=1g2 · NOTnb=1g3 · BUFb_far=0g4 · ANDt1=0g5 · ANDt2=1g6 · ORY1=1g7 · ANDt3=1g8 · ANDt4=1g9 · ORY2=1g10 · ANDY1r=1g11 · ANDY2r=1d1 · BUFy1=1d2 · BUFy2=1r=0a=1b=0
r=0 a=1 b=0
g1 · NOTr=0 → nr=1
g2 · NOTb=0 → nb=1
g3 · BUFb=0 → b_far=0
g4 · ANDy2=1, b_far=0 → t1=0
g5 · ANDy1=1, y2=1 → t2=1
g6 · ORt1=0, t2=1 → Y1=1
g7 · ANDa=1, nb=1 → t3=1
g8 · ANDy2=1, a=1 → t4=1
g9 · ORt3=1, t4=1 → Y2=1
g10 · ANDY1=1, nr=1 → Y1r=1
g11 · ANDY2=1, nr=1 → Y2r=1
d1 · BUFY1r=1 → y1=1
d2 · BUFY2r=1 → y2=1
Read the connections
GateKindInputsOutput
g1NOTrnr
g2NOTbnb
g3BUFbb_far
g4ANDy2, b_fart1
g5ANDy1, y2t2
g6ORt1, t2Y1
g7ANDa, nbt3
g8ANDy2, at4
g9ORt3, t4Y2
g10ANDY1, nrY1r
g11ANDY2, nrY2r
d1BUFY1ry1
d2BUFY2ry2

Outputs: y1, y2. MUX inputs: d0, d1, select. Latch/flip-flop inputs: data, enable/clock. Unknown values are marked x; high impedance is folded into x in this model.

Gate delay 35. Settled after 35 gate delays from t = 0.

Output values at each gate delay01234567891011121314151617181920212223242526272829303132333435y1xxx000000000000000000000000000011111y2xxx000000000000000000000000111111111
Scroll horizontally ↔
Every computed frame
Timey1y2
0xx
1xx
2xx
300
400
500
600
700
800
900
1000
1100
1200
1300
1400
1500
1600
1700
1800
1900
2000
2100
2200
2300
2400
2500
2600
2701
2801
2901
3001
3111
3211
3311
3411
3511

  1. Step 21 · In A at ab = 11. b rose at 8 and a at 14. The circuit is in A (00), stable at ab = 11.
  2. Step 27 · y2 changes. b fell at 22. Through the short path, `Y2` rises and `y2` = 1 at 27: the move to B has happened.
  3. Step 28 · The old b is still there. `b_far` still shows 1, so the gate y2·b sees 1 and 1. `t1` rises: as if b had fallen and risen again.
  4. Step 35 · Wrong state. `y1` rose at 31 and now holds itself through y1·y2. The circuit sits in C (11), not B.

A slow wire carries b to one gate; the y2 loop has a delay of 1. The feedback arrives first.

No consensus term helps: the cover is already correct. The fix is timing. The feedback must not reach that gate before the input change does.

A Delay in the Feedback Loop
A Delay in the Feedback Loopg1 · NOTnr=1g2 · NOTnb=1g3 · BUFb_far=0g4 · ANDt1=0g5 · ANDt2=0g6 · ORY1=0g7 · ANDt3=1g8 · ANDt4=1g9 · ORY2=1g10 · ANDY1r=0g11 · ANDY2r=1d1 · BUFy1=0d2 · BUFy2=1r=0a=1b=0
r=0 a=1 b=0
g1 · NOTr=0 → nr=1
g2 · NOTb=0 → nb=1
g3 · BUFb=0 → b_far=0
g4 · ANDy2=1, b_far=0 → t1=0
g5 · ANDy1=0, y2=1 → t2=0
g6 · ORt1=0, t2=0 → Y1=0
g7 · ANDa=1, nb=1 → t3=1
g8 · ANDy2=1, a=1 → t4=1
g9 · ORt3=1, t4=1 → Y2=1
g10 · ANDY1=0, nr=1 → Y1r=0
g11 · ANDY2=1, nr=1 → Y2r=1
d1 · BUFY1r=0 → y1=0
d2 · BUFY2r=1 → y2=1
Read the connections
GateKindInputsOutput
g1NOTrnr
g2NOTbnb
g3BUFbb_far
g4ANDy2, b_fart1
g5ANDy1, y2t2
g6ORt1, t2Y1
g7ANDa, nbt3
g8ANDy2, at4
g9ORt3, t4Y2
g10ANDY1, nrY1r
g11ANDY2, nrY2r
d1BUFY1ry1
d2BUFY2ry2

Outputs: y1, y2. MUX inputs: d0, d1, select. Latch/flip-flop inputs: data, enable/clock. Unknown values are marked x; high impedance is folded into x in this model.

Gate delay 35. Settled after 35 gate delays from t = 0.

Output values at each gate delay01234567891011121314151617181920212223242526272829303132333435y1xxx0000xxxxxxx0000000000000000000000y2xxxxxxxxxx00000000000000000000000011
Scroll horizontally ↔
Every computed frame
Timey1y2
0xx
1xx
2xx
30x
40x
50x
60x
7xx
8xx
9xx
10x0
11x0
12x0
13x0
1400
1500
1600
1700
1800
1900
2000
2100
2200
2300
2400
2500
2600
2700
2800
2900
3000
3100
3200
3300
3401
3501

  1. Step 34 · Together. `y2` now arrives at 34, at the same time as the change on `b_far`. The gate y2·b never sees both at 1.
  2. Step 36 · Settled in B. The circuit ends in B (01), as the flow table says.

The same circuit with a delay of 8 in the y2 loop. The feedback can no longer outrun the input. At 8, y2 and the late b arrive together; in this model any loop delay of 7 or more ends in B. A real circuit adds margin for delay spread.

The Muller C-Element

The Muller C-element is the basic memory of handshake circuits. When its inputs agree, the output copies them. When they differ, the output holds.

A C-Element From Gates
A C-Element From Gatesg0 · ANDab=0g1 · ANDac=0g2 · ANDbc=0g3 · ORc=0a=0b=0
a=0 b=0
g0 · ANDa=0, b=0 → ab=0
g1 · ANDa=0, c=0 → ac=0
g2 · ANDb=0, c=0 → bc=0
g3 · ORab=0, ac=0, bc=0 → c=0
Read the connections
GateKindInputsOutput
g0ANDa, bab
g1ANDa, cac
g2ANDb, cbc
g3ORab, ac, bcc

Outputs: c. MUX inputs: d0, d1, select. Latch/flip-flop inputs: data, enable/clock. Unknown values are marked x; high impedance is folded into x in this model.

Gate delay 24. Settled after 24 gate delays from t = 0.

Output values at each gate delay0123456789101112131415161718192021222324cxx00000000001111111111110
Scroll horizontally ↔
Every computed frame
Timec
0x
1x
20
30
40
50
60
70
80
90
100
110
121
131
141
151
161
171
181
191
201
211
221
231
240

  1. Step 6 · a alone. `a` rose at 4. `b` is still 0, so no AND gate turns on: `c` holds 0.
  2. Step 12 · Both 1. `b` rose at 10. `ab` turns on and `c` rises at 12. Now `ac` and `bc` are on as well.
  3. Step 18 · a falls. `a` fell at 16, but `bc` is still on. `c` holds 1.
  4. Step 24 · Both 0. `b` fell at 22. Every AND gate is off, and `c` falls at 24.

c = ab + ac + bc. The two terms with c in them are the memory.

The C-Element as a Flow Table
Flow table. A circled entry is stable. The ringed cell is the present state and input.
Stateab = 00ab = 01ab = 11ab = 10c
lowlowlowhighlow0
highlowhighhighhigh1

low → high: stable in high.

StepInputPathOutput
000low0
110low0
211low → high1
301high1
400high → low0
501low0
611low → high1
Every step in words
  1. Start in low, stable under 00.
  2. low is already stable under 10.
  3. low → high: stable in high.
  4. high is already stable under 01.
  5. high → low: stable in low.
  6. low is already stable under 01.
  7. low → high: stable in high.

  1. Step 1. a rises alone: the inputs disagree, and c stays 0.
  2. Step 2. Both are 1: c rises.
  3. Step 3. a falls alone: the inputs disagree again, and c holds 1.
  4. Step 4. Both are 0: c falls. The output changes only when the inputs agree.

Two rows, one state variable. Where the inputs differ, each row is stable: that is the memory.

Four-Phase Handshakes

Circuits with no shared clock pass data with a handshake. In the four-phase protocol, req and ack each go up and come back down for every transfer.

  1. Request

    The sender puts the data out and raises req.

  2. Acknowledge

    The receiver takes the data and raises ack.

  3. Release

    The sender sees ack and drops req.

  4. Return to zero

    The receiver sees req low and drops ack. Both are back at 0.

With two receivers, the sender must wait for both. A C-element on the two acks does this: its output rises after the slower answer and falls after the slower reset.

One Request, Two Receivers, One Joined Acknowledgementreq goes to both receivers. Their acks meet at a C-element, whose output is the ack the sender sees.
  • I/O
  • Control / FSM
  • Control
One request, two receivers, one joined acknowledgementreq goes to both receivers. Their acks meet at a C-element, whose output is the ack the sender sees. io Sender drives req io Receiver A ack_a io Receiver B ack_b control C-element waits for both reqreqack_aack_back
  1. io Senderdrives req
    • req → Receiver A
    • req → Receiver B
  2. io Receiver Aack_a
    • ack_a → C-element
  3. io Receiver Back_b
    • ack_b → C-element
  4. control C-elementwaits for both
    • ack → Sender
  1. Request

    The sender raises req to both receivers at once.

  2. Answers

    Each receiver answers in its own time. The C-element output waits until both acks are 1.

  3. Joined

    Only then does the sender see ack. The return to zero works the same way, waiting for both resets.

Read the diagram as text
  • Sender: drives req
  • Receiver A: ack_a
  • Receiver B: ack_b
  • C-element: waits for both
  • Sender → Receiver A: req
  • Sender → Receiver B: req
  • Receiver A → C-element: ack_a
  • Receiver B → C-element: ack_b
  • C-element → Sender: ack

The lab's circuit. The C-element is the celem module.

EventTime in the laback
A answers70
B answers110
C-element output rises131
B resets161
A resets201
C-element output falls220

Measured: the first transfer of the lab. The C-element adds two gate delays after the later input.

Asked in interviews
  1. What is an essential hazard?

    A hazard in the flow table. One input change leads to one state; three changes of the same input lead to another. In a circuit it misfires when the new state comes back round its loop faster than the input change reaches some gate. It is fixed with delay in the feedback, not with logic.

  2. What is a Muller C-element?

    A gate whose output follows its inputs when they all agree and holds when they differ. From gates it is c = ab + ac + bc. It joins handshakes: its output changes only when every input has.

  3. Two-phase or four-phase handshake?

    Four-phase returns req and ack to 0 after each transfer: simple logic, but four edges per transfer. Two-phase uses each change of req and ack as an event, so it needs two edges per transfer but more complex logic.

Try It

Each line is printed when an ack changes. The first line is the C-element settling at 0: it starts unknown, and both inputs are 0.

ack rises 2 units after the later answer and falls 2 units after the later reset. That is one AND gate plus the OR gate.

Replace celem with a plain AND of the two acks and predict the line where ack falls. Then run it.

RUNIcarus Verilog · in your browser
Edit the code, then run it
Expected: t= 2 req=0 ack_a=0 ack_b=0 ack=0 t= 7 req=1 ack_a=1 ack_b=0 ack=0 t=11 req=1 ack_a=1 ack_b=1 ack=0 t=13 req=1 ack_a=1 ack_b=1 ack=1 t=16 req=0 ack_a=1 ack_b=0 ack=1 t=20 req=0 ack_a=0 ack_b=0 ack=1 t=22 req=0 ack_a=0 ack_b=0 ack=0 t=26 req=1 ack_a=1 ack_b=0 ack=0 t=30 req=1 ack_a=1 ack_b=1 ack=0 t=32 req=1 ack_a=1 ack_b=1 ack=1 t=35 req=0 ack_a=1 ack_b=0 ack=1 t=39 req=0 ack_a=0 ack_b=0 ack=1 t=41 req=0 ack_a=0 ack_b=0 ack=0
Read included file: tb.sv
// tb.sv: the bench (read-only). A sender talks to two receivers with a four-phase handshake. Each receiver copies
// req to its own ack after its own delay; a C-element joins the two acks into one.
module tb;
  logic req = 0, ack_a = 0, ack_b = 0;
  wire  ack;
  celem join2 (.a(ack_a), .b(ack_b), .c(ack));
  always @(posedge req) #3 ack_a = 1;     // receiver A: fast to answer, slow to reset
  always @(negedge req) #6 ack_a = 0;
  always @(posedge req) #7 ack_b = 1;     // receiver B: slow to answer, fast to reset
  always @(negedge req) #2 ack_b = 0;
  always @(ack_a or ack_b or ack) #0 $display("t=%2t  req=%b  ack_a=%b ack_b=%b  ack=%b", $time, req, ack_a, ack_b, ack);
  initial begin
    #4;
    repeat (2) begin
      req = 1;                            // phase 1: request
      wait (ack == 1);                    // phase 2: both receivers have answered
      #1 req = 0;                         // phase 3: release
      wait (ack == 0);                    // phase 4: both have reset
      #1;
    end
  end
endmodule

Check Yourself

ConceptA flow table has an essential hazard at a stable state. What does the three-change test show there?
ConceptWhat is the output of a C-element with inputs 1 and 0, if it was 1 before?
Predict the outputThe lab's C-element gets a = 1, then b = 1, then a = 0. The program prints c each time. Predict the exact line.
// celem: a Muller C-element from gates. The output copies the inputs when they agree and holds when they differ:
// c = ab + ac + bc, the majority of a, b and the output itself.
module celem (input wire a, b, output wire c);
  wire ab, ac, bc;
  and #1 g1 (ab, a, b);
  and #1 g2 (ac, a, c);
  and #1 g3 (bc, b, c);
  or  #1 g4 (c, ab, ac, bc);
endmodule

module tb;
  logic a = 0, b = 0;
  wire c;
  celem u (.a(a), .b(b), .c(c));
  initial begin
    #5 a = 1; #5 $write("%b", c);
    b = 1;    #5 $write("%b", c);
    a = 0;    #5 $display("%b", c);
  end
endmodule
ConceptIn a four-phase handshake, when may the sender raise req for the next transfer?
ConceptAn essential hazard misfires on some chips. Which change makes it worse?

Common Mistakes

Wrong Treat an essential hazard like a static hazard and add a consensus term.

An essential hazard is in the flow table, not in the cover. With every prime term present, the gate still sees the new state with the old input.

Fix Make the feedback slower than the input path: add delay in the loop, or speed up the input wire.

Wrong Add the delay on the slow input path.

The hazard happens because the input arrives late at one gate. Delaying the input more makes the window wider.

Fix Put the delay in the feedback loop, so the new state arrives after the input change.

Wrong Build a C-element from one AND gate.

AND rises when both inputs are 1, but it also falls when only one input falls. A C-element must hold until both agree.

Fix Feed the output back: c = ab + ac + bc holds its value while the inputs differ.

Wrong Raise the next request before the acknowledgement has gone back to 0.

In a four-phase handshake, the return to zero is part of the protocol. A new request during it can be lost or taken twice.

Fix Wait for ack = 0 after dropping req, then start the next request.

Remember

  • An essential hazard: one input change and three changes of it end in different states.
  • It misfires when feedback outruns an input to some gate; add delay in the feedback, not logic.
  • A Muller C-element copies its inputs when they agree and holds when they differ: c = ab + ac + bc.
  • A four-phase handshake goes req up, ack up, req down, ack down; a C-element joins several acks.

Practice

Report a problem with this page