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

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).

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.

I would regard papers like this with great scepticism.

First of all, the polynomials listed in that paper are apparently the "reversed reciprocal" of the actual standardized polynomials. They don't explain why - and this is really weird. The polynomial for CRC-16-CCITT is for example 0x1021, or if you will x^16 + x^12 + x^5 + 1. Apparently Wikipedia makes some effort into trying to make sense of this particular paper.

The polynomials were designed to remind as little of the most probable error pattern of the intended application. While the whole idea of Hamming Distance as some sort of ideal in data communication, is often taken out of the blue. To quote the paper:

For embedded networks, the property of interest is usually the Hamming Distance (HD), which is the minimum possible number of bit inversions that must be injected into a message to create an error that is undetectable by that message's CRC-based Frame Check Sequence.

This is already making a whole lot of weird assumptions, such as that generic bit inversions are the most probable errors. They base the whole paper on this assumption.

But in a whole lot of cases, this only holds true when a low voltage bit gets turned into a high voltage bit by EMI - the other way around is far less likely. So if you come up with some theoretical test where you flip random bits in a generic data package, then ponder about Hamming Distance from there, you have already gone wrong and left scientific methods behind.

In order to make any sense of such assumptions, we must define the communication media. For example they mention the polynomial of CAN, which is a differential signal. When an error occurs from EMI, the chance of both lines flipping is non-existent and most of the error detection lies on the hardware level, not in the CRC. In fact CAN has such good error detection on the hardware level - sampling every bit carefully, that the CRC is mostly there for show.

And of course the probable error patterns on a CAN bus will be very different from error patterns in other applications. Take for example flash memory, where the main error-causing culprit is data retention over time, or possibly exceeding the number of write cycles - not EMI.

Therefore, to boldly claim that a polynomial with a particular "Hamming weight" is more/less suitable, without taking any specific application in account, is unscientific hogwash.

• I refute the statement about CAN being robust... it is susceptible to bit stuffing errors.
– user16222
Jul 19, 2019 at 18:55
• also Koopman is an expert in this field (who wrote the paper you refuted). He was the one that highlighted the error in CAN and CRC and why ARINC-825 mandates an addition checksum for safety critical data.
– user16222
Apr 19, 2021 at 8:29