|
[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index] RE: effect of initializing CRC reg to 1's depends on implementati on? iSCSIMake a note about when a CRC has to be valid. Julo pat_thaler Sent by: To: ltuikov@yahoo.com, owner-ips@ece. pat_thaler@agilent.com, ni1d@arrl.net, cmu.edu vince_cavanna@agilent.com cc: ips@ece.cmu.edu Subject: RE: effect of initializing 18-12-01 23:32 CRC reg to 1's depends on implementati on? iSCSI 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
Home Last updated: Thu Dec 20 13:17:46 2001 8167 messages in chronological order |