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

From: "CAVANNA,VICENTE V (A-Roseville,ex1)" <[email-masked]>
Date: Fri, 14 Dec 2001 14:09:02 -0700

Paul,

Looks fine as long as one realizes that:

1. If someone choses to use the divide-only circuit that is commonly found
in texts they cannot initialize the registers to 1's and hope to achieve the
same effect as complementing the first 32 bits of the PDU. 

2. If someone choses to use the multiply-divide circuit as in ethernet spec
they can initialize the registers to 1's and achieve the same effect as
complementing the first 32 bits of the PDU.

I am pretty sure the intent in predecessors to the ethernet spec (FDDI,
HDLC) was to initialize the registers of the implementation to ones. The
effect, for the referenced implementation which was a multiply-divide
implementation, could be obtained by complementing the most significant bits
of the message.

Vince

|-----Original Message-----
|From: Paul Koning [mailto:[email-masked]]
|Sent: Friday, December 14, 2001 12:18 PM
|To: [email-masked]
|Cc: [email-masked]
|Subject: RE: effect of initializing CRC reg to 1's depends on
|implementati on? iSCSI
|
|
|I guess the problem with the spec is that it is a confusing mix of
|pieces of the mathematical definition and pieces of description from a
|specific (and unstated) implementation.
|
|Ok, so let me propose specific replacement text.
|
|This is for Appendix D, starting at the top of page 193 in the -09 rev
|of the spec.
|
|----------------
|The generator polynomial for the CRC is x^32 + x^28 + x^27 + x^26 +
|x^25 + x^23 + x^22 + x^20 + x^19 + x^18 +x^14 + x+13 + x+11 + x^10 +
|x^9 + x^8 +x^6 + 1.
|
|The CRC value for a PDU is defined mathematically as follows:
|
|1. The first 32 bits of the PDU are complemented.
|
|2. The N bits of the PDU are then considered to be coefficients of a
|polynomial M(x) of degree N-1.  Bit 0 of byte 0, i.e., the low order
|bit of the high order byte of the first word of the PDU, corresponds
|to the X^(N-1) term of this polynomial, and the high order bit of the
|last byte of the PDU corresponds to the x^0 term.  Note that any pad
|bytes for the PDU are included.
|
|3. M(x) is multiplied by x^32, and divided by G(x), producing a
|remainder R(x) of degree < 32.
|
|4. The coefficients of R(x) are considered to be a 32-bit sequence.
|
|5. This bit sequence is complemented and the result is the CRC.
|
|The CRC is trannsmitted with the high order bit (corresponding to the
|x^31 term of R(x)) in the low order bit of the first byte transmitted,
|and the low order bit (corresponding to the x^0 term of R(x)) in the
|high order bit of the fourth byte transmitted.
|----------------
|
|This text is inspired by the text in the Ethernet spec, with some
|wording changes needed for the iSCSI context.  I believe this is a
|precise definition of what is needed.
|
|For additional information, more text could be included.  For example:
|
|----------------
|The above algorithm is exactly that used in the Ethernet/802.3 LAN,
|with the exception of the choice of generator polynomial.
|----------------
|
|And perhaps a note on implementation:
|
|----------------
|The above algorithm may be efficiently implemented in a variety of
|ways, such as linear feedback shift registers, table lookup, etc.
|----------------
|
|Finally, we could capture the "magic constant" receive algorithm as
|follows:
|
|----------------
|Implementation of the CRC32C checking for PDU reception can be done in
|several ways.  
|
|One approach is to calculate the CRC over the PDU not including the
|CRC field, and compare that with the received CRC.  If the two values
|are equal, the digest is considered valid.
|
|Another approach is to perform the above algorithm over the entire
|received PDU, including the CRC field.  With that approach, a valid
|digest results in R(x) having the value x^28 + x^27 + x^26 + x^21 +
|x^19 + x^18 +x^16 + x^12 + x^11 + x^8 + x^7 + x^6 + x^5 + x^3 
|+ x^2 + 1,
|i.e., the value of the 32-bit sequence obtained in step 4 is
|0x1c2d19ed. 
|----------------
|
|Following Pat Thaler's comments, I am not proposing any more text on
|implementation approaches.  Both the table based approaches and the
|LFSR approach can be covered by references to literature, though
|admittedly some of the references may not be all that easy to
|acquire. 
|
|So my proposal is to replace the text on page 193 up to the
|"Proprietary algorithms MAY also..." with the four pieces given
|above.  If people don't like the later pieces, then I'll fall back to
|proposing just the first chunk of text (the formal definition of the
|CRC) as replacement for the current text.
|
|	 paul
|

---

From: [email-masked]
Date: Mon, 17 Dec 2001 18:42:51 -0700

Mark,

The text you suggest assumes a specific implementation. It is
not suitable to go into the spec. The text describing the CRC
in the spec should be in the mathematical form similar to what
was used to describe the CRC in Ethernet. Describe:

 Formation of the message polynomial
 Division by G(x) to get the remainder
 Inversion of the remainder

Don't talk about initiating registers which will be different 
for different forms of valid implementation.

Pat

-----Original Message-----
From: Mark Bakke [mailto:[email-masked]]

<stuff deleted> 

Here is some text that I had suggested adding instead of (or 
in addition to) the mathematical description a while ago:

The generator polynomial selected is evaluated in [Castagnioli93].
When using the CRC the CRC register must be initialized to all 1s
(0xFFFFFFFF).  Input bytes are processed with bit 7 being the most
significant bit.  Before transmission, the CRC bits must be
reflected (bit 31 swapped with bit 0, bit 30 swapped with bit 1,
etc.), and complemented.  The CRC bytes must be transmitted in
network order.  Padding bytes, when present, in a segment covered
by a CRC, should be set to 0 and are included in the CRC.

Running the CRC-32C generator on an input stream that includes a
valid CRC-32C will result in the constant remainder 0x1c2d19ed,
(without being reversed and complemented).

The above, plus the examples, have seem to work out just fine
for the implementors.  Getting the math right would be nice, but
most of us implementors don't look at it anyway, and prefer the
more practical description.  If we are going to include the math,
it has to match the examples.

Anyway, my guess is that is what you are discussing; it was just
disturbing to think that anything but the Ethernet + new poly
was being considered, since that has been agreed on for a long
time, and is being widely implemented.

--
Mark

Luben Tuikov wrote:
> 
> --- Paul Koning <[email-masked]> wrote:
> > Excerpt of message (sent 14 December 2001) by Luben
> > > This is actually equivalent to XORing the first
> > > 32 bits of the message with the magic constant as Vince
> > > and I have shown.
> >
> > Are you saying that you believe the intent of the current
> > spec is NOT
> > the same as the Ethernet CRC, i.e., complement the first
> > 32 bits,
> > multiply by x^32, then divide by G(x)?
> 
> In our profession we cannot talk about beliefs and
> intentions, more so for documents, rfc, etc.
> 
> If you show the current description of the CRC of the draft
> to a mathematician, they will object to the same thing I've
> objected.
> 
> The reason is that they don't have the preconception about
> what circuit is being used, and any such higher level
> notions.
> 
> All they would have and all I had was long division in Z_2.
> (Actually Z_2[x] since we deal with polynomials.)
> 
> Then I started from first principles of CRC, polydivision,
> etc, etc. -- similarly to how Williams proceeds in his
> paper, but my treatment was purely algebraic.
> 
> The same applies to anyone looking at a description of an
> algorithm. (An ``algorithm'' has a precise definition in
> Computer Science.)
> 
> In its current form the description of the algorithm to
> compute the CRC in the iSCSI draft is not consistent, just
> because there is an unspoken assumption that a SMD circuit
> will be used. We cannot afford to do this in a definition
> document, unless we refer explicitly to it. We cannot even
> assume that a circuit will be used...
> 
> Please also note that the Ethernet spec CRC algorithm, is
> an optimized version of a basic
> prefix-postfix-initialize-the-
> CRC-register-to-some-constant algoritm. BUT as SMD it
> operates on NON-AUGMENTED messages. FOR THAT REASON you
> cannot say that we have to multiply M(x) by x^32!!!
> 
> I.e. SMD algoritms like the one in the Ethernet spec,
> operate on non-augmented messages, while simple Division
> (D) algorithms operate on augmented messages.
> 
> Any D can be optimized to SMD, but the constant has to be
> changed. Also, prefixing a message is equivalent to loading
> the CRC register with that prefix (WLG), but this is not so
> for SMD. (elaborated below)
> 
> Further more for any SMD there is an equivalent D,
> including for the Ethernet spec SMD; and for any D there is
> an equivalent SMD.
> 
> > If that is your interpretation, then we absolutely MUST
> > fix the spec,
> > I'm quite sure that the intent of the spec is as I wrote
> > it, i.e.,
> > Ethernet except for the generator.
> 
> Probably it is. But lets not hasten here.
> We can further generalize the explanation of the algorithm.
> 
> > > If this is changed, then the message in its form:
> > >   M'(x) = x^32 M(x) + x^(32+n) I(x)
> > >
> > > yields to better optimizations as Vince and I have
> > shown.
> > > (see his circuits and worksheet4.pdf, which I posted
> > > yesterday)
> > >
> > > I.e. the message is augmented (mult by x^32, aka
> > postfixed)
> > > and prefixed by 32 1's (aka CRC=32 1's).
> >
> > But that is NOT what the spec currently says.  What you
> > describe may
> > be a fine CRC but it is not the one that's in the spec.
> > Initializing
> > the CRC register to all 1 is not the same as prefixing 32
> > 1 bits onto
> > the message.
> 
> It is, in a simple division, e.g. in D. This is clearly and
> simply explained in the Williams paper. It is an equivalent
> to a long division.
> 
> Now, in D, if I initialize the CRC to all 1's and then do
> division of M(x) by G(x), so that I catch 0's at the
> beginning of the message,
> 
> (which is equivalent to prefixing the message by 1's of the
> number of the width of the CRC, and then do just simple
> division,(CRC=0), since after so many clicks the CRC will
> be loaded with the prefixing bits, and also 0/G(x) = 0)
> 
> then I can find a constant which I can XOR to the first 32
> bits of the message and then perform the division, still in
> D, with the same effect. In this particular case that
> constant is the magic constant. (We are one step closer to
> SMD...)
> 
> (Now we jump to SMD, by means of worksheet4.pdf, Prefixing
> part.)
> 
> Now, in the Ethernet CRC spec, that constant is 32 1's, and
> XORing 32 1's with the 32 MSb of the message is equivalent
> to complementing them.
> 
> BUT the Ethernet spec uses SMD, not D, so I claim that
> there is an equivalent D, which for a suitable initial CRC
> (also equivalent to prefixing the message with it) value
> will yield IDENTICAL results as Ethernet SMD.
> 
> Now using a bit of algebra similar to worksheet4.pdf which
> I posted a couple of days ago and numerical methods
> (solving a linear system of 33 unknowns) I have found such
> a constant:
> 0x2a26f826 which in simple division, D, will yield results
> identical to SMD of Ethernet.
> 
> So, here is an abstractization of the Ethernet CRC SMD,
> explained in a simple, simple, simple division only way:
> 
> TX:
> 1. Mutliply the message, M(x), by x^32.
> 2. Prefix the result of 1. with 0x2a26f826.
> 3. Find the remainder of the result of 2.
> 4. Complement that remainder and add it to the
>    result of 1.
> 5. Send the result of 4. to the recipient.
> 
> RX: (same as steps 1-3 in TX)
> 1. Mutliply the message by x^32.
> 2. Prefix the result of 1. with 0x2a26f826.
> 3. Find the remainder of the result of 2.
> 
> The result of 3 should be 0x1c2d19ed (the magic constant).
> 
> Of course I've ommitted the mirroring of bytes for clarity
> and brevity. It can be mentioned on the side, e.g. How to
> build the message: mirror the bytes == to swapping the bits
> inside the bytes, ....
> 
> Also note that step 4 in TX, adding means exactly that,
> since we already mult. by x^32, so the remainder will
> nicely fit in the last 32 0 bits.
> 
> Also note that step 2, can be made clearer:
> let C(x), be the polynomial representation of 0x2a26f826.
> Let n = deg G(x), k-1 = deg M(x) (there are k bits), then
> step 2 is:
> 
> 2. Add x^n x^k C(x) to the message M(x).
> 
> Or we can swap step 1 and 2:
> 
> 1. Add x^k C(x) to M(x).
> 2. Multiply the result of 1. by x^n.
> 
> I hope this makes things a bit clearer.
> 
> So from this D specification above, I can derive SMD
> exaclty as it is in the Ethernet spec. I'll include this
> derivation in the paper -- it will be pure math, but in
> english it goes like this: First we notice that after 32
> clicks the CRC register will contain only 32 1's XOR-ed
> with the message, then we see that we can just load the crc
> with ones and then kick one byte off the left xor it with
> the next message bit...
> 
> The above equivalence I've tested empirically.
> 
> > What does "better optimizations" mean?
> 
> See above.
> 
> > > In an SMD, one would have to set the CRC to the magic
> > > constant and then proceed as the algorithm indicates,
> > > (this is identical to what you'd find in Ethernet, ...
> >
> > No it isn't.  The Ethernet spec appendix C, and, more
> > importantly, the
> > formal definition of the CRC in the body of the spec,
> > makes it quite
> > clear that it isn't.  I don't understand how you arrive
> > at any other
> > conclusion.
> 
> I didn't mean identical as in the constant. I meant
> identical in a way of equivalence of algorithms, that one
> can be derived from the other, etc. See above. Or simpler
> answer: Math.
> 
> -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

-- 
Mark A. Bakke
Cisco Systems
[email-masked]
763.398.1054

---

From: "THALER,PAT (A-Roseville,ex1)" <[email-masked]>
Date: Tue, 18 Dec 2001 15:21:21 -0700

Paul,

I like your text. I would include the note about Ethernet. My preference
would be to not include the implementation notes though I don't find
anything terribly objectionable in them. It would be nice to include a
reference to additional informative information on CRC generation
particularly since some references out in the world seem to be misleading. 

Regards,
Pat

-----Original Message-----
From: Paul Koning [mailto:[email-masked]]
Sent: Friday, December 14, 2001 12:18 PM
To: [email-masked]
Cc: [email-masked]
Subject: RE: effect of initializing CRC reg to 1's depends on
implementati on? iSCSI

I guess the problem with the spec is that it is a confusing mix of
pieces of the mathematical definition and pieces of description from a
specific (and unstated) implementation.

Ok, so let me propose specific replacement text.

This is for Appendix D, starting at the top of page 193 in the -09 rev
of the spec.

----------------
The generator polynomial for the CRC is x^32 + x^28 + x^27 + x^26 +
x^25 + x^23 + x^22 + x^20 + x^19 + x^18 +x^14 + x+13 + x+11 + x^10 +
x^9 + x^8 +x^6 + 1.

The CRC value for a PDU is defined mathematically as follows:

1. The first 32 bits of the PDU are complemented.

2. The N bits of the PDU are then considered to be coefficients of a
polynomial M(x) of degree N-1.  Bit 0 of byte 0, i.e., the low order
bit of the high order byte of the first word of the PDU, corresponds
to the X^(N-1) term of this polynomial, and the high order bit of the
last byte of the PDU corresponds to the x^0 term.  Note that any pad
bytes for the PDU are included.

3. M(x) is multiplied by x^32, and divided by G(x), producing a
remainder R(x) of degree < 32.

4. The coefficients of R(x) are considered to be a 32-bit sequence.

5. This bit sequence is complemented and the result is the CRC.

The CRC is trannsmitted with the high order bit (corresponding to the
x^31 term of R(x)) in the low order bit of the first byte transmitted,
and the low order bit (corresponding to the x^0 term of R(x)) in the
high order bit of the fourth byte transmitted.
----------------

This text is inspired by the text in the Ethernet spec, with some
wording changes needed for the iSCSI context.  I believe this is a
precise definition of what is needed.

For additional information, more text could be included.  For example:

----------------
The above algorithm is exactly that used in the Ethernet/802.3 LAN,
with the exception of the choice of generator polynomial.
----------------

And perhaps a note on implementation:

----------------
The above algorithm may be efficiently implemented in a variety of
ways, such as linear feedback shift registers, table lookup, etc.
----------------

Finally, we could capture the "magic constant" receive algorithm as
follows:

----------------
Implementation of the CRC32C checking for PDU reception can be done in
several ways.  

One approach is to calculate the CRC over the PDU not including the
CRC field, and compare that with the received CRC.  If the two values
are equal, the digest is considered valid.

Another approach is to perform the above algorithm over the entire
received PDU, including the CRC field.  With that approach, a valid
digest results in R(x) having the value x^28 + x^27 + x^26 + x^21 +
x^19 + x^18 +x^16 + x^12 + x^11 + x^8 + x^7 + x^6 + x^5 + x^3 + x^2 + 1,
i.e., the value of the 32-bit sequence obtained in step 4 is
0x1c2d19ed. 
----------------

Following Pat Thaler's comments, I am not proposing any more text on
implementation approaches.  Both the table based approaches and the
LFSR approach can be covered by references to literature, though
admittedly some of the references may not be all that easy to
acquire. 

So my proposal is to replace the text on page 193 up to the
"Proprietary algorithms MAY also..." with the four pieces given
above.  If people don't like the later pieces, then I'll fall back to
proposing just the first chunk of text (the formal definition of the
CRC) as replacement for the current text.

	 paul

---

From: "Mukund, Shridhar" <[email-masked]>
Date: Tue, 18 Dec 2001 16:38:23 -0800

Paul,

I largely agree with your message of last Friday. I prefer we 
stay away from implementation notes or analysis. Reference to 
additional information is perfectly fine.

-Shridhar Mukund

Paul,

Regards,
Pat
 Mukund,> Folks,

 Mukund,> This thread seems to be going on and on. I think that Pat
 Mukund,> has hit the nail on the head. Ethernet Spec does describe
 Mukund,> CRC computation "precisely". Additionally, if we spec the
 Mukund,> order of bits in the iSCSI message format, we are done.

That's exactly what I did in my message of last Friday.  Do you agree,
or do you have comments on how to make it do the job?

   paul

---

From: "THALER,PAT (A-Roseville,ex1)" <[email-masked]>
Date: Wed, 19 Dec 2001 15:55:48 -0700

Luben,

Your statement "That is, it has to have the correct CRC _after_ _each_ _bit_
has arrived." is incorrect for Ethernet. If the frame was not an integral
number of bytes, then the excess bits (the ones that are not part of a
complete byte) are not to be used in the CRC calculation. The IEEE 802.3
spec (and the
earlier DIX Ethernet spec) requires that the CRC checking algorithm only
process whole bytes. Therefore, a good CRC algorithm for Ethernet would only
process bits once a whole byte worth of bits had arrived.

This really isn't relevant to the iSCSI reflector so I suggest we take this
offline if you want to discuss it further. 

IEEE 802.3 is about 1500 pages in the 2000 edition so if I am making a point
with respect to it, I think it is polite to provide a reference to where
that information can be found so that people can read it for themselves.
Certainly no offense was intended by making a specific citation.

Regards,
Pat Thaler

-----Original Message-----
From: Luben Tuikov [mailto:[email-masked]]
Sent: Tuesday, December 18, 2001 2:57 PM
To: [email-masked]; [email-masked]; [email-masked]
Cc: [email-masked]
Subject: RE: effect of initializing CRC reg to 1's depends on
implementati on? iSCSI

--- [email-masked] wrote:
>
> method. However, that is irrelavent to what should go
> into the standard.

I never posted a message of the sort: 
``Here guys put this into the draft: ...''. And I don't
want to post one.

All I've been doing is mathematical analysis of the
algorithm(s). And all I've been looking for is an
unambiguious definition.

> 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."

Read the sentence again please: indefinite article ``a''.
This means ``any'' CRC algorithm.

No there is no error.

> 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
... [cut]

Don't you think I can read this myself?

Then again: indefinite article ``a''.

-l

=====
--

---

From: "Julian Satran" <[email-masked]>
Date: Thu, 20 Dec 2001 03:09:24 +0200

Make a note about when a CRC has to be valid.

Julo

                    pat_thaler                                                                        
                    Sent by:             To:     [email-masked],                                   
                    owner-ips@ece.        [email-masked], [email-masked],                      
                    cmu.edu               [email-masked]                                   
                                         cc:     [email-masked]                                      
                                         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:[email-masked]]
Sent: Monday, December 17, 2001 8:04 PM
To: THALER,PAT (A-Roseville,ex1); Paul Koning; VICENTE V CAVANNA
Cc: [email-masked]
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

=====
--