CRC is an FPGA PITA...

Kevin Neilson · Nov 21, 2021

The resources on CRCs are terrible and they explain things poorly. I\'ve had the opposite problem--the last one I did had to compute a CRC with 512 bits of input per cycle. In that case you need to do a matrix operation--the 512-bit input vector is summed with the shifted CRC and multiplied (over GF(2)) by a 512x32 binary matrix. I compute these generator matrices in Matlab: each row of the matrix is a shifted and reduced version of the generator poly. But the textbooks never seem to cover this stuff. The permutations of Endianness and inversions confuse things further.

For 1-bit-input operations, the matrix reduces to a row vector.

The problem with most resources is they don\'t answer some of these questions:

1. How is this doing a modulo operation? (The way they draw the diagrams, it\'s not clear that there are 2 things going on: a shift, which is a multiplication of the poly by x, and a subtraction, which is an XOR. Also, Horner\'s Method is being used, which isn\'t always clear.)
2. How is XOR a subtraction? (In a characteristic-2 field, addition and subtraction are the same.)
3. Why are we doing a modulo? (The point is to make the codeword, which is the message plus the CRC, a polynomial which has zeros (roots) at certain locations.)
4. That doesn\'t look like a polynomial! (It\'s not--it\'s the GF(2) binary coefficients of the polynomial written as a hex word. Even though the field being used might not be GF(2), the coefficients of the poly are in GF(2))..
5. Why not use a regular checksum? (A regular checksum doesn\'t have good minimum Hamming distance qualities. You can have 2 bit errors and still have a good checksum, but the CRC will show the error if the minimum Hamming distance of the CRC code is >=4.)

On Monday, December 14, 2020 at 2:02:23 PM UTC-7, gnuarm.del...@gmail.com wrote:

On Monday, December 14, 2020 at 2:59:02 AM UTC-5, David Brown wrote:
On 13/12/2020 21:06, Anssi Saari wrote:
\"gnuarm.del...@gmail.com\" <gnuarm.del...@gmail.com> writes:

Anyone else have similar problems?

I\'ve only used this one on FPGA designs: https://www.easics.com/crctool/

It generates a VHDL or Verilog implementation. Selectable polynomial
with some common ones predefined, selectable input data width.

BTW, with the standard bit order CRC32, polynomial 0x04C11DB7, the inverted output of an input \"ABCD1234\" (lsb first) would be 16#E928FF7E. Anyone care to confirm that?

Not really. I don\'t have anything I trust handy for that. From some
(software) experimentation years ago when I wanted to generate the same
CRC32 as is used in zip, rar and sfv files (and also Python\'s crc32
function in binascii package) the polynomial used was reversed from
that, 0xEDB88320.

That\'s the joy of CRC. With the same bit size and polynomial, you can
bit reverse the data coming in, byte reverse the incoming data (if it is
handled in larger lumps), bit reverse the generated crc, byte reverse
the generated crc, start with a non-zero shift register, and various
other options - in any combination. The result is equally strong
(though some people argue that starting with a non-zero shift register
is better because the crc of an all-zero input then varies by the length
of the input).

If you are handling the crc in two different ways (two different
implementations), you have to check that it really matches up, and be
prepared to fiddle the options a little until you get it right.

But the actual implementation is simple. In software, you usually do
this a byte at a time, with a lookup table. In an FPGA, a bitwise CRC
is a simple linear feedback register and should be straightforward - I\'d
expect an experienced FPGA designer will find it less effort to
implement it themselves than to use some random web page of questionable
quality. The key trick is to ignore the mathematical background for how
it works - polynomial division rings sound scary, but the implementation
is quite easy. (This means picking your polynomial from the wikipedia
page rather than guessing one yourself.)
Funny that you talk about the number of ways to permute the algorithm and then talk about how easy it is to design in an FPGA. Yeah, we had one error in the code which I found by inspection... eventually. That was only perhaps a quarter of the work though. The vast majority was trying to understand what all the references were doing since they often don\'t actually explain at the bit level detail. Hell, maybe half of them don\'t even allow hex inputs, must less talk about the bit ordering fed into the algorithm. I think this is because they are software people who are only thinking of CRC calculations on files of characters.

Like I said in the first post, there is little on the Internet to support debugging a CRC. I did finally find one site that would allow me to enter data in binary which means I could calculate on 1 bit at a time to check each stage of the computation.

That was the hard part, finding that one web site.
https://leventozturk.com/engineering/crc/

--

Rick C.

+ Get 1,000 miles of free Supercharging
+ Tesla referral code - https://ts.la/richard11209

Mike Perkins · Nov 21, 2021