help with error checking GPS data over audio link

[micromuc]

I am sending GPS data over an audio link using a modem ic. On the TX side I have broken down the GPS data and I’m sending just the speed, heading and altitude. If it matters, I’m dropping the decimal numbers and only working with whole numbers to make things easier to convert later. My problem is that the wireless link is not the best and the data gets corrupted at times. What I’m doing is sending the speed, heading and altitude three times to the RX unit then I want to compare them against each other. Since my GPS updates every 2 seconds there are no issues with timing. I am successfully sending the data to the RX unit then outputting to the PC now. I just don’t know the best way to compare the data or the best format to send it. Eventually my plan is to send it to a LCD not a PC. At this time the program consists of three serin (1200bps) lines, one for each $1, $2, and $3; then three serout (4800bps) commands to view the data. It would be great if I could compare the speed, heading and altitude individually rather than the whole line. I don’t mind if I drop a couple of updates here and there I just don’t want to display garbage on the screen. Any help would be greatly appreciated.
·
Best regards,
Mark
·
·
Here is the format it is sent/received in. I am planning to change the 1,2,3 to A,B,C;
·
$1,speed,heading,altitude
$2,speed,heading,altitude
$3,speed,heading,altitude
·
·
Here is a snippet of some actual data transmitted to the receive unit and output to the PC. As you can see it makes it through 2 out of 3 times most of the time.;
·
$1,2,351,334
$2,2,351,334
$3,2,¦Sbššâj
·
$1,2<357,334
$2,2,357,334
$3,2,357,334
·
w¿ñ$1,2,355,¦&SHø
$2,2,355,334
$3,2,355,334
·
ÿ$1,1,353,333
$2,1,353,333
$3,1,353,333
·
$1,1,35Miššj
$2,1,355,333
$3,1,355,333
·
$1,1,11–¦&¦Hø
$2,1,11,332
$3,1,11,332
·
ø$1.1,29,332
$2,1,29*332
$3,1,29,33¶-
ã
·
·
·

[Jim McCorison]

What you want is a Cyclical Redundancy Check, or CRC. It is a method of checking for data corruption. You calculate the CRC, then transmit the data and the CRC value. The receiving side recalculates the CRC on the received data and compares it to the transmitted CRC. If it matches, the data is good. You can read more detail about it, including a sample routine written in pseudocode on Wikipedia at en.wikipedia.org/wiki/Cyclic_redundancy_check (http://en.wikipedia.org/wiki/Cyclic_redundancy_check). I've never written on as I've always had a system function that implements it. I'm not sure if it can be written on a stamp.

You could implement a much simpler checksum. This is just mathematically adding up all the bytes to be transmitted, ignoring the overflow. The resulting checksum byte is used just like a CRC value mentioned above. Checksum is quick and easy, but there are various types of data corruptions that it will not catch. Still, it would be easy to implement on a Stamp and may meet your needs,

Jim

[micromuc]

Thanks Jim,

I think I'll try the checksum. I'm very new to this stuff and as you stated it would be the easiest to implement. So, I need to create a checksum to send with my data over my wireless link. I have three to five string variables to send. I will not know the length of the strings as they will always be changing. Can I just add the strings and save the result as a word or byte? For example;
·
spd········ var byte
deg········ var byte
alt········ ··var byte
cs········· ·var word
·
‘serin my data as string variables
cs = spd + deg + alt
serout Pinout,baudout,["$A,",str spd,",",str deg,",",str alt,"*",cs,"*",13,10]···············
···
·
Will this work? If anyone has the knowledge to do this please help. If I'm way off base please let me know. This checksum thing has got me stumped. I’m new to programming and don’t know how to proceed.
·
Regards,
Mark

[Jim McCorison]

Mark,

In rereading your first posting, you say you want to ultimately transmit the data to an LCD. You'll be having a stamp (or some sort of processor) receiving, verifying and formating the data for display right? I don't see anyway around that part, so let's go with that assumption.

If you don't know how long the transmitted data string is, the traditional approach would be to transmit a length first, or, more usually, to transmit an "end of transmission" (EOT) code. However, in your case you say it will be either 3 or 5 bytes. I'd just transmit 5 bytes every time. Leave the unused bytes zero.

Also, when you calculate your checksum, you want to calculate it for everything you transmit. After all, if the $A is a command code, you wouldn't want a glitched bit to turn the "A" into a "C". I'd also leave out the all the formatting that isn't absolutely necessary. The more formatting included, the more bytes are transmitted, and the more chance for a glitch. So, instead you might do:


txHdr CON "$"
txCode CON "A"
spd VAR Byte
deg VAR Byte
alt VAR Byte
var4 VAR Byte
var5 VAR Byte
cs VAR Byte

cs = txHdr + txCode + spd + deg + alt + var4 + var5

serout Pinout, baudout, [txHdr, txCode, spd, deg, alt, var4, var5, cs]

' And the receive side would be:

GetData:

serin Pinout, baudout, [txHdr, txCode, spd, deg, alt, var4, var5, cs]

chkCs = txHdr + txCode + spd + deg + alt + var4 + var5

IF chkCs <> cs THEN GetData





I'm assuming that the "$A" has some kind of significance in the final product. Similarly, the 13 and 10 of course won't be necessary for the stamp to stamp transmission, should would be dropped in the final form.

Please note that my grasp of the SEROUT and SERIN commands is quite limited, so don't take my coding on them as gospel. Perhaps one of the others with more experience with these commands can chime in and let you know how much of a cock-up I've made of them. http://forums.parallax.com/images/smilies/smile.gif
Jim

[micromuc]

Thanks Jim,

Jim or anyone tha can help, errors are still getting through. I have posted the program info for the TX and RX side of this project. The problem I am having is calculating a checksum that works. Please read through and you will see my problem. I am new to programming so I may be doing something stupid. Please let me know how to correctly calculate a checksum for my application.

Here is the transmit side information. I acquire data from the GPS at 4800bps then sending it out at 1200bps. I have no problems with this working. I acquire the data and save it as string. I also calculate a checksum by just adding the strings together and with three numbers I made up. I send out the “$A,” in front of the data because I am using the WAIT (“$A,”) on the receive side as a marker to start saving data. I also am sending the 13,10 to make reading the info on HyperTerminal easier at the RX side. They will be dropped once I get things working. Because there is a 2 second period between GPS updates I am sending the data three times before waiting to acquire GPS data again.

TX CODE ----------------------------------------------------------------

vld var byte
spd var byte[8]
deg var byte[8]
alt var byte[8]
cs var byte
loop var byte

start:
SerIn GPSin,baudIN,3000,start,[WAIT("$GPRMC,"),WAIT(","),str vld\2\",",WAIT(","),WAIT(","),WAIT(","),WAIT(","),str spd\8\".",WAIT(","),str deg\8\"."]
SerIn GPSin,baudIN,3000,start,[WAIT("$GPGGA,"),WAIT(","),WAIT(","),WAIT(","),WAIT(","),WAIT(","),WAIT(","),WAIT(","),WAIT(","),str alt\8\"."]

if vld = 86 then start 'if gps signal not valid then wait for valid signal before sending data

cs = (spd + 15) + (deg + 17) + (alt + 19) ‘numbers 15,17,19 are made up by me

for loop = 1 to 3
serout GPSout,baudOUT,["$A,",str spd,",",str deg,",",str alt,"*",cs,"#",13,10]
pause 50
next loop
goto start

END

-------------------------------------------------------------

Now on the RX side I serial in the data that was sent out above. I WAIT for the “$A,” then save the spd, deg and alt as strings. Next I run the same checksum calculation on the strings and save the result. Then I compare the checksum (cs) that was calculated and sent from the TX to the checksum (csRX) calculated at the RX. For now I am just outputting the data out to HyperTerminal. The problem is that the checksum calculated at the TX and RX will match sometimes but the data has errors. I have posted an example of this under the RX code.

RX CODE -------------------------------------------------------------

spd var byte[8]
deg var byte[8]
alt var byte[8]
cs var byte[16]
csRX var byte

start:
SerIn GPSin,baudIN,2500,start,[WAIT("$A,"),str spd\8\",",str deg\8\",",str alt\8\"*",str cs\16\"#"]

csRX = (spd + 15) + (deg + 17) + (alt + 19)

serout GPSout,baudOUT,[str spd,",", str deg,",",str alt,"*",#cs,",",#csRX,13,10]
goto start


END

-------------------------------------------------------------


Here is a copy of what I captured in HyperTerminal. I have BOLD faced the lines that data was bad but the checksums are equal. Any help is greatly appreciated.

Here is the format it should be in;
Spd,Deg,Alt*cs,csRX


0,147,#51*135,183
0,147,351*199,199
0,147,351*199,199
0,147,351*199,199
0,147,351*135,199
0,147,351*135,199
0,147,351*199,199
0,147,35!*199,199·
0,147,351*199,199
0,147,#51*135,183
0,147,351*135,199
0,147,35!*199,199
0,147,351*199,199
0,147,35!*199,199
0,147,351*199,199
0,147,351*199,199
0,147,351*135,199
0,147,35!*199,199
0,147,351*199,199
0,147,351*199,199
0,147,351*135,199
0,147,351*135,199
0,147,351*135,199
0,147,351*199,199
0,147,351*199,199
0,147,351*199,199
0,147,351*135,199
0,147,35!*199,199
0,147,351*199,199
0,147,#51*199,183
0,147,35!*199,199
0,147,351*135,199
0,147,35!*199,199
0,147,351*199,199
0,147,35!*199,199
0,147,351*199,199
0,!47,351*199,183
0,147,35!*199,199
0,147,351*199,199
0,147,351*135,199
2,303,351*203,203
2,303,351*139,203
2,303,35!*203,203
d±š_šb4ª ,ŠRZ7©Høÿd±š_šb4ª ,ÿÿÿÝÿ$A,ŠRZ7©Høÿd±š_šb4ª *50,32
",303,351*203,187
r,354,351*203,11
2,354Tͪ
R2,Z7©Hø$A,354Tͪ
R2*50,242
2,356,351*203,203
2,35H±šªŠR2,Z7©Hø$Al35H±šªŠR2*2,242
2,355,35!*203,203
2,355,351*203,203
2,355,351*203,203
2,348,351*203,203
2,348,351*139,203
2,348,351*203,203
2,348,351*203,203
2,348,351*203,203
2,349,351*203,203
2,349,#51*139,187
2,349,351*203,203
2,309,ci`©[7©H309*248,251
2,349,351*203,203
2,349,351*203,203
",34=XͪŠR",Z7©@øÿÿÿ34=XͪŠR"*248,226
2,349,351*139,203
2,s49,35!*203,11
2,349,351*203,203
28Í¢ÊBšªì,ŠÒZ7©Høô28Í¢ÊBšªì,ýÿþ$A,2,ŠÒZ7©Høô28Í¢ÊB šªì*51,236
2,349,35!*203,203
2,349,351*203,203
2,349,351*203,203
2,349,351*139,203
",349,351(Ë#
349*36,187
2,349,351*203,203
2,3¤6-351*2,Ë#
$A,23¤6-351*2*12,99
0,3ÇÝb_ªŠR0,Z7©Hø$A,3ÇÝb_ªŠR0*34,240
2,335,351*203,203
",3#5,351*203,187
1,336,351*202,202
1,336,35!*202,202
!,336,351*202,186
2,0,351*200,200
2, ,351*200,184
2,0,351*200,200
",357,351*139,187
2,357,351*203,203
2,357,351*203,203
2ì356,351*‹#
2ì356,$A,2,356351*‹#
2ì356*44,188
2,356,350*139,203
2,3kÙb_U_’2,Z1©Hø$A,3kÙb_U_’2*50,242
2,fÕªb_"úV2,Z7©Hø$A,fÕªb_"úV2*50,37
2,0,348*200,200
1,7,346*206,206
1,7,346*206,206
!,245,345*201,185
1,250,#45*217,185
3,178,344*202,202
3,178,344*202,202
0,74LfÑšRj0,7©Èø$A,074LfÑšRj0*44,209
0,74,343*205,205
0,74,343*205,205
0,74,343*205,205
0,74,343*205,205
0,74,343*205,205
0,74,34#+Í#
74*36,205
0,74,34c*205,205
0,7h±š¢šRj0,7©Hø$A,07h±š¢šRj0*44,209
0,74,343*205,205
0,74,343*205,205
0,74,343*205,205
1,357,343*138,202
1,357,343*202,202
1,357,343*202,202
1,357,343*202,202
1,359,343*202,202
1,359,s4g«R7©H359*248,10
2,!79,342*201,185
2,1?9,342*201,201
2,179,342*201,201
2,171,342*201,201
2,171,;42*201,209
2,17!,34"*201,201
2,165,34-:É#
165*36,201
2,165,341*201,201
2,106,740*201,205
2<q06$34„, J’#
þü2<q06$34„,ÿÿ$A,2,8 J’#
þü2<q06$34„*51,132
2,83,340*208,208
1,72,340*206,206
1,72,340*206,206
1,72,340*206,206
2,179,342*201,201
2,171,342*201,201
2,171,;42*201,209
2,17!,34"*201,201
2,165,34-:É#
165*36,201
2,165,341*201,201
2,106,740*201,205
2<q06$34„, J’#
þü2<q06$34„,ÿÿ$A,2,8 J’#
þü2<q06$34„*51,132
2,83,340*208,208
1,72,340*206,206
1,72,340*206,206
1,72,340*206,206

Post Edited (micromuc) : 2/27/2005 2:23:38 AM GMT

[Jim McCorison]

Mark,

I would request that you reread my previous post. Pertinent points are:

1) Checksum eveything that is transmitted. That includes the '$A' and the various puncuation symbols. You can skip the 10 and 13 for now as they will go away. I would also reiterate that you should keep your transmitted data to a minimum. If the puncuation ('*', ',') aren't necesary, other than for your eyes in testing, I'd not included them.

2) You are not verifying the check sum on the receive side. Look at my code after getdata:. If the recieved checksum doesn't match the transmitted checksum you want to through away the transmission, not just pass it on.

I noticed you've change your GPS data to be arrays of 8 byte. Why? What is the exact format of the data received from the GPS? As I said before, I'm not a whiz with SEROUT / SERIN so I don't understand what you are trying to accomplish by using the 'STR' modifier.

I don't know why you are adding in the values 15, 17, and 19 when calculating the checksum. What are you trying to accomplish by this?

Jim

[Forrest]

You're hurting yourself by adding the values 15, 17 and 19 to your data to calculate the checksum. It's no coincidence that the bad data has an ASCII value that's precisely 16 higher (ASCII of ! is 33 and ASCII of 1 is 48).

Here's a link to a QBASIC program for Xmodem (an old file transfer protocal) that you should be able to modify and shorten for your use. Just concentrate on the FUNCTION CalcCheckSum and FUNCTION CalcCRC& that generates 8, 16 and 32 bit CRC's at www.qbasic.com/files/xmodem.bas (http://www.qbasic.com/files/xmodem.bas)

[micromuc]

Jim,
·
Okay, I missed that. I thought calculating the “$A,” and “,” was not necessary because they are not used on the RX side. They are there as a separator between data (“,”). If for some reason one of these is corrupted in transmission the checksums don’t add up because two strings will run together. If the “$A,” is not sent or corrupt the RX just waits for it and will go no further. From what I understand I need something to separate each piece of data. I was using the same format that the GPS puts out. It puts a “,” between each piece of data. If I don’t use “,” how would I know where each str starts and ends? Like I said I am new to this so please correct me if I’m wrong.
·
I know I’m not verifying the checksum at this time, although I thank you for the example. I will use it when I get things worked out. At this time I want to see everything that comes through. That is the only reason it is not being used.
·
Why am I using arrays of eight bytes? This is one thing I may be doing totally wrong (in addition to the checksum). Here is a description of why. Please tell me if you understand. Sometimes I’m not good at conveying what I’m trying to do. The GPS separates its data by “,”. The data, take for instance speed, can be one digit or three. Basically I don’t know how many digits it will be. I don’t want to use DEC because I may want to pass the speed with the decimal and remainder digits. I also may want to send data that are not numbers that are sent from the GPS at a later date. So I chose to take each piece in as a string using the characters “,” between data as a stop. For speed I use “.” as my stop because I want to drop the decimal to make converting to mph easier. I will do this conversion on the RX side once things are working. So the only way I could see to input an unknown length of data into a string was too purposely make the length of the string longer than what I know is going to be sent. Then I rely on the stop to end the str. This will also let me use different GPS types on the same circuit. I think J…
·
Here is the RMC sentence sent by my GPS;
$GPRMC,033652,A,3556.4105,N,08402.6662,W,0.0,172.5 ,240105,4.9,W,A*71
·
Here is what each piece means;
$GPRMC,time,valid_signal,lat,N,long,W,speed,degree s,date,mag_variation,W,newlabel*checksum(*71)
·
·
·
Jim and Forrest,
·
I knew I was really doing something stupid with the 15,17,19. I was playing around with different ways to calculate the CS. It seemed when I did this that less errors were getting through so I left it. I guess I need to just remove it.
·
·
Forrest,
·
Thanks for the link I’ll check it out.
·
Mark

[micromuc]

Well Forest, I looked at the code and I have to say I have no idea what is going on. I just don't have the experience with programming. Maybe someone can show me how to implement this for my application. I have posted the section you wanted me to look at below.
·
Another thing I found while searching was to XOR the bits. This is how the GPS checksum is created. Does anyone have any thoughts on this?
·
Mark
·
·
FUNCTION CalcCheckSum (Blk$)··············· 'Returns CheckSum on Blk$
·
C& = 0····································· 'Use Long Int to Avoid Overflow
FOR Q = 1 TO LEN(Blk$)
·· C& = C& + ASC(MID$(Blk$, Q, 1))········· 'Add to Add Bits of Each Byte
NEXT Q
C& = (C& AND 255)·························· 'AND Out Hi Byte Bits
CalcCheckSum = C&
END FUNCTION
·
FUNCTION CalcCRC& (B$, CRCHigh%, CRCLow%)····· 'Calculates CRC for Each Block
·
DIM Power(0 TO 7)····························· 'For the 8 Powers of 2
DIM CRC AS LONG
·
FOR I = 0 TO 7································ 'Calculate Once Per Block to
·· Power(I) = 2 ^ I··························· ' Increase Speed Within FOR J
NEXT I········································ ' Loop
CRC = 0································· ······'Reset for Each Text Block
FOR I = 1 TO LEN(B$)·························· 'Calculate for Length of Block
·· ByteVal = ASC(MID$(B$, I, 1))
·· FOR J = 7 TO 0 STEP -1
····· TestBit = ((CRC AND 32768) = 32768) XOR ((ByteVal AND Power(J)) = Power(J))
··· ··CRC = ((CRC AND 32767&) * 2&)
····· IF TestBit THEN CRC = CRC XOR &H1021&···· ' <-- This for 16 Bit CRC
····· '*** IF TestBit THEN CRC = CRC XOR &H8005&···· ' <-- This for 32 Bit CRC
·· NEXT J
NEXT I
CRCHigh% = (CRC \ 256)························· 'Break Word Down into Bytes
CRCLow% = (CRC MOD 256)························ ' for Comparison Later
ComputeCRC& = CRC······························ 'Return the Word Value
END FUNCTION

[Bean]

The ultimate would be ECC (Error Correction Code). Using ECC the receiver can actually correct wrong bits.
Do a google for ECC or SECDED (Single error correction, double error detection). SECDED can correct a wrong bit, and can detect if two bits are wrong (although it cannot correct a two bit error). But this is bits per byte sent, so every byte could have 1 bit wrong and the receiver could correct it. But you have to send 13 bits for 8 bits of data.

You could also do a "triple vote" on the data. You are already sending it three times. What you do is check every bit against the other two in each position and use the bit value that appears at least twice.

Both of these methods would require quite a bit more code than a simple checksum.

Actually serial data is not a very good format for RF transmission.

Bean.

▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔
Check out· the "SX-Video Display Module"

www.sxvm.com (http://www.sxvm.com)
·

[Jim McCorison]

micromuc said...
errors are still getting through


then:


micromuc said...
I know I’m not verifying the checksum at this time, although I thank you for the example. I will use it when I get things worked out. At this time I want to see everything that comes through. That is the only reason it is not being used.



Mark,

The reason errors are still "getting through" is that you are not trapping them. Adding a checksum isn't magic, it is a tool. In order to be useful you must use the tool. The checksum's only purpose is to allow you to detect errors and reject the resulting bad transmission. You will still get errors in your transmission, but by using the checksum you will be able to detect the error and reject the transmission. Until you do that, you will continue to see those errors.

Ok, now I understand about the array and ',' values. Flexibility is always a good thing.

The '*' in the data stream coming from the GPS is used in the NMEA sentence to say "here comes a checksum". The NMEA world has a huge number of defined sentences and even more undefined sentences. Therefore the incoming data stream is parsed until a '*' is seen and the next value is treated as a checksum. Since you will be passing a known number of fields between your devices, then you can forgo the '*'.


Bean & Forrest,

In the initial start of the thread I mentioned simple checksum and CRC16. Given the short length of the transmitted data, and the fact that he will be transmitting each reading three times, and that a completely missed reading is no big deal to him, the fancier ECC algorithms are serious over kill. Although it would be fun to see if you could convince a Stamp to do them.

For simplicity's sake micromuc choose checksum. I agree with his initial choice. Once he has the application functional he can examine his data and determine if the checksum is letting through data errors. At that point he can upgrade the error detection scheme to a more robust one.


Mark,

In order to support such a possibility, you should make your checksum calculation a subroutine. (use GOSUB/RETURN) That way if you do decide to upgrade the error detection routine you only have to look at one spot.

Jim

[micromuc]

Jim,

I should not have written "errors are still getting through". Instead I should have written "the data is corrupt but the checksums are the same". These would have sent corrupt data through because the checksums are equal. I bold faced the lines where this was happening in a few posts back. I hope this makes sense.

Mark

0,147,35!*199,199
0,147,351*135,199
0,147,35!*199,199
0,147,351*199,199
0,147,35!*199,199
0,147,351*199,199
0,!47,351*199,183
0,147,35!*199,199
0,147,351*199,199
0,147,351*135,199
2,303,351*203,203
2,303,351*139,203
2,303,35!*203,203
0,74,34c*205,205

[Jim McCorison]

Mark,

Would you please post your exact code as written. The sample you posted earlier has many problems (syntax, insufficient variable space, etc.) and doesn't even compile. As such I am unable to replicate your results, nor determine what the problem might be.

Jim

[Forrest]

Yes, please post both your transmit and receive programs so we can help.

[micromuc]

I don't have my stuff with me. I flew to NY today. I'll post it when I get back in a couple of weeks.

Mark

[Jim McCorison]

Micromuc PM'ed me shortly after my posting saying that he was just leaving town for a week and would post it when he got back.

Jim