http://en.wikipedia.org/wi

http://en.wikipedia.org/wi

See also http://www.netrino.com/Emb

Solved

Posted on 2011-05-02

I'm sending various sized packets from 16 Bytes to 8KBytes over a short range 24 inches (fairly reliable) Bluetooth link. I need to get rid of packets that contain any errors so I'm planning on a checksum. To keep processing simple I'd like to use as simple and small a checksum as possible.

Any suggestions?

Thanks.

Any suggestions?

Thanks.

19 Comments

http://en.wikipedia.org/wi

http://en.wikipedia.org/wi

See also http://www.netrino.com/Emb

Of course the smallest checksum would be a simple bit (even or odd parity). But it would be more difficult to transmit a single bit.

Thanks.

Also, whether false positives are acceptable or not (you can never really avoid them, but you can minimize the probability) ?

Yes. Which will discard a valid message, and can let a corrupt message go through.

Now you could improve your odds by using a 16 bit or 32 bit check-sum. But the fundimental flaw of the check-sum is that it will fail to catch a pair of offsetting errors. For example, if bit 7 of the 1st byte in the packet was supposed to be a 1, but it was a zero, the check-sum will catch that there is something wrong... unless there is a second error somewhere else in the packet where bit 7 was supposed to be a 0, but it was instead a 1. So check-sums are simple, but have this basic flaw.

Now things like CRC are more complex and are sort of like a hashing function. The basic idea behind hashing functions is that a small change in the input makes a huge difference in the output. The result is that a pair of matching errors won't cancel each other out and therefore produce a much more reliable form of error detection.

As a metaphorical example, let's say we are generating error detection for the following sentance. At the end of each sentence is a pair of "check digit". The 1st is the "check digit" produced by a check-sum, the 2nd is the "check digit" produces by CRC (or a hash function).

You want to send:

The brown fox jumped over the lazy dog. "G, "G"

The crown fox jumped over the lazy dog. "H", "X"

The brown fox humped over the lazy dog. "F", "A"

The brown fox jumped over the lazy god. "G", "L"

For the check-sum, you can see that a single minor change in the text produces a minor change in the check digit (one letter off in the alphabet). The result is that a pair of minor changes results in the same check digit and you miss the error.

For the CRC (hash) function, you can see that a minor change in the text produces a major change in the check digit. The result is that a pair of minor changes results in two major changes in the math and therefore results in a much less likelyhood that a pair of errors would "offset" each other.

So you have a basic engineering decision to make. Do you implement a quick and simple check-sum that is likely to miss SOME errors? Or do you take the time and resources needed to implement a CRC and obtain a much higher rate of error detection? Depending upon the application and the results of missing an occational error will dictate if you can live with a simple check-sum, or do you need the reliablility of the CRC.

the probability of not detecting an error with checksum is higer than what it was stated before

the math it's no so simple, but you can read it here

the documment has some math font missing but you can read it on google preview searching it by its name.

if the BER could be high I would use a 32 bits CRC, it's just a table and a couple of additional operations compared to a simple sum but it's way safer than an 8 bit checksum.

False positive is when an error ruins the checksum, but the payload is unaltered.

False negative is when the error is missed.

It’s seems to me you forgot considering the error/s that end up giving the same checksum...

not really, the distribution of error becomes a flat BER , the worst BER gives the worst senario, the probabilities are finally a function of the BER, see the paper.

An 8 bit checksum has 256 possibilities. If the message gets uniform randomly scrambled, there is exactly a 1/256 chance that the checksum will happen to match.

That's only true if you assume certain distributions. They assume poisson interarrival times for errors (which is typical); however, if you have errors caused by interference, then they could actually come at somewhat regular intervals which throws off the methods that rely on exponential distribution of error.

The following example is contrived, but illustrates my point.

If you have 512 bit packets, and single bit errors coming in on an average of 1 every 2000 bits with a standard deviation of 20, then a parity bit checksum will catch more than 99.999% of the errors. If the errors come in single bit error pairs every 4000 bits (same BER 1/2000), the parity bit will rarely catch any error at all.

2) I really never saw an Internet/Network device specifying more than a BER (when they do it...)

Anybody have an equation where I can vary packet size, BER, and get out the number of bits required in the checksum?

Thanks.

2) even if your BER is good the nature of a wireless link makes it always more exposed to quick changes on the considered BER (ocassional interference, link stablishment, etc)

3) there's not a formula but you can see tables on the paper I quoted before.

http://en.wikipedia.org/wi

Title | # Comments | Views | Activity |
---|---|---|---|

How to silent print from safari browser | 6 | 97 | |

tenRun challenge | 28 | 67 | |

changePi Challenge | 15 | 56 | |

word0 challenge | 4 | 37 |

A short article about a problem I had getting the GPS LocationListener working.

Join the community of 500,000 technology professionals and ask your questions.

Connect with top rated Experts

**21** Experts available now in Live!