CRC Algorithm

Cyclic Redundancy Check (CRC) algorithm is often used in communication devices for transmission error control. In this post simple explanations are described to this algorithm and a common approach of hardware implementation is also given.

In transmitter information data with fixed length (packet) should be encoded by appending some CRC bits. When receiver receives the encoded packet it'll check if there is any error bit occurred during transmission using the CRC bits.

Suppose we have a N-bit packet (e.g. 10101101) to be transmitted. There should be a pre-defined K-stage Generated Code e.g. 11001 (K=4).
1) The information data is appended with K zeros at right side, 101011010000.
2) The information data is divided by the Generated Code.
3) We throw away the quotient, and keep the residual 1001, which is exact the CRC checking code.
Finally the transmitted data with CRC code should be 101011011001.

In the receiver the received data will be also divided by the same Generated Code as that used in transmitter. Then it is checked to see if the residual is zero. If yes, there's no error bit in the packet, otherwise the packet contains at least one error bit and error control mechanism then will be started.

Below I'm giving a algorithm description for CRC.

GC[3:0] = 4'b1001; //Generated Code
Shf[3:0] = 4'b0000; //Temporary shift register to XOR with GC
Packet[MSB:LSB]; //Information packet data
i = MSB; //The number of information data's Most Significant Bit
while (i != LSB) {
tmp = Shf[3];
Shf = {Shf[2:0], Packet[i]}
if (tmp == 1'b1) Shf = Shf XOR GC
i = i - 1;
}
CRC_Code[3:0] = Shf[3:0];