non-order dependant checksum

Hi

I've searched the internet unsuccessfully trying to find a non-order
dependent error detection algorithm that has low prob of undetected errors
(lower than a 2's complement add checksum). The reason being that my
algorithm processes image data in an order different that what's
transmitted to the FPGA. While I've got portions of the data in my L2, it
is more efficient to compute the checksum in chunks rather than re-read the
whole image before sending it to the FPGA.  (wouldn't it be nice of C64x+
DMA's could compute a CRC while they send an image!)

Anyone heard of any non-order dependent checksums?

Also, I came across this great paper by Maxino called "The Effectiveness of
Checksums for Embedded Networks" that shows the performance of various
checksums (Fletcher, Alder, 2's compl, XOR, etc). Unfortunately only the
XOR and add checksums have pretty lousy prob of undetected errors.

Cheers

SailingDreams wrote:

> Hi
> 
> I've searched the internet unsuccessfully trying to find a non-order
> dependent error detection algorithm that has low prob of undetected errors
> (lower than a 2's complement add checksum). The reason being that my
> algorithm processes image data in an order different that what's
> transmitted to the FPGA. While I've got portions of the data in my L2, it
> is more efficient to compute the checksum in chunks rather than re-read the
> whole image before sending it to the FPGA.  (wouldn't it be nice of C64x+
> DMA's could compute a CRC while they send an image!)
> 
> Anyone heard of any non-order dependent checksums?
> Also, I came across this great paper by Maxino called "The Effectiveness of
> Checksums for Embedded Networks" that shows the performance of various
> checksums (Fletcher, Alder, 2's compl, XOR, etc). Unfortunately only the
> XOR and add checksums have pretty lousy prob of undetected errors.


Any linear function, such as CRC, could be computed with taking the 
order of data into the account. You can modify CRC algorithm so it will 
be CRC(*x, position, length).

Vladimir Vassilevsky
DSP and Mixed Signal Design Consultant
http://www.abvolt.com

On Sep 8, 8:15&#4294967295;am, "SailingDreams" <epatton@n_o_s_p_a_m.yahoo.com>
wrote:
> Hi
>
> I've searched the internet unsuccessfully trying to find a non-order
> dependent error detection algorithm that has low prob of undetected errors
> (lower than a 2's complement add checksum). The reason being that my
> algorithm processes image data in an order different that what's
> transmitted to the FPGA. While I've got portions of the data in my L2, it
> is more efficient to compute the checksum in chunks rather than re-read the
> whole image before sending it to the FPGA. &#4294967295;(wouldn't it be nice of C64x+
> DMA's could compute a CRC while they send an image!)
>
> Anyone heard of any non-order dependent checksums?
>
> Also, I came across this great paper by Maxino called "The Effectiveness of
> Checksums for Embedded Networks" that shows the performance of various
> checksums (Fletcher, Alder, 2's compl, XOR, etc). Unfortunately only the
> XOR and add checksums have pretty lousy prob of undetected errors.
>
> Cheers

The effectiveness of the cksum depends on the type of errors you
expect to see. Are you expecting bit errors or missing bytes or what?
Basically I'm saying don't get bogged down in worrying if a particular
cksum method is considered good in some sort of general sense, but
rather you need to consider the types of errors your system has and
then find a suitable cksum method for detecting those errors. It may
be simple xoring is good enough for your application. Even a rotate
and add circular may do well for you. It may not be absolutely order
independent, but use your data in chucks with sizes that are mutliples
of the number of bits used in the circular arithmetic.

Clay

On 09/08/2010 07:07 AM, Vladimir Vassilevsky wrote:
>
>
> SailingDreams wrote:
>
>> Hi
>>
>> I've searched the internet unsuccessfully trying to find a non-order
>> dependent error detection algorithm that has low prob of undetected
>> errors
>> (lower than a 2's complement add checksum). The reason being that my
>> algorithm processes image data in an order different that what's
>> transmitted to the FPGA. While I've got portions of the data in my L2, it
>> is more efficient to compute the checksum in chunks rather than
>> re-read the
>> whole image before sending it to the FPGA. (wouldn't it be nice of C64x+
>> DMA's could compute a CRC while they send an image!)
>>
>> Anyone heard of any non-order dependent checksums?
>> Also, I came across this great paper by Maxino called "The
>> Effectiveness of
>> Checksums for Embedded Networks" that shows the performance of various
>> checksums (Fletcher, Alder, 2's compl, XOR, etc). Unfortunately only the
>> XOR and add checksums have pretty lousy prob of undetected errors.
>
>
> Any linear function, such as CRC, could be computed with taking the
> order of data into the account. You can modify CRC algorithm so it will
> be CRC(*x, position, length).
>
And I strongly suspect that any good error detection algorithm would be 
order dependent, although I don't know for sure and would have to learn 
some math to either prove or disprove it.

I'd look into the difficulty of making a CRC like Vladimir is proposing. 
  If you're dealing with fixed-length blocks it may not be all that bad.

-- 

Tim Wescott
Wescott Design Services
http://www.wescottdesign.com

Do you need to implement control loops in software?
"Applied Control Theory for Embedded Systems" was written for you.
See details at http://www.wescottdesign.com/actfes/actfes.html

Tim Wescott <tim@seemywebsite.com> wrote:
(snip on order independent checksums)

> And I strongly suspect that any good error detection algorithm would be 
> order dependent, although I don't know for sure and would have to learn 
> some math to either prove or disprove it.

I would think it would depend on the possible (or likely) errors
in the system in question.  Where people are involved, digit 
transposition is common, and algorithms are designed around that.

The ISBN checksum includes multiplying each digit by some digit
position specific weight, summing the result, and then using
the modulo 11 result of the sum.  (That is why the check digit
is sometimes X.)  The weighted sum can easily be done in a
different order, if you know the order.
 
> I'd look into the difficulty of making a CRC like Vladimir is proposing. 
>  If you're dealing with fixed-length blocks it may not be all that bad.

It sounds hard to me, though I haven't thought about all
the details.  More obvious to me would be to do CRC by blocks.
If, for example, one was computed columnwise, while the other rowwise,
it wouldn't be hard to keep the running CRCs in an array such that
you could compute columnwise CRCs in rowwise data.  Then you need a
good way to combine them in the end, maybe another CRC.

-- glen

No non-order-dependent checksum is going to be really strong
against double-errors, but you can make it stronger against
completely identical double errors by adding some nonlinearity.

e.g. instead of x0 ^ x1 ^ x2 ... for 8-bit-symbols x, compute
f(x0) ^ f(x1) ^ f(x2) ... where f() is some arbitrary 1-to-1
mapping on 8-bit symbols.   

(Here ^ means bitwise exclusive or.)

This should have the effect of making it more immune against
really simple double-error patterns.  You may want to scramble
the data first, in addition.

Steve

On Sep 8, 12:44�pm, spop...@speedymail.org (Steve Pope) wrote:
> No non-order-dependent checksum is going to be really strong
> against double-errors, but you can make it stronger against
> completely identical double errors by adding some nonlinearity.
>
> e.g. instead of x0 ^ x1 ^ x2 ... for 8-bit-symbols x, compute
> f(x0) ^ f(x1) ^ f(x2) ... where f() is some arbitrary 1-to-1
> mapping on 8-bit symbols. �
>
> (Here ^ means bitwise exclusive or.)
>
> This should have the effect of making it more immune against
> really simple double-error patterns. �You may want to scramble
> the data first, in addition.
>
> Steve

The point I was making is he may not need industrial strength error
detection. What is the cause and nature of his errors?

Clay

Clay  <clay@claysturner.com> wrote:

>On Sep 8, 12:44&#4294967295;pm, spop...@speedymail.org (Steve Pope) wrote:

>> No non-order-dependent checksum is going to be really strong
>> against double-errors, but you can make it stronger against
>> completely identical double errors by adding some nonlinearity.
>>
>> e.g. instead of x0 ^ x1 ^ x2 ... for 8-bit-symbols x, compute
>> f(x0) ^ f(x1) ^ f(x2) ... where f() is some arbitrary 1-to-1
>> mapping on 8-bit symbols. &#4294967295;

>The point I was making is he may not need industrial strength error
>detection. What is the cause and nature of his errors?

Right.

(You must be using a newsreader that looks at the References line,
which I don't use.  I was replying to the OP.)

Steve

On Sep 8, 4:46�pm, spop...@speedymail.org (Steve Pope) wrote:
> Clay &#4294967295;<c...@claysturner.com> wrote:
> >On Sep 8, 12:44&#4294967295;pm, spop...@speedymail.org (Steve Pope) wrote:
> >> No non-order-dependent checksum is going to be really strong
> >> against double-errors, but you can make it stronger against
> >> completely identical double errors by adding some nonlinearity.
>
> >> e.g. instead of x0 ^ x1 ^ x2 ... for 8-bit-symbols x, compute
> >> f(x0) ^ f(x1) ^ f(x2) ... where f() is some arbitrary 1-to-1
> >> mapping on 8-bit symbols. &#4294967295;
> >The point I was making is he may not need industrial strength error
> >detection. What is the cause and nature of his errors?
>
> Right.
>
> (You must be using a newsreader that looks at the References line,
> which I don't use. &#4294967295;I was replying to the OP.)
>
> Steve

No worries - I use google groups.

Clay

Hi All

Thank you for your ideas.

The nature of the errors are:

1) the accidental writing by the CPU into the video buffer (want to catch
this during the development phase and should never happen in production),

2) transmission errors across our various interfaces. This should be bursty
(multiple bytes) if it occurs.

I hoped that there was something equivalent to a Fletchers checksum that
would be easy to implement in SW and have similar performance.
Unfortunately the idea of computing a CRC on segments is not possible given
the processing time and the number of segments that are continuous (the
number of CRCs that would have to be appended to the frame would be too
large).

Cheers