SORT BY:

LIST ORDER
THREAD
AUTHOR
SUBJECT


SEARCH

IPS HOME


    [Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

    RE: CRC32C code -- please check



    Luben,
    
    I think I see the problem:
    
    Luben> Ok, so the receiver got M''(x) assuming no noise.
    
     Luben> M''(x) = Q(x)*G(x) + I(x).  (this is (3))
    
     Luben> Now we work the algorithm again: ..., find the remainder:
     Luben> Clearly, from (3) the remainder of M''(x) modulo G(x) is I(x).
                             ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
                              this is not true.
    
     Luben> Then we complement the value as per the draft:
    
     Luben> ~I(x) = 0.
    
     Luben> And we end up with remainder 0.
    
    Remember I(x) is the polynomial of order 31 with all the coefficients equal
    to 1. G(x) is a polynomial of order 31 with some of its coefficients equal
    to 0. Therefore, G(x) goes into I(x) once.
    
    The remainder of M''(x) modulo G(x) is I(x) - G(x).
    
    So that should explain the "magic number."
    
    Regards,
    Pat
    
    
    -----Original Message-----
    From: Paul Koning [mailto:ni1d@arrl.net]
    Sent: Monday, November 26, 2001 7:12 AM
    To: ltuikov@yahoo.com
    Cc: ips@ece.cmu.edu
    Subject: Re: CRC32C code -- please check
    
    
    >>>>> "Luben" == Luben Tuikov <ltuikov@yahoo.com> writes:
    
     Luben> Here is some C code at the end, the draft quoted and my notes
     Luben> alongside it. ...
    
     Luben> So, here we get M'(x) = x^32 * M(x). Getting R(x) is trivial.
     Luben> So we have:
    
     Luben> M'(x) = Q(x)*G(x) + R(x) = Q(x)*G(x) - R(x), (1)
    
     Luben> since plus is same as minus in modulo 2 arithmetic.
    
     >> - the bit sequence is complemented and the result is the
     Luben> CRC
    
     Luben> Now, from boolean logic we know that b XOR 1 = ~b, then,
    
     Luben> ~R(x) = R(x) XOR I(x) = R(x) + I(x) (2)
    
     Luben> where I(x) is a polynomial of the same degree as R(x) and
     Luben> whose coefficients are all equal to 1. So, to get M''(x) which
     Luben> we send we have:
    
     Luben> M''(x) = M'(x) + ~R(x) (draft) = Q(x)*G(x) - R(x) + R(x) +
     Luben> I(x) (using (1) and (2)) = Q(x)*G(x) + I(x).
    
     Luben> or succinctly,
    
     Luben> M''(x) = Q(x)*G(x) + I(x), (3)
    
     Luben> and this is the message which we send. 
    
    Not quite.  Your M' is taken from M by complementing the first 32
    bits and appending 32 zeroes.  That's what you feed into the CRC
    calculation -- but what you transmit has the original (uncomplemented)
    first 32 bits.
    
     Luben> On the other end we
     Luben> get M''(x), assuming there was no noise, and all
     Luben> link/TCP/Ethernet transformations are transparent for the
     Luben> sender and the receiver. ...
    
     Luben> Ok, so the receiver got M''(x) assuming no noise.
    
     Luben> M''(x) = Q(x)*G(x) + I(x).  (this is (3))
    
     Luben> Now we work the algorithm again: ..., find the remainder:
     Luben> Clearly, from (3) the remainder of M''(x) modulo G(x) is I(x).
    
     Luben> Then we complement the value as per the draft:
    
     Luben> ~I(x) = 0.
    
     Luben> And we end up with remainder 0.
    
    I think I see the problem.
    
    In CRC generation, you process the message (M).
    
    In CRC checking, there are two approaches:
    
    1. You process M and compare the 4 bytes that follow (the CRC) with
    what you computed.  This is fine, if you know ahead of time where M
    ends. 
    
    2. If you don't know where M ends ahead of time (as in the Ethernet
    MAC layer) or you simply prefer to process the whole received message,
    you run everything including the received CRC through the CRC
    algorithm.  Note that the string processed in this case is 4 bytes
    longer than in case (1), because it includes the CRC.  That's what you
    described, but I believe you missed a step.
    
    The CRC algorithm says: take the message (M'' in this case) and
    multiply by x^32, then divide by the CRC polynomial.  You missed the
    multiply.   In other words, you should have:
    
    	    (M''(x)*x^32) mod G(x)
    rather than simply
                M''(x) mod G(x)
    
    and that is *not* zero.  I haven't done the math but I expect that you
    will find the answer to be the non-zero constant that appears in the
    spec. 
    
    Ethernet works the same way, except for a change in the polynomial.
    You suggested earlier that Ethernet is using a non-standard algorithm
    because it comes up with a non-zero remainder at the receive end.
    That is not the case.
    
    You should not need any fudge factors to make the answer come out
    according to the spec if you get the algorithm right...
    
    	  paul
    


Home

Last updated: Wed Nov 28 23:17:46 2001
7934 messages in chronological order