SORT BY:

LIST ORDER
THREAD
AUTHOR
SUBJECT


SEARCH

IPS HOME


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

    RE: I-D ACTION:draft-cavanna-iscsi-crc-vs-cksum-00.txt



    Julian,
    
    Good summary. One correction. "codes shorter than m" is shorter than m
    values not m bits and m is about 64 K. Therefore, it is shorter than about
    63 kbytes for Adler and shorter than 127 kbytes for Fletcher. 
    
    I'm thinking about your question about Pud but it will take me a bit to come
    up with an answer. For the three bit error case, I think the formulas used
    for CRC bit errors will be approximately correct. For the burst errors and
    the errors where two (Fletcher only) or three non-contiguous bytes are
    corrupted, I'm not sure what to use for the probability that a byte gets
    corrupted.
    
    Regards,
    Pat
    
    -----Original Message-----
    From: julian_satran@il.ibm.com [mailto:julian_satran@il.ibm.com]
    
    Pat,
    
    Thanks. I am not going to check every line for awhile and I assume it is
    correct.
    For the benefit of the list the summary of the statement is that:
    
    -the burst protection is for 16 bit (I recall the text saying 32)
    -the numbers to be used for low noise symmetric channel protection are:
                   - dmin= 3 for codes shorter than m (approx 8kbytes)
                   - dmin= 2 for codes longer than m
    
    Do you have a formula to evaluate Pud for low noise channels with BER = e?
    Any formula to evaluate the conditional probability of an undetected error
    on bursts of 17, 18, 19 bits?
    
    Is there any reason to believe hat we can approximate them to ones used for
    CRC?
    
    I would like to have all the codes readily comparable.
    
    Regards,
    Julo
    
    "THALER,PAT (A-Roseville,ex1)" <pat_thaler@agilent.com> on 06/03/2001
    19:24:13
    
    Please respond to "THALER,PAT (A-Roseville,ex1)" <pat_thaler@agilent.com>
    
    To:   Julian Satran/Haifa/IBM@IBMIL, "THALER,PAT (A-Roseville,ex1)"
          <pat_thaler@agilent.com>
    cc:   ips@ece.cmu.edu, Dafna_Sheinwald@il.ibm.com
    Subject:  RE: I-D ACTION:draft-cavanna-iscsi-crc-vs-cksum-00.txt
    
    
    
    
    Julian,
    
    It is relatively easy to investigate the Hamming distance and burst
    detection of Adler32 and Fletcher32 using mathematics. In the argument
    below, I will use "value" to identify the quantities that get summed since
    Adler sums bytes and Fletcher32 sums 16-bits.
    
    Both Adler and Fletcher calculate for each value:
    
     S1 = (S1 + value) mod m
     S2 = (S2 + S1) mod m
    
    where m is 65521 for Adler and 65535 for Fletcher.
    
    Which means that for an n value string of values V1 to Vn:
     S1 = (V1 + V2 + ... + Vn (+ 1 for Adler)) mod m
     S2 = (n * V1 + (n-1) * V2 + ... + Vn (+ n for Adler)) mod m
    
    A two bit error can only change two values. For a two bit error to be
    undetectable the two changed values must produce no change to S1 and S2.
    
    Let
     x be the change to the first errored value
     y be the change to the second errored value
     k be the separation between the first and second errored values.
    
    Then for an undetectable error:
    
     delta S1 = (x + y) mod m = 0
     delta S2 = ((k + 1) * x + y) mod m = 0
              = (k * x + x + y) mod m =0
              = (k * x) mod m = 0          because (x + y) mod m = 0
    
    Therefore, for an undetectable 2 bit error, k * x must be a multiple of m.
    
    For Adler, m is prime and the maximum value of x is 255 so the only way to
    satisfy the condition is for k to equal 65521. Then x can be any value so
    it
    could be a one bit error such as changing the lsb of the first value from 0
    to 1. y would then need to be the inverse changing the lsb of the second
    value from 1 to 0.
    
    For Fletcher, m is factorable to 3, 5, 17, 257. For x to provide one or
    more
    of those factors, it would have to have more than a 1 bit change and y
    would
    have to have the inverse of that change which would mean an error of at
    least 4 bits. The only way to get a two bit undetectable error is for k to
    equal 65535.
    
    So, Fletcher and Adler do have 2-bit undetectable errors if the messages
    are
    longer than the modulus.
    
    What about burst protection? For Fletcher, we know that a change of a value
    from all 0's to all 1's produces an an undetectable error so we know that
    burst protection is less than 16. k = 1 for a burst spread across two
    consecutive values. Therefore, the only way for a burst spread across two
    consecutive values to produce an undetectable error is for x to equal
    65535.
    A burst shorter than 16 can't do it.
    
    For Adler, corrupting two consecutive bytes can't produce an undetectable
    error because that would be the case above where k equals 1. There is no
    way
    for a burst across two consectutive values to be undetectable in Adler
    since
    x is less than the modulus.
    
    For a burst across three values:
    
    let x equal the error in the first value
        y equal the error in the second value
        z equal the error in the third value.
    
    For the burst to be undetectable
    
     Delta S1 = (x + y + z) mod m = 0
     Delta S2 = (3x + 2y + z) mod m = 0
    
    Since the maximum values of x, y, and z are 255 and m is more than 6 times
    that, the sums above will always be less than m and we can drop the mod m.
    
     Delta S2 = (3x + 2y + z) = 2x + y + (x + y + z) = 0
              = 2x + y = 0                    because x + y + z = 0
    
            y = - 2x
    
     Delta S1 = x + y + z = 0
              = x - 2x + z = 0
              = -x + z
            z = x
    
    So an undetectable error is created when in three consecutive values the
    errors are
        x
      -2x
        x
    
    This could for instance be errors of 1, -2, and 1. Since the error to the
    first and third values are the same, the error must span at least 2 * the
    length of the value + 1. So for Adler, it must be a 17 bit burst at least.
    
    Also, note that this can be created by a 3 bit error and is equally
    applicable to Adler and Fletcher.
    
    Therefore, for messages shorter than the modulus + 1, the Hamming distance
    of Adler32 and Fletcher 32 is 3 and, for messages longer than that, the
    Hamming distance is 2.
    
    Regards,
    Pat Thaler
    
    
    
    
    
    -----Original Message-----
    From: julian_satran@il.ibm.com [mailto:julian_satran@il.ibm.com]
    
    Pat,
    
    I did not run a check. That is very expensive.
    With CRCs there are methods that enable you to run a check on the
    complement code
    (that has only 2**32 different patterns for any block length) and derive
    from there the distances (Fujiwara has done this in 1989 for the IEEE
    CRC-32 and about some more recent experiments I'll get back to the list).
    
    And that is the trouble with this whole line of argument.
    There are no numbers to prove Adler32 or Fletcher32 and there are plenty
    for CRCs.
    
    The big question is then is there anybody out there that wants to build a
    modern bridge based only on its beauty?
    
    Regards,
    Julo
    
    
    pat_thaler@agilent.com on 05/03/2001 23:27:49
    
    Please respond to pat_thaler@agilent.com
    
    To:   Julian Satran/Haifa/IBM@IBMIL
    cc:
    Subject:  RE: I-D ACTION:draft-cavanna-iscsi-crc-vs-cksum-00.txt
    
    
    
    
    Julian,
    
    I know that Hamming distance gets down to 2 for errors that are separated
    by
    the modulus (or a multiple of it). Is there another case?
    
    Pat
    
    > - Adler and Fletcher are weak and there is no theory behind your
    > distribution statements, nor any simulation results as far as I know.  We
    > found that on very simple sequences the Hamming distance gets
    > down to 2 (or
    > lower) and the burst protection is probably not better than 16 bit.
    There
    > is even a simple formula for what sequences will get you false codes (see
    > bellow for a reference)
    >
    
    
    
    
    


Home

Last updated: Tue Sep 04 01:05:26 2001
6315 messages in chronological order