Parallax RF Transceiver object using polynomial CRC method to reduce Data Error
Beau Schwabe
Posts: 6,573
Updated latest version here
This is in the early stages, but I wanted to put a CRC object together that provided a little bit stronger
error detection than just addition or XORing each data byte on top of the adjacent neighbour. So I've put together a CRC engine that uses polynomials written in Propeller assembly. Once you tell it the size of the packet and where the Data is as well as the Polynomial key it will automatically update a CRC result that can be appended to your data transmission. On the receive end, if you have the same Polynomial CRC Driver running you must use the same Polynomial key. By comparing the Received CRC value verses the locally calculated CRC value, you can determine if a data packet is valid or not.
The main CORE program is called 'CRC_polynomial.Spin' ... There are a couple of example RX and TX programs that use the RF Transceivers, they still need some work but get the idea across. The main program to try to incorporate and use is the 'CRC_polynomial.Spin' file.
What is CRC anyway? A CRC is an error-detecting code. It stands for cyclic redundancy check and there are many forms of CRC. Some have very weak error detecting abilities while others have very strong error detecting abilities. An example of a week error detection scheme would be the use of the Parity bit in serial transmission. In this form The Parity simply represents the total number of Bits indicating if they are ODD or EVEN. Another approach is simply to ADD all of the data bytes together and look at the LSB 8-Bits of the result. With each of the approaches mentioned, the error detecting gradually gets better and better, you still can't beat polynomial division when it comes to CRC. The computation resembles a long division operation in which the quotient is discarded and the remainder becomes the result, with the important distinction that the arithmetic used is the carry-less arithmetic.
Example:
Edit: Files updated on 11-05-2009
▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔
Beau Schwabe
IC Layout Engineer
Parallax, Inc.
Post Edited (Beau Schwabe (Parallax)) : 4/7/2010 8:42:02 PM GMT
This is in the early stages, but I wanted to put a CRC object together that provided a little bit stronger
error detection than just addition or XORing each data byte on top of the adjacent neighbour. So I've put together a CRC engine that uses polynomials written in Propeller assembly. Once you tell it the size of the packet and where the Data is as well as the Polynomial key it will automatically update a CRC result that can be appended to your data transmission. On the receive end, if you have the same Polynomial CRC Driver running you must use the same Polynomial key. By comparing the Received CRC value verses the locally calculated CRC value, you can determine if a data packet is valid or not.
The main CORE program is called 'CRC_polynomial.Spin' ... There are a couple of example RX and TX programs that use the RF Transceivers, they still need some work but get the idea across. The main program to try to incorporate and use is the 'CRC_polynomial.Spin' file.
What is CRC anyway? A CRC is an error-detecting code. It stands for cyclic redundancy check and there are many forms of CRC. Some have very weak error detecting abilities while others have very strong error detecting abilities. An example of a week error detection scheme would be the use of the Parity bit in serial transmission. In this form The Parity simply represents the total number of Bits indicating if they are ODD or EVEN. Another approach is simply to ADD all of the data bytes together and look at the LSB 8-Bits of the result. With each of the approaches mentioned, the error detecting gradually gets better and better, you still can't beat polynomial division when it comes to CRC. The computation resembles a long division operation in which the quotient is discarded and the remainder becomes the result, with the important distinction that the arithmetic used is the carry-less arithmetic.
Example:
Polynomial (Must match the sender as well as the receiver)
│
 10101100 <-- quotient (discarded we don't care what this value is)
_______________
11011 ) 111001010000 <-- dividend (The DATA)
11011
-----
1111010000
11011
-----
10110000
11011
-----
1101000
11011
-----
100 <-- CRC (remainder or what we append to the data sent)
Edit: Files updated on 11-05-2009
▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔
Beau Schwabe
IC Layout Engineer
Parallax, Inc.
Post Edited (Beau Schwabe (Parallax)) : 4/7/2010 8:42:02 PM GMT
Comments
Here is the SPIN version of the CORE program before I converted it to Spin so you can get a better idea of what the Propeller assembly is doing...
[b]CON[/b] [b]_CLKMODE[/b] = [b]XTAL1[/b] + [b]PLL16X[/b] [b]_XINFREQ[/b] = 5_000_000 PacketLength = 2 Polinomial = %11011 [b]OBJ[/b] Term : "FullDuplexSerial.Spin" [b]VAR[/b] [b]byte[/b] Dividend[noparse][[/noparse]­PacketLength] 'Data to Send [b]PUB[/b] MOD_Test|TempPoly,TempDividend,BitPoly,BitDividend,Remainder,Index Term.start(31, 30, 0, 38400) '' Initialize serial communication to the PC Dividend[noparse][[/noparse]­0] := %00001110 'MSB Dividend[noparse][[/noparse]­1] := %01010000 'LSB 0100 ' Dividend[noparse][[/noparse]­0] := %00000001 'MSB ' Dividend[noparse][[/noparse]­1] := %00100111 'LSB 1110 TempPoly := Polinomial TempDividend := Dividend[noparse][[/noparse]­0] BitPoly := BitCount(TempPoly) BitDividend := BitCount(TempDividend) '------------------------------------------------------ [b]repeat[/b] Index [b]from[/b] 1 to PacketLength [b]repeat[/b] [b]while[/b] BitDividend => BitPoly TempPoly := Polinomial << (BitDividend-BitPoly) TempDividend ^= TempPoly BitDividend := BitCount(TempDividend) TempDividend := TempDividend << 8 | Dividend[noparse][[/noparse]­Index] BitDividend := BitCount(TempDividend) '------------------------------------------------------ Remainder := TempDividend >> 8 '--------------------------------------------------Display Output Data--------------------------------------------- [b]repeat[/b] Term.tx(1) ' Position cursur at the Home position Term.bin(Remainder,32) Term.[b]str[/b]([b]string[/b](" ")) Term.tx(13) ' Send the RETURN key code to the DEBUG terminal [b]PUB[/b] BitCount(Number)|BitWeight 'Get number of bits in Number [b]Result[/b] := 0 BitWeight := 1 [b]repeat[/b] [b]while[/b] BitWeight =< Number [b]Result[/b]++ BitWeight <<= 1▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔
Beau Schwabe
IC Layout Engineer
Parallax, Inc.
Then you can hardcode the summation of bits like:
.... oh .... now I understand ... it does not give you the number of bits, but the position of the highest bit. Anyway ... BitCount is called several times, so it would be good to optimize.
That sounds like a binary search would be helpful as for searching in·32 items·it only needs 5 steps.
I think number of bits is correct, it's not the number of bits that are "1", it's the total minimal number of bits required to represent the number.
Anyway, yes, I think a lookup table would work here, and there's probably a simple formula that could be applied that I just haven't messed with in detail yet instead of the iterative process I'm currently using.
The main thing I was looking for was functionality with the idea in mind that the bandwidth of the RF is limited to about 10kBits/sec. With that in mind there is plenty of overhead when calculating the CRC value.
Edit...
This code reduces the iteration loop from 20 clocks to 12 clocks almost in half
'-------------------------Detect Bit Width--------------------------------------------------------- DetectWidth 't1 contains the value we want to know the bit width of cmp t1, #0 wz mov _BitWidth, #0 if_z jmp #DetectWidth_ret mov t2, #0 '----------------------------------------------------------------------------------------- WidthLoop rol t1, #1 wc add t2, #1 'increment BitWidth if_nc jmp #WidthLoop '----------------------------------------------------------------------------------------- mov _BitWidth, #32 sub _BitWidth, t2 DetectWidth_ret ret '_BitWidth returns the bit width '--------------------------------------------------------------------------------------------------▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔
Beau Schwabe
IC Layout Engineer
Parallax, Inc.
Post Edited (Beau Schwabe (Parallax)) : 11/4/2009 10:32:23 PM GMT
Revision History:
Version 1.0.a - (10-30-2009) original file created
Version 1.0.b - (11-04-2009) improved bit width routine
Version 1.0.c - (11-05-2009) optimized flow of long division routine
MagIO2,
I have been thinking, and I'm not sure that a lookup table would help much since the BitWidth could technically be close to 16 Bits wide and higher as I change the program to allow polynomial keys wider than 16 Bits.
▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔
Beau Schwabe
IC Layout Engineer
Parallax, Inc.
You've probably been down the CRC16 table road, but it is worth mentioning.
Here's a link to my table driven CCITT CRC16 Spin code. The table used is 512 bytes.
http://forums.parallax.com/showthread.php?p=800272
Of course CRC also has limits. CRC16 can have duplicate results for < 1000 byte packets.
For packets > 1000 bytes, CRC32 should be considered.
Wikipedia has a good article on CRC en.wikipedia.org/wiki/Cyclic_redundancy_check
Cheers.
Post Edited (jazzed) : 11/5/2009 10:52:11 AM GMT
I looked at your code, but I don't see the same polynomial listed here
wikipedia shows that for CRC16 CCITT that the polynomial should be...
I would be curious to compare the result of your CRC program with the program that I am running against the same 512 Byte data packet.
▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔
Beau Schwabe
IC Layout Engineer
Parallax, Inc.
Post Edited (Beau Schwabe (Parallax)) : 11/5/2009 6:22:14 PM GMT
▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔
My Prop Info&Apps: ·http://www.rayslogic.com/propeller/propeller.htm
The one in my code is CRC-CCITT. Using CRC16 poly instead works too.
You can test your results here to see if the CRC is as expected.
Ok, I understand there are several different polynomial forms that can be used (even called the same thing). Which helps the confusion factor.
Thanks for the link
I'm still trying to figure out how 0x1021 equates to ---> x16 + x12 + x5 + 1
x16 + x12 + x5 + 1 = %10001000000100001 0x1021 = %00001000000100001 ^ | Is the MSB assumed to be 1 ? I guess it is, that makes sense. So it would be 0x11021▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔
Beau Schwabe
IC Layout Engineer
Parallax, Inc.
Post Edited (Beau Schwabe (Parallax)) : 11/5/2009 6:18:33 PM GMT
Post Edited (jazzed) : 11/5/2009 6:28:11 PM GMT
I had to lay down a few basic principles and a few of them evolved in order to decide what the most logical approach to this would be. Some priority obligations have limited my output on this but I hope to have something very soon. The basic building blocks are mostly in play, they just need to be pieced together. Included is a flow diagram of how I think things should happen, and I've posted it in a few other locations and haven't had anybody knock it down >yet< as to some fundamental thing I might be overlooking, so for now I will use it as the code template for how it's going to work. Perhaps a future implementation would be bi-directional Full-duplex in continuous mode.
Basically there are two modes: Normal and continuous
TX side:
- Will send the data you place in a buffer and append the CRC when you issue a SEND command (who da thunk?)
- A small amount of handshaking will transpire and the TX unit will keep sending the data packet until an acknowledgement has been received or until a number of user set retries have expired.
- If an acknowledgement is received and the TX unit is in continuous mode it just starts all over again, otherwise the TX command has completed.
RX side:
- As data is received it goes into one of two buffers (two buffers explained later) If the received CRC does not match the locally calculated CRC, the receiver goes into a wait for sync loop (beginning of Flow)... This in turn generates a timeout on the TX side so that hopefully the packet will be re-transmitted.
- If the CRC is valid, the RX module goes into TX mode and sends an acknowledgement to the TX unit which 'should' be waiting in receive mode for the acknowledgement.
- If the RX unit is in continuous mode it will return to the beginning of the flow where it will wait for the next incoming SYNC signal, otherwise the RX command has completed.
Note:
- Treat 'Normal' mode as a standard Serial connection in a single threaded application. - Treat 'Continuous' mode similar to a live wire mode, but apply that live wire analogy to a user defined group of BYTES that just magically appear in a specific RAM location. - Continuous mode should also be launched in its own cog - The reason for having two receive buffers is to ensure that at any given time the data in one of them is the most recent and valid. If the data comes in, and the CRC is not valid, then we don't want to read the data from this buffer, but instead the other buffer... whichever one is NOT being written to before the CRC passes it. Toggling this on every other valid CRC is a simple way to manage this.Revision History: Version 1.0.a - (10-30-2009) original file created Version 1.0.b - (11-04-2009) improved bit width routine Version 1.0.c - (11-05-2009) optimized flow of long division routine Version 1.0.d - (11-06-2009) adjusted CRC to return LONG value instead of BYTE value this allows for the full remainder to be returned for polynomials greater than 1 BYTE wide. Version 1.0.e - (11-13-2009) converted CRC engine driver for one shot mode▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔
Beau Schwabe
IC Layout Engineer
Parallax, Inc.
Post Edited (Beau Schwabe (Parallax)) : 11/13/2009 8:10:09 AM GMT
Best Regards, David
I tried to implement a Half Duplex mode with acknowledgement from the receiver to verify that Data had been received and was valid, but the RF Transceivers have problems switching modes mid stream from a Transmitter to a Receiver and then back to a Transmitter. By the time they re-negotiate it ends up being incredibly slow. In practice, with the CRC applied and the double buffering on the receiver, I have not received any data errors with any of the data that does get through.
What you can do (left for the user to exercise) is to send packets in burst mode from point A to point B and then reverse the direction.
The Code has been reduced to simple Send, Receive, Put, and Get commands. You basically just treat the Put and Get like an address "on the other end". Both Send and Receive update from one database to the other database via the Transceivers.
As always, please provide feedback where applicable, and I will post this object to the OBEX after a trial period.
Enjoy!
▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔
Beau Schwabe
IC Layout Engineer
Parallax, Inc.
Post Edited (Beau Schwabe (Parallax)) : 11/19/2009 5:19:52 AM GMT
▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔
Beau Schwabe
IC Layout Engineer
Parallax, Inc.
Post Edited (Beau Schwabe (Parallax)) : 4/27/2010 4:44:32 AM GMT
I'd like to do this for streaming ADC readings over USB using an FTDI chip (using either VCP or D2XX driver)