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.
- Change 1
req rises. Receiver A answers first; ack stays 0, because B has not answered.
- Change 3
B answers too. Only now does ack rise.
- Change 4
The sender drops req. B resets first, A later: ack holds 1 until both are 0.
- 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 = 11 | b changes | Ends in |
|---|---|---|
| Once | 11 to 10 | B |
| Three times | 11 to 10 to 11 to 10 | C |
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.
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.
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.
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.
Request
The sender puts the data out and raises req.
Acknowledge
The receiver takes the data and raises ack.
Release
The sender sees ack and drops req.
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.
- I/O
- Control / FSM
- Control
- Request
The sender raises req to both receivers at once.
- Answers
Each receiver answers in its own time. The C-element output waits until both acks are 1.
- 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.
| Event | Time in the lab | ack |
|---|---|---|
| A answers | 7 | 0 |
| B answers | 11 | 0 |
| C-element output rises | 13 | 1 |
| B resets | 16 | 1 |
| A resets | 20 | 1 |
| C-element output falls | 22 | 0 |
Measured: the first transfer of the lab. The C-element adds two gate delays after the later input.
Asked in interviews
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.
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.
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.
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=0Read 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
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.