1. Home
  2. Embedded Programming
  3. Table-based CRC Question

Table-based CRC Question

Hi All,

I am having some trouble figuring out how table-based CRC works, and hope that someone can point out where I am going wrong. Lets start by defining a few things:

Message: 1101011011 Polynomial: x^4 + x^1 + 1 (ie 10011) Augmented Message: 11010110110000 (add 'W' = 4 zeros) Padded Message: 0011010110110000 (extend to 16-bits)

These numbers may be familiar to some, as they are taken from the "Painless Guide to CRC Error Detection Algorithms". Now, lets start by working through the problem by hand. Note that '^' represents the XOR operation:

0011010110110000 ^ 10011 0001001110110000 ^ 10011 0000000010110000 ^ 10011 0000000000101000 ^ 10011 0000000000001110

Which gives the expected '1110' checksum. It is fairly trivial to write code that will perform this sort of bit-by-bit CRC generation. However, if we want to speed things up, we need to be able to work with more than a single bit at a time. It would be nice to be able to process the message byte-by-byte. This may be done using the following algorithm (again taken from the guide):

Algorithm

---------

  1. Shift the register left by one byte, reading in a new message byte.
  2. Use the top byte just rotated out of the register to index the table of 256 8-bit values.
  3. XOR the table value into the register.
  4. Goto 1 iff more augmented message bytes.

Now, as far as I understand it, the table index corresponds to every possible message byte (ie 2^8 combinations of bits). The table entry at a particular index contains the XOR sum of the polynomial offset according to the table index. For example, at table index '00110101' (the first byte of the padded message), the table entry would be:

00110101 Table index -------- 10011 | ^ 10011 | Only this bit gets XOR'ed together, ie ^ 10011 | do not include the index. ^ 10011 | -------- 00110000 Table entry

However, if you work through the algorithm with this table entry, you do not end up with the correct checksum. Now, I have tried all sorts of weird and wonderful combinations to try and get it to work, with no success. For example, I thought that you might need to include the index in the XOR calculation that is used to fill the table - however this did not work either.

Given that its apparent what the algorithm is trying to do when you look at the hand worked example at the top of this post, I am somewhat alarmed by my inability to figure out what I am doing wrong. Can anyone spot the problem?

- S

Reply to
Santiago
Loading thread data ...

I can't figure out, from your explanation, where you're going wrong.

But I can say _why_ table-based CRC calculations work, and maybe this will help.

They work because the CRC calculation is a linear operation over binary numbers that are added modulo 2 (or, for that matter, over any integer field that is added modulo N). While it's not linear in the sense that one is used to when one thinks of filter theory, it is linear in the sense that superposition works.

Because superposition works, if you know what the state of your CRC will be 8 ticks in the future given it's current state and an all-zero input, and you know what your CRC will be given a zero state and any given 8-bit input, then you can take those two numbers (polynomials) and XOR them (add them term-for-term), and get the state 8 ticks in the future with the given input.

What I'm having trouble remembering because it's been a long time since I've done it and I'd have to actually get out of this chair and exert myself to find out, is the details of how you utilize those two facts. If I recall correctly, the times that it's been useful is either when the future state of the CRC generator can be calculated from a shifted version of its present state, a table look-up of its most significant N bits, and a table lookup of the N bits coming in, or better yet if it can be calculated from a shifted version of its present state, and the XOR of it's N most significant bits and the N bits coming in.

(Come to think of it, I think that at worst you need one table each for each incoming N-tuple, and each N bits in the CRC state -- but don't take that as gospel; I'm feeling exceedingly lazy about thinking at the moment).

So I _think_ that what's missing is that you're not taking your CRC generator state into account properly, as well as the incoming bits.

--
Tim Wescott
Control system and signal processing consulting
www.wescottdesign.com
Reply to
Tim Wescott

The "painless guide" uses a 32 bit poly for its table driven CRC example. I'm no expert on CRC, but I am guessing you use of 4 bit poly is incompatible with an 8 bit table. Maybe would work if your table was 4 bits?

Reply to
Bob

The table entry for state S is generated by starting in state S, then taking the final state after N iterations, where N is the number of bits in the table index.

Consider a 4-bit CRC with characteristic polynomial 11001 and a start state of 0101 with the next 4 message bits ABCD; the middle 4 bits are the CRC state, and a lower case letter indicates inversion:

start: .... 0101 ABCD shift: ...0 101A BCD. xor: 0000 ...0 101A BCD. shift: ..01 01AB CD.. xor: 1001 ..01 11Ab CD.. shift: .011 1AbC D... xor: 1001 .011 0Abc D... shift: 0110 AbcD .... xor: 0000 0110 AbcD ....

The net result is that the final state is the next 4 message bits XOR'd with 0110, regardless of the values of those four bits (they didn't have a chance to affect the bits which are shifted out and thus influence which XORs are performed). So the table entry for a state of 0101 would be 0110, which would be the final state if ABCD was 0000.

HTH.

Reply to
Nobody

Hi There.

This is a brilliant example that has helped me to figure out what I had gone wrong - both practically, and conceptually. Thanks for your help, and to all the others who posted in reply too.

- S

Reply to
Santiago

8 bit table. Maybe would work if your table was 4 bits?

The length of the table determines how many bits you can do at the same time. (So you could use a 64K table with nowadays computers.) The width of the table entries is determined by the CRC. If it is a 32 bit CRC you need 32 bit entries. With the smallish CRC the OP cannot go wrong.

This is my Forth code, where the table is generated while compiling:

---------------------8R 1 RSHIFT R> 1 AND IF CRC32_POLYNOMIAL XOR THEN LOOP , LOOP \ For initial CRC and BUFFER COUNT pair, leave the updated CRC : CRC-MORE BOUNDS DO DUP I C@ XOR 0FF AND CELLS CRCTable + @ SWAP 8 RSHIFT XOR LOOP ; \ For BUFFER COUNT pair, leave the CRC . : CRC -1 ROT ROT CRC-MORE INVERT ; DECIMAL

---------------------8

Reply to
Albert van der Horst

ElectronDepot website is not affiliated with any of the manufacturers or service providers discussed here. All logos and trade names are the property of their respective owners.