Search code examples
logicverilogcrcredundancycrc16

How is this calculating CRC-A using polynomial - x^16 + x^12 + x^5 + 1


I came across this piece of code. But I am not sure how is CRC calculated here. I know the theoretical way of calculating CRC but I guess here it is using some kind of different logic, maybe. Please correct me.

r_o[14:13] <= r_o[13:12];
r_o[12]    <= r_o[11]^r_o[15]^x16;
r_o[11]    <= r_o[10];
r_o[10:6]  <= r_o[9:5];
r_o[5]     <= r_o[4]^r_o[15]^x16;
r_o[4]     <= r_o[3];
r_o[3:1]   <= r_o[2:0];
r_o[0]     <= r_o[15]^x16;

Solution

  • Well, if you know about the theoretical way to do we can start with

    Assuming u is the input bit, and that every iteration you calculate r = r * x + u*x^16, remember that in the given ring x^16 = x^12 + x^5 + 1, a direct implementation of this would be

    parameter X16_MASK = 16'h1021; // (1 << 12) ^ (1 << 5) ^ 1
    function [15:0] step(input [15:0] prev_state, input u);
      logic [15:0] state;
    begin
      
      state = {prev_state[14:0], 1'b0};
      if(state[15]) state = state ^ X16_MASK;
      if(u) state = state ^ X16_MASK;
      step = state;
    end
    endfunction
    

    This could simply be written as {r_o[14:0], 1'b0} ^ (X16_MASK * (r_o[15] ^ u)) and let the synthesis to optimize whatever is necessary, it should be able to simplify the multiplication by a 1-bit signal. Now check the positions where the mask has an effect you will get to assignments above.

    I would simplify

    r_o[11]    <= r_o[10];
    r_o[10:6]  <= r_o[9:5];
    

    to r_o[11:6] = r_o[10:5] and

    r_o[4]     <= r_o[3];
    r_o[3:1]   <= r_o[2:0];
    

    to r_o[4:1] = r_o[3:0]

    In the code you presented I am missing the assignment to r_o[15].

    So you could say

    r_o[15:13] <= r_o[14:12];
    r_o[12]    <= r_o[11]^r_o[15]^x16;
    r_o[11:6]  <= r_o[10:5];
    r_o[5]     <= r_o[4]^r_o[15]^x16;
    r_o[4:1]   <= r_o[3:0];
    r_o[0]     <= r_o[15]^x16;
    

    And if you like the one linear bit packing

    r_o <= {r_o[14:12], r_o[11]^r_o[15]^x16, r_o[10:5], r_o[4]^r_o[15]^x16,r_o[3:0], r_o[15]^x16}