Capstone: a pipelined CRC engine with a levels budget

Build a byte-per-cycle CRC-32 engine, find the one cut its feedback loop allows, and bring it inside a budget of levels of logic without changing a single CRC.

Lesson
R4.7
Time
40 min
Runs on
Your browser
Check
5 questions

A CRC-32 engine took one byte per cycle and measured 6 levels of logic on this flow, one over its budget of 5. Its designer put a register halfway through the eight shift steps. The count fell to 5, and 31 of 32 packets came out with the wrong CRC. The register sat inside the engine's feedback loop.

VersionCellsFlopsLevels of logic on this flowPackets wrong
one stage: eight steps per byte1403360 of 32
a register after four of the eight steps20071531 of 32
the byte's share computed a cycle early2386650 of 32

Measured with Yosys 0.70 and the lesson's bench. The budget is 5 levels.

A CRC in one picture

A cyclic redundancy check (CRC) is a short code computed over a packet, so the receiver can detect corrupted bytes. The circuit is a shift register with XOR feedback. For each data bit it shifts left by one. If the bit that falls off the top differs from the data bit, it XORs a fixed pattern, the polynomial, into the register.

This engine uses the CRC-32 polynomial 0x04C11DB7, most significant bit first, with the register set to all ones before each packet. One byte per cycle means eight shift steps per cycle. The for loop in crc_step unrolls into one block of XOR logic, all inside one clock cycle.

The engine: a loop through eight stepsArrows carry data. The CRC register feeds the steps that compute its next value, so the steps and the register form a loop.
The engine: a loop through eight stepsArrows carry data. The CRC register feeds the steps that compute its next value, so the steps and the register form a loop. manager in_data one byte per cycle bus INIT or crc in_first picks bridge eight shift steps XOR logic, 6 levels completer crc 32 flops completer crc_valid after the last byte bytestart valuenext crcold crcfinal
  1. The first byte

    in_first picks INIT, all ones. The steps fold in the byte 0x31, the character "1", and the register takes 9efbcf93.

    Follow the calls, values and waits
    1. data 0x31: in_data → eight shift steps
    2. data 9efbcf93: eight shift steps → crc
  2. Round the loop

    For the next byte the start value is the register itself. Every byte goes round the loop once: the six levels sit between the register's output and its input.

    Follow the calls, values and waits
    1. data 9efbcf93: crc → INIT or crc
  3. The last byte

    With in_last set, crc_valid rises after the edge that folds in the last byte. The register then holds the packet's CRC.

Read the diagram as text
  • in_data: one byte per cycle
  • INIT or crc: in_first picks
  • eight shift steps: XOR logic, 6 levels
  • crc: 32 flops
  • crc_valid: after the last byte
  • in_data → eight shift steps: byte
  • INIT or crc → eight shift steps: start value
  • eight shift steps → crc: next crc
  • crc → INIT or crc: old crc
  • crc → crc_valid: final

Measured: 140 cells, 33 flops, 6 levels; the longest path runs from in_first to crc[11].

The packet "123" with a gapThe starter on the lab bench. A gap is a cycle with in_valid at 0; the engine simply waits.
01234clkin_validin_firstin_lastin_data3132003300crc9efbcf933fec5e6ad952f164crc_valid
  1. Cycle 0

    Edge 2 takes "1" with in_first set: the register starts from all ones and becomes 9efbcf93.

  2. Cycle 2

    A gap. in_valid is 0, so crc holds 3fec5e6a, the CRC of "12".

  3. Cycle 3

    Edge 5 folds in "3" with in_last set. crc is d952f164 and crc_valid rises; the bit-serial model agrees.

Measured on the lesson's bench, edges 2 to 6.

The one cut the loop allows

R4.6 showed that a register inside a loop changes the function. Halfway through the steps is inside the loop, which is why 31 packets broke. So the cut has to take logic out of the loop, not split it.

The CRC gives a way to do that. It is linear: the next value is the register's share XOR the byte's share. The register's share is eight steps with a zero byte; the byte's share is eight steps from a zero register. Measured for the first byte, 4e08bfb4 XOR d0f37027 is 9efbcf93. The engine computed the same value.

A register inside the loop

half_q <= crc_step4(in_first ? INIT : crc,
                    in_data[7:4]);
low_q  <= in_data[3:0];
if (v1) crc <= crc_step4(half_q, low_q);

5 levels, 31 of 32 packets wrong: each byte now takes two edges to go round.

The byte's share a cycle early

dpart_q <= crc_step('0, in_data);
v1 <= in_valid;
first1 <= in_first; last1 <= in_last;
if (v1) crc <= crc_step(first1 ? INIT : crc,
                        8'h00) ^ dpart_q;

5 levels, 0 wrong. The byte's share depends on the byte alone, so it leaves the loop.

Measured after the legal cut, the longest path runs from crc[31] to crc[12]: the loop itself. That is the floor for this coding. The valid, first and last bits move through stage 1 beside the byte's share, so the latency becomes 2.

Wider engines: more data per cycle
Data bits per cycleOne stage: cellsOne stage: levelsData's share early: cellsData's share early: levels
1 (bit-serial)803
814062385
1621583858
323581567517
6464925120024

Measured with Yosys 0.70: the lesson's engine with the data width changed and the step loop run once per data bit.

The levels grow with the data width, because each bit of the next CRC folds in more register and data bits. The early cut does not always pay. At 32 bits the loop alone measured 17 levels, from crc[30] to crc[17], more than the whole one-stage engine. At 32 bits the data word is as wide as the register, so the register's share runs through the same XOR network as the whole one-stage engine. The cut leaves all of it in the loop and adds one XOR. The synthesizer builds each version differently, so measure every cut.

The lab: meet the budget

Design brief
PortDirectionWidthMeaning
clkinput1clock
rst_ninput1reset, asynchronous, active-low
in_validinput1in_data holds a byte this cycle
in_first, in_lastinput1the byte starts or ends a packet
in_datainput[7:0]the byte
crcoutput[W-1:0], W = 32CRC-32, polynomial 0x04C11DB7, most significant bit first, all ones before each packet, no final inversion; "123456789" gives 0376e6e7
crc_validoutput1crc holds a finished packet's CRC
Latency
1 as shipped; 2 after the cut, with in_valid, in_first and in_last moving through stage 1
Throughput
one byte per cycle; gaps (in_valid = 0) may come anywhere, and the engine waits
Parameters
Budget: at most 5 levels of logic on this flow; no latches; every CRC equal to the bit-serial model
  1. Run and measure the starter

    Run prints both packets ok and "32 packets, 0 wrong". Synthesize: 140 cells, 33 flops, 6 levels.

  2. Compute the byte's share a cycle early

    Register crc_step('0, in_data) with the valid, first and last bits beside it. In the loop, start from INIT or crc, run eight steps of zeros, and XOR the byte's share.

  3. Run again

    Every CRC is the same and 0 are wrong. Each packet line appears one edge later: packet 1 at edge 6.

  4. Synthesize

    238 cells, 66 flops, 5 levels: inside the budget. The cell count nearly doubled; the budget here is levels, and cells come second.

The budget is a count of logic levels from one pinned flow, Yosys 0.70 with its generic gates. It is not a delay. A real library has slow and fast cells, and a timing tool adds wires. The count still ranks two codings of one design on the same flow, and that comparison is what carries over.

Asked in interviews
  1. How does a CRC circuit work?

    A shift register with XOR feedback. For each data bit it shifts once, and when the bit leaving the top differs from the data bit it XORs in the polynomial. After the last bit the register holds the CRC.

  2. How do you process a byte per cycle?

    Unroll eight bit steps into one block of combinational XOR logic. Each next-state bit becomes an XOR of some register bits and some data bits. Measured here, the byte-wide CRC-32 is 6 levels against 3 for one bit per cycle.

  3. How would you pipeline a CRC?

    Not inside the loop: a register there changes the result. Use linearity instead: compute the data's share a cycle early and XOR it into the register's share. The valid and framing bits move with it, and the latency grows by one.

Try it

Packet 1 is "123": the engine folds one byte per edge and waits through the gap at edge 4. Packet 2 is "123456789", and its CRC 0376e6e7 matches the bit-serial model. Thirty random packets with random gaps add no error.

After the cut the same CRCs appear one edge later (packet 1 at edge 6, packet 2 at edge 17), and Synthesize reports 5 levels.

RTLIcarus Verilog · in your browser · Lint: Verilator service · Synthesize: Yosys service
Edit the design, then Run, Lint or Synthesize
Expected: e2 in_valid=1 first=1 last=0 data=31 crc=9efbcf93 crc_valid=0 e3 in_valid=1 first=0 last=0 data=32 crc=3fec5e6a crc_valid=0 e4 in_valid=0 first=0 last=0 data=00 crc=3fec5e6a crc_valid=0 e5 in_valid=1 first=0 last=1 data=33 crc=d952f164 crc_valid=1 e5 packet 1 crc=d952f164 model=d952f164 ok e6 in_valid=0 first=0 last=0 data=00 crc=d952f164 crc_valid=0 e7 in_valid=0 first=0 last=0 data=00 crc=d952f164 crc_valid=0 e16 packet 2 crc=0376e6e7 model=0376e6e7 ok 32 packets, 0 wrong

Original design · 140 cells · 33 flip-flops · 0 latches · 6 logic levels. Synthesis uses Yosys; counts depend on the toolchain.

Read included file: tb.sv
`timescale 1ns/1ps
module tb;
  logic clk = 0;
  always #5 clk = ~clk;                   // rising edges at 5, 15, 25, ...
  logic rst_n = 1;                        // falls at 1 ns: a real edge, so an asynchronous reset acts before any clock
  int edge_n = -1;
  always @(posedge clk) edge_n = edge_n + 1;
  logic        in_valid = 0, in_first = 0, in_last = 0;
  logic [7:0]  in_data = 0;
  logic [31:0] crc;
  logic        crc_valid;
  logic [31:0] model = 0;                 // the bit-serial model's register
  logic [31:0] want[$];                   // the model's CRC for each finished packet
  int packets = 0, wrong = 0;
  bit watch = 0;                          // 1: print every edge
  int unsigned seed = 11;
  // The model: one bit per step, most significant bit first, polynomial 0x04C11DB7.
  function automatic logic [31:0] model_bit(input logic [31:0] c, input logic b);
    logic top;
    top = c[31] ^ b;
    c = c << 1;
    if (top) c = c ^ 32'h04C11DB7;
    return c;
  endfunction
  // Send one byte (gaps cycles of in_valid = 0 first), and feed it to the model bit by bit.
  task automatic send(input logic [7:0] d, input bit first, input bit last, input int gaps = 0);
    repeat (gaps) begin in_valid = 0; in_first = 0; in_last = 0; in_data = 0; tick(); end
    if (first) model = 32'hFFFFFFFF;
    for (int i = 7; i >= 0; i--) model = model_bit(model, d[i]);
    if (last) want.push_back(model);
    in_valid = 1; in_first = first; in_last = last; in_data = d; tick();
  endtask
  task automatic idle(input int n);
    repeat (n) begin in_valid = 0; in_first = 0; in_last = 0; in_data = 0; tick(); end
  endtask
  crc_engine dut (.clk(clk), .rst_n(rst_n), .in_valid(in_valid), .in_first(in_first), .in_last(in_last),
                  .in_data(in_data), .crc(crc), .crc_valid(crc_valid));
  // Advance to the next rising edge, wait for the design to settle, then print one line.
  task automatic tick();
    @(posedge clk); #1;
    if (watch) $display("e%0d in_valid=%b first=%b last=%b data=%h crc=%h crc_valid=%b",
                       edge_n, in_valid, in_first, in_last, in_data, crc, crc_valid);
    if (crc_valid) begin
      logic [31:0] w;
      w = want.pop_front();
      packets++;
      if (crc !== w) wrong++;
      if ((watch || packets == 2) && crc === w) $display("e%0d packet %0d crc=%h model=%h ok", edge_n, packets, crc, w);
      if ((watch || packets == 2) && crc !== w) $display("e%0d packet %0d crc=%h model=%h WRONG", edge_n, packets, crc, w);
    end
  endtask
  initial begin
    #1 rst_n = 0; tick(); tick(); rst_n = 1;   // asserted at 1 ns, edges 0 and 1 in reset, released 1 ns after edge 1
    // Packet 1: "123" with a one-cycle gap before the last byte, every edge printed.
    watch = 1;
    send("1", 1, 0); send("2", 0, 0); send("3", 0, 1, 1);
    idle(2);
    watch = 0;
    // Packet 2: "123456789" back to back.
    send("1", 1, 0);
    for (int k = 2; k <= 8; k++) send(8'h30 + k, 0, 0);
    send("9", 0, 1);
    idle(2);
    // 30 more packets of 1 to 16 random bytes, with random gaps, checked but not printed.
    for (int p = 0; p < 30; p++) begin
      int len;
      seed = seed * 1103515245 + 12345; len = 1 + seed[19:16];
      for (int k = 0; k < len; k++) begin
        seed = seed * 1103515245 + 12345;
        send(seed[23:16], k == 0, k == len - 1, seed[25:24] == 0 ? 1 : 0);
      end
    end
    idle(3);
    $display("%0d packets, %0d wrong", packets, wrong);
    $finish(0);                             // quiet: no "$finish called" line
  end
endmodule

Check yourself

Predict the outputA CRC-8 with polynomial 0x07 starts from 0 and folds in the bytes 0x01, then 0x02, most significant bit first. The program prints the register in hex. What is the output line?
module tb;
  // CRC-8: polynomial 0x07, register starts at 0, most significant bit first.
  function automatic logic [7:0] crc8_byte(input logic [7:0] c, input logic [7:0] d);
    for (int i = 7; i >= 0; i--)
      c = {c[6:0], 1'b0} ^ ((c[7] ^ d[i]) ? 8'h07 : 8'h00);
    return c;
  endfunction
  logic [7:0] c;
  initial begin
    c = 8'h00;
    c = crc8_byte(c, 8'h01);
    c = crc8_byte(c, 8'h02);
    $display("crc=%h", c);
    $finish(0);
  end
endmodule
Spot the bugEach option sets the polynomial for a CRC-32 that runs most significant bit first. The bench computes the CRC of "123456789" from all ones and expects 0376e6e7. Which option fails?
ConceptWhy is the byte-wide CRC-32 6 levels on this flow when the bit-serial one is 3?
ConceptThe cut engine measures 5 levels and meets the budget of 5. What does that tell you?
Read the waveformThis is the cut engine (latency 2) on the same packet "123" with a gap. In which cycle does crc first hold the finished CRC d952f164?
The cut engine on the packet "123"
012345in_validin_lastin_data3132003300crcffffffff9efbcf933fec5e6ad952f164crc_valid

One value per edge, from edge 2 of the bench, printed after the edge settles.

Remember

  • A CRC is a shift register with XOR feedback. A byte per cycle unrolls eight steps into one block of XOR logic: 6 levels for CRC-32 on this flow, against 3 for one bit per cycle.
  • The CRC register and its update form a loop, so a register inside the steps changes the function: measured, 31 of 32 packets wrong.
  • A CRC is linear: the next value is the register's share XOR the byte's share. The byte's share can be computed a cycle early, which takes it out of the loop.
  • The legal cut met the budget: 6 levels became 5 and every CRC stayed equal to the bit-serial model, at the cost of 98 more cells and a latency of 2.
  • A levels budget ranks codings on one pinned flow; it is not a delay, and wider engines need each cut measured.