CODEWITHSUNDEEP
checksumcrctelecommunicationerror-detectiondata-link-layer
irl_irl
irl_irl

Reputation: 3975

Error Detection Effiency (CRC, Checksum, etc)

I have a hypothetical situation of sending data units, each of a thousand bytes. Failure rate is rare but when a error does occur it is less likely to be a single bit error and more likely to be an error in a few bits in a row.

At first I thought of using a checksum, but apparently that can miss bit errors larger than a single bit. A parity check won't work either so CRC might be the best option.

Is using a Cyclic Redundancy Check on a thousand bytes efficient? Or are there other methods that would work better?

Upvotes: 5

Views: 5603

Answers (4)

Robert Cartaino
Robert Cartaino

Reputation: 28142

Cyclic Redundancy Checks (CRCs) are popular specifically because of their efficiency at detecting multiple bit errors with a guaranteed accuracy.

There are different designs to generate CRC polynomials where the trade-off is accuracy vs. computational complexity. In your case, you can choose the "fastest" one that meets your requirements for accuracy.

You might want to start with this Wikipedia article on the Cyclic Redundancy Check.

Upvotes: 8

Tim Holloway
Tim Holloway

Reputation: 106

How big are your disk sectors? Probably at least 512 bytes. And CRC is a time-honored scheme for hardware-level disk ECC.

The stock CRC polynomial algorithms are quite effective for small numbers of bit errors. The exact precision is mathematically computable. CRC is also highly efficient to do in hardware where a relatively small number of gates and shift registers can manage the job on the fly.

Upvotes: 1

nik
nik

Reputation: 13468

CRC is covered in another question here
When is CRC more appropriate to use than MD5/SHA1?
It is suitable for detecting random errors and easy to implement.

Upvotes: 2

ChrisW
ChrisW

Reputation: 56123

It's normal to use a CRC. I'm not certain what you mean by 'efficiency', but I think that sometimes the CRC is implemented in hardware (e.g. on the Ethernet card). Otherwise you may find 'optimized' implementations (using a lookup table).

Upvotes: 1

Related Questions