How to calculate CRC32 by hand?

Introduction

A 32 bit Cyclical Redundancy Check is a means of error detection in data transmission. There are plenty of online calculators that will help you automatically calculate the CRC32 of a given value.

What I wanted to do was to understand how it is calculated. So what better way than to try and replicate a calculation by hand.

The Ground Work

The first thing I had to do was a lot of ground work. It took me a couple of weeks because I was reading everything in my path.

This link (http://stackoverflow.com/questions/2587766/how-is-a-crc32-checksum-calculated) is pretty good and I recommend reading the links to resources within that.

Then I recommend watching this YouTube video (https://www.youtube.com/watch?v=MSAog5MEhrs) because it goes through a simple example with some degree of explanation.

Finally this link (http://www.barrgroup.com/Embedded-Systems/How-To/CRC-Calculation-C-Code is good reading too.

Useful reference sites.

• https://ghsi.de/CRC/
• http://www.sunshine2k.de/coding/javascript/crc/crc_js.html
• http://www.asciitohex.com/

The challenge

Using various online CRC32 calculators such as http://www.lammertbies.nl/comm/info/crc-calculation.html I discovered that the CRC32 of the ascii character ‘a’ is 0xE8B7BE43.

So my challenge was to try and get from ‘a’ to 0xE8B7BE43 with a pencil and some paper.

My Variables

So my input was ‘a’. The CRC32 starting polynomial is defined as: x³²+ x²⁶+ x²³+ x²²+ x¹⁶+ x¹²+ x¹¹+ x¹⁰+ x⁸+ x⁷+ x⁵+ x⁴+ x²+ x¹+ x⁰

All I had to do now was to get to 0xE8B7BE43.

Step 1: The ground work

Read as much of the “ground work” material as your brain can manage and your stomach can handle. You don’t need to understand every single sentence. Just try and get the gist of it. Then get comfortable in binary. Practise some mod 2 binary “division” on short 4 bit words. It’s not half as scary as it sounds.

Step 2: A common language

Let’s convert our known variables to a common unit – binary.

‘a’ becomes 01100001 (via the neat asciitohex site)
The polynomial becomes 100000100110000010001110110110111

Step 3: Know the method

This part took me the longest. The actual mathematics was dead easy. It was figuring out what needed to be done and it none of this information was all in one place. It is now!

1. Reverse the input bits.
2. Pad the input with degree of polynomial  – 1.
3. XOR with 0xFFFFFFFF (In hardware this is used to set the memory to a known state).
4. Start the binary division and stop when you’ve fully divided the divisor into the dividend.
5. Take the remainder and XOR with 0xFFFFFFFF again.
6. Reverse the bits and then voila!

Step 4: An example

Attached is the above example worked through.

crc32 example (.ods)

crc32 example (.xlsx)