Re: Cheacksum implementation in VHDL

[Vincent Li]

onsdag den 5. april 2000 kl. 09.00.00 UTC+2 skrev Ron:
> I'm looking for checksum implementation in VHDL (or at least the basic rules
> to build one).
> Regards
> Ron
rip

[Vincent Li]

2nd this

[Mike Perkins]

Do you really mean checksum, or CRC?

Checksum is easy to understand, CRC less so.

I confess it's a long time since I used/looked up first principles to
generate CRCs and use this website:
https://www.easics.com/crctool/

--
Mike Perkins
Video Solutions Ltd
www.videosolutions.ltd.uk

[gnuarm.del...@gmail.com]

On Wednesday, November 10, 2021 at 12:39:22 PM UTC-4, Mike Perkins wrote:
> On 09/11/2021 14:14, Vincent Li wrote:
> > onsdag den 5. april 2000 kl. 09.00.00 UTC+2 skrev Ron:
> >> I'm looking for checksum implementation in VHDL (or at least the basic rules
> >> to build one).
> >> Regards
> >> Ron
> > rip
> Do you really mean checksum, or CRC?
>
> Checksum is easy to understand, CRC less so.
>
> I confess it's a long time since I used/looked up first principles to
> generate CRCs and use this website:
> https://www.easics.com/crctool/

The only hard part to CRC is understanding the nomenclature. There are several options for computing CRCs based on polarity and direction. Specifying this is not consistent and often it is assumed that you know the "standard". With the combinations it can be very hard to get it right and be able to verify that. So by all means make sure you verify your results in the simplest medium you can before proceeding to anything more complex like coding.

--

Rick C.

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

[David Brown]

That's what I usually see as a challenge for CRC's - getting different
implementations to agree. If you can use the same implementation on all
parts, then the details (bit ordering, polarity, polynomial, etc.) don't
matter. My usual solution is using a lookup table of 256 entries. It's
simple for 8-bit CRC's, and not too difficult for 16-bit or 32-bit
CRC's, and should be as straightforward to make on an FPGA as it is in
C, Python, or whatever programming language takes your fancy. That
makes it easy to get matching results on multiple systems. But it would
take a bit more FPGA resources than a bit-wise linear feedback register.

[gnuarm.del...@gmail.com]

Meh... it still doesn't assure equivalent implementations. I did this just a year or so ago and had the hardest time with it because of all these details and the fact that there is no consistent nomenclature for it all. In FPGAs you think in terms of shifting bits and XORing stuff. The software implementations typically do the table lookup and twiddle things in ways that suit byte organizations rather than matching the algorithm/math description very much. Given it is important as to which bits you pick for your output and which way you shift the data and where the data enters the shifter... maybe I'm just getting old and the hair I no longer see on the outside is growing on the inside mucking up the works.

In contrast I found LFSR to be very simple indeed, even if calculated 32 bits at a time and it always worked, matching other implementations.

--

Rick C.

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

[David Brown]

I guess experience varies, and the algorithm you find simplest will
depend on that experience. The "best" algorithm will also depend on
whether your data is coming in as a bitstream, or in bytes, or larger
lumps, along with the size and speed requirements.

An 8-bit CRC done by table lookup involves a single 256-entry by 8-bit
wide table - for each incoming byte, you xor with the current CRC
register then look it up in the table to get the new CRC value. IIRC, a
32-bit CRC will involve 4 tables, each 256 entries of 32 bits, and
you'll have 4 xors, all of which can be done in parallel. I think that
to get the same performance in a bit-wise LFSR you'd need 32 of them
chained in a pipeline. (Correct me if that's wrong.)

Still, whichever way you implement the CRC, it's often best if you can
replicate the same algorithm at both ends - whether it be
software-friendly lookup tables in an FPGA, or FPGA-friendly LFSR's in
software. Then you don't need to worry about the different naming for
all the little details of bit ordering, inversion, etc.

[Stef]

On 2021-11-20 David Brown wrote in comp.arch.fpga:

>
> That's what I usually see as a challenge for CRC's - getting different
> implementations to agree. If you can use the same implementation on all
> parts, then the details (bit ordering, polarity, polynomial, etc.) don't
> matter. My usual solution is using a lookup table of 256 entries. It's

This site is very helpfull when trying to figure out which
implementation to use.
https://reveng.sourceforge.io/crc-catalogue/legend.htm

--
Stef

We are Microsoft. Unix is irrelevant. Openness is futile. Prepare
to be assimilated.

[gnuarm.del...@gmail.com]

I don't know what you mean about equivalent performance in a "bit-wise LFSR". Why are you conflating the two things? An LFSR can be done as many bits at a time as you wish.

> Still, whichever way you implement the CRC, it's often best if you can
> replicate the same algorithm at both ends - whether it be
> software-friendly lookup tables in an FPGA, or FPGA-friendly LFSR's in
> software. Then you don't need to worry about the different naming for
> all the little details of bit ordering, inversion, etc.

Sure, but different horses for different courses. What is best in an FPGA is not always best in software, etc. It's not hard to get the two ends working together as much as it is to find good reference data to test against to assure you are actually implementing the correct algorithm, correctly.

When you say "both ends", you do realize that often CRCs are used in standards where you are only working on one end and the other is existing equipment. Then you have to understand the terminology in all it's glory to get it right.

--

Rick C.

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