found the constant for divide-only circuit!

["CAVANNA,VICENTE V (A-Roseville,ex1)" <vince_cavanna@agilent.com>]

Luben and I found the constant polynomial, C1(x), that makes the following
two operations eqivalent for a divide-only implementation (attached) of
CRC32c:

1. CRC register initialized to zeroes and C1(x) added (XORed) to the most
significant bits of the message.

2.CRC initialized to ones and nothing added to the message.

At the end I summarize my recommendation to Julian for fixing the iSCSI
spec.

C1(x) turned out to be the same as the magic constant specified in the iSCSI
spec!!
As some of us have explained before, the magic constant is equal to L(x)x^32
modulo G(x) with L(x) being the 32 bit all 1's poly and G(x) the CRc poly.
For the simultaneous multiply and divide circuit we already knew that the
constant, C2(x), is just L(x).

We now know the equivalences for both implementations:

1. For the divide-only circuit, initializing the register to all 1s and
applying an all zeroes message is equivalent (produces the same results) as
initializing the register to all zeroes and applying the C1(x) input message
above.

We can also say that C1(x) is what you would add (not append) to the most
significant 32 bits of your message and apply to the divide-only circuit
which has been initialized to zeroes. You would get the same results as if
you initialized the circuit to ones and applied the raw message.

2. For the simultaneous multiply and divide circuit we already knew that
initializing the register to 1s and applying an all zeroes message is
equivalent to initializing the register to zeroes and applying the C2(x)
input message.

So C2(x) is what you would add (not append) to the most significant 32 bits
of your message and apply to the multiply-divide circuit which has been
initialized to zeroes. You would get the same results as if you initialized
the circuit to ones and applied the raw message.

For those interested here is one way to find the constant C1(x):

Initialize the divide-only circuit to 1's and apply an all-zeroes message.
Look at the state after the 32nd clock and record that value, which I called
C1(x). We now want to find what 32-bit input message would produce the same
result when the circuit is initialized to 0's. I reasoned that, until the
33rd clock, the order of the input poly is less than that of the CRC
polynomial and thus the current remainder must be equal to the input message
itself. Thus if I let the input be C1(x), after 32 clocks I would end up
with C1(x) in the CRC register which was indeed the case. 
Luben had a different development (see upcoming internet draft) that is more
rigorous and shows why C1(x) happens to be equal to the magic constant.


	There are several ways we can fix the iSCSi spec:

	1. making it explicit that the assumed implementation performs
simultaneous multiplication by x^32 and division by G(x) by showing an
implementation such as the attached circuit OR 

	2. saying that the CRC must be initialized to ones and not saying
that this is equivalent to adding 1s to the most significant 32 bits of the
message (because the statement would be only true for one implementation).

	3. saying that the CRc must be initialized to ones and explaining
that, for the multiply-divide implementation, this is equivalent to adding
1s to the most significant 32 bits, and, for the divide-only implementation,
this is equivalent to adding the magic constant to the most significant 32
bits.

	Option one is the simplest, and the one I recommend. In fact, for
options 2 and 3 we may (need to think about this some more) need to fix the
examples.


Vince
 <<BothCircuits.pdf>> 



>  -----Original Message-----
> From: 	CAVANNA,VICENTE V (A-Roseville,ex1)  
> Sent:	Wednesday, December 12, 2001 10:06 PM
> To:	'ips@ece.cmu.edu'
> Cc:	'ltuikov@yahoo.com'; 'Paul Koning'; CAVANNA,VICENTE V
> (A-Roseville,ex1); SHEEHY,DAVE (A-Americas,unix1); THALER,PAT
> (A-Roseville,ex1)
> Subject:	assumed CRC circuit performs simultaneous mult and division
> 
> Regarding my earlier memo "effect of initializing CRC reg to 1's depends
> on implementation?", here are more details and a proposed fix. This little
> detail has generated a _lot_ of discussion among Luben Tuikov, Paul Koning
> and myself and in fact we have not all quite agreed yet on the severity of
> hte problem and how to fix it. 
> 
> Where I see the iSCSI spec deficient is in not making explicit that the
> assumed circuit performs _simultaneous_ multiplication by x^32 of the
> message, M(x), and division by G(x). When the spec says that the message
> M(x) is multiplied by x^32 and divided by G(x), if the spec said that the
> division must occur simultaneously with the multiplication by x^32, as it
> does in the attached circuit, then the spec would be correct. In other
> words, with that assumption the spec is correct in saying that
> initializing the CRC register to 1's is equivalent (produces same
> remainder and quotient) to complementing the first 32 bits of the message.
> 
> If the assumed circuit is the divide-only circuit that I also am
> attaching, then initializing the CRC register to 1's, as the spec
> requires, will _not_ result in the correct remainder specified by iSCSI in
> its examples since initializing _that_ circuit to 1's implements a
> different division than what the iSCSI examples assume. 
> On the other hand the receiver will still compute the same magic constant
> that the iSCSi spec specifies since the magic constant is not dependent on
> the actual message or its remainder but rather on the fact that there were
> no errors. This is what Luben observed and what he and Paul and I have
> been discussing (and still are) for a while.
> 
> This is why I am claiming that the iSCSI spec should be fixed by either:
> 
> 1. making it explicit that the assumed circuit performs simultaneous
> multiplication by x^32 and division by G(x) such as the attached circuit
> OR 
> 
> 2. saying that hte most significant 32 bits of the message should be
> complemented - rather than saying that the CRC register be initialized to
> 1s, since the effect of the last statement is implementation dependent,
> whereas the effect of the first statement is independent of the
> implementation.
> 
> Vince
> 
>  << File: Scan_Fro.pdf >> 
>

BothCircuits.pdf