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

[pat_thaler@agilent.com]

Luben,

I have a pretty fair idea of the constraints on Ethernet implementations
having worked on Ethernet implementations and standards for over 15 years.
The issue is not whether a certain implementation is common or not. It isn't
the merits of one implementation method over another. The point is that
whereever possible (that is wherever it doesn't damage interoperability)
standards should be written in terms of results - that is in terms of the
behavior of the black box at its interfaces. Any implementation that
produces that behavior is valid and the implementor should be left with the
freedom to use whatever implementation method fits the implementation's
circumstances.

I agree with the analysis of D and SMD. SMD is a widely used implementation
method. However, that is irrelavent to what should go into the standard.

By the way, there is an error in your statement below with respect to
Ethernet behavior: "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."

Actually and Ethernet implementation is specifically required not to behave
this way. If you will refer to IEEE 802.3 4.2.9 procedure ReceiveLinkMgmt
processes the frame before function ReceiveDataDecap checks the CRC (an
interaction controlled by receiveSucceeding). ReceiveLinkManagement
truncates the frame to an octet boundary. This was done to be tolerant of
some untidy physical layer implementations that add a few "dribble bits" to
frames (sad but true). The CRC is the last 4 full octets of the frame rather
than the last 32 bits - a difference that only matters when there are
dribble bits. If an implementation calculated the CRC as each bit arrived,
it would have to back out the effect of the dribble bits to check the CRC on
an octet boundary which would be inconvenient. Most implementations I am
aware of calculate the CRC on a byte or multi-byte parallel basis rather
than a bit at a time.

Regards,
Pat

-----Original Message-----
From: Luben Tuikov [mailto:ltuikov@yahoo.com]
Sent: Monday, December 17, 2001 8:04 PM
To: THALER,PAT (A-Roseville,ex1); Paul Koning; VICENTE V CAVANNA
Cc: ips@ece.cmu.edu
Subject: RE: effect of initializing CRC reg to 1's depends on
implementati on? iSCSI


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