RE: clarification please

[Luben Tuikov <ltuikov@yahoo.com>]

I've been sticking closely to the iSCSI draft,
some papers I found on CRC and CRC32/4, some
lecture notes, my abstract algebra lecure notes and
approached the CRC computation from a purely
mathematical model showing the exact origin of the
``magic'' value of 0x1c2d19ed, using pure algebra.

The two methods which I refer to are not equivalent,
since they do not produce the same remainder, R(x),
when it is computed at the sender.

Please see the 1 page worksheet attached for the math.

In a software implementation:
1. I assume straightforward poly division (table lookup,
shifting, whatever).

2. Premultiplication by x^32 (deg of generator poly).
E.g. appending 32 0s. This is so that when ~R(x) is added,
the message bits are unchanged!

3. Prefixing by 32 1s. E.g. CRC = 31 1's and then
the message bits are fed in from the right, popping out
the left. Logically this is s.t. a sequence of 1 or more
0s at the start of a message are detected.

The aforementioned steps, get the right CRC for the
all 0s example in the iSCSI draft but the rest three
examples are not correct.

Now if I stipulate step 3:

3. Complement the first 32 bits of the message and let
the CRC be 0 and then do the division.

Then I do not get even close to the samples in the draft.

If I stipulate step 3 as:

3. Complement the first 32 bits of the message and let this
be the initial value of the CRC and then do the division.

Then I do not get even close to the samples in the
draft.

Clearly the last 2 are equivalent.

In all 3 cases I _do_get_ the magic value at the end, 
and this is mathematically sound, since playing
with the CRC is like adding a certain polynomial,
C(x), and C(x)+C(x)=0, since the CRC is done the same
at the receiver, and the coefficients are in Z_2.

For any CRC, we have to have a solid mathematical model,
in order to avoid confision, etc.

We CAN provide a solid mathematical model for CRC32/4,
as is specified in the iSCSI draft, but the sample
CRC's will have to be changed.

My interpretation (word for word from the draft) is:
specifies CRC32/4, straightforward
premult. by x^32 and prefixing by 32 1s, and
straightforward division.

NO! Prefixing and adding ARE NOT equivalent in any sense!

I say prefixing, since it makes more sense to catch 0's
rather than not to. As well as it makes less sense to
mess with the message bits (as it would be for adding).

But the examples seem to be taken from a different
(Ethernet algo with CRC32/4 poly?) algorithm, or the
examples were mistyped.

If something else was intended, then so mentioned it
should've been.

-l


=====
--

__________________________________________________
Do You Yahoo!?
Check out Yahoo! Shopping and Yahoo! Auctions for all of
your unique holiday gifts! Buy at http://shopping.yahoo.com
or bid at http://auctions.yahoo.com

worksheet3.pdf