Cheacksum implementation in VHDL...

On Saturday, November 20, 2021 at 10:59:20 AM UTC-4, David Brown wrote:
On 20/11/2021 15:19, gnuarm.del...@gmail.com wrote:
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.

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.
Click to expand...

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
 
On 29/11/2021 17:06, gnuarm.del...@gmail.com wrote:
On Saturday, November 20, 2021 at 10:59:20 AM UTC-4, David Brown
wrote:
On 20/11/2021 15:19, gnuarm.del...@gmail.com wrote:
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.

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.

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.
Click to expand...

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.
 
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
Click to expand...

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.
 
On Monday, November 29, 2021 at 3:37:16 PM UTC-4, David Brown wrote:
On 29/11/2021 17:06, gnuarm.del...@gmail.com wrote:
On Saturday, November 20, 2021 at 10:59:20 AM UTC-4, David Brown
wrote:
On 20/11/2021 15:19, gnuarm.del...@gmail.com wrote:
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.

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.

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.

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.)
Click to expand...

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.
Click to expand...

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
 
You must log in or register to reply here.

Welcome to EDABoard.com

Sponsor

Back
Top