using checksum for data integrity

I have some data that I am sending over a GPRS connection to a server. Data integrity is very important so I am looking to find out what people are typically using as a checksum in Arduino? I found an MD5 library but even the basic example sketch is 14KB. I am using an UNO so that is just to large for me to use. Any suggestions on how to verify data integrity is appreciated.

CRC is probably a lot smaller.

How's this CRC solution??

Do you need error correction, or will you re-send?