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

["THALER,PAT (A-Roseville,ex1)" <pat_thaler@agilent.com>]

Paul,

I agree that we should use the mathematical description of the CRC as the
spec. Equivalent ways of obtaining the effect of inverting the first bits or
checking the result (magic number) are implementation details. I'm not
convinced that we need to show an implementation example in the annex. Given
the misleading information that Vince has found in some of the literature if
we show an implementation example, we need to point out that the technique
of initializing the register to 1's applies specifically to that
implementation and may not work for other implementations.

Regards,
Pat

-----Original Message-----
From: Paul Koning [mailto:ni1d@arrl.net]
Sent: Thursday, December 13, 2001 8:40 AM
To: vince_cavanna@agilent.com
Cc: ips@ece.cmu.edu; pat_thaler@agilent.com; dave_sheehy@agilent.com
Subject: Re: effect of initializing CRC reg to 1's depends on
implementation?


>>>>> "vince" == vince cavanna <vince_cavanna@agilent.com> 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