On 12/04/2011 14:20, Shane williams wrote:> On Apr 12, 5:31 am, D Yuniskis<not.going.to...@seen.com> wrote: >> Hi Shane, >> >> On 4/10/2011 6:04 AM, Shane williams wrote: >> >> >> >>> Out of curiosity, I've lashed up a program (see below) to try and test >>> the detection failure rate for the ccitt 16 bit crc. It repeatedly >> >> 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) > > > 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. >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.
ccitt crc error detection failure rate test program
Started by ●April 10, 2011
Reply by ●April 12, 20112011-04-12
Reply by ●April 12, 20112011-04-12
On Apr 13, 12:59=A0am, David Brown <da...@westcontrol.removethisbit.com> wrote:> On 12/04/2011 14:20, Shane williams wrote: > > > 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. > > Why? >As I wrote at the start of this thread - curiosity.> 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.um, I never said there was.> > 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). =A0They will do better at detecting > runs of errors, for example, than a simple "1 in 65536" would suggest.Sure, I'm aware of that. Any run of 16 bits or less gets detected with the crc I'm using.
Reply by ●April 12, 20112011-04-12
On 12/04/2011 15:15, Shane williams wrote:> On Apr 13, 12:59 am, David Brown<da...@westcontrol.removethisbit.com> > wrote: >> On 12/04/2011 14:20, Shane williams wrote: >> >>> 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. >> >> Why? >> > > As I wrote at the start of this thread - curiosity. >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?> >> 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. > > um, I never said there was. > > >> >> 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. > > Sure, I'm aware of that. Any run of 16 bits or less gets detected > with the crc I'm using. >
Reply by ●April 12, 20112011-04-12
On 12.04.2011 14:59, David Brown wrote:> 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.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.
Reply by ●April 12, 20112011-04-12
Shane williams wrote:> Out of curiosity, I've lashed up a program (see below) to try and test > the detection failure rate for the ccitt 16 bit crc. It repeatedly > generates a buffer of 32 pseudo-random bytes, calculates the crc, then > complements 8 pseudo-random bits and re-calculates the crc.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 http://www.abvolt.com
Reply by ●April 12, 20112011-04-12
Hi Vladimir, On 4/12/2011 12:16 PM, Vladimir Vassilevsky wrote:> Shane williams wrote: > >> Out of curiosity, I've lashed up a program (see below) to try and test >> the detection failure rate for the ccitt 16 bit crc. It repeatedly >> generates a buffer of 32 pseudo-random bytes, calculates the crc, then >> complements 8 pseudo-random bits and re-calculates the crc. > > 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.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.> 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.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.
