Half Duplex: CSMA/CD and Why 64 Bytes
Put two stations on one wire, make them collide, and find out why the shortest frame is 64 octets.
You Will Be Able To
- Describe deference, collision detection and the jam on a shared wire.
- Compute the backoff range after the n-th collision.
- Explain why a frame must last longer than the round trip of the wire.
- Tell which of these rules still apply on a full-duplex link.
- Lesson
- P11.12
- Time
- 30 min
- Runs on
- Your browser
- Check
- 6 questions
Classic Ethernet put every station on one cable. Only one may talk at a time. Who goes first, and what if two start together?
| Shortest frame | Every collision is seen up to a one-way delay of | Round trip |
|---|---|---|
| 32 octets | 20 octet times | 320 bit times |
| 48 octets | 28 octet times | 448 bit times |
| 64 octets | 36 octet times | 576 bit times |
Bench sweep: B starts at every moment before A's signal reaches it. Longer frames keep A sending until the collision comes back.
Listen, Then Talk
The access method is CSMA/CD: carrier sense, multiple access, collision detection (4.1.2.2).
- I/O
- Channel / handshake
- Control / FSM
- Data
- Control
- Carrier sense
A hears a quiet wire for a full gap and starts.
- Multiple access
B has not heard A yet, so B starts too.
- Collision detect
B hears A at once. A hears B only one delay later.
- Recover
Each sender jams, then waits a random number of slots before trying again.
Read the diagram as text
- Station A: sends, listens
- Shared wire: one-way delay d
- Station B: sends, listens
- Jam, then back off: 32 bits, then r slots
- Station A → Shared wire
- Shared wire → Station B
- Station B → Shared wire: collision
- Shared wire → Station A: comes back
- Station A → Jam, then back off
- Station B → Jam, then back off
IEEE Std 802.3-2022 4.1.2.2 and 4.2.3.2. The bench gives the wire a delay in octet times.
A station with a frame watches the wire. While it is busy, the station defers. After it goes quiet, the station waits one interpacket gap, 96 bit times, then starts (4.2.3.2.1).
Two stations can still start together. Each hears a quiet wire because the other's signal has not arrived yet.
Collision and Jam
A sender that sees a collision does not stop at once. It sends a jam of 32 bits first (4.2.3.2.4). The jam makes sure every sender sees the collision.
| Time (octet times) | Event |
|---|---|
| 0 | A starts attempt 1 |
| 15 | B starts attempt 1 |
| 20 | B hears a collision after 5 octets and jams |
| 23 | B backs off 1 slots |
| 35 | A hears a collision after 35 octets and jams |
| 38 | A backs off 0 slots |
| 56 | A starts attempt 2 |
| 127 | A sends its last octet (72 in the packet) |
| 160 | B starts attempt 2 |
| 231 | B sends its last octet (72 in the packet) |
Bench run of the example: one-way delay 20 octet times, A ready at 0, B at 15. After the collision A waits 0 slots, B 1.
- Cycle 3
B starts at t = 15. A's first octet reaches B at t = 20, so B jams at once.
- Cycle 7
B's signal reaches A at t = 35. A jams. A waits 0 slots after it; B waits 1 slot.
- Cycle 11
The far ends still see the old signals for 20 octet times.
- Cycle 12
A wins the retry: it starts again at t = 56, after a quiet gap.
Bench run of the example. Columns are t = 0, 5, 10 up to 75.
The bench counts time in octet times, 8 bit times each. So the jam is 4 octet times, the gap 12, and one slot 64.
Truncated Binary Exponential Backoff
After the jam, a sender waits a whole number of slot times before trying again. Before the n-th retry it picks r at random, with 0 ≤ r < 2^k and k = min(n, 10) (4.2.3.2.5).
| Collision n | k = min(n, 10) | r from | Longest wait at 10 Mb/s |
|---|---|---|---|
| 1 | 1 | 0 to 1 | 0.0512 ms |
| 2 | 2 | 0 to 3 | 0.1536 ms |
| 3 | 3 | 0 to 7 | 0.3584 ms |
| 4 | 4 | 0 to 15 | 0.768 ms |
| 5 | 5 | 0 to 31 | 1.5872 ms |
| 6 | 6 | 0 to 63 | 3.2256 ms |
| 7 | 7 | 0 to 127 | 6.5024 ms |
| 8 | 8 | 0 to 255 | 13.056 ms |
| 9 | 9 | 0 to 511 | 26.1632 ms |
| 10 | 10 | 0 to 1,023 | 52.3776 ms |
| 11 | 10 | 0 to 1,023 | 52.3776 ms |
| 12 | 10 | 0 to 1,023 | 52.3776 ms |
| 13 | 10 | 0 to 1,023 | 52.3776 ms |
| 14 | 10 | 0 to 1,023 | 52.3776 ms |
| 15 | 10 | 0 to 1,023 | 52.3776 ms |
| 16 | give up | excessive collisions |
IEEE Std 802.3-2022 4.2.3.2.5 and 4.4.2. One slot is 512 bit times = 51.2 µs at 10 Mb/s. Bench arithmetic.
The range doubles with each collision, then stops growing at 1,024 slots. That is the "truncated" part. After 16 attempts the frame is dropped as an error.
Twin no_backoff = 1: both stations retry after the gap alone. The bench measured this with its full transmitter, which draws r at random and gives up after 16 attempts. That model is private, because P11.12.2 grades its retry decision.
In all 20 bench runs started together, every frame collided 16 times and was given up: 40 of 40 frames.
With backoff, all 20 runs delivered both frames. Each frame saw 1.60 collisions on average and 2 at most.
Why the Shortest Frame Is 64 Octets
A sender only notices a collision while it is still sending. If its frame is too short, it finishes first and walks away.
The bench made both frames 32 octets on a wire with a delay of 30 octet times. B started at t = 29.
A saw no collision and believed its frame was sent. Yet B never received it: the frame was lost and nobody retried.
Padded to 64 octets, the same frames collided, backed off and were both delivered.
That is why the slot time must be longer than the round trip plus the jam (4.2.3.2.3). The slot also bounds a collision fragment and is the backoff unit.
The minimum frame of 512 bits (4.2.3.3) is one slot. With the 64-bit preamble the bench saw every collision up to a round trip of 576 bit times. A real network keeps its round trip plus jam inside 512, for margin.
A collision seen later than one slot into the packet is a late collision. It points to a round trip that is too long (29.3.1.2 i). Or it points to a duplex mismatch: a full-duplex station at the far end sends whenever it likes (4.2.3.2.6). aLateCollisions counts it (30.3.1.1.10).
One Gigabit: Carrier Extension, and Full Duplex
| Parameter | Up to 100 Mb/s | 1 Gb/s | Above 1 Gb/s |
|---|---|---|---|
| slotTime | 512 bit times | 4096 bit times | not applicable |
| jamSize | 32 bits | 32 bits | not applicable |
| attemptLimit | 16 | 16 | not applicable |
| backoffLimit | 10 | 10 | not applicable |
| minFrameSize | 512 bits (64 octets) | 512 bits | 512 bits |
| burstLimit | not applicable | 65,536 bits | not applicable |
IEEE Std 802.3-2022 Table 4-2 (4.4.2). Above 1 Gb/s every MAC is full duplex.
At 1 Gb/s a 512-bit frame lasts only 512 ns. The slot was raised to 4096 bit times without changing the minimum frame (4.2.3.4).
A short frame is followed by extension symbols until it lasts one slot. A sender may also send a burst of frames up to burstLimit (4.2.3.2.7). Neither was much deployed.
At 1 Gb/s a late collision is never retried: the MAC must stop and report it (4.2.8). At 10 and 100 Mb/s the 4.2.8 procedure retries it, but an implementation may stop.
A full-duplex MAC never defers to received traffic, never jams and never backs off (4.2.3.2.6). Only the gap stays. Every link above 1 Gb/s is full duplex.
Try It
Two stations, A and B, at the two ends of a wire with a one-way delay of 20 octet times. Each sends one 64-octet frame.
B starts at t = 15, before A's signal arrives. Both jam and back off. This readable station takes its waits from plan: A waits 0 slots, B waits 1, so A wins the retry.
Add w.a.no_backoff = 1; w.b.no_backoff = 1; before w.run, and change 15 to 0. Both now retry after the gap alone and collide every time: 8 attempts each in 400 octet times.
This readable station never gives up. A real MAC draws r at random and stops after 16 attempts: that decision is P11.12.2.
t=0: A starts attempt 1 t=15: B starts attempt 1 t=20: B hears a collision after 5 octets and jams t=23: B backs off 1 slots t=35: A hears a collision after 35 octets and jams t=38: A backs off 0 slots t=56: A starts attempt 2 t=127: A sends its last octet (72 in the packet) t=160: B starts attempt 2 t=231: B sends its last octet (72 in the packet) delivered: A 1, B 1Read included file: hs_pkg.sv
`timescale 1ns/1ns
// hs_pkg.sv: shared pure functions, and the bench random generator (read-only).
package hs_pkg;
// xorshift32 (Marsaglia 2003): a linear generator over GF(2), period 2^32 - 1. A zero state is
// replaced by 1, because zero maps to itself.
function automatic [31:0] xs32(input [31:0] s);
reg [31:0] x;
x = (s == 32'd0) ? 32'd1 : s;
x = x ^ (x << 13); x = x ^ (x >> 17); x = x ^ (x << 5);
return x;
endfunction
// A Fibonacci PRBS generator x^n + x^m + 1 (PRBS7: 7,6; PRBS9: 9,5; PRBS15: 15,14; PRBS23: 23,18;
// PRBS31: 31,28). The output bit is s[n-1]; the next state shifts the feedback into bit 0.
function automatic [31:0] prbs_next(input [31:0] s, input int n, input int m);
reg fb;
fb = s[n-1] ^ s[m-1];
return ((s << 1) | {31'd0, fb}) & ((n == 32) ? 32'hffffffff : ((32'd1 << n) - 32'd1));
endfunction
function automatic int ones(input [63:0] v);
int n; n = 0;
for (int i = 0; i < 64; i++) n += v[i];
return n;
endfunction
// GF(16) with x^4 + x + 1, and GF(1024) with x^10 + x^3 + 1: shift-and-add multiply, no tables.
function automatic [3:0] gf16_mul(input [3:0] a, input [3:0] b);
reg [3:0] p, x; p = 4'd0; x = a;
for (int i = 0; i < 4; i++) begin
if (b[i]) p = p ^ x;
x = x[3] ? ({x[2:0], 1'b0} ^ 4'b0011) : {x[2:0], 1'b0};
end
return p;
endfunction
function automatic [3:0] gf16_pow(input int e); // alpha^e, alpha = x
reg [3:0] p; int k; p = 4'd1; k = e % 15; if (k < 0) k += 15;
for (int i = 0; i < k; i++) p = gf16_mul(p, 4'd2);
return p;
endfunction
function automatic int gf16_log(input [3:0] a); // -1 for 0
reg [3:0] p; p = 4'd1;
if (a == 4'd0) return -1;
for (int i = 0; i < 15; i++) begin if (p == a) return i; p = gf16_mul(p, 4'd2); end
return -1;
endfunction
function automatic [9:0] gf1024_mul(input [9:0] a, input [9:0] b);
reg [9:0] p, x; p = 10'd0; x = a;
for (int i = 0; i < 10; i++) begin
if (b[i]) p = p ^ x;
x = x[9] ? ({x[8:0], 1'b0} ^ 10'b0000001001) : {x[8:0], 1'b0};
end
return p;
endfunction
function automatic [9:0] gf1024_pow(input int e);
reg [9:0] p; int k; p = 10'd1; k = e % 1023; if (k < 0) k += 1023;
for (int i = 0; i < k; i++) p = gf1024_mul(p, 10'd2);
return p;
endfunction
endpackage
// hs_rng: the bench's random numbers. Same seed, same numbers, on every engine.
module hs_rng;
int unsigned s = 32'h2545f491;
function automatic void seed(input int unsigned v); s = (v == 0) ? 32'd1 : v; endfunction
function automatic int unsigned next(); s = hs_pkg::xs32(s); return s; endfunction
function automatic int below(input int n); s = hs_pkg::xs32(s); return (n <= 0) ? 0 : int'(s % n); endfunction
function automatic bit bit1(); s = hs_pkg::xs32(s); return s[16]; endfunction
function automatic bit chance_ppm(input int ppm); s = hs_pkg::xs32(s); return (s % 1000000) < ppm; endfunction
function automatic [7:0] byte8(); s = hs_pkg::xs32(s); return s[23:16]; endfunction
endmodule
Read included file: hs_code.sv
`timescale 1ns/1ns
// hs_code.sv: line codes, CRCs and scramblers (read-only).
// ---------------------------------------------------------------------------------------------
// hs_8b10b: 8b/10b encoder and decoder with running disparity and the 12 K codes.
// code[9:0] = {a,b,c,d,e,i,f,g,h,j}; bit a (code[9]) goes on the wire first. rd: 0 = RD-, 1 = RD+.
// encode(d, k, rd_in) -> {rd_out, code[9:0]} (11 bits)
// decode(code, rd_in) -> {rd_out, disp_err, code_err, k, d[7:0]} (12 bits)
// enc(d, k) / dec(code): the same, with the running disparity kept in rd_tx / rd_rx
// A K request for a byte that is not one of the 12 K codes is encoded as data and counted in bad_k.
// Decoder: code_err = the code is in neither column of the table; disp_err = it is a valid code
// only in the other column. rd_out follows the sub-block rule on the received bits.
// Faults: no_rd (always the RD- column), a7_never (never the alternate D.x.A7),
// keep_rd_on_unbalanced (the 4b sub-block is chosen with the disparity from before the 6b one),
// no_balanced_flip (D.07 and D.x.3 keep their RD- form at RD+), dec_no_disp_check.
module hs_8b10b;
bit no_rd = 0, a7_never = 0, keep_rd_on_unbalanced = 0, no_balanced_flip = 0, dec_no_disp_check = 0;
bit trace = 0;
bit rd_tx = 0, rd_rx = 0;
int bad_k = 0, symbols = 0, code_errs = 0, disp_errs = 0;
bit last_k = 0, last_code_err = 0, last_disp_err = 0;
bit valid_m [0:1023]; bit valid_p [0:1023]; bit [8:0] kd [0:1023]; bit built = 0;
function automatic [5:0] t6(input [4:0] x); // 5b/6b, RD- column, abcdei
case (x)
5'd0: return 6'b100111; 5'd1: return 6'b011101; 5'd2: return 6'b101101; 5'd3: return 6'b110001;
5'd4: return 6'b110101; 5'd5: return 6'b101001; 5'd6: return 6'b011001; 5'd7: return 6'b111000;
5'd8: return 6'b111001; 5'd9: return 6'b100101; 5'd10: return 6'b010101; 5'd11: return 6'b110100;
5'd12: return 6'b001101; 5'd13: return 6'b101100; 5'd14: return 6'b011100; 5'd15: return 6'b010111;
5'd16: return 6'b011011; 5'd17: return 6'b100011; 5'd18: return 6'b010011; 5'd19: return 6'b110010;
5'd20: return 6'b001011; 5'd21: return 6'b101010; 5'd22: return 6'b011010; 5'd23: return 6'b111010;
5'd24: return 6'b110011; 5'd25: return 6'b100110; 5'd26: return 6'b010110; 5'd27: return 6'b110110;
5'd28: return 6'b001110; 5'd29: return 6'b101110; 5'd30: return 6'b011110; default: return 6'b101011;
endcase
endfunction
function automatic [3:0] t4d(input [2:0] y); // 3b/4b data, RD- column, fghj (y = 7 is P7)
case (y)
3'd0: return 4'b1011; 3'd1: return 4'b1001; 3'd2: return 4'b0101; 3'd3: return 4'b1100;
3'd4: return 4'b1101; 3'd5: return 4'b1010; 3'd6: return 4'b0110; default: return 4'b1110;
endcase
endfunction
function automatic [3:0] t4k(input [2:0] y); // 3b/4b for K codes, RD- form before the flip
case (y)
3'd0: return 4'b1011; 3'd1: return 4'b0110; 3'd2: return 4'b1010; 3'd3: return 4'b1100;
3'd4: return 4'b1101; 3'd5: return 4'b0101; 3'd6: return 4'b1001; default: return 4'b0111;
endcase
endfunction
function automatic bit k_ok(input [7:0] d);
return d[4:0] == 5'd28 || d == 8'hf7 || d == 8'hfb || d == 8'hfd || d == 8'hfe;
endfunction
function automatic int n6(input [5:0] v); return v[0] + v[1] + v[2] + v[3] + v[4] + v[5]; endfunction
function automatic int n4(input [3:0] v); return v[0] + v[1] + v[2] + v[3]; endfunction
// running disparity at the end of a sub-block (more ones: +; more zeros: -; 000111 and 0011: +; 111000 and 1100: -)
function automatic bit rd6(input [5:0] v, input bit rd);
return (n6(v) > 3) ? 1'b1 : (n6(v) < 3) ? 1'b0 : (v == 6'b000111) ? 1'b1 : (v == 6'b111000) ? 1'b0 : rd;
endfunction
function automatic bit rd4(input [3:0] v, input bit rd);
return (n4(v) > 2) ? 1'b1 : (n4(v) < 2) ? 1'b0 : (v == 4'b0011) ? 1'b1 : (v == 4'b1100) ? 1'b0 : rd;
endfunction
// faults: [0] no_rd [1] a7_never [2] keep_rd_on_unbalanced [3] no_balanced_flip
function automatic [10:0] core(input [7:0] d, input bit k, input bit rd_in, input [3:0] f);
reg [5:0] six; reg [3:0] four; reg rd0, r6, rd1, a7, kk; reg [4:0] x; reg [2:0] y; int o6, o4;
x = d[4:0]; y = d[7:5]; kk = k && k_ok(d); rd0 = f[0] ? 1'b0 : rd_in;
six = (kk && x == 5'd28) ? 6'b001111 : t6(x); o6 = n6(six);
if (rd0 && (o6 != 3 || (six == 6'b111000 && !f[3]))) begin six = ~six; o6 = 6 - o6; end
r6 = (o6 > 3) ? 1'b1 : (o6 < 3) ? 1'b0 : (six == 6'b000111) ? 1'b1 : (six == 6'b111000) ? 1'b0 : rd0;
rd1 = f[2] ? rd0 : r6;
if (kk) begin
four = t4k(y); if (rd1) four = ~four;
end else begin
a7 = (y == 3'd7) && !f[1] && ((!rd1 && (x == 5'd17 || x == 5'd18 || x == 5'd20)) || (rd1 && (x == 5'd11 || x == 5'd13 || x == 5'd14)));
four = a7 ? 4'b0111 : t4d(y);
if (rd1 && (n4(four) != 2 || (four == 4'b1100 && !f[3]))) four = ~four;
end
o4 = n4(four);
return {(o4 > 2) ? 1'b1 : (o4 < 2) ? 1'b0 : (four == 4'b0011) ? 1'b1 : (four == 4'b1100) ? 1'b0 : r6, six, four};
endfunction
function automatic [10:0] encode(input [7:0] d, input bit k, input bit rd_in);
if (k && !k_ok(d)) bad_k++;
return core(d, k, rd_in, {no_balanced_flip, keep_rd_on_unbalanced, a7_never, no_rd});
endfunction
function automatic void build();
reg [10:0] c;
for (int i = 0; i < 1024; i++) begin valid_m[i] = 0; valid_p[i] = 0; kd[i] = 9'd0; end
for (int i = 0; i < 268; i++) begin
reg [7:0] d; reg k;
if (i < 256) begin d = i[7:0]; k = 0; end
else begin k = 1; d = (i < 264) ? {3'(i - 256), 5'd28} : (i == 264) ? 8'hf7 : (i == 265) ? 8'hfb : (i == 266) ? 8'hfd : 8'hfe; end
c = core(d, k, 1'b0, 4'd0); valid_m[c[9:0]] = 1; kd[c[9:0]] = {k, d};
c = core(d, k, 1'b1, 4'd0); valid_p[c[9:0]] = 1; kd[c[9:0]] = {k, d};
end
built = 1;
endfunction
function automatic [11:0] decode(input [9:0] code, input bit rd_in);
reg here, there, ce, de, r;
if (!built) build();
here = rd_in ? valid_p[code] : valid_m[code];
there = rd_in ? valid_m[code] : valid_p[code];
ce = !(here || there); de = !ce && !here && !dec_no_disp_check;
r = rd4(code[3:0], rd6(code[9:4], rd_in));
return {r, de, ce, ce ? 9'd0 : kd[code]};
endfunction
function automatic [9:0] enc(input [7:0] d, input bit k);
reg [10:0] r; r = encode(d, k, rd_tx); rd_tx = r[10];
if (trace) $display("s%0d TX %s%0d.%0d code=%b rd=%s", symbols, (k && k_ok(d)) ? "K" : "D", d[4:0], d[7:5], r[9:0], r[10] ? "+" : "-");
symbols++;
return r[9:0];
endfunction
function automatic [8:0] dec(input [9:0] code);
reg [11:0] r; r = decode(code, rd_rx); rd_rx = r[11];
last_disp_err = r[10]; last_code_err = r[9]; last_k = r[8];
if (r[9]) code_errs++; if (r[10]) disp_errs++;
if (trace && (r[9] || r[10])) $display("RX %b %s", code, r[9] ? "code error" : "disparity error");
return r[8:0];
endfunction
function automatic bit comma7(input [6:0] w); return w == 7'b0011111 || w == 7'b1100000; endfunction
endmodule
// ---------------------------------------------------------------------------------------------
// hs_crc: a CRC of 1 to 32 bits with any polynomial, seed, bit order and final inversion.
// The register shifts left; the polynomial omits the x^width term. The field is sent register bit
// width-1 first (USB 2.0, USB 3.2 and Ethernet all send it this way).
// use_crc32(), use_crc16_usb2(), use_crc5_usb2(), use_crc16_usb3(): parameter sets
// reset(), crc_bit(b), crc_byte(v), crc_bits(v, n), field(), field_bit(i), check_value(), crc_residue_ok()
// Faults: msb_first (bytes enter MSB first), no_invert (the field is not complemented), seed_zero.
module hs_crc;
int width = 32;
bit [31:0] poly = 32'h04c11db7, seed = 32'hffffffff, residue = 32'hc704dd7b;
bit lsb_first = 1, invert = 1;
bit msb_first = 0, no_invert = 0, seed_zero = 0;
bit [31:0] r = 32'hffffffff;
function automatic [31:0] mask(); return (width >= 32) ? 32'hffffffff : ((32'd1 << width) - 32'd1); endfunction
function automatic void reset(); r = seed_zero ? 32'd0 : (seed & mask()); endfunction
function automatic void set(input int w, input [31:0] p, input [31:0] s, input [31:0] res, input bit lsb, input bit inv);
width = w; poly = p; seed = s; residue = res; lsb_first = lsb; invert = inv; reset();
endfunction
function automatic void use_crc32(); set(32, 32'h04c11db7, 32'hffffffff, 32'hc704dd7b, 1, 1); endfunction
function automatic void use_crc16_usb2(); set(16, 32'h8005, 32'hffff, 32'h800d, 1, 1); endfunction
function automatic void use_crc5_usb2(); set(5, 32'h05, 32'h1f, 32'h0c, 1, 1); endfunction
function automatic void use_crc16_usb3(); set(16, 32'h100b, 32'hffff, 32'hf6aa, 1, 1); endfunction
function automatic void crc_bit(input bit b);
reg fb; fb = b ^ r[width - 1];
r = ((r << 1) ^ (fb ? poly : 32'd0)) & mask();
endfunction
function automatic void crc_byte(input [7:0] v);
for (int i = 0; i < 8; i++) crc_bit(v[(lsb_first ^ msb_first) ? i : 7 - i]);
endfunction
function automatic void crc_bits(input [31:0] v, input int n); // n bits of v, bit 0 first
for (int i = 0; i < n; i++) crc_bit(v[i]);
endfunction
function automatic [31:0] field(); return (invert && !no_invert) ? (~r & mask()) : r; endfunction
function automatic bit field_bit(input int i); reg [31:0] f; f = field(); return f[width - 1 - i]; endfunction
// the usual published "check" number: the field with its first-sent bit read as bit 0
function automatic [31:0] check_value();
reg [31:0] f, o; f = field(); o = 32'd0;
for (int i = 0; i < width; i++) o[i] = f[width - 1 - i];
return lsb_first ? o : f;
endfunction
function automatic bit crc_residue_ok(); return r == (residue & mask()); endfunction
endmodule
// ---------------------------------------------------------------------------------------------
// hs_scr: additive (frame-synchronous) and multiplicative (self-synchronising) scramblers.
// poly holds the coefficients: bit k is x^k; the +1 term is always used (taps() sets bit 0); len is the degree.
// Additive: a Galois LFSR. The key bit is s[len-1]; each step shifts left and adds the low terms of
// the polynomial when the key bit is 1. The data never enters the register.
// Multiplicative: the line bit is the data bit XOR the register bits at the polynomial's terms;
// the scrambler shifts its own output in, the descrambler shifts the received line bit in.
// scr_add(len, poly, seed), scr_mul(len, poly), use_usb3_gen1(), use_x58(), use_x23_usb3() (see its note)
// scr_bit(b), dscr_bit(b), scr_byte(v), dscr_byte(v) (bit 0 first), scr_reset(), scr_hold() (a skip
// symbol: no step), scr_unscrambled() (a symbol sent in the clear: 8 steps, data untouched)
// Faults: advance_on_skip (scr_hold steps the LFSR 8 times), no_reset (scr_reset does nothing),
// wrong_tap (the lowest term x^k becomes x^(k+1)), seed_zero (scr_reset loads 0).
module hs_scr;
bit mult = 0; int len = 16;
bit [63:0] poly = 64'h10039, seed = 64'hffff;
bit advance_on_skip = 0, no_reset = 0, wrong_tap = 0, seed_zero = 0;
bit [63:0] s = 64'hffff;
int steps = 0;
function automatic [63:0] lmask(); return (len >= 64) ? 64'hffffffffffffffff : ((64'd1 << len) - 64'd1); endfunction
function automatic [63:0] taps();
reg [63:0] p; int k; p = poly | 64'd1; k = 1;
if (wrong_tap) begin
while (k < len && !p[k]) k++;
if (k < len) begin p[k] = 1'b0; p[k + 1] = 1'b1; end
end
return p;
endfunction
function automatic void load(); s = (seed_zero ? 64'd0 : seed) & lmask(); endfunction
function automatic void scr_add(input int n, input [63:0] p, input [63:0] sd); mult = 0; len = n; poly = p; seed = sd; s = sd & lmask(); endfunction
function automatic void scr_mul(input int n, input [63:0] p); mult = 1; len = n; poly = p; seed = 64'd0; s = 64'd0; endfunction
function automatic void use_usb3_gen1(); scr_add(16, 64'h10039, 64'hffff); endfunction // x^16 + x^5 + x^4 + x^3 + 1, seed FFFFh
function automatic void use_x58(); scr_mul(58, (64'd1 << 58) | (64'd1 << 39) | 64'd1); endfunction // x^58 + x^39 + 1
// USB 3.2 Gen 2 (§6.3.2.3) polynomial x^23 + x^21 + x^16 + x^8 + x^5 + x^2 + 1 with seed 1DBFBCh. Only the
// polynomial and seed are the specification's: the register form here is this library's Galois form, and
// the reset and bypass rules of §6.3.2.3 are not modelled, so do not quote its key stream as USB's.
function automatic void use_x23_usb3(); scr_add(23, (64'd1 << 23) | (64'd1 << 21) | (64'd1 << 16) | (64'd1 << 8) | (64'd1 << 5) | (64'd1 << 2) | 64'd1, 64'h1dbfbc); endfunction
function automatic void scr_reset(); if (!no_reset) load(); endfunction
function automatic bit key(); return s[len - 1]; endfunction
function automatic void step();
reg kb; kb = s[len - 1];
s = ((s << 1) & lmask()) ^ (kb ? (taps() & lmask()) : 64'd0);
steps++;
endfunction
// the XOR of the register bits at the polynomial's terms x^1..x^len (bit k-1 of the register for x^k)
function automatic bit fbx(input [63:0] st); return ^(st & (taps() >> 1) & lmask()); endfunction
function automatic bit scr_bit(input bit b);
reg o;
if (!mult) begin o = b ^ s[len - 1]; step(); end
else begin o = b ^ fbx(s); s = ((s << 1) | {63'd0, o}) & lmask(); steps++; end
return o;
endfunction
function automatic bit dscr_bit(input bit b);
reg o;
if (!mult) begin o = b ^ s[len - 1]; step(); end
else begin o = b ^ fbx(s); s = ((s << 1) | {63'd0, b}) & lmask(); steps++; end
return o;
endfunction
function automatic [7:0] scr_byte(input [7:0] v);
reg [7:0] o; for (int i = 0; i < 8; i++) o[i] = scr_bit(v[i]); return o;
endfunction
function automatic [7:0] dscr_byte(input [7:0] v);
reg [7:0] o; for (int i = 0; i < 8; i++) o[i] = dscr_bit(v[i]); return o;
endfunction
// a skip symbol passes unscrambled and the LFSR holds
function automatic void scr_hold(); if (advance_on_skip && !mult) for (int i = 0; i < 8; i++) step(); endfunction
// another symbol that is sent unscrambled (a K code other than COM and SKP): the LFSR still steps 8 times
function automatic void scr_unscrambled(); if (!mult) for (int i = 0; i < 8; i++) step(); endfunction
endmodule
Read included file: eth_mac.sv
`timescale 1ns/1ns
// eth_frame: one MAC frame as octets, its packet as wire bits, and a bit-serial receiver.
// pay[i] client data, set by the bench before build()
// build(da, sa, lt, len) destination, source, Length/Type, len data octets, then the FCS -> oct[0..n-1].
// It adds no pad: give it 46 data octets or more. (Padding is P11.2.1's task; the
// pages show the padding MAC's frames as measured tables.)
// wire_bits(), wire_bit(i) the packet in transmit order: preamble, SFD, frame
// rx_start(), rx_bit(b), rx_end() hunt for the SFD, collect octets, then parse()
// parse() da, sa, lt, is_length, is_type, data_len, fcs_rx, fcs_calc, fcs_ok
// Faults: fcs_msb_first, fcs_no_invert, fcs_covers_preamble, sfd_wrong, msb_first_octets.
module eth_frame;
localparam int MIN_FRAME = 64, MAX_BASIC = 1518, MAX_QTAG = 1522, MAX_ENVELOPE = 2000;
bit fcs_msb_first = 0, fcs_no_invert = 0, fcs_covers_preamble = 0, sfd_wrong = 0, msb_first_octets = 0;
hs_crc crc();
bit [7:0] pay [0:2047];
bit [7:0] oct [0:2047];
int n = 0;
bit [47:0] da = 0, sa = 0; bit [15:0] lt = 0;
bit is_length = 0, is_type = 0, fcs_ok = 0;
int data_len = 0;
bit [31:0] fcs_rx = 0, fcs_calc = 0;
// receiver state
bit in_frame = 0; bit [7:0] hist = 0, cur = 0; int nb = 0, excess = 0, sfd_at = -1, bits_seen = 0;
// The FCS of oct[0..len-1] as four octets: the first octet sent is in [7:0].
function automatic [31:0] fcs_of(input int len);
crc.use_crc32(); crc.msb_first = fcs_msb_first; crc.no_invert = fcs_no_invert; crc.reset();
if (fcs_covers_preamble) begin
for (int i = 0; i < 7; i++) crc.crc_byte(8'h55);
crc.crc_byte(8'hd5);
end
for (int i = 0; i < len; i++) crc.crc_byte(oct[i]);
return crc.check_value();
endfunction
function automatic void build(input [47:0] d, input [47:0] s, input [15:0] t, input int len);
int k; reg [31:0] f;
k = 0;
for (int i = 0; i < 6; i++) begin oct[k] = d[47 - 8*i -: 8]; k++; end
for (int i = 0; i < 6; i++) begin oct[k] = s[47 - 8*i -: 8]; k++; end
oct[k] = t[15:8]; k++;
oct[k] = t[7:0]; k++;
for (int i = 0; i < len; i++) begin oct[k] = pay[i]; k++; end
f = fcs_of(k);
for (int i = 0; i < 4; i++) begin oct[k] = f[8*i +: 8]; k++; end
n = k; excess = 0;
parse();
endfunction
function automatic void parse();
da = 0; sa = 0; lt = 0; is_length = 0; is_type = 0; fcs_ok = 0; data_len = 0; fcs_rx = 0; fcs_calc = 0;
if (n >= 14) begin
da = {oct[0], oct[1], oct[2], oct[3], oct[4], oct[5]};
sa = {oct[6], oct[7], oct[8], oct[9], oct[10], oct[11]};
lt = {oct[12], oct[13]};
is_length = (lt <= 16'd1500);
is_type = (lt >= 16'd1536);
end
if (n >= 18) begin
fcs_rx = {oct[n-1], oct[n-2], oct[n-3], oct[n-4]};
fcs_calc = fcs_of(n - 4);
fcs_ok = (fcs_rx == fcs_calc);
data_len = is_length ? int'(lt) : n - 18;
end
endfunction
function automatic int wire_bits(); return 8 * (8 + n); endfunction
function automatic bit wire_bit(input int i);
int o, b; reg [7:0] v;
o = i / 8; b = i % 8;
if (o < 7) v = 8'h55;
else if (o == 7) v = sfd_wrong ? 8'h55 : 8'hd5;
else v = oct[o - 8];
return msb_first_octets ? v[7 - b] : v[b];
endfunction
function automatic void rx_start();
in_frame = 0; hist = 0; cur = 0; nb = 0; n = 0; excess = 0; sfd_at = -1; bits_seen = 0;
endfunction
function automatic void rx_bit(input bit b);
bits_seen++;
if (!in_frame) begin
hist = {hist[6:0], b}; // the oldest bit is hist[7]
if (hist == 8'b10101011) begin in_frame = 1; sfd_at = bits_seen; end
end else begin
if (msb_first_octets) cur[7 - nb] = b; else cur[nb] = b;
nb++;
if (nb == 8) begin oct[n] = cur; n++; nb = 0; end
end
endfunction
function automatic void rx_end(); excess = nb; parse(); endfunction
endmodule
// eth_axis: a MAC client bus in the style of AXI4-Stream (IHI 0051B 2.2 handshake, 2.5 TKEEP, 2.6 TLAST, 2.9 TUSER),
// 64 bits wide. Byte 0 of a beat is tdata[7:0] and is first in the frame (AXI4-Stream 2.4.1). Bench conventions,
// not AXI4-Stream's or 802.3's: tkeep is all ones except on the last beat, where it covers bytes 0 to k-1; one tuser
// bit (transfer-based, 2.9.1), read on the last beat only, marks a bad frame (receive) or asks the MAC to abort it
// (transmit).
// load(n) beats for octets oct[0..n-1]: bd[], bk[], bl[], nbeats; bv[] = valid per cycle, ncyc
// tx_cycles() the transmit MAC: one beat per cycle once a frame has started. Returns 0 sent,
// 1 underrun (tvalid fell inside the frame), 2 aborted by tuser. sent_octets, fail_cycle.
// Fault: tvalid_gap (load() leaves cycle 3 of the frame empty: the client was late with a beat).
module eth_axis;
bit tvalid_gap = 0;
bit [7:0] oct [0:2047];
bit [63:0] bd [0:300]; bit [7:0] bk [0:300]; bit bl [0:300]; bit bu [0:300];
int nbeats = 0;
bit bv [0:301]; int bix [0:301]; int ncyc = 0;
int sent_octets = 0, fail_cycle = -1;
function automatic void load(input int n);
int b, k;
nbeats = (n + 7) / 8;
for (b = 0; b < nbeats; b++) begin
bd[b] = 64'd0; bk[b] = 8'd0; bl[b] = (b == nbeats - 1); bu[b] = 0;
for (k = 0; k < 8; k++) if (8*b + k < n) begin bd[b][8*k +: 8] = oct[8*b + k]; bk[b][k] = 1'b1; end
end
ncyc = 0;
for (b = 0; b < nbeats; b++) begin
if (tvalid_gap && b == 3) begin bv[ncyc] = 0; bix[ncyc] = -1; ncyc++; end
bv[ncyc] = 1; bix[ncyc] = b; ncyc++;
end
endfunction
function automatic int tx_cycles();
bit started; started = 0; sent_octets = 0; fail_cycle = -1;
for (int c = 0; c < ncyc; c++) begin
if (!bv[c]) begin
if (started) begin fail_cycle = c; return 1; end
end else begin
started = 1;
if (bl[bix[c]] && bu[bix[c]]) begin fail_cycle = c; return 2; end
for (int k = 0; k < 8; k++) if (bk[bix[c]][k]) sent_octets++;
end
end
return 0;
endfunction
endmodule
// eth_pause: the PAUSE function of MAC Control (Annex 31B) at the station that receives PAUSE frames, in octet
// times (one octet time is 8 bit times; a pause quantum is 512 bit times = 64 octet times, 31B.2).
// reset(), rx_pause(t, q) a valid PAUSE frame with pause_time q ended at time t: the timer restarts (31B.3.3)
// may_start(t) 1 when a new data frame may start at time t. A frame already started is never cut
// (31B.3.7). react is the bench's reaction time: frames may still start until t + react.
// paused_until the time the timer runs out
// pause_octets(q, o[]) not here: build a PAUSE frame with eth_frame (DA 01-80-C2-00-00-01, 8808h, 0001h, q)
// Faults: pause_ignored, pause_adds_not_overrides (a new frame adds to the timer, and zero does not cancel),
// slow_reaction (react = 70 quanta, over the 60 allowed at 10 Gb/s), timer_in_bits (q counts bit times).
module eth_pause;
localparam int QUANTUM = 64; // octet times
bit pause_ignored = 0, pause_adds_not_overrides = 0, slow_reaction = 0, timer_in_bits = 0;
int react = 0, t_rx = -1, paused_until = 0;
function automatic void reset(); t_rx = -1; paused_until = 0; endfunction
function automatic void rx_pause(input int t, input int q);
int len;
if (pause_ignored) return;
len = timer_in_bits ? (q + 7) / 8 : q * QUANTUM;
if (pause_adds_not_overrides && paused_until > t) paused_until = paused_until + len;
else paused_until = t + len;
t_rx = t;
endfunction
function automatic bit may_start(input int t);
int r;
r = slow_reaction ? 70 * QUANTUM : react;
if (t_rx < 0) return 1;
if (t < t_rx + r) return 1;
return t >= paused_until;
endfunction
endmodule
// eth_pfc: priority-based flow control (Annex 31D). The frame is 802.3's; holding a priority's queue is the MAC
// Control client's job (IEEE 802.1Q, not held), so the eight timers here are a bench client, in octet times.
// build(f_oct[], pev, times[]) not here: the bench writes opcode 01-01, the vector and eight times into eth_frame
// reset(), rx(t, pev, tm[0..7]) for each e[n] = 1 (bit n of the vector's low octet), priority n stops until
// t + 64 * time[n] (hold_end[n]); e[n] = 0 leaves priority n alone; time[n] = 0 releases it
// blocked(n, t) 1 while priority n is held
// Fault: pfc_wrong_priority (reads e[n] from bit 7 - n).
module eth_pfc;
bit pfc_wrong_priority = 0;
int hold_end [0:7];
function automatic void reset(); for (int i = 0; i < 8; i++) hold_end[i] = 0; endfunction
function automatic void rx(input int t, input [15:0] pev, input [127:0] tm); // tm[16*n +: 16] = time[n]
bit e;
for (int n = 0; n < 8; n++) begin
e = pfc_wrong_priority ? pev[7 - n] : pev[n];
if (e) hold_end[n] = t + 64 * int'(tm[16*n +: 16]);
end
endfunction
function automatic bit blocked(input int n, input int t); return t < hold_end[n]; endfunction
endmodule
// eth_csma_tx: one half-duplex transmitter (4.2.3.2), one call of tick() per octet time.
// reset(), load(frame_octets) a frame of frame_octets (DA to FCS) waits to be sent; it is padded to min_frame
// tick(carrier) carrier: another station's signal is on the wire here now. Returns 1 when the
// station puts an octet (packet or jam) on the wire.
// plan[i] the wait, in slots, after collision i + 1. The bench sets it (default 0). This
// readable station draws nothing and has no attempt limit.
// state 0 idle, 1 defer, 2 send, 3 jam, 4 backoff, 5 sent (as far as the sender knows)
// pkt, sent, quiet, left, attempts, late, last_start, last_r
// min_frame is 64 octets; a bench may lower it to show why it is 64. Fault: no_backoff (every wait is 0 slots).
// Deference is a bench simplification: the 12-octet quiet count restarts on any carrier, own or received, and the
// station never starts while carrier is present. 4.2.8 restarts only the first part of the gap, and then transmits
// whatever the carrier.
module eth_csma_tx;
localparam int SLOT = 64, JAM = 4, GAP = 12, PRE = 8; // octet times
bit no_backoff = 0;
int min_frame = 64;
int plan [0:63];
int state = 0, pkt = 0, sent = 0, quiet = GAP, left = 0, attempts = 0, late = 0, last_start = -1, last_r = 0, now = 0;
function automatic void reset();
state = 0; pkt = 0; sent = 0; quiet = GAP; left = 0; attempts = 0; late = 0; last_start = -1; last_r = 0; now = 0;
endfunction
function automatic void load(input int frame_octets);
pkt = PRE + frame_octets;
if (frame_octets < min_frame) pkt = PRE + min_frame;
state = 1; attempts = 0; sent = 0; late = 0;
endfunction
function automatic bit tick(input bit carrier);
bit on;
on = 0;
if (state == 1 && !carrier && quiet >= GAP) begin state = 2; sent = 0; last_start = now; end
if (state == 2 && carrier) begin
attempts++; if (sent > SLOT) late++;
state = 3; left = JAM;
end
case (state)
2: begin sent++; on = 1; if (sent == pkt) state = 5; end
3: begin
on = 1; left--;
if (left == 0) begin
last_r = no_backoff ? 0 : plan[(attempts - 1) % 64];
left = SLOT * last_r;
state = (left == 0) ? 1 : 4;
end
end
4: begin left--; if (left == 0) state = 1; end
default: ;
endcase
quiet = (carrier || on) ? 0 : ((quiet < GAP) ? quiet + 1 : GAP);
now++;
return on;
endfunction
endmodule
// eth_csma: two eth_csma_tx stations, A and B, at the two ends of a wire with a one-way delay of d octet times.
// run(fa, ready_a, fb, ready_b, tmax) each station loads its frame (fa, fb octets) at its ready time
// on_a[t], on_b[t] what each station put on the wire at time t
// ev_t[], ev_who[] (0 A, 1 B), ev_kind[], ev_v[], n_ev the event log:
// kind 0 starts attempt v; 1 sees a collision after v octets; 2 jam over, backs off v slots;
// 3 last octet sent (v = octets); 4 gives up after v attempts
// delivered(i) 1 when station i's last attempt reached the far end with no overlap there
// a.plan[], b.plan[], a.no_backoff, b.no_backoff, a.min_frame, b.min_frame: the stations' settings
module eth_csma;
eth_csma_tx a(); eth_csma_tx b();
int d = 10, n_ev = 0, tend = 0;
bit on_a [0:16383]; bit on_b [0:16383];
int ev_t [0:255]; int ev_who [0:255]; int ev_kind [0:255]; int ev_v [0:255];
function automatic void log_ev(input int t, input int who, input int kind, input int v);
if (n_ev < 256) begin ev_t[n_ev] = t; ev_who[n_ev] = who; ev_kind[n_ev] = kind; ev_v[n_ev] = v; n_ev++; end
endfunction
function automatic void note(input int t, input int who, input int s0, input int s1, input int sent0, input int att, input int r, input int sent1);
if (s0 != 2 && s1 == 2) log_ev(t, who, 0, att + 1);
if (s0 == 2 && (s1 == 3 || s1 == 4)) log_ev(t, who, 1, sent0);
if (s0 == 3 && (s1 == 4 || s1 == 1)) log_ev(t, who, 2, r);
if (s0 != 5 && s1 == 5) log_ev(t, who, 3, sent1);
if (s0 != 6 && s1 == 6) log_ev(t, who, 4, att);
endfunction
function automatic void run(input int fa, input int ready_a, input int fb, input int ready_b, input int tmax);
bit ca, cb; int sa, sb, xa, xb;
a.reset(); b.reset(); n_ev = 0; tend = tmax;
for (int t = 0; t < tmax; t++) begin
if (t == ready_a) a.load(fa);
if (t == ready_b) b.load(fb);
ca = (t >= d) ? on_b[t - d] : 1'b0;
cb = (t >= d) ? on_a[t - d] : 1'b0;
sa = a.state; sb = b.state; xa = a.sent; xb = b.sent;
on_a[t] = a.tick(ca);
on_b[t] = b.tick(cb);
note(t, 0, sa, a.state, xa, a.attempts, a.last_r, a.sent);
note(t, 1, sb, b.state, xb, b.attempts, b.last_r, b.sent);
end
endfunction
function automatic bit delivered(input int i);
int s, p, u;
if (i == 0 && a.state != 5) return 0;
if (i == 1 && b.state != 5) return 0;
s = (i == 0) ? a.last_start : b.last_start;
p = (i == 0) ? a.pkt : b.pkt;
for (int t = s; t < s + p; t++) begin
u = t + d;
if (u < tend && ((i == 0) ? on_b[u] : on_a[u])) return 0;
end
return 1;
endfunction
endmodule
// eth_gap: how long the gap before the next Start is on a 4-lane XGMII, where Start must sit on lane 0
// (46.3.1.4). A gap counts every character from the Terminate to the last idle before Start. A packet is
// 8 + n characters (Start, six preamble octets, SFD, an n-octet frame) and starts on lane 0.
// reset() DIC = 0 (the count is reset only at initialisation)
// method 0 deficit idle count, 1 always insert (both allowed by 46.3.1.4)
// next_gap(n, mac_gap) the gap after an n-octet frame when the MAC asks for mac_gap (12 or more)
// deleted, inserted, dic what the last call did, and the count after it
// Faults: ipg_min_only (always deletes, ignoring the bound), dic_max4 (bounds the count at 4, not 3),
// start_any_lane (no alignment: the gap is always mac_gap).
module eth_gap;
bit ipg_min_only = 0, dic_max4 = 0, start_any_lane = 0;
int method = 0, dic = 0, deleted = 0, inserted = 0;
function automatic void reset(); dic = 0; deleted = 0; inserted = 0; endfunction
function automatic int next_gap(input int n, input int mac_gap);
int m, top;
deleted = 0; inserted = 0;
m = (n + mac_gap) % 4; // lanes past lane 0 the next Start would land on
if (start_any_lane || m == 0) return mac_gap;
top = dic_max4 ? 4 : 3;
if (method == 0 && (ipg_min_only || dic + m <= top)) begin deleted = m; dic = dic + m; end
else begin inserted = 4 - m; if (method == 0) dic = dic - (4 - m); end
return mac_gap - deleted + inserted;
endfunction
endmodule
Check Yourself
Common Mistakes
Wrong Stop sending the moment a collision is seen.
The far station may not have seen it yet.
Fix Send the 32-bit jam first, then back off.
Wrong Let r grow without limit: 0 ≤ r < 2^n.
The exponent stops at backoffLimit, 10.
Fix Use k = min(n, 10), and give up after 16 attempts.
Wrong Think the minimum frame size is about wasted bandwidth.
It exists so a sender is still sending when a collision returns.
Fix Size frames so they last longer than the round trip of the wire.
Wrong Expect collision counters to move on a full-duplex link.
A full-duplex MAC ignores collision indications.
Fix Look for a duplex mismatch when late collisions appear on a link that should be full duplex.
Remember
- Half duplex: listen, wait a gap, send, and watch for a collision.
- On a collision, send a 32-bit jam, then wait r slots with 0 ≤ r < 2^min(n, 10).
- Give up after 16 attempts.
- A frame must last longer than the round trip, or a collision goes unseen. Hence 64 octets.
- 1 Gb/s half duplex uses a 4096-bit slot with carrier extension. Full duplex has no CSMA/CD at all.