CRC calculation

kt88seamp

So does a CRC work by this?

- The transmitter calculates a checksum by dividing the contents of the packet by a defined constant and places it in the packet.

- The transmitter transmits the packet.

- The reciever verifies the checksum by multiplying the contents of the packet by the same defined constant.

- If the two match, the packet is good.

I am new at this and I probably am missing something.

Mike Green

You've got the right general idea. A CRC is a particular kind of check-data calculation (Cyclical redundancy check). This is done by computing the value of a polynomial applied to the bits of the data (look up in the Wikipedia for details of the polynomials used). The calculated information is appended to the data and transmitted with the data. For reception, the CRC is calculated again from the data and the received CRC is compared to the calculated one. Parity is also used for error checking and correcting. There are other types of check data calculations, some of which can also be used for data correction. In that case, the differences between the original check data and the received check data can be used to correct the received data. Again, follow the links in the Wikipedia article to get more information and more details.

David B

I've found that you can get two very different explanations of how a CRC works, depending on whether you ask a mathematician or an engineer.

If you ask the mathematician, you'll get a detailed mathematical explanation phrased in terms of multiplications, divisions, remainders, polynomials, etc., but which may not be very helpful in implementing one in code or hardware.

But if you ask an engineer, you'll be shown how a serial stream of bits can be processed by doing a relatively simple one bit operation as each new bit arrives, resulting in a number that says the full packet is either good or no good.

Depending on your interest, one or the other may be more useful.

kt88seamp

What is the best method for checking this packet for errors? In other words, what should I divide it by? It will be transmitted via RF. I guess it is one of those CRC16's from Wikipedia.

< preamble > < data > < checksum >

Lets say the packet contains this data:

< 10101010 > < 10010011 > < computed checksum >

Rayman

Check out my YMODEM code, it has CRC16 in it:

http://forums.parallax.com/showthread.php?p=718391


Ray

▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔
My Prop Info&Apps: ·http://www.rayslogic.com/propeller/propeller.htm

My Prop Products:· http://www.rayslogic.com/Propeller/Products/Products.htm

James Newman

David B> Actually that seems like two different methods there. CRC checks are a specific algorithm that uses quite a bit of math to come up with a number that has an -extremely- low chance of being the same if any of the data is changed. The second thing you describe sounds more like a parity check. Parity is a very simple check where you append an extra bit to a few bits, that causes all of the bits to add to either an even or odd bit. If an even number of bits get corrupted in a a byte, the parity check will still hold.

kt88seamp> An actual crc check is more complicated, but yes, similar. Now I do wanna emphasize that you don't modify the data to be transmitted, this would just result in some sort of crappy encryption. Can't tell if that's what you where intending in the post or not.

Post Edited (James Newman) : 4/3/2010 12:21:20 AM GMT

Rayman

I think RF things like XBEE and Wifi GSX already have some sophisticated error checking in them... But, if you are doing real low level RF comms, you probably do need something like CRC16 as a minimum...

▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔
My Prop Info&Apps: ·http://www.rayslogic.com/propeller/propeller.htm

My Prop Products:· http://www.rayslogic.com/Propeller/Products/Products.htm

kt88seamp

I think I found something that may work, thanks to Bean.

http://forums.parallax.com/showthread.php?p=853681

I does not appear that if corrupt data is found, a retransmit will be requested due to latencies between switching modes. What does Bean mean by sending packets in burst? Does it mean send a bunch of packets, and verify them all in a batch instead of in real time?

Post Edited (kt88seamp) : 4/3/2010 4:38:09 AM GMT

Beau Schwabe

kt88seamp,

I'm not sure where I see your reference to 'Bean' in that link

You are correct though, there is no bi-directional handshaking to negotiate a re-transmit if the received data does not match the locally generated CRC.

I could not find in the thread where you mention "sending packets in burst?" ... typically though CRC is performed on a large data block instead of just a few BYTEs, so sending data packet bursts are not that uncommon. That said, a CRC is performed individually on each data packet and because the CRC routine is written in Propeller Assembly it can keep up in reasonable real time. (<--tested at 9600 baud wireless.)

▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔
Beau Schwabe

IC Layout Engineer
Parallax, Inc.

jazzed

Beau Schwabe (Parallax) said...
... That said, a CRC is performed individually on each data packet and because the CRC routine is written in Propeller Assembly it can keep up in reasonable real time. (<--tested at 9600 baud wireless.)

A bigger table based version would be even faster

▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔
May the road rise to meet you; may the sun shine on your back.
May you create something useful, even if it's just a hack.

Dave Hein

jazzed said...

A bigger table based version would be even faster

RFC 1662 contains an algorithm that uses a 256-word table ( http://tools.ietf.org/html/rfc1662·).· See section c.2.· With the table fcstab defined in a DAT section·the computation for each byte reduces to

fcs := (fcs >> 8) ^ fcstab[noparse][[/noparse](fcs ^ databyte) & $ff]

·

Cluso99

I implemented it in asm on a Z8 8MHz which was also doing modem control so the prop should be able to do it easily. No lookup tables were used.

▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔
Links to other interesting threads:

· Home of the MultiBladeProps: TriBlade,·RamBlade,·SixBlade, website
· Single Board Computer:·3 Propeller ICs·and a·TriBladeProp board (ZiCog Z80 Emulator)
· Prop Tools under Development or Completed (Index)
· Emulators: CPUs Z80 etc; Micros Altair etc;· Terminals·VT100 etc; (Index) ZiCog (Z80) , MoCog (6809)·
· Prop OS: SphinxOS·, PropDos , PropCmd··· Search the Propeller forums·(uses advanced Google search)
My cruising website is: ·www.bluemagic.biz·· MultiBlade Props: www.cluso.bluemagic.biz

Dave Hein

Cluso99 said...
I implemented it in asm on a Z8 8MHz which was also doing modem control so the prop should be able to do it easily. No lookup tables were used.

The implementation method depends on the ultimate application, and how many cycles you want to budget for CRC computation versus averything else that needs to be done.· I've used both the bit-by-bit method and the table lookup method on a super-scalar VLIW processor that also needed to encode video in real time.· The table lookup method saved a few cycles that could be used for video encoding.
Depending on the application, a bit-by-bit implementation in spin may be good enough.
Dave

jazzed

Beau's CRC thread is good to read and gets into the math of CRC calculations a little.
http://forums.parallax.com/showthread.php?p=853681

There are many ways to do some things. The way you choose depends on your goal.
Often programming requires a trade-off between size and speed.

The smallest non table driven Spin CRC method is slow but useful if you have lots of spare time.
The alternative table driven Spin CRC method is much faster if you have lots of spare memory.

The same non-table CRC algorithm to PASM is faster if you have a spare COG and extra HUB.
Beau's PASM CRC code which does this is here for reference:
http://forums.parallax.com/attachment.php?attachmentid=64921

A table driven Spin CRC method is reasonably fast and can be found here for reference:
http://forums.parallax.com/showthread.php?p=800272

A non table driven Spin CRC method is included at the end of Rayman's YModem.spin file here:
http://forums.parallax.com/showthread.php?p=718391

▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔
May the road rise to meet you; may the sun shine on your back.
May you create something useful, even if it's just a hack.

kt88seamp

I made a typo, its Beau. OOPS. Anyway, it was the new version of the TX, RX program. In the new version, the methods are just a simple TX and RX. How would I, if I were to write a program around it, do lets say an if statement to see if the data made it through intact.

jazzed

kt88seamp said...
I made a typo, its Beau. OOPS. Anyway, it was the new version of the TX, RX program. In the new version, the methods are just a simple TX and RX. How would I, if I were to write a program around it, do lets say an if statement to see if the data made it through intact.

It looks like he is discarding the data packet if the CRC is bad.
You could use RF_Transceiver.spin CRC_Valid after calling Recieve to tell if the the last packet was bad.

I assume you mean the latest version like here:
http://forums.parallax.com/showthread.php?p=856983

▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔
May the road rise to meet you; may the sun shine on your back.
May you create something useful, even if it's just a hack.

Beau Schwabe

That's correct, the packet is discarded if the CRC is bad. I implement a double receive buffer method, so that another application can read from the last "known to be good" buffer, while the opposing receive buffer is being loaded with the very newest data. This method is an easy way to manage the data and prevent any data collisions.

▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔
Beau Schwabe

IC Layout Engineer
Parallax, Inc.