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

From: "THALER,PAT (A-Roseville,ex1)" <[email-masked]>
Date: Tue, 6 Mar 2001 12:24:13 -0500

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: [email-masked] [mailto:[email-masked]]

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

[email-masked] on 05/03/2001 23:27:49

Please respond to [email-masked]

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)
>

---

From: [email-masked]
Date: Tue, 6 Mar 2001 20:39:57 +0200

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)" <[email-masked]> on 06/03/2001
19:24:13

Please respond to "THALER,PAT (A-Roseville,ex1)" <[email-masked]>

To:   Julian Satran/Haifa/IBM@IBMIL, "THALER,PAT (A-Roseville,ex1)"
      <[email-masked]>
cc:   [email-masked], [email-masked]
Subject:  RE: I-D ACTION:draft-cavanna-iscsi-crc-vs-cksum-00.txt

Julian,

 S1 = (S1 + value) mod m
 S2 = (S2 + S1) mod m

Let

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.

consecutive values to produce an undetectable error is for x to equal
65535.

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.

        y = - 2x

 Delta S1 = x + y + z = 0
          = x - 2x + z = 0
          = -x + z
        z = x

Regards,
Pat Thaler

-----Original Message-----

Pat,

Regards,
Julo

Julian,

Pat

There

---

From: [email-masked]
Date: Tue, 6 Mar 2001 20:39:57 +0200

Pat,

Regards,
Julo

Julian,

 S1 = (S1 + value) mod m
 S2 = (S2 + S1) mod m

Let

        y = - 2x

 Delta S1 = x + y + z = 0
          = x - 2x + z = 0
          = -x + z
        z = x

Regards,
Pat Thaler

-----Original Message-----

Pat,

Regards,
Julo

Julian,

Pat

There

---

From: [email-masked]
Date: Tue, 6 Mar 2001 17:47:03 -0700

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

Pat,

Regards,
Julo

Julian,

 S1 = (S1 + value) mod m
 S2 = (S2 + S1) mod m

Let

        y = - 2x

 Delta S1 = x + y + z = 0
          = x - 2x + z = 0
          = -x + z
        z = x

Regards,
Pat Thaler

-----Original Message-----

Pat,

Regards,
Julo

Julian,

Pat

There

---

From: [email-masked]
Date: Wed, 7 Mar 2001 11:17:05 -0700

Hi Julian,

I will attempt to answer your questions about the probability of undetected
error since your question strikes to the heart of what I was trying to point
out in my I-D on CRCs vs. Checksums, i.e. where CRCs shine and where they do
are not as good as many people think.

For a link where random noise with Gaussian probability distribution and
White spectral density is the source of errors, it is easy to determine the
probability, Pu, of undetected error. This type of link is not only amenable
to analysis but is a good model for many well designed links.

For this type of link the BER (bit error ratio) is determined by the
probability that the noise amplitude will exceed the signal amplitude and
can be easily shown to be BER(z) = 1/2 erfc(z/sqroot(2)) where erfc is the
complementary error function and z is the SNR (signal to noise ratio), that
is, the signal amplitude as a multiple of the standard deviation [note1] of
the noise. For example, at a SNR of 7, the BER is 10^(-12). With this noise
mechanism and small BER,  patterns with a small number of erroneous bits are
far more probable than those with large numbers or errors and the
probability of getting a certain number of errors, x,  decreases
monotonically and rapidly with increasing x. I have made a mathcad worksheet
showing this dramatically in graphical form. Ask me if you want it.

The number of errors in a pattern is a random variable with binomial
distribution. The probability of x errors in n bits, where the probability
of each bit being in error is BER, may be gotten from the binomial
distribution with parameters n and p. The number of independent trials, n,
is the number of bits; the probability of success in each trial, p, is the
BER.

The binomial distribution allows us to calculate the probability of a
pattern with a certain number of errors and we can use it to find a bound
for the probability of x errors at a given BER [note 2].

Let's take an ethernet-like link using some kind of group encoding such as
8B:10B. It is trivial to design a CRC polynomial that will catch all two bit
errors. Two or less bits in error result in no more than 2 bursts of size 8
(due to 8B:10B encoding). If the CRC is designed to catch all such double
bursts (easy to do and the CRC-32 used in ethernet does) all such errors are
caught. An undetected error thus occurs only if there are 3 or more bits in
error on the link within a frame - this is conservative since most such
errors will also be caught but I will assume none are. I am also neglecting
the fact that it is easy to design a CRC to catch all 3 bit errors. I don't
want to take advantage of it because 3 bit errors may (again due to group
encoding) result in 3 bursts which are not so easy to detect.

With this error mechanism large bursts happen because of the group encoding.
Without group encoding it would be extremely unlikely to get a burst of size
3 or larger. 

The probability of 3 or more bits is approximately equal to the probability
of exactly 3 bits since as long as p << 0.5 the probability of a pattern
having x errors decreases rapidly as x increases.

For a BER of 10^(-12) the prob of 3 or more  errors in 1500*8 bits (ethernet
frame) is approximately the probability of exactly 3 errors in 1500*8 bits
which is 5.62 x 10^(-25). At 10 gig this represents a mean time between
undetected errors of 5.6 x 10^6 years. This assumes we catch all 2 bit
errors. If we could only catch single bit errors the mean time between
undetected errors would be 10 days! What a difference a bit makes!! Also the
probability of exactly 4 errors is 2.1 x10^(-33). Again, what a difference a
bit makes! I have a mathcad spreadsheet where I have done this analysis for
10 gig ethernet. Let me know if you are interested in a copy.

This is why CRC is so nice for a link with this error source. We can claim
practically complete protection. Ther are no holes.

For cases, such as iSCSI protection environment, where the BER is not
determined by the SNR then we may not be able to claim that a small number
of erroneous bits are far more probable than a large number of them and the
analysis is not as simple  and in such cases CRCs are not necessarily better
than checksums - it depends on how probable the patterns of errors that are
undetected are.

Vince

notes:

[1] strictly speaking I should have said rms value instead of standard
deviation but for a random process for which the time statistics are the
same as the ensemble statistics (an ergodic process) the two are equivalent.

[2] Binomial distribution wiht parameters n and p: P(x,n,p) =
(n!/(x!*(n-x))*(p^x(1-p)^(n-x))

|-----Original Message-----
|From: THALER,PAT (A-Roseville,ex1) 
|Sent: Tuesday, March 06, 2001 4:47 PM
|To: [email-masked]; [email-masked]
|Cc: THALER,PAT (A-Roseville,ex1); [email-masked];
[email-masked]; CAVANNA, VICENTE
|Subject: 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: [email-masked] [mailto:[email-masked]]
|
|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)" <[email-masked]> on 06/03/2001
|19:24:13
|
|Please respond to "THALER,PAT (A-Roseville,ex1)" 
|<[email-masked]>
|
|To:   Julian Satran/Haifa/IBM@IBMIL, "THALER,PAT (A-Roseville,ex1)"
|      <[email-masked]>
|cc:   [email-masked], [email-masked]
|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: [email-masked] [mailto:[email-masked]]
|
|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
|
|
[email-masked] on 05/03/2001 23:27:49
|
|Please respond to [email-masked]
|
|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)
|>
|
|
|
|
|

---

From: [email-masked]
Date: Thu, 8 Mar 2001 03:38:44 +0200

Vince,

We have now a good handle and plethora of references for CRC behavior in
low noise symmetric channels (the ones you consider) and on bursts.

To complete the comparison we will need formulas for the checksums you
propose (Adler and Fletcher 32).

We will corroborate it with information from other sources wherever
available.

Regards,
Julo

[email-masked] on 07/03/2001 20:17:05

Please respond to [email-masked]

To:   Julian Satran/Haifa/IBM@IBMIL
cc:   [email-masked], [email-masked], [email-masked],
      [email-masked]
Subject:  RE: I-D ACTION:draft-cavanna-iscsi-crc-vs-cksum-00.txt

Hi Julian,

I will attempt to answer your questions about the probability of undetected
error since your question strikes to the heart of what I was trying to
point
out in my I-D on CRCs vs. Checksums, i.e. where CRCs shine and where they
do
are not as good as many people think.

For a link where random noise with Gaussian probability distribution and
White spectral density is the source of errors, it is easy to determine the
probability, Pu, of undetected error. This type of link is not only
amenable
to analysis but is a good model for many well designed links.

mechanism and small BER,  patterns with a small number of erroneous bits
monotonically and rapidly with increasing x. I have made a mathcad
worksheet

8B:10B. It is trivial to design a CRC polynomial that will catch all two
bit
bursts (easy to do and the CRC-32 used in ethernet does) all such errors

With this error mechanism large bursts happen because of the group
encoding.
Without group encoding it would be extremely unlikely to get a burst of
size
3 or larger.

For a BER of 10^(-12) the prob of 3 or more  errors in 1500*8 bits
(ethernet
frame) is approximately the probability of exactly 3 errors in 1500*8 bits
which is 5.62 x 10^(-25). At 10 gig this represents a mean time between
undetected errors of 5.6 x 10^6 years. This assumes we catch all 2 bit
errors. If we could only catch single bit errors the mean time between
undetected errors would be 10 days! What a difference a bit makes!! Also
the
probability of exactly 4 errors is 2.1 x10^(-33). Again, what a difference
a
bit makes! I have a mathcad spreadsheet where I have done this analysis for
10 gig ethernet. Let me know if you are interested in a copy.

analysis is not as simple  and in such cases CRCs are not necessarily
better

Vince

notes:

[1] strictly speaking I should have said rms value instead of standard
deviation but for a random process for which the time statistics are the
same as the ensemble statistics (an ergodic process) the two are
equivalent.

---

From: [email-masked]
Date: Mon, 12 Mar 2001 19:43:51 -0700

Julian asked:

"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 that we can approximate them to ones used for
CRC?"

Abstract:

The following will show that the formula used in the case of CRC for Pud
does not apply to checksums. Many data sets with small differences produce
the same checksum while few such data sets produce the same CRC. Therefore,
Pud for checksum is significantly worse than that for CRC. For independent
bit errors, Pud is approximately 12,000 times worse for Fletcher32 than for
CRC and 22,000 times worse for Adler32 than for CRC. 

Note:
While Fletcher32 is better than Adler32 for the error case analyzed here,
Fletcher32 has more susceptibility to two byte errors that Adler32 does not
have. Overall, Fletcher32 is not necessarily a better choice.

The grungy details:

The formula for Pud for CRC in a low noise channel is:

 Pud = Pcrc * Cn,x * Pxerrors

Where:
 Pcrc is the probability that the received CRC matches the errored message
 Cn,x is the number of combinations of 3 errors in an n bit message
 Pxerrors is the probability of getting a particular combination of 3 errors
 Pbe is the probability of a bit error.

Inserting the values for 3 bit errors in a 1000 byte message where Pbe << 1:

 Pud = 2^-32 * C8000,3 * Pbe^3
     = 2^-32 * 85e9 * Pbe^3
     = 20 * Pbe^3

Note that this equation is assuming that the CRC in question does not detect
all 3 bit errors. If the CRC detects all 3 bit errors as many do, the Pud
would be 0. Also, actually equals Pxerrors = (Pbe ^ errored_bits) * ((1 -
Pbe) ^ unerrored_bits, but the latter is very close to 1 for low noise
channels.

Approximately 20 positions of 3 bit errors cause undetectable errors in a
1000 byte message with the CRC.

How many 3 bit errors cause undetectable errors for checksums? In the
attached analysis of checksum Hamming distance and burst error detection, I
showed that an undetectable error for both checksums is formed by sequence
of three errored values with errors: x, -2x, and x. The same error pattern
in three values with equal spacing between them will cause an undetectable
error (see Undetectable 3 bit errors in non-consecutive values below). 

For Adler32: 
A value is one byte long.
For x = 1, 2, 4, 8, 16, 32 or 64: The three errors can be caused by a 1 bit
change each.

There are 998 sets of 3 consecutive bytes in a 1000 byte frame.
There are 996 sets of 3 bytes spaced with 1 bytes between them.
There are 994 sets of 3 bytes spaced with 2 bytes between them.
....
There are 2 sets of 3 bytes spaced with 498 bytes between them.

Therefore, the undetectable errors analyzed below yield (998 + 2) * 49 / 2
sets of bytes that can have one of 7 sets of 3 bits change for an
undetectable error in a 1000 byte frame. Of the 8 ways those three bits can
be changed, 2 of them produce an undetectable error. 

If the pattern discussed here is the only one that produces 3 bit errors,
then Pud for 3 bit errors in a 1000 byte message with Adler32 would be:

  Pud = Pcsum * Cerror * P3errors

where 
 Pcsum equals the probability that the 3 bit error results in a correct
checksum which is 0.25 for the 3 bit errors.
 Cerror is the number of combinations of undetectable 3 bit errors.
 P3errors is the probability of getting a particular combination of 3
errors.
      
   Pud  = 0.25 * (998 + 2) * 499/2 * 7 * Pbe^3
        = 437 * 10^3 * Pbe^3

For Fletcher32:
A value is two bytes long.
For x = 1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024, 2048, 4096, 8192 or
16384: The three errors can be caused by a 1 bit change each. 

In a 1000 byte message, there are 500 values.
There are 498 sets of 3 consecutive values in a 1000 byte frame.
There are 496 sets of 3 values spaced with 1 values between them.
There are 494 sets of 3 values spaced with 2 values between them.
....
There are 2 sets of 3 values spaced with 248 values between them.

Therefore, the undetectable errors analyzed below yield (498 + 2) * 249/ 2
sets of bytes that can have one of 15 sets of 3 bits change for an
undetectable error in a 1000 byte frame. Of the 8 ways those three bits can
be changed, 2 of them produce an undetectable error. 

If the pattern discussed here is the only one that produces 3 bit errors,
then Pud for 3 bit errors in a 1000 byte message with Fletcher32 would be:

  Pud = 0.25 (498 + 2) * 249/2 * 15 * Pbe^3
      = 233 * 10^3 * Pbe^3

To recap:
CRC           Pud = 20 * Pbe^3
Adler32:      Pud = 437 * 10^3 * Pbe^3
Fletcher32:   Pud = 233 * 10^3 * Pbe^3
  
Regards,
Pat Thaler

------- Analysis of checksum Hamming distance and burst error detection
-----------

 S1 = (S1 + value) mod m
 S2 = (S2 + S1) mod m

Let

from all 0's to all 1's produces an undetectable error so we know that

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 consecutive values to be undetectable in Adler
since
x is less than the modulus.

        y = - 2x

 Delta S1 = x + y + z = 0
          = x - 2x + z = 0
          = -x + z
        z = x

Regards,
Pat Thaler

---------- Undetectable 3 bit errors in non-consecutive values
---------------

For undetectable errors in 3 values spaced with k1 from the first error to
second error and k2 values from the second error to the third:
 Delta S1 = (x + y + z) mod m = 0
 Delta S2 = ((k1 + k2 + 1)x + (k2 + 1)y + z) mod m = 0
          = ((k1 + k2)x + (k2)y +(x + y + z)) mod m = 0
          = ((k1 + k2)x + (k2)y) mod m = 0         because (x + y + z) mod m
= 0

  y = - x(k1 + k2)/k2

  z = -x - y = - x + x(k1 + k2)/k2
    = x (-k2 + k1 + k2)/k2 = x(k2/k1)

For k1 = k2, the result is the same as for 3 consecutive values. That is:
  y = -2x
  z = x

Therefore, if x is 1, 2, ... 64 (for Adler32) or 1, 2, ... 16384 (for
Fletcher32), 
then x, y, and z will be single bit errors.

---

From: [email-masked]
Date: Tue, 13 Mar 2001 08:37:09 +0200

Pat,

Thanks a lot for you patience and hard work.  I assumed that was the case
based on the experimental results on the effects of ATM splicing on CRC and
checksums published in 1998 that show how data bias affects checksums.

On another subject - can you comment on weighted checksums?

Thanks,
Julo

[email-masked] on 13/03/2001 04:43:51

To:   Julian Satran/Haifa/IBM@IBMIL, [email-masked]
cc:   [email-masked], [email-masked]
Subject:  RE: I-D ACTION:draft-cavanna-iscsi-crc-vs-cksum-00.txt

Julian asked:

Is there any reason to believe that we can approximate them to ones used
for
CRC?"

Abstract:

Note:

The grungy details:

Where:
 Pcrc is the probability that the received CRC matches the errored message
 Cn,x is the number of combinations of 3 errors in an n bit message
 Pxerrors is the probability of getting a particular combination of 3
errors
 Pbe is the probability of a bit error.

Inserting the values for 3 bit errors in a 1000 byte message where Pbe <<
1:

Note that this equation is assuming that the CRC in question does not
detect
all 3 bit errors. If the CRC detects all 3 bit errors as many do, the Pud
would be 0. Also, actually equals Pxerrors = (Pbe ^ errored_bits) * ((1 -
Pbe) ^ unerrored_bits, but the latter is very close to 1 for low noise
channels.

For Adler32:

where

For Fletcher32:

To recap:
CRC           Pud = 20 * Pbe^3

Regards,
Pat Thaler

 S1 = (S1 + value) mod m
 S2 = (S2 + S1) mod m

Let

        y = - 2x

 Delta S1 = x + y + z = 0
          = x - 2x + z = 0
          = -x + z
        z = x

Regards,
Pat Thaler

          = ((k1 + k2)x + (k2)y) mod m = 0         because (x + y + z) mod
m
= 0

  y = - x(k1 + k2)/k2