Cyclic Redundancy Check

home | our design | design code | software | firewire | resources | design team | contact us  

Cyclic Redundancy Code (CRC) Checksum Generator
 


Introduction

The CRC module generates 32-bit CRC. The CRC is calculated to transmit along with the message and to check CRC of the received packet. The purpose of the error detection technique is to enable the receiver, of the message transmitted through a noisy (error-introducing) channel, to determine whether the message has been corrupted or not.

The message transmitted through the 1394 bus uses two CRCs,

These CRCs are placed in the packet as shown by the figure

Figure: The header and data CRCs in a 1394 packet

1394 packet with header and data CRC
 






IEEE-1394 CRC is same as that of IEEE 802 LANs and FDDI

Both the header CRC and the data CRC are generated and checked using a standard algorithm. This is the same CRC used by the IEEE 802 LANs and FDDI.
The most significant bit (the x 31 term of R(x)) of the CRC shall be transmitted first.

Definitions:

F(x) A degree k-1 polynomial that is used to represent the k bits of the packet covered by the CRC. For the purposes of the CRC, the coefficient of the highest order term shall be the first bit transmitted.

L(x) A degree 31 polynomial with all of the coefficients equal to one, i.e.,
L(x) = x 31 + x 30 + x 29 + ... x 2 + x 1 + 1

G(x) The standard generator polynomial:
G(x) = x 32 + x 26 + x 23 + x 22 + x 16 + x 12 + x 11 + x 10 + x 8 + x 7 + x 5 + x 4 + x 2 + x + 1

R(x) The remainder polynomial that is of degree less than 32.

P(x) The remainder polynomial on the receive checking side that is of degree less than 32.

CRC The CRC polynomial that is of degree less than 32.

Q(x) The greatest common multiple of G(x) in [x 32 F(x) + x k L(x)].
Q*(x) x 32 Q(x).

M(x) The sequence that is transmitted.
M*(x) The sequence that is received.
C(x) A unique polynomial remainder produced by the receiver upon reception of an error-free sequence. This polynomial has the value: C(x) = x 32 L(x)/G(x)
C(x) = x 31 + x 30 + x 26 + x 25 + x 24 + x 18 + x 15 + x 14 + x 12 + x 11 + x 10 + x 8 + x 6 + x 5 + x 4 + x 3 + x + 1

CRC generation equations.

The equations that are used to generate the CRC sequence from F(x) are:

a) CRC = L(x) + R(x) = R$(x) where R$(x) is the one’s complement of R(x).
b) [x 32 F(x) + x k L(x)]/G(x) = Q(x) + R(x)/G(x)
c) M(x) = [x 32 F(x)] + CRC

NOTE: All arithmetic is modulo 2. Equation (a), adding L(x) (all ones) to R(x) simply produces the one’s complement of R(x); thus this equation is specifying that the R(x) is inverted before it is sent out. Equation (c) simply specifies that the CRC is appended to the end of F(x).

The CRC Generator Module generates the CRC checksum according to the specification of the IEEE-1394 1995 standard.
The pin diagram of the CRC module.
 


Figure: The CRC generator module

Pin Diagram
 




Table: Port description of the CRC module
 

Signal Name and Description
reset_n To reset CRC before a new calculation
crc_in To notify the CRC module to strobe data on the CRC_DATA lines. 
Should be HIGH only for one BCLK cycle. 
CALC_CRC CRC module places the calculated CRC on these lines after each crc_in.
CRC_DATA Input data to CRC module is placed here.


 
 

Protocols of the CRC module

Whenever a new CRC value is to be calculated the CRC module must be reset. This is done by reset_n signal, which is an active low signal. This reset_n causes the initial value of calc_CRC to become ‘FFFFFFFF’ hex which is the necessary condition.

Figure: The CRC module waveform

Waveforms
 


The protocol of the CRC module requires that data be placed on the ‘D’ lines at positive edge of BCLK and simultaneously the ‘crc_in’ signal is asserted. The calculated CRC of data appears at the output ‘calc_CRC’ at the next positive edge of BCLK.
This protocol can be well understood by the above diagram.
 


Figure: The CRC module Flow Chart- Click to View

Flow Chart
 




Features

The CRC module is designed for general-purpose use.
The calculated CRC is immediately available on the output lines.
There is no need of a separate signal to get the calculated CRC checksum.
 
 

CRC and its Algorithms

How CRC is Used

Cyclic Redundancy Checking is a method of checking for errors in data that has been transmitted on a communications link. A sending device applies a 16- or 32-bit polynomial to a block of data that is to be transmitted and appends the resulting cyclic redundancy code (CRC) to the block. The receiving end applies the same polynomial to the data and compares its result with the result appended by the sender. If they agree, the data has been received successfully. If not, the sender can be notified to re-send the block of data.
 

Algorithms

On the basis of certain criterion different techniques are used to implement CRC in different devices some of them are as under:

Bit-by-Bit Calculation

To implement a CRC algorithm we have to perform CRC division. Following algorithm is used to implement CRC division.

  1. load the register with zero bits
  2. augment the message by appending w zero bits to the end of it.
  3. while(more message bits)

begin
shift the register left by one bit, reading the next bit of the augmented message into the register bit position ‘0’.
if(a ‘1’ bit popped out of the register during previous step)
register = register xor poly;
end

The register now contains the remainder.

Here,
register = augmented message (data).
poly = register with bits at positions representing the polynomial terms.
W = width of data register.

Implementation Problem

Since the above mentioned algorithm operates at the bit level it is rather awkward to code and inefficient to execute and specifically in ‘1394’ data is transferred in 32 bit words (quadlet) so this algorithm utilizes 32-cycles to prepare CRC for a single quadlet. This drastically reduces the speed of the system. When speed is one of the requirements this delay is not required. Due to this reason it is not feasible to implement.

Table Driven Implementation:

In order to implement the algorithm we must have a pre-computed table having values for each possible combination of data bits present in the quadlet. These table values are calculated with the help of polynomial .The number of table entries depend upon the number of bits in the data which is transferred, e.g. for 32 data there will be 232 entries in the table.

while(augmented message is not exhausted)
begin
top = top_byte(register);
register = (register << 24 ) | next_aug_message_byte;
register = register xor pre_computed_table[top];
end

Here,
register = 32 bit wide and contains augmented message
top = 8 bit wide, contains top 8 bit of incoming message
pre_computed_table = it contains 28 entries each 32 bit in width.

Implementation Problem

As was mentioned earlier the ‘1394’ deals with 32-bit data so table driven implementation require a table having 232 entries of 32-bit each. Thus the table size is 32 x 232 bits = 137438953472 bits = 17179869184 bytes = 16 G-bytes.

Imagine how many ‘hard disks’ could be needed!

Use of Equations:

In order to implement CRC in systems specially Systems on Chip (SoC) a variety of techniques were developed which could overcome the shortcomings of table-driven and bit-wise implementation. CRC module of our design also utilizes one of such techniques.

This technique provides both faster execution and less, rather no, usage of memory.

Description

In this technique there are 32 different equations, one for each bit of the calculated CRC word. These equations are based on the polynomial used. The polynomial used in 1394 as mentioned in IEEE standard is

x32 + x26 + x23 + x22 + x16 + x12 + x11 + x10 + x8 + x7 + x5 + x4 + x2 + x + 1

The hexadecimal equivalent value of this polynomial is 04C11DB7.
The initial value of the CRC register according to standard must be FFFFFFFF.

As far as the authenticity of the results generated by these equations is concerned it is stated here that the results of these equations completely verifies the standard. The algorithm was verified using C-language programs. You can find the C language code for CRC generation by both algorithms at the end of document. Some interesting links are also provided at the end of document.
 
 

The equations that are used to generate the CRC checksum are generated by the CRC tool available at http://www.easics.com/webtools/crctool . The secret of generation of these equations is still not known. We don’t know how these equations are generated. What is the criteria? We are trying to uncover the secret. If you have some related information then please do share with us. As soon as more information is known we will update this page to be more helpful.

This page is basically related to the design discussion and some very general information. If you need detailed information you can use the links provided or freely email us at mailto:support@linklayercontroller.com This information is also available on the CD available at the Department of Computer and Information Systems, NED UET.
 
 

The Altera Problem

When we were implementing the CRC algorithm using Altera MAX-PLUS II ver. 9.4, it was found that the results were not real. It was then found that there is a problem with the software tool. The tool can not process with 32-bit words! The problem was solved by using two 16-bit registers instead of one 32-bit register! Here is the mail for your aid. Hope this problem is fixed in newer versions.
 
 

The CRC checksum Generator Code in C-language

Specified by the Standard

Get File (crc_std.c)

/*This C language code is the standard implementation as discussed in the IEEE-1394 High Performance Serial Bus Standard
Some amendments rather additions have been done to make an executable file. This change does not alter any feature of the standard.*/
#define LSB_32 0x00000001
#define MSB_32 0x80000000
#define ONES_32 0xffffffff
#define crccompute ((Quadlet) 0x04C11DB7)
#define crcresults ((Quadlet) 0xC704DD7B)
#include "stdlib.h"
#include "stdio.h"
#include "conio.h"

typedef unsigned long Quadlet;

main()
{
Quadlet inquad, crcsum, newmask;
int newbit, oldbit, sumbit, pp[32], aa;
crcsum=(Quadlet)0xFFFFFFFF;
inquad=(Quadlet)0; //0xaaaaaaaa;
clrscr();
for(newmask=MSB_32; newmask!=0; newmask>>=1)
{
newbit=((inquad&newmask) !=0);
oldbit=((crcsum&MSB_32) !=0);
sumbit=oldbit ^ newbit;
crcsum=((crcsum<<1) & ONES_32) ^ (sumbit ? crccompute:0);
}
for(aa=31; aa>=0; aa--)
{
pp[aa]=LSB_32&crcsum;
crcsum = _lrotr(crcsum,1);
}
printf("\n");
for(aa=0; aa<32; aa++)
printf("%d", pp[aa]);
printf("\n%f", (float)crcsum);
getch();
}
 

The CRC checksum Generator Code in C-language

Satisfies the Standard

Get File (crc_web.c)
 
 

Links

Following is a list of some wonderful documents/information related to CRC.

Hope you will enjoy the CRC work!
 

| Home | Mail | Top |

The HMZ – IEEE-1394 High Speed Serial Bus Link Layer Controller Project – Web Version
Also available on CD.

1