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

[Luben Tuikov <ltuikov@yahoo.com>]

Pat,

First I refer you to this message by Vince.
http://www.pdl.cmu.edu/mailinglists/ips/mail/msg08109.html
Read it again, please.

Then, let us think a bit.

In Ethernet realm, we get bits off the wire, one at a time.

A good CRC algorithm will have to be as strong as being
able to produce the CRC at any time. That is, it has to
have the correct CRC _after_ _each_ _bit_ has arrived.

I.e. in any moment in time, if I were to say STOP, I would
have to be able to ``produce'' the right CRC.

In other words, the algorithm needs NOT know in advance
how many bits there are of the message.

This eliminates the need to store the whole message and
then ``multiply it by x^32''.

I.e. I need only 32 + 1 bits of storage to compute the CRC
of any length message, and I can do so as the bits are
coming in from/to the wire, no need to store any bits. 32
for the CRC and 1 for the newly arrived bit. I don't need
to know the previous or next bits.

AND I will give you a CRC which is the same as if you HAD
multiplied the message by x^32, and done division of
the message, putting a suitable constant in the CRC
register (equivalent to prepending the message by it and
CRC=0) in D.

You see, this is the whole point of SMD (Simultaneous
Multiply and Divide) algorithm. It needs not multiply by
x^32, or prepend the message.

This multiplication of x^32 is needed only when we are in D
(simple Division) algorithm. And this is where it is coming
from.

Lets see a simple example in the decimal system:
let G(x) = 4 and M(x) = 7 (WLG).

then R(x) = 7 modulo 4 = 3

But this is wrong, we should have computed the remainder
of 70 modulo 4 which is 2.

and then we'd send 72, which has remainder 0 modulo 4.

And this is the SMD in Ethernet (WLG), if you feed it 7 it
will tell you 2 (not 3), so that you can append 2 at the
end to get 72 which has 0 remainder, etc.

Once we have a 0 remainder I can add any value from 1 to
3 to get that value back when the thing is received and
the remainder is computed e.g. 7 append (2+1) = 73.
73 modulo 4 = 1, etc. as per the spec. and this is where
the magical constant comes from...

And then the next digit comes along, say 5, now we have 75,
but the algorithm gives 2 (rather than 75 modulo 4 = 3).
And 2 is correct since 752 modulo 4 = 0...

So you see, before quoting the document, please
try to actually implement it, at least. And then
see how that would fit into Ethernet.

You can even implement it by hand, as arithmetic
in Z_2 is quite easy (XOR). And the make things
interesting make the message be one bit longer than
G(x), i.e. 34 bits.

Then you'll see how cumbersome is the multiplication
by x^32. And that a better way has to exist.

In fact SMD is what is actually implemented in Ethernet,
and in a real circuit I bet you'd never see actual
multiplication by x^32.

-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