Subject: effect of initializing CRC reg to 1's depends on implementation?

From: [email-masked]
Date: Wed, 12 Dec 2001 15:21:18 -0700

In working with Luben Tuikov to document the math behind the CRC I
discovered something that surprised me. I intend to study this further but
hope someone can save me work by pointing out that I am wrong (or right) and
offering some proof.

Consider two ways to implement the iSCSI CRC with a serial divider (see PDF
file):

1. divide the message directly using a serial circuit that, when its stages
are initialized to zeroes, simultaneously multiplies by x^32 and divides by
G(x).

2. pre-multiply message by x^32 and then divide the results by G(x) using a
serial circuit that, when its stages are initialized to zeroes performs a
division by G(x).

The two circuits, of course, produce the same results when they are
initialized to 0's.

In the approach in (1) initializing the register to 1's appears equivalent
(produces the same quotient; same remainder) to initializing the register to
0's and complementing the most significant 32 bits of the message prior to
processing.

In the approach of (2) such an equivalence does not appear true!

This means to me that it is meaningless to specify that the CRC must be
initialized to 1's unless we refer to a specific implementation which we did
not do in the iSCSI spec! What is troublesome is that I have seen claims in
the literature (and in one textbook on data communications) that
initializing the CRc to 1's is equivalent to complementing the most
significant n bits of the dividend for both implementations. I have also
seen the same claim with no reference to an implementation (e.g. iSCSI)
which would imply that the implementation does not matter.

The implementation that I have most often seen referred to is a parallel
version of (1) wherein n message bits are processed at one time;
fortunately, for such an implementatiaon, the claim appears to be correct.

Thanks. <<Scan_Fro.pdf>> 

Vince Cavanna
Agilent TEchnologies

---

From: Paul Koning <[email-masked]>
Date: Thu, 13 Dec 2001 11:40:01 -0500 (EST)

>>>>> "vince" == vince cavanna <[email-masked]> writes:

 vince> In working with Luben Tuikov to document the math behind the
 vince> CRC I discovered something that surprised me. I intend to
 vince> study this further but hope someone can save me work by
 vince> pointing out that I am wrong (or right) and offering some
 vince> proof.

 vince> Consider two ways to implement the iSCSI CRC with a serial
 vince> divider (see PDF file):

 vince> 1. divide the message directly using a serial circuit that,
 vince> when its stages are initialized to zeroes, simultaneously
 vince> multiplies by x^32 and divides by G(x).

 vince> 2. pre-multiply message by x^32 and then divide the results by
 vince> G(x) using a serial circuit that, when its stages are
 vince> initialized to zeroes performs a division by G(x).

 vince> The two circuits, of course, produce the same results when
 vince> they are initialized to 0's.

 vince> In the approach in (1) initializing the register to 1's
 vince> appears equivalent (produces the same quotient; same
 vince> remainder) to initializing the register to 0's and
 vince> complementing the most significant 32 bits of the message
 vince> prior to processing.

 vince> In the approach of (2) such an equivalence does not appear
 vince> true!

 vince> This means to me that it is meaningless to specify that the
 vince> CRC must be initialized to 1's unless we refer to a specific
 vince> implementation which we did not do in the iSCSI spec! What is
 vince> troublesome is that I have seen claims in the literature (and
 vince> in one textbook on data communications) that initializing the
 vince> CRc to 1's is equivalent to complementing the most significant
 vince> n bits of the dividend for both implementations. I have also
 vince> seen the same claim with no reference to an implementation
 vince> (e.g. iSCSI) which would imply that the implementation does
 vince> not matter.

I must be sounding like a broken record at this point, but I believe
the answer is to use the Ethernet spec as an example.

The Ethernet spec has the mathematical definition of the CRC in the
body of the spec.  In other words, it talks about complementing the
message, multiplying by x^32. dividing by G(x), and so forth.  That
definition is unambiguous.

In addition, the Ethernet spec gives an EXAMPLE implementation in
appendix C.  That is not normative; it merely shows one way to
translate the math into gates.  In that example implementation -- and
NOT in the mathematical definition in the normative part -- it is
meaningful to talk about initializing the shift register to all 1's.

I would recommend using the same descriptive approach in the iSCSI
spec.  It may be possible simply to copy the description as it appears
there (with suitable alteration to the placement of the LFSR taps, of
course, for the sample implementation); I see no copyright claims on
the document that prevent doing so.

    paul