Calculating number of errors that is undetected by a CRC using a particular polynomial

Question

My goal is to determine optimal generator polynomial and size of the Frame Check Sequence (CRC field) for protocol that I am developing. Reading the paper, "Cyclic Redundacy Code (CRC) Polynomial Selection For Embedded Networks" by Koopman and Chakravarty, provided me with a solid understanding of the topic and proved to be a valuable resource.

Especially interesting for me is Table 1. (provided below), "Example Hamming weights for data word size 48 bits". My question is how to come up with this table on my own? That is, how to calculate number of undetectable errors, provided generator polynomial and data word size? I am not sure if this number is also dependent on bit error ratio (BER).

Namely, I want to write script to calculate these, as data provided by authors of the paper do not cover polynomials and data lengths that I have at hand.

Any reference to the material where I could get necessary knowledge to come up with an algorithm is welcome (preferably without entering into field theory).

Answer 1

You can simply use a statistical approach.

Select a block size of N zero bits. Set the first and last bits. Set K-2 other random bits in this block. Check whether the CRC of this thing is zero. Repeat. After some time, print the lowest (K,N) pairs found.

Obviously there's no point in testing a (K,N) pair if a pair with smaller-or-equal K and/or N is already known.

Pairs with K=2 typically have N=1+2^M, so run these first to find suitable upper bounds.

Computers are fast, these days. The values converge pretty quickly.

Math people will probably throw up and/or walk away in disgust at this approach, but I don't care. Anyway, my excuse is that the protocol I designed encodes an arbitrary bitstream as a sequence of integers, in the range (1;2^b-1). (This is for a self-clocking two-or-more-wire protocol: a null transition is not allowed.) I wanted to test my conjecture that a CRC over the bytestream would be as useless as I suspected it to be. (It was: not detecting all single-bit errors is not acceptable.) Even if it is possible to rigorously prove this, I have no idea how to go about that and would probably have to ask a crypto person or two.