CRC Generator - This circuit and VHDL? (I need only explanation)

[kaiserschmarren87]

Hi,

I have understood what CRC algorithm is. I found enough information online. Also found online tools to generate VHDL code for the specified data and polynomial. Could someone be generous to explain how the data and crc bits are chosen for CRC generation in this VHDL code generated from this webpage: **broken link removed**

-- ########################################################################
-- CRC Engine RTL Design 
-- Copyright (C) www.ElectronicDesignworks.com 
-- Source code generated by ElectronicDesignworks IP Generator (CRC).
-- Documentation can be downloaded from www.ElectronicDesignworks.com 
-- ******************************** 
--            License     
-- ******************************** 
-- This source file may be used and distributed freely provided that this
-- copyright notice, list of conditions and the following disclaimer is
-- not removed from the file.                    
-- Any derivative work should contain this copyright notice and associated disclaimer.                    
-- This source code file is provided "AS IS" AND WITHOUT ANY WARRANTY, 
-- without even the implied warranty of MERCHANTABILITY or FITNESS FOR A 
-- PARTICULAR PURPOSE.
-- ********************************
--           Specification 
-- ********************************
-- File Name       : CRC8_DATA16.vhd    
-- Description     : CRC Engine ENTITY 
-- Clock           : Positive Edge 
-- Reset           : Active High
-- First Serial    : MSB 
-- Data Bus Width  : 16 bits 
-- Polynomial      : (0 2 3 4 8)                   
-- Date            : 16-Jun-2015  
-- Version         : 1.0        
-- ########################################################################
                    
LIBRARY IEEE ;
USE ieee.std_logic_1164.all ;
USE ieee.std_logic_arith.all ;
USE ieee.std_logic_unsigned.all ;

ENTITY crc_gen IS 
   PORT(           
           clock      : IN  STD_LOGIC; 
           reset      : IN  STD_LOGIC; 
           soc        : IN  STD_LOGIC; 
           data       : IN  STD_LOGIC_VECTOR(15 DOWNTO 0); 
           data_valid : IN  STD_LOGIC; 
           eoc        : IN  STD_LOGIC; 
           crc        : OUT STD_LOGIC_VECTOR(7 DOWNTO 0); 
           crc_valid  : OUT STD_LOGIC 
       );
END crc_gen; 

ARCHITECTURE behave OF crc_gen IS 

 SIGNAL crc_r          : STD_LOGIC_VECTOR(7 DOWNTO 0);
 SIGNAL crc_c          : STD_LOGIC_VECTOR(7 DOWNTO 0);
 SIGNAL crc_i          : STD_LOGIC_VECTOR(7 DOWNTO 0);
 SIGNAL crc_const      : STD_LOGIC_VECTOR(7 DOWNTO 0) := "00000000";

BEGIN 

	      
crc_i    <= crc_const when soc = '1' else
            crc_r;

crc_c(0) <= data(0) XOR data(4) XOR data(5) XOR data(6) XOR data(13) XOR crc_i(5) XOR data(15) XOR crc_i(7) XOR data(10) XOR crc_i(2); 
crc_c(1) <= data(1) XOR data(5) XOR data(6) XOR data(7) XOR data(14) XOR crc_i(6) XOR data(11) XOR crc_i(3); 
crc_c(2) <= data(0) XOR data(2) XOR data(7) XOR data(8) XOR crc_i(0) XOR data(12) XOR crc_i(4) XOR data(4) XOR data(5) XOR data(13) XOR crc_i(5) XOR data(10) XOR crc_i(2); 
crc_c(3) <= data(0) XOR data(1) XOR data(3) XOR data(8) XOR data(9) XOR crc_i(1) XOR crc_i(0) XOR data(14) XOR crc_i(6) XOR data(11) XOR crc_i(3) XOR data(4) XOR data(15) XOR crc_i(7) XOR data(10) XOR crc_i(2); 
crc_c(4) <= data(0) XOR data(1) XOR data(2) XOR data(9) XOR crc_i(1) XOR data(12) XOR crc_i(4) XOR data(11) XOR crc_i(3) XOR data(6) XOR data(13) XOR crc_i(5); 
crc_c(5) <= data(1) XOR data(2) XOR data(3) XOR data(10) XOR crc_i(2) XOR data(13) XOR crc_i(5) XOR data(12) XOR crc_i(4) XOR data(7) XOR data(14) XOR crc_i(6); 
crc_c(6) <= data(2) XOR data(3) XOR data(4) XOR data(11) XOR crc_i(3) XOR data(14) XOR crc_i(6) XOR data(13) XOR crc_i(5) XOR data(8) XOR data(15) XOR crc_i(7) XOR crc_i(0); 
crc_c(7) <= data(3) XOR data(4) XOR data(5) XOR data(12) XOR crc_i(4) XOR data(15) XOR crc_i(7) XOR data(14) XOR crc_i(6) XOR data(9) XOR crc_i(1); 


crc_gen_process : PROCESS(clock, reset) 
BEGIN                                    
 IF(reset = '1') THEN  
    crc_r <= "00000000" ;
 ELSIF( clock 'EVENT AND clock = '1') THEN 
    IF(data_valid = '1') THEN 
         crc_r <= crc_c; 
    END IF; 
 END IF;    
END PROCESS crc_gen_process;      
    

crc_valid_gen : PROCESS(clock, reset) 
BEGIN                                    
 If(reset = '1') THEN 
     crc_valid <= '0'; 
 ELSIF( clock 'EVENT AND clock = '1') THEN 
    IF(data_valid = '1' AND eoc = '1') THEN 
        crc_valid <= '1'; 
    ELSE 
        crc_valid <= '0'; 
    END IF; 
 END IF;    
END PROCESS crc_valid_gen; 

crc <= crc_r;

END behave;

I know that the CRC is obtained from the polynomial given from which a Linear Feed Back Shift Register realization will yield the required CRC as shown below (just for example but not specific to the VHDL code given above).




I just need the logic behind XOR operation GIVEN IN THAT VHDL CODE which helps for parallel CRC operation as per the below documents:

1. http://outputlogic.com/my-stuff/parallel_crc_generator_whitepaper.pdf

2. http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.75.387&rep=rep1&type=pdf


I have implemented CRC Generation and Detection from the general XOR operation but it takes more clock cycles. So I had to rely on parallel CRC generation technique.

 

[vGoodtimes]

CRC works on polynomial division. In this case, with coefficients in "GF2". GF2 is a "field" with 2 elements. 0,1. It also has two operators, "+" is xor, and "*" is and. These operators fill the normal field requirements (see wikipedia). As a result, it is common to describe them by writing "+" instead of "xor", and "*" instead of "and".

The CRC polynomial defines an expression, eg: x**8 = x**4 + x**3 + x**2 + 1. However, x**9 = x*x**8 = x**5 + x**4 + x**3 + x. Indeed, with this rule you can reduce x**N as a polynomial of at most degree 7. The HW implementation will store all 8 1b coefficients from x**7 downto x**0. (ignore the value for x. it isn't important. The expression will never be evaluated -- the coefficients are all that matter)

The CRC circuit works by shifting data in serially (for the first concept). a 1 can be shifted into the x**0 position. on the next input, it will be shifted to the x**1 position and so on. Once it gets to the x**8 position, the rule for x**8 = x**4 + x**3 + x**2 + 1. Thus a 1 gets added (xor'd) into the x**4 place, (and the x**3, x**2, and x**0 place).

Shifting by 2 bits per cycle is easy as well -- one value will end up in the x**8 place and will be reduced with the above rule. There will also be a value in the x**9 place, which also will be reduced back down. the output is thus the shifted previous state plus the sum of the reduced x**8 term and the reduced x**9 term. (again, for GF2 "sum" means "repeated xor")

And because the effect of x**N is known for all N, a CRC can be generated of any size.

In this case, the value calculated included the additional N shifts as normal in CRC calculations. eg, an input of 0x0001 will result in a CRC of 0x1D, not 0x01.

 

[kaiserschmarren87]

Thank you for the explanation vGoodTimes

I have another question regarding CRC Generator and Detector.

I got this Parallel CRC calculation document: https://apt.cs.manchester.ac.uk/ftp/pub/amulet/papers/MGrymel_TVLSI10.pdf

It says, suppose I use the below parallel CRC calculation VHDL code at the Generator end, crc_i will be polynomial_width-1 number of zeroes which will be appended during calculation. (Polnmoial is 100011101)

crc_c(0) <= data(0) XOR data(4) XOR data(5) XOR data(6) XOR data(13) XOR crc_i(5) XOR data(15) XOR crc_i(7) XOR data(10) XOR crc_i(2); 
crc_c(1) <= data(1) XOR data(5) XOR data(6) XOR data(7) XOR data(14) XOR crc_i(6) XOR data(11) XOR crc_i(3); 
crc_c(2) <= data(0) XOR data(2) XOR data(7) XOR data(8) XOR crc_i(0) XOR data(12) XOR crc_i(4) XOR data(4) XOR data(5) XOR data(13) XOR crc_i(5) XOR data(10) XOR crc_i(2); 
crc_c(3) <= data(0) XOR data(1) XOR data(3) XOR data(8) XOR data(9) XOR crc_i(1) XOR crc_i(0) XOR data(14) XOR crc_i(6) XOR data(11) XOR crc_i(3) XOR data(4) XOR data(15) XOR crc_i(7) XOR data(10) XOR crc_i(2); 
crc_c(4) <= data(0) XOR data(1) XOR data(2) XOR data(9) XOR crc_i(1) XOR data(12) XOR crc_i(4) XOR data(11) XOR crc_i(3) XOR data(6) XOR data(13) XOR crc_i(5); 
crc_c(5) <= data(1) XOR data(2) XOR data(3) XOR data(10) XOR crc_i(2) XOR data(13) XOR crc_i(5) XOR data(12) XOR crc_i(4) XOR data(7) XOR data(14) XOR crc_i(6); 
crc_c(6) <= data(2) XOR data(3) XOR data(4) XOR data(11) XOR crc_i(3) XOR data(14) XOR crc_i(6) XOR data(13) XOR crc_i(5) XOR data(8) XOR data(15) XOR crc_i(7) XOR crc_i(0); 
crc_c(7) <= data(3) XOR data(4) XOR data(5) XOR data(12) XOR crc_i(4) XOR data(15) XOR crc_i(7) XOR data(14) XOR crc_i(6) XOR data(9) XOR crc_i(1);

But at the Detector end the crc_i will be the appended CRC received along with the message input. This time that CRC will be fed to the detection algorithm instead of zeroes and finally the result should be zero if the message with crc has no errors.

Does that mean, I will be using the same algorithm as used at the input and get the result from that? Or this is there any change at the DETECTOR side for getting the remainder as ZEROES(if the message with crc has no errors?

 

[std_match]

But at the Detector end the crc_i will be the appended CRC received along with the message input. This time that CRC will be fed to the detection algorithm instead of zeroes and finally the result should be zero if the message with crc has no errors.

Does that mean, I will be using the same algorithm as used at the input and get the result from that? Or this is there any change at the DETECTOR side for getting the remainder as ZEROES(if the message with crc has no errors?

It is only the basic circuit (called LFSR in the linked CRC paper) that will give zeros if you feed it with the message + correct CRC. The disadvantage with that circuit for CRC generation is that you must feed it with m zeros after the message to get the m-bit CRC. Because of this, the CRC generation is normally done with the modified circuit (called LFSR2 in the paper) that will give the same result without feeding it the appended zeros. If your parallel CRC generator is of the LFSR2 type, you can not use the same logic as a checker and feed it the CRC after the message. To use the LFSR2 logic as a checker, you must stop the CRC calculation after the message and compare the generated CRC with the received CRC.

You can make a parallel implementation of LFSR that will give zero if you feed it the message + a correct CRC, but the logic is not identical to a parallel implementation of LFSR2 for the same polynomial.