ccitt crc error detection failure rate test program

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.

How many iterations should I have to run it for to get the same crc on
the "corrupted" data as the non-corrupted data?  The detection failure
rate doesn't appear to be one in 65536 or anything like it.

If I corrupt more bits would I get a higher detection failure rate?

If I generate two pseudo-random 32 byte "messages" and compare their
CRCs, how long would I have to iterate for to get a match on the CRCs?

Any thoughts?





This code was written for MS visual C++

//#include "stdafx.h"

#include <stdio.h>
#include <tchar.h>
#include <windows.h>
#include <string>
#include <conio.h>

using namespace std;

//The following was generated for it for the
//ITU_T polynomial: x^16 + x^12 + x^5 + 1


typedef unsigned short uint16;
typedef unsigned char uchar;

uint16 const ccitt_crc16_table[256] = {
0x0000, 0x1021, 0x2042, 0x3063, 0x4084, 0x50a5, 0x60c6, 0x70e7,
0x8108, 0x9129, 0xa14a, 0xb16b, 0xc18c, 0xd1ad, 0xe1ce, 0xf1ef,
0x1231, 0x0210, 0x3273, 0x2252, 0x52b5, 0x4294, 0x72f7, 0x62d6,
0x9339, 0x8318, 0xb37b, 0xa35a, 0xd3bd, 0xc39c, 0xf3ff, 0xe3de,
0x2462, 0x3443, 0x0420, 0x1401, 0x64e6, 0x74c7, 0x44a4, 0x5485,
0xa56a, 0xb54b, 0x8528, 0x9509, 0xe5ee, 0xf5cf, 0xc5ac, 0xd58d,
0x3653, 0x2672, 0x1611, 0x0630, 0x76d7, 0x66f6, 0x5695, 0x46b4,
0xb75b, 0xa77a, 0x9719, 0x8738, 0xf7df, 0xe7fe, 0xd79d, 0xc7bc,
0x48c4, 0x58e5, 0x6886, 0x78a7, 0x0840, 0x1861, 0x2802, 0x3823,
0xc9cc, 0xd9ed, 0xe98e, 0xf9af, 0x8948, 0x9969, 0xa90a, 0xb92b,
0x5af5, 0x4ad4, 0x7ab7, 0x6a96, 0x1a71, 0x0a50, 0x3a33, 0x2a12,
0xdbfd, 0xcbdc, 0xfbbf, 0xeb9e, 0x9b79, 0x8b58, 0xbb3b, 0xab1a,
0x6ca6, 0x7c87, 0x4ce4, 0x5cc5, 0x2c22, 0x3c03, 0x0c60, 0x1c41,
0xedae, 0xfd8f, 0xcdec, 0xddcd, 0xad2a, 0xbd0b, 0x8d68, 0x9d49,
0x7e97, 0x6eb6, 0x5ed5, 0x4ef4, 0x3e13, 0x2e32, 0x1e51, 0x0e70,
0xff9f, 0xefbe, 0xdfdd, 0xcffc, 0xbf1b, 0xaf3a, 0x9f59, 0x8f78,
0x9188, 0x81a9, 0xb1ca, 0xa1eb, 0xd10c, 0xc12d, 0xf14e, 0xe16f,
0x1080, 0x00a1, 0x30c2, 0x20e3, 0x5004, 0x4025, 0x7046, 0x6067,
0x83b9, 0x9398, 0xa3fb, 0xb3da, 0xc33d, 0xd31c, 0xe37f, 0xf35e,
0x02b1, 0x1290, 0x22f3, 0x32d2, 0x4235, 0x5214, 0x6277, 0x7256,
0xb5ea, 0xa5cb, 0x95a8, 0x8589, 0xf56e, 0xe54f, 0xd52c, 0xc50d,
0x34e2, 0x24c3, 0x14a0, 0x0481, 0x7466, 0x6447, 0x5424, 0x4405,
0xa7db, 0xb7fa, 0x8799, 0x97b8, 0xe75f, 0xf77e, 0xc71d, 0xd73c,
0x26d3, 0x36f2, 0x0691, 0x16b0, 0x6657, 0x7676, 0x4615, 0x5634,
0xd94c, 0xc96d, 0xf90e, 0xe92f, 0x99c8, 0x89e9, 0xb98a, 0xa9ab,
0x5844, 0x4865, 0x7806, 0x6827, 0x18c0, 0x08e1, 0x3882, 0x28a3,
0xcb7d, 0xdb5c, 0xeb3f, 0xfb1e, 0x8bf9, 0x9bd8, 0xabbb, 0xbb9a,
0x4a75, 0x5a54, 0x6a37, 0x7a16, 0x0af1, 0x1ad0, 0x2ab3, 0x3a92,
0xfd2e, 0xed0f, 0xdd6c, 0xcd4d, 0xbdaa, 0xad8b, 0x9de8, 0x8dc9,
0x7c26, 0x6c07, 0x5c64, 0x4c45, 0x3ca2, 0x2c83, 0x1ce0, 0x0cc1,
0xef1f, 0xff3e, 0xcf5d, 0xdf7c, 0xaf9b, 0xbfba, 0x8fd9, 0x9ff8,
0x6e17, 0x7e36, 0x4e55, 0x5e74, 0x2e93, 0x3eb2, 0x0ed1, 0x1ef0
};

uint16 crcByte(uint16 fcs, unsigned char c)
{
    fcs = ccitt_crc16_table[(fcs >> 8 ^ c) & 0xffU] ^ (fcs << 8);
    return fcs;
}

int get_millisecs()
{
   static SYSTEMTIME st;
   GetSystemTime(&st);
   return st.wMilliseconds;
}

FILE * currstream;
std::string currfile;
int ms;
unsigned long fail;
unsigned long lowtotal;
unsigned long hightotal;

uchar message[64];
int msgsize = 32;
uint16 crc1;
uint16 crc2;

uchar get_next_stream_byte()
{
	int ch = getc(currstream);
	if (ch == EOF)
	{
		fclose(currstream);
		currstream = fopen(currfile.c_str(),"r");
      ch = getc(currstream);
	}
   return ch;
}

uchar get_next_byte()
{
   static int x1 = 0x1234;
   uchar ch = get_next_stream_byte();
   x1 -= 13;
   if (x1 <= 0)
   {
      x1 = (get_next_stream_byte() << 8) + get_next_stream_byte();
      if (x1 < 0) x1 *= -1;
      ms = get_millisecs();
   }
   return ch + ms + x1;
}


void check_next_message()
{
   uchar bitmask[8] = {1,2,4,8,0x10, 0x20, 0x40, 0x80};
   crc1 = 0;
   for (int k = 0; k < msgsize; ++k)
   {
      message[k] = get_next_byte();
      crc1 = crcByte(crc1,message[k]);
   }
   uchar v1, v2, v3, v4, v5, v6, v7, v8;
   v1 = get_next_byte();
   v2 = get_next_byte();
   while (v1 == v2) v2 = get_next_byte();
   v3 = get_next_byte();
   while (v1 == v3 || v2 == v3) v3 = get_next_byte();
   v4 = get_next_byte();
   while (v1 == v4 || v2 == v4 || v3 == v4) v4 = get_next_byte();
   v5 = get_next_byte();
   while (v1 == v5 || v2 == v5 || v3 == v5 || v4 == v5) v5 =
get_next_byte();
   v6 = get_next_byte();
   while (v1 == v6 || v2 == v6 || v3 == v6 || v4 == v6 || v5 == v6) v6
= get_next_byte();
   v7 = get_next_byte();
   while (v1 == v7 || v2 == v7 || v3 == v7 || v4 == v7 || v5 == v7 ||
v6 == v7) v7 = get_next_byte();
   v8 = get_next_byte();
   while (v1 == v8 || v2 == v8 || v3 == v8 || v4 == v8 || v5 == v8 ||
v6 == v8 || v7 == v8) v8 = get_next_byte();
   // corrupt the message
   message[v1>>3] ^= bitmask[v1&7];
   message[v2>>3] ^= bitmask[v2&7];
   message[v3>>3] ^= bitmask[v3&7];
   message[v4>>3] ^= bitmask[v4&7];
   message[v5>>3] ^= bitmask[v5&7];
   message[v6>>3] ^= bitmask[v6&7];
   message[v7>>3] ^= bitmask[v7&7];
   message[v8>>3] ^= bitmask[v8&7];
   crc2 = 0;
   for (int k = 0; k < msgsize; ++k)
   {
      crc2 = crcByte(crc2,message[k]);
   }
   if (crc1 == crc2)
   {
      fail += 1;
   }
}


void show_message()
{
   printf("\r\n");
   for (int k = 0; k < msgsize; ++k)
   {
      printf("%2x ", message[k]);
   }
   printf(" %4x %4x", crc1, crc2);
}


int main(int argc, unsigned char* argv[])
{
	currfile = "someverybigfile.exe";
   currstream = fopen(currfile.c_str(),"r");
   while (1)
   {
      if (++lowtotal == 0) ++hightotal;
      check_next_message();
      //show_message();
      //if (fail > 0) break;
      if (_kbhit()) break;
      //if (lowtotal > 5) break;
   }
   printf("%lu %lu  %lu", fail, lowtotal, hightotal);
   getchar();
	return 0;
}

> Out of curiosity, 

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.

> ccitt 16 bit crc. ...32 pseudo-random bytes, calculates the crc, then
> complements 8 pseudo-random bits and re-calculates the crc.

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:
http://www.embeddedFORTH.de/temp/crc.pdf

MfG  JRD

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.
> 
> How many iterations should I have to run it for to get the same crc on
> the "corrupted" data as the non-corrupted data?  The detection failure
> rate doesn't appear to be one in 65536 or anything like it.
> 
> If I corrupt more bits would I get a higher detection failure rate?
> 
> If I generate two pseudo-random 32 byte "messages" and compare their
> CRCs, how long would I have to iterate for to get a match on the CRCs?

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 = [
0x0000, 0x1021, 0x2042, 0x3063, 0x4084, 0x50a5, 0x60c6, 0x70e7,
0x8108, 0x9129, 0xa14a, 0xb16b, 0xc18c, 0xd1ad, 0xe1ce, 0xf1ef,
0x1231, 0x0210, 0x3273, 0x2252, 0x52b5, 0x4294, 0x72f7, 0x62d6,
0x9339, 0x8318, 0xb37b, 0xa35a, 0xd3bd, 0xc39c, 0xf3ff, 0xe3de,
0x2462, 0x3443, 0x0420, 0x1401, 0x64e6, 0x74c7, 0x44a4, 0x5485,
0xa56a, 0xb54b, 0x8528, 0x9509, 0xe5ee, 0xf5cf, 0xc5ac, 0xd58d,
0x3653, 0x2672, 0x1611, 0x0630, 0x76d7, 0x66f6, 0x5695, 0x46b4,
0xb75b, 0xa77a, 0x9719, 0x8738, 0xf7df, 0xe7fe, 0xd79d, 0xc7bc,
0x48c4, 0x58e5, 0x6886, 0x78a7, 0x0840, 0x1861, 0x2802, 0x3823,
0xc9cc, 0xd9ed, 0xe98e, 0xf9af, 0x8948, 0x9969, 0xa90a, 0xb92b,
0x5af5, 0x4ad4, 0x7ab7, 0x6a96, 0x1a71, 0x0a50, 0x3a33, 0x2a12,
0xdbfd, 0xcbdc, 0xfbbf, 0xeb9e, 0x9b79, 0x8b58, 0xbb3b, 0xab1a,
0x6ca6, 0x7c87, 0x4ce4, 0x5cc5, 0x2c22, 0x3c03, 0x0c60, 0x1c41,
0xedae, 0xfd8f, 0xcdec, 0xddcd, 0xad2a, 0xbd0b, 0x8d68, 0x9d49,
0x7e97, 0x6eb6, 0x5ed5, 0x4ef4, 0x3e13, 0x2e32, 0x1e51, 0x0e70,
0xff9f, 0xefbe, 0xdfdd, 0xcffc, 0xbf1b, 0xaf3a, 0x9f59, 0x8f78,
0x9188, 0x81a9, 0xb1ca, 0xa1eb, 0xd10c, 0xc12d, 0xf14e, 0xe16f,
0x1080, 0x00a1, 0x30c2, 0x20e3, 0x5004, 0x4025, 0x7046, 0x6067,
0x83b9, 0x9398, 0xa3fb, 0xb3da, 0xc33d, 0xd31c, 0xe37f, 0xf35e,
0x02b1, 0x1290, 0x22f3, 0x32d2, 0x4235, 0x5214, 0x6277, 0x7256,
0xb5ea, 0xa5cb, 0x95a8, 0x8589, 0xf56e, 0xe54f, 0xd52c, 0xc50d,
0x34e2, 0x24c3, 0x14a0, 0x0481, 0x7466, 0x6447, 0x5424, 0x4405,
0xa7db, 0xb7fa, 0x8799, 0x97b8, 0xe75f, 0xf77e, 0xc71d, 0xd73c,
0x26d3, 0x36f2, 0x0691, 0x16b0, 0x6657, 0x7676, 0x4615, 0x5634,
0xd94c, 0xc96d, 0xf90e, 0xe92f, 0x99c8, 0x89e9, 0xb98a, 0xa9ab,
0x5844, 0x4865, 0x7806, 0x6827, 0x18c0, 0x08e1, 0x3882, 0x28a3,
0xcb7d, 0xdb5c, 0xeb3f, 0xfb1e, 0x8bf9, 0x9bd8, 0xabbb, 0xbb9a,
0x4a75, 0x5a54, 0x6a37, 0x7a16, 0x0af1, 0x1ad0, 0x2ab3, 0x3a92,
0xfd2e, 0xed0f, 0xdd6c, 0xcd4d, 0xbdaa, 0xad8b, 0x9de8, 0x8dc9,
0x7c26, 0x6c07, 0x5c64, 0x4c45, 0x3ca2, 0x2c83, 0x1ce0, 0x0cc1,
0xef1f, 0xff3e, 0xcf5d, 0xdf7c, 0xaf9b, 0xbfba, 0x8fd9, 0x9ff8,
0x6e17, 0x7e36, 0x4e55, 0x5e74, 0x2e93, 0x3eb2, 0x0ed1, 0x1ef0
]

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

def crc (message):
    c = 0
    for m in message:
        c = crcByte (c, m)
    return c


def check_corrupt_message (message_length, error_count):
    message = [data_set.randint (0, 255) for i in xrange (message_length)]
    crc1 = crc (message)
    # make a list of target bit numbers
    targets = data_set.sample (range (len (message)*8), error_count)
    # corrupt the targeted message bits
    for t in targets:
        message [t>>3] ^= 1<< (t & 7)
    crc2 = crc (message)
    return crc1 != crc2	# True if the corrupted message was caught

# The same seed value will rerun the same test, if that's required
RANDOMSEED = 3458731652668731	#blind keyboarding made this number
MSGSIZE = 12
ERROR_COUNT = 8
data_set = random.Random ()
#~ data_set.seed (RANDOMSEED)
print 'Testing %d errors in %d-byte message.' % (ERROR_COUNT, MSGSIZE)
test_runs = 1000
failed = 0
for i in xrange (test_runs):
    if not check_corrupt_message (MSGSIZE, ERROR_COUNT):
        failed += 1
print 'Failed %d runs out of %d.' % (failed, test_runs)

On Apr 11, 2:51=A0am, Rafael Deliano <rafael_delianoENTFER...@arcor.de>
wrote:
> > Out of curiosity,
>
> 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=B4t created equal.
>
> > ccitt 16 bit crc. ...32 pseudo-random bytes, calculates the crc, then
> > complements 8 pseudo-random bits and re-calculates the crc.
>
> Hopefully your CPU is fast enough:

It's not.

> statistics works on big numbers.

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


> 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:http://www.embeddedFOR=
TH.de/temp/crc.pdf

Thanks.

On Apr 11, 4:05=A0am, Mel <mwil...@the-wire.com> wrote:
> I start to suspect that biting the bullet and reading up on CRC theory wi=
ll
> bring more clarity than anything else you can do. =A0The 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 runti=
me. =A0
> It took a few minutes to find no false positives (corrupt messages though=
t
> to be good) in a million trials.
>

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.

Shane williams <shane.2471958@gmail.com> 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.
>
>How many iterations should I have to run it for to get the same crc on
>the "corrupted" data as the non-corrupted data?  The detection failure
>rate doesn't appear to be one in 65536 or anything like it.
>
>If I corrupt more bits would I get a higher detection failure rate?

For a 16-bit CRC it should be about one in 65536 on average for large
numbers of bit errors. BUT, if you use a polynomial divisible by (x+1)
what you get is 100% of odd numbers of bit flips detected and only one
out of 32768 even numbers.  In other words, the whole undetected error
budget gets pushed into the even number of bit errors case.  I'll bet
you are seeing 1/32768 because you are flipping an even number of bits.

For small numbers of bit errors it all depends on the polynomial.  So
this is generic asymptotic error detection performance as number of bit
errors increases.

>If I generate two pseudo-random 32 byte "messages" and compare their
>CRCs, how long would I have to iterate for to get a match on the CRCs?

It turns out the message content doesn't matter, only the error
patterns.  But for that it is pseudo-random; asymptotically zero OR one
out of every 64K OR one out of every 32K for large numbers of bit errors
depending on even/odd number of errors and the polynomial.

>Any thoughts?

Simulations take a really long time to evaluate polynomials.   Also, you
have to use a good random number generator or your results won't be
accurate.  I tried that for a while but it just takes forever to get
answers. There are some analytic answers available that are pretty hairy
to do on your own, but are exact answers (not stochastic simulations).

This paper is a starting point:

Ray, J., & Koopman, P. "Efficient High Hamming Distance CRCs for
Embedded Applications," DSN06, June 2006.
http://www.ece.cmu.edu/~koopman/roses/dsn04/koopman04_crc_poly_embedded.pdf

It gives good CRC 16-bit polynomials and has references to the relevant
literature if you want to dig further.  

There are other related papers here:
http://www.ece.cmu.edu/~koopman/projects.html#crc

Cheers,
-- Phil




Phil Koopman -- koopman@cmu.edu -- http://betterembsw.blogspot.com/

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)

> generates a buffer of 32 pseudo-random bytes, calculates the crc, then
> complements 8 pseudo-random bits and re-calculates the crc.

Why always 8?

> How many iterations should I have to run it for to get the same crc on
> the "corrupted" data as the non-corrupted data?  The detection failure
> rate doesn't appear to be one in 65536 or anything like it.
>
> If I corrupt more bits would I get a higher detection failure rate?

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.

> If I generate two pseudo-random 32 byte "messages" and compare their
> CRCs, how long would I have to iterate for to get a match on the CRCs?

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

> Any thoughts?

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.

On Apr 12, 3:32=A0am, Philip Koopman <koop...@cmu.edu> wrote:
> Shane williams <shane.2471...@gmail.com> 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. =A0It repeatedly
> >generates a buffer of 32 pseudo-random bytes, calculates the crc, then
> >complements 8 pseudo-random bits and re-calculates the crc.
>
> >How many iterations should I have to run it for to get the same crc on
> >the "corrupted" data as the non-corrupted data? =A0The detection failure
> >rate doesn't appear to be one in 65536 or anything like it.
>
> >If I corrupt more bits would I get a higher detection failure rate?
>
> For a 16-bit CRC it should be about one in 65536 on average for large
> numbers of bit errors. BUT, if you use a polynomial divisible by (x+1)
> what you get is 100% of odd numbers of bit flips detected and only one
> out of 32768 even numbers. =A0In other words, the whole undetected error
> budget gets pushed into the even number of bit errors case. =A0I'll bet
> you are seeing 1/32768 because you are flipping an even number of bits.
>

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.



> For small numbers of bit errors it all depends on the polynomial. =A0So
> this is generic asymptotic error detection performance as number of bit
> errors increases.
>
> >If I generate two pseudo-random 32 byte "messages" and compare their
> >CRCs, how long would I have to iterate for to get a match on the CRCs?
>
> It turns out the message content doesn't matter, only the error
> patterns. =A0But for that it is pseudo-random; asymptotically zero OR one
> out of every 64K OR one out of every 32K for large numbers of bit errors
> depending on even/odd number of errors and the polynomial.

ok, I'm getting this.


>
> >Any thoughts?
>
> Simulations take a really long time to evaluate polynomials. =A0 Also, yo=
u
> have to use a good random number generator or your results won't be
> accurate. =A0I tried that for a while but it just takes forever to get
> answers. There are some analytic answers available that are pretty hairy
> to do on your own, but are exact answers (not stochastic simulations).

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.

On Apr 12, 5:31=A0am, 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. =A0It repeatedly
>
> To clarify, you are trying to determine how many *undetectable*
> errors there are? =A0What 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.


>
> > generates a buffer of 32 pseudo-random bytes, calculates the crc, then
> > complements 8 pseudo-random bits and re-calculates the crc.
>
> Why always 8?


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.


>
> > How many iterations should I have to run it for to get the same crc on
> > the "corrupted" data as the non-corrupted data? =A0The detection failur=
e
> > rate doesn't appear to be one in 65536 or anything like it.
>
> > If I corrupt more bits would I get a higher detection failure rate?
>
> This depends on the polynomial. =A0E.g., simple "parity" will
> detect *all* one bit errors -- but *no* 2 bit errors. =A0And,
> yet again, all *3* bit errors, etc.
>
> > If I generate two pseudo-random 32 byte "messages" and compare their
> > CRCs, how long would I have to iterate for to get a match on the CRCs?
>
> How "random" is your PRNG? =A0Chances are, you are generating *it*
> with a polynomial, as well...

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


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

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.

On Apr 11, 4:05=A0am, Mel <mwil...@the-wire.com> wrote:
>
> The Python version below gained a bit of clarity, at the expense of runti=
me. =A0
> It took a few minutes to find no false positives (corrupt messages though=
t
> to be good) in a million trials.
>

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.