Is there such thing as a 4 bit CRC ?

CRC is build from a polynomial with specific properties. Such polynomials exist for any number of bits. With low number of bit CRC have limited detection capability: 1-bit CRC is essentially the same as parity, 4-bit CRC is not very good. OTOH with only 4 data bits 4 (or 8) bit CRC is trivial: essentially you just get back your bits. So it is the same as transmiting two copies of your command: if they match then command is hopefully OK, is not you have error. That will catch single bit errors and most two bit errors, but will miss case when both command bit and corresponding bit in the copy is togled. As other pointed out Hamming code can do better, that is discover all 2 bit errors and correct one bit errors. Or alternatively, detect up to 3 bit errors.

--
                              Waldek Hebisch
Reply to
antispam
Loading thread data ...

No. Two copies will only ALERT you to a bit error; it will not allow you to recover (correct) that error.

1010 1011 leaves you unsure as to whether the intended command was 1010 *or* 1011 (along with any number of less likely corruptions).

So, simple duplication wastes bits. You can get better coverage with other encodings.

Reply to
Don Y

...or correct 2 bit errors.

Hamming has been used for 2 bit correcting EDACs for years (at least 20):

formatting link

Hans

formatting link

>
Reply to
HT-Lab

With 4 syndrome bits on a 4 bit datum?? (as the OP suggested)

Reply to
Don Y

That would be "no".

(This post is not really a direct follow up to Don's post, that's just a place to put it.)

It's easy to do the calculations. If you have 8 bits of total transferred data, to correct 1 bit of error you need to distinguish 9 cases - 1 case of all bits correct, and 8 cases of single bit errors. This means 4 bits need to be syndrome, leaving 4 bits for data.

If you want to correct 2 bit errors, you need another (8 * 7) / 2 = 28 cases, or 37 cases in total. That takes 6 bits, leaving 2 bits for data.

Good sizes for single-bit correction are thus:

4-bit data, 3-bit syndrome 11-bit data, 4-bit syndrome 26-bit data, 5-bit syndrome

(You can use an extra bit as parity, giving 1 bit correction and 2 bit detection without correction.)

For double-bit correction, you can have:

2-bit data, 5 bit syndrome 8-bit data, 7 bit syndrome 22-bit data, 9 bit syndrome 52-bit data, 11 bit syndrome

For triple-bit correction, you can have:

1-bit data, 6 bit syndrome 5-bit data, 10 bit syndrome 19-bit data, 13 bit syndrome 48-bit data, 16 bit syndrome

Bigger sizes give greater efficiency. But it's not always easy to get good Hamming code algorithms for bigger sizes, and it is of course not necessarily the most sensible way to handle error detection and correction. For advanced algorithms you might be interested in the distribution of possible errors (is it more likely to have multiple errors in a row, rather than completely independent errors?), and at your receiver end you might have additional information about the signal quality. If you know a particular part of a received message is untrustworthy, it gets far easier to do the correction. (You can correct a missing bit of an arbitrarily long message with just one parity bit.)

Reply to
David Brown

You are reading something that I not wrote: where you find claim that CRC can correct errors?

As I wrote above (with better = Hamming).

--
                              Waldek Hebisch
Reply to
antispam

If duplicating data, at least complement / negate the copy, so it will help in detecting some types of errors.

With short data+CRC after a CRC error is detected, you could flip individual bits at a time and recalculate CRC. If CRC matches, there is a candidate for correct message. If no other matches occur, we most likely have the corrected message. With longer messages, the computational load will be too high.

Indeed.

Reply to
upsidedown

For some values of "likely", that might be acceptable. The trouble you face is that a CRC does not guarantee that it will let you do that in practice - you might find that there is more than one candidate bit that could be flipped in order to get a matching CRC. (Remember also that the incorrect bit might be in the CRC itself.)

Reply to
David Brown

ElectronDepot website is not affiliated with any of the manufacturers or service providers discussed here. All logos and trade names are the property of their respective owners.