SORT BY:

LIST ORDER
THREAD
AUTHOR
SUBJECT


SEARCH

IPS HOME


    [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? 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: Tue Dec 18 01:17:41 2001
8123 messages in chronological order