Saturday, May 6, 2023

Large-Block Checksums

Large-Block Modular Addition Checksum Algorithms

Philip Koopman

Checksum algorithms are widely employed due to their use of a simple algorithm with fast computational speed to provide a basic detection capability for corrupted data. This paper describes the benefits of adding the design parameter of increased data block size for modular addition checksums, combined with an empirical approach to modulus selection. A longer processing block size with the right modulus can provide significantly better fault detection performance with no change in the number of bytes used to store the check value. In particular, a large-block dual-sum approach provides Hamming Distance 3-class fault detection performance for many times the data word length capability of previously studied Fletcher and Adler checksums. Moduli of 253 and 65525 are identified as being particularly effective for general-purpose checksum use.

Download the full paper here: https://arxiv.org/abs/2302.13432





Tuesday, April 4, 2023

Why Life Critical Networks Tend To Provide HD=6

I'm thinking about why a Hamming Distance of 6 for network checksums/CRCs is so often found. Certainly that is designed into many network protocols, but sometimes I like to ask the question as to whether folk wisdom makes sense. So I did a trial calculation:

  • 100 bit messages
  • 1000 messages/second
  • 20 year operational life
  • 10 million deployed units
  • 1e-5 bit error ratio

I got 47.47 expected arrivals of 5-bit corrupted messages (random independent bisymmetric "bit flip" fault model at BER), and probability of only 1% of any 6-bit corrupted messages. So that seems to justify HD=6 as being reasonable for this example system, which looks to me like a CAN network with low-cost network driver circuits on a car fleet. (Even 10x fleet size still works out as more likely than not there will be no 6-bit faults.) The safety argument here would simply be that there will never be an undetected network message fault for this fault model.


Did I miss something? (Did I get my math wrong :) ?) Does anyone know of a place where HD=6 is justified in a different way other than by folklore? So much of checksums and CRCs risks being lost in folklore as the grey beards retire. I'm trying to capture some of this type of thinking for posterity before it is my turn to retire...


In my experience 1e-5 BER is a typical conservative number for an embedded network. That means about 1% of network messages are corrupted. More than that and it's going to be difficult to get a working system. Less than that and there is economic pressure to use cheaper cabling with worse BER. But this is a rule-of-thumb approximation. You should do the calculation for your own network. For IT networks BER is dramatically lower, but they tend to operate in a much more benign environment and have budget for better network hardware.


Wolfram Alpha computation for those who'd like to check my work (you might need to click on "approximate solution" to get the actual number):

https://www.wolframalpha.com/input?i=n%3D100%3Bf%3D5%3BB%3D1e-5%3B+++X%3D%28B**f%29%3B+Y%3D%28%281-B%29**%28n-f%29%29%3B+Z%3Dcombination%28n%2Cf%29%3B++X*Y*Z*20*365.25*24*3600*1000*10000000

              



Excel source: https://archive.org/details/hd-worksheet

Tuesday, August 11, 2020

Pending clean-up of papers

 I received the following comments with potential issues in some of my work.  I'm delighted to receive such feedback since a major point of my work is to try to get a complex topic straight.

At the moment I'm fully engaged working on self-driving car safety so it will be a while before I can resolve these. However, in the spirit of transparency here are the points raised so you know to be careful on these points when reading my work.

(This is posted with permission conditioned on anonymity. Thanks to the person who sent the comments.)

----------------------------------------------

1) On page 5 of http://users.ece.cmu.edu/~koopman/roses/dsn04/koopman04_crc_poly_embedded.pdf you say that SMBus uses CRC-8, polynomial 0xEA in your notation and say that 0x83 would be better. I am not familiar with SMBus but three sources say that the polynomial chosen for SMBus was 0x83.

CRC Catalogue entry CRC-8/SMBUS lists poly=0x07 (they use what Wikipedia calls Normal form)

SMBus Spec page 27 clearly states that the polynomial is x8 + x2 + x1 + 1

Presentation 22 April 1999 USAR Systems has the same.

2) On same page of same document as 1), it says XMODEM also uses CRC-8 polynomial 0xEA but it appears that XMODEM uses a 16-bit CRC according to Wikipedia and the CRC Catalogue amongst others. There is reference to an earlier 8-bit FCS but that was called a checksum in the references I found, not a CRC. ref1, ref2, ref3

3) Finally, I am having trouble reproducing your Probability of Undetected Error graphs from your koopman04 paper. The maxino_ms.pdf, page 9 gives the equation for Pud as

Pud = HW * BER^x * (1-BER)^(n-x)

where n is code word length in bits, x is number of bit errors, HW is Hamming weight at the HD. For example, polynomial 0x9C at 9 bit data word length is shown as just above 1e-33 (I used a tool to read scaled values off log charts to get about 6e-33 since I can't find a numeric value anywhere), but the formula gives 3.4e-29 at same BER of 1e-6, since HD=5 and HW(5)=34.

I suspect this is because your Pud graphs are, as you say in section 4.1, "weighted by the percentage of errors caught per corresponding polynomial weights for each data word length" but I cannot find a formula or example of this weighting which gives the required correction. Although formula (2) in page 18 of the faa15_tc-14-49.pdf document is different from the above, as far as I can see the combin(c, HD) term cancels out because UndetectedFractionHD = HW/combin(c, HD). So please could you provide the weighting formula, preferably with one numerical example.

----------------------------------------------

Initial responses:

- I would not be at all surprised for #1 and #2 I was referring to documents that got the polynomials wrong, which was previously quite common but is getting better over time.

- For #3 the graphs and probability equations can be a bit tricky.  I'll have to get all that stuff back in my head before being able to respond.  I'd suggest going with the analysis here if you're in doubt, which had the math reviewed by researchers from Honeywell, so hopefully it's OK: http://www.tc.faa.gov/its/worldpac/techrpt/tc14-49.pdf  

Monday, June 29, 2020

CRC Information Quick Start

I'm not able to spend much if any time on this lately due to my work in self driving car safety. Here is a quick start for those looking for info.

A tutorial on using CRCs and Checksums (how to apply them, pitfalls, system considerations; not a deep crawl through the math):
https://betterembsw.blogspot.com/2013/11/crc-webinar.html

A report written for the FAA on CRCs and Checksums (goes with the tutorial)
https://betterembsw.blogspot.com/2015/04/faa-crc-and-checksum-report.html

A web site of "best" CRCs, including:

A summary of "Seven Deadly Sins of CRCs and Checksums":
https://betterembsw.blogspot.com/2013/06/seven-deadly-sins-of-crcs-and-checksums.html

Maximal length LFSR polynomials:
https://users.ece.cmu.edu/~koopman/lfsr/index.html  

My papers on this topic are here:
https://users.ece.cmu.edu/~koopman/projects.html#crc

(There are other posts you might find of interest in the blog as well.)
https://betterembsw.blogspot.com/2015/04/faa-crc-and-checksum-report.html

Also, some FAQ:
  • Can I combine using two small CRCs to get better HD?  Probably not.
    It doesn't work because of error patterns that hit both CRC fields. Maybe it can be done, but every paper I've read has been flawed for this reason and the polynomial searches I ran came up empty handed due to this reason.
  • How does polynomial X perform?
    Please look at the zoo and see if you can find it.  If it is not there I'll add it when I have time if it is a published value.  Be sure to consider there are different notations, which are accounted for in the Zoo.
  • Can you please provide me with free consulting help?
    Sorry, too busy with self driving car safety these days in addition to teaching.  I sometimes answer general interest questions on my blog, but I can only spend a minute or two and it has to be something others will likely find interesting.




Friday, August 16, 2019

Effect of Initial Seed Values on CRCs and Checksums

Checksums and CRCs involve a repeated computation over the length of a dataword that
accumulates a result to form an FCS value. The accumulation value must be initialized to some
known value for this process to produce a predictable result for any given codeword. When the
initial value is unstated, it is typically assumed to be zero.

In some cases, a non-zero value is used instead, such as 0xFFFF for a 16-bit checksum or CRC.
This has the advantage of making an all zero codeword impossible. Perhaps more importantly
for Fletcher checksum, ATN-32, and CRCs, this has the additional advantage of causing leading
zeros of a message to affect the FCS value. To better understand, consider a CRC initialized
with an all zero seed value. Any number of all zero dataword chunks can be fed into the CRC
and it will stay at a zero value, throwing away information about how many zero chunks have
been processed. However, if the CRC computation is initialized to any non-zero value,
processing chunks with a value of zero will cycle patterns through the CRC, tracking the number
of zero-valued chunks that have been processed as a sort of counter. This can help with
situations in which additional leading-zero bytes have been erroneously added to a dataword.

In general, any non-zero seed value can be used. The value selected does not affect
error-detection properties beyond those previously discussed. In particular, CRC error detection,
in terms of the BER fault model, is independent of the seed value used.

The CRC and checksum values can be alternately or additionally modified to create an FCS
value. A common modification is to XOR the result of a checksum computation with a value,
such as 0xFFFF, which inverts bits, but does not lose any of the information content of the
checksum computation. In some cases, CRC result values must be bit-reversed to preserve burst
error properties across the dataword to FCS boundary, depending upon the computation method and message bit ordering in the dataword.

Note:
The "seed value" is sometimes also called the "initial value"

Source:

Saturday, March 11, 2017

Video on Hamming Codes & Hamming Distance

Nice video that talks about Hamming Codes and gives a hypercube explanation that helps understand Hamming Distance

Perfect Codes:

https://youtu.be/WPoQfKQlOjg
on computerphile.

Sunday, January 22, 2017

On sabbatical

I noticed that my e-mail has some CRC queries. I'm on sabbatical through summer 2017, so there might be significant delays before I'm able to respond to e-mails.  If you notice something that seems to be a problem please do let me know, but please bear with me until I have time to respond.

(Contrary to what some might think "sabbatical" is usually the opposite of "vacation" for engineering faculty.  It is a chance for us to concentrate on a large difficult problem that we can't do during normal semesters because of all the many demands made upon our time.)

32-bit CRCs might be insufficient for WiFi

A new paper suggests CRCs might not be enough for WiFi. Is It Time to Upgrade From CRC-32?  /  Mohit Balany; Craig Partridge (IEEE Xplore / ...