ccitt crc error detection failure rate test program

I have done similar tests with 7 byte data and an 8 bit CRCs on a 6502 microprocessor: easy to see that these short CRCs do not detect all errors and all CRCs aren´t created equal.

Hopefully your CPU is fast enough: statistics works on big numbers. Otherwise these simulations are not much fun.

As you might have guessed you are not the first one interested in the undetected error probability of 16 bit CRCs:

MfG JRD

I start to suspect that biting the bullet and reading up on CRC theory will bring more clarity than anything else you can do. The CRC polynomials will have been chosen to preserve as much difference as possible (rather as linear-feedback-shift-register polynomials are chosen for greatest cycle lengths) and with the theory digested it will be obvious how this is so.

The Python version below gained a bit of clarity, at the expense of runtime. It took a few minutes to find no false positives (corrupt messages thought to be good) in a million trials.

Mel.

import random

#The following was generated for it for the #ITU_T polynomial: x^16 + x^12 + x^5 + 1 ccitt_crc16_table = [

def crcByte (fcs, c): fcs = ccitt_crc16_table[(fcs >> 8 ^ c) & 0xFF] ^ (fcs >3] ^= 1

It's not.

Yep, if I keep on buying Lotto tickets indefinitely I'll eventually win.

TH.de/temp/crc.pdf

Thanks.

ll

will

me. =A0

Thanks. Do you feel like running it with it set to corrupt 150 bits in every message?

I've done this for 1.5 million reps and got no undetected errors. It's possible there's something wrong with my code but I can't see it.

I've also tried generating two messages and comparing the CRCs. I got about 8 out of 115000 with the same CRC.

To clarify, you are trying to determine how many *undetectable* errors there are? What does the polynomial *claim* to detect? (i.e., it might detect *all* N bit errors, *some* M bit errors and, possibly, *no* P bit errors)

Why always 8?

This depends on the polynomial. E.g., simple "parity" will detect *all* one bit errors -- but *no* 2 bit errors. And, yet again, all *3* bit errors, etc.

How "random" is your PRNG? Chances are, you are generating *it* with a polynomial, as well...

Theory will help you more than practice, here. You need to run a really *long* simulation to get meaningful numbers. And, have to be sure your PRNG really *is* random and doesn't just loop over a small subregion of the space. E.g., if your PRNG has too short of a cycle length, there are values (combinations of bits) that you will never exercise.

I was actually getting zero errors because there was something wrong with my random number generator. Now that I've improved the PRNG I'm getting similar numbers to 1/32768 regardless of whether I flip 8 bits or 150 bits. I deliberately flipped an even number of bits because I knew it detected all odd number bit flips.

ok, I'm getting this.

ok.

In another thread here I learnt/realized that in a byte protocol that has stop bits and start bits, corruption of a start bit can result in the data "morphing" into something else if it occurs before the length byte of a message and defeat the ability of the crc to detect single bit errors. It could also be a problem if it occurs after the length byte, depending on how gaps in data are handled etc.

Thanks.

I'm just trying to see for myself that the rate of undetected errors for an even number of bit flips with the ccitt 16 bit crc is on average, at least 1 in 65536 when the number of bits flipped is more than 3.

I lashed up the program late at night in a hurry and the way I did the bit flipping was "manual" rather than loop driven so I needed a small even number greater than 3. I've improved my code now so I can do any number.

It's not random enough. I'm mainly relying on get_millisecs from my operating system to return sufficiently varying values.

My PRNG wasn't working to start with and I got zero detection failures in 300 million iterations. I suspect the Python version posted by Mel has this problem too because he got zero "undetected errors" for a million iterations when it should have been approx 1000000/32768 =3D 30.

me. =A0

I think it should be getting about 30 false positives in a million trials if you're flipping an even number of bits and the data is truly random.

Why?

Do you expect to use the crc in a system that flips a certain even number of bits every now and again?

I certainly can't think of any type of noise or other corruption that would swap the polarity of exactly eight random bits in a message.

If you want to figure out what your detection rates are for errors that can occur in a system, you must first characterise those errors. Typical real-world errors are a sequence of zeros or a sequence of ones, a short burst of ones followed closely by a short burst of zeros (like a spike on the line), failure to change from from zero to one after a long burst of zeros, etc.

One of the reasons crcs are popular for checking transmissions is that the type of errors they detect are /not/ randomly and evenly distributed (unlike simple additive checksums). They will do better at detecting runs of errors, for example, than a simple "1 in 65536" would suggest.

As I wrote at the start of this thread - curiosity.

um, I never said there was.

Sure, I'm aware of that. Any run of 16 bits or less gets detected with the crc I'm using.

Fair enough, I suppose - curiosity is as good a reason as any. I did a similar thing myself a number of years ago, for hamming codes for forward error correction.

I just thought you should be aware that you are spending time and effort on something of little realistic value - if you want to experiment, why not use test out other forms of corruption that you might see in use?

Easy. Take an NRZ-encoded bit stream using bit stuffing for clock recovery (yes, CAN, I'm looking at you). Two bit flips in just the right places, creating or disrupting stuff sequences, can shift around an almost arbitrary number of bits without affecting the data length.

Basically the same thing can happen in any asynchronous serial medium if the sender's or receiver's clock are sufficiently unstable to drift by about one bit time and back in the space of one frame. You could end up receiving one bit twice, another one not at all.

Both scenarios end up moving an entire string of bits by one bit time. Do that with a message of alternating ones and zeroes, and you invert all of them.

There is significant difference in the error detection performance of the different polynomials depending on particular block size, expected error rate and the distribution of errors. The "standard" polynomials are not necessarily the best in this regard. A polynomial which performs extremely well in one situation may not perform in the other situation. Thus, is good to tailor the polynomial for the needs of the particular application. The practical way to do that is simulation.

Vladimir Vassilevsky DSP and Mixed Signal Design Consultant

E.g., the way errors manifest on a CD/DVD is very different from the way they manifest in a serial comm link. And, of course, the actual environment can have a pronounced effect on communications reliability.

I think the OP needs to step back and look at the entire comm process/mechanism. As I have stated before, the CRC's only work on "data". The comm system doesn't always deliver "real data" to the CRC -- e.g., if it fails to synchronize properly to the *actual* data stream (i.e., not "noise"!), then it can *drop* data and/or *fabricate* data that isn't really data at all!

Unless you can understand (model, simulate) the nature of the entire process, you can't come up with a realistic error detection or recovery scheme.