home | our design | design code | software | firewire | resources | design team | contact us
Cyclic Redundancy Code (CRC)
Checksum Generator
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
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
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. |
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
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
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.
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.
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.
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:[email protected]
This information is also available on the CD available at the
Department of Computer and Information Systems, NED UET.
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
/*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
Following is a list of some wonderful documents/information related to CRC.
Hope you will enjoy the CRC work!
The HMZ – IEEE-1394 High Speed
Serial Bus Link Layer Controller Project – Web Version
Also available on CD.