## Error detection using CRC code

What is error detection code?

Error detection codes such as Hamming, parity, LRC, checksum and CRC are codes added to the main data to let us detect any kind of error.

Imagine that we want to send some data to a receiver.

In order for the recipient to make sure that the delivered data is correct, an extra detection code attached to data (redundancy) needs to be sent.

The recipient calculates the error detection code based on the received data and then compares it with the actual received detection code.

If both are equal, the received data is correct.

## What is the advantage of using CRC code?

As mentioned in the previous section, there are different error detection codes.

CRC is important because there is almost no way that the error won’t be detected.

The weakness of CRC code is its complicated mathematical calculations compared to other mentioned codes.

Luckily, using the CRC calculation hardware like CRC calculation peripheral in microcontroller or its implementation in FPGA, its calculation problem is solved since the hardware can calculate the CRC of the data.

**CRC
code applications**

CRC code is used in different protocols such as Ethernet network, CAN bus, SD memory card communication, PCI communication, RAR file and so on.

CRC code in some applications is used for error detection like ds18b20 temperature sensor. In some protocols such as UART and I2C this code can be added so that the probability of not receiving the right data becomes almost zero.

**CRC
types**

CRC code can exist in different number of bits for example CRC8 code can detect 8 bits of error in a row.

The more the number of CRC code bits, the more accurate it will be.

For example in Ethernet protocol, CRC code is used in 32 bits.

**Generative
polynomial in CRC code **

CRC code is built from a generative polynomial.

This polynomial needs to be an odd number and preferably a primitive number, because data needs to be divided by this polynomial.

Some polynomials are very popular and are used in different protocols.

For example you can study Wikipedia in this regard.

For example in CRC8, 263 can be chosen as the polynomial. This number equals 100000111 in binary which is a 9-bit number. This number is also shown as x8+x2+x+1 and it shows the bits that are 1.

The reason why this is a 9-bit number is that if an n-bit data is divided by a 9-bit number, the result will be an 8-bit number.

The remainder of the data divided by the polynomial will give us its CRC code.

**Hand
calculation of CRC **

Imagine we have the number 200 as our data () and the generative polynomial (G(x)) is 263. These two numbers are divided by each other in binary. Xor is used instead of subtraction .

First we add as many zeros as the number of CRC bits in front of the data.

Because we want to calculate CRC8 here, we add 8 zeros to the data then calculate the CRC.

In each stage of the division above, xor was used instead of subtraction.

In each stage, we used the one or two zeros added (you can see it with yellow color) so that the length of the data being divided equals the number of bits of G(x).

CRC8 of the number 200 equals 118.

**Long
CRC calculation **

If M(x) data length is even more, CRC calculation is possible again but the number of steps will be more. For example CRC8 of the number 8321 will be 32 or CRC8 of the number 2131718 is 140.

**CRC hardware
calculation **

As you saw earlier, CRC hand calculations are very time-consuming.

CRC hardware calculation can be done using a simple shift-register circuit.

First of all, we need to form a matrix.

This matrix is a combination of a diagonal matrix (entries outside the main diagonal are 0 and the main diagonal is 1), a zero matrix and a matrix consisting of CRC coefficients except the MSB.

For example for generative polynomial of 263, this matrix equals the M matrix as shown below:

In this matrix, the yellow column is the coefficients of the generative polynomial (without the MSB), the orange column is the diagonal matrix and the green one is the zero matrix.

This is an 8 by 8 matrix because we are calculating CRC8. To calculate the CRC32, this matrix becomes 32 x 32.

The code to generate this matrix in MATLAB can be seen below:

**Serial CRC
hardware calculation **

In serial approach, data enters the CRC calculation hardware bit by bit (MSB first) and its CRC code is calculated.

To calculate serial CRC hardware, we need to build the matrices below:

Imagine we want to calculate CRC8. CRC_new is the new CRC code which is an 8×1 matrix with 8 rows and 1 column.

M is an 8×8 matrix.

CRC_old is the CRC calculated in the previous step which is 8×1.

G consists of generative polynomial coefficients without the MSB which is 8×1.

Data matrix is a serial data which is 1×1.

When multiplying M by CRC_old, instead of adding we use xor.

After simplifying the above equation, we’ll have:

And then we’ll get the final equation.

And this equation tells us that in order to calculate the MSB of CRC in the new stage, we should give it the CRC6 bit of the previous stage.

Or to calculate the zero bit of the new CRC, we need to get bits of the previous seven stages xor the input data.

Based on the IEEE802.11, the hardware form of calculating this type of CRC has been drawn in the picture below:

**CRC calculation in VHDL language**

In VHDL, we use “process” in order to calculate the CRC. And in Verilog we use “always”. In the code below you can see the implemented program. Online CRC calculation websites can also be used.

library IEEE; use IEEE.STD_LOGIC_1164.ALL; entity crc8 is Port ( data_in : in STD_LOGIC_VECTOR (7 downto 0); en : in STD_LOGIC; clk : in STD_LOGIC; crc : out STD_LOGIC_VECTOR (7 downto 0); valid : out STD_LOGIC); end crc8; architecture Behavioral of crc8 is signal sdata:std_logic_vector(7 downto 0); signal crc_old:std_logic_vector(7 downto 0); signal crc_new:std_logic_vector(7 downto 0); signal flag:std_logic:='0'; signal start:std_logic:='0'; signal d0:std_logic:='0'; signal i:integer range 0 to 8; begin process(clk) begin if(rising_edge(clk))then valid<='0'; if(en='1')then sdata<=data_in; crc_old<=x"00"; crc_new<=x"00"; flag<='0'; start<='1'; i<=0; end if; if(start='1')then if(flag='0')then crc_old<=crc_new; d0<=sdata(7); sdata<=sdata(6 downto 0)&'0'; i<=i+1; if(i=8)then crc<=crc_new; valid<='1'; start<='0'; end if; flag<='1'; else crc_new(7)<=crc_old(6); crc_new(6)<=crc_old(5); crc_new(5)<=crc_old(4); crc_new(4)<=crc_old(3); crc_new(3)<=crc_old(2); crc_new(2)<=crc_old(7) xor d0 xor crc_old(1); crc_new(1)<=crc_old(7) xor d0 xor crc_old(0); crc_new(0)<=crc_old(7) xor d0; flag<='0'; end if; end if; end if; end process; end Behavioral;

**CRC
calculation in C language**

C language is not as fast as Hardware Description Languages. And CRC calculation is time-consuming in this language because except for some microcontroller chips that CRC calculation unit is embedded in them, CPU should run the instructions.

In the code below you can see that xor can do this. Online CRC calculation websites can also be used in the C language.

unsigned char calcCRC (unsigned char x) { unsigned char i,j[8],temp,crca[8],p; temp=x; for(i=0;i<8;i++) { j[i]=temp%2; temp=temp/2; crca[i]=0; } for(i=0;i<8;i++) { temp=(1==j[7-i]) ^ crca[7]; crca[7] = crca[6]; crca[6] = crca[5]; crca[5] = crca[4]; crca[4] = crca[3]; crca[3] = crca[2]; crca[2] = crca[1] ^ temp; crca[1] = crca[0] ^ temp; crca[0] = temp; } p=1; temp=0; for(i=0;i<8;i++) { temp+=(crca[i]*p); p*=2; } return temp; }

## Parallel CRC calculation

** **buy this part of education with 20$

in this part you learned about data input with any length of data input…

author:M.R. Beygi

translated by: F. Mirabbasi