Searching \ for '[OT] CRCs on short packets' in subject line. ()
Make payments with PayPal - it's fast, free and secure! Help us get a faster server
FAQ page: piclist.com/techref/method/errors.htm?key=crc
Search entire site for: 'CRCs on short packets'.

Exact match. Not showing close matches.
PICList Thread
'[OT] CRCs on short packets'
1999\08\23@224531 by James Cameron

flavicon
face
Assuming I'm going to be generating between two to eight words of twelve
bits each in a data stream over a remote control UHF link, what sort of
checksum or CRC is appropriate?

I get the impression that calculating a checksum or a CRC on such small
data streams might be ineffective, because of the probabilities
involved.

For example; sending 24 bits of data followed by a 12 bit arithmetic
checksum ... the chances of corruption affecting one of the 24 bits and
then also one of the 12 bits of checksum to mask the corruption seem to
be higher.

I'm not exactly sure how to express this ... but is there a concern?

--
James Cameron                                      (spam_OUTquozlTakeThisOuTspamus.netrek.org)

Linux, Firewalls, OpenVMS, Software Engineering, CGI, HTTP, X, C, FORTH,
COBOL, BASIC, DCL, csh, bash, ksh, sh, Electronics, Microcontrollers,
Disability Engineering, Netrek, Bicycles, Pedant, Farming, Home Control,
Remote Area Power, Greek Scholar, Tenor Vocalist, Church Sound, Husband.

"Specialisation is for insects." -- Robert Heinlein.

1999\08\23@231307 by Richard Prosser

flavicon
face
My suggestion would be based on the importance/consequences of errors.

If you must be able to detect errors to a very high probability, then the
more complex CRC is possibly the better way to go. If the error rate is
likely to be low anyway, and the consequences of an error are not too bad -
then I'd use a simple checksum - sending (say) the 4 (or less) lsb only.

My guess - based on the small amount of data - 2 or 4 bit checksum.

Richard

> {Original Message removed}

1999\08\23@232934 by Wagner Lipnharski

picon face
James Cameron wrote:
>
> Assuming I'm going to be generating between two to eight words of twelve
> bits each in a data stream over a remote control UHF link, what sort of
> checksum or CRC is appropriate?
>
> I get the impression that calculating a checksum or a CRC on such small
> data streams might be ineffective, because of the probabilities
> involved.
>
> For example; sending 24 bits of data followed by a 12 bit arithmetic
> checksum ... the chances of corruption affecting one of the 24 bits and
> then also one of the 12 bits of checksum to mask the corruption seem to
> be higher.
>
> I'm not exactly sure how to express this ... but is there a concern?


James, CRC's (8,16 or 32) offers a high confidence to your data
transmission, doesn't matter if is only one byte or one million bytes.
If your transmission media corrupts one bit of data (or CRC), it means
you have a *corrupted* data, nothing else, and you need to retransmit
the thing.  Except, of course, if you use an inteligent protocol and
correction codes to *de-corrupt* the bit (or bits).

Your worries about to have a higher probability of data corruption
because transmitting just two data bytes followed by 2 CRC bytes
(CRC-16), meaning that you will double the corruption probability, is
not ... hmmm... nice, since your transmission media should be clean. You
can not think of it as a machine gun shooting gallery, while if your
data is skinny better the chances to survive across the bullets.

If you suspect your media is dirty and noise poluted, this is a strong
reason to use a good CRC system. This is the price to pay.

Some time ago I saw a check system, silly but functional, (I don't
recommend, but...), send every bit followed with its binary complement.
Noise could change just one or multiple bits, and probably, (I will
repeat), probably, noise will not change the complement bit to the right
level, so it will be easy to identify the discrepancy between the
original and the complement bit... it doubles the transmission data size
and not ensure a good check system.

I would stick to a plain and easy CRC16 (any variation of it).

--------------------------------------------------------
Wagner Lipnharski - UST Research Inc. - Orlando, Florida
Forum and microcontroller web site:  http://www.ustr.net
Microcontrollers Survey:  http://www.ustr.net/tellme.htm

1999\08\24@003715 by Scott Dattalo

face
flavicon
face
On Tue, 24 Aug 1999, James Cameron wrote:

> Assuming I'm going to be generating between two to eight words of twelve
> bits each in a data stream over a remote control UHF link, what sort of
> checksum or CRC is appropriate?
>
> I get the impression that calculating a checksum or a CRC on such small
> data streams might be ineffective, because of the probabilities
> involved.
>
> For example; sending 24 bits of data followed by a 12 bit arithmetic
> checksum ... the chances of corruption affecting one of the 24 bits and
> then also one of the 12 bits of checksum to mask the corruption seem to
> be higher.
>
> I'm not exactly sure how to express this ... but is there a concern?

James,

Read up on ECC's (error correction codes). ECC's are used to identify
and/or fix errors in one or more bits much in the same way a parity bit is
used as a simple integrity check. For 2^n bits, you need n extra bits to
identify and fix single bit errors. So in your case, 5 extra bits are
needed. The downside is that they're computationally more difficult than
CRC's. The upside (for this amount of data) is that they're more efficient
from a bandwidth point of view.

Scott

1999\08\24@004947 by Nicholas Uloth

flavicon
face
At 11:27 PM 23/08/99 -0400, you wrote:
{Quote hidden}

The tradeoff is between correctness and efficiency, longer CRCs increase
chance of
detecting corruption but also decrease throughput because more packets will
have errors.



>Some time ago I saw a check system, silly but functional, (I don't
>recommend, but...), send every bit followed with its binary complement.
>Noise could change just one or multiple bits, and probably, (I will
>repeat), probably, noise will not change the complement bit to the right
>level, so it will be easy to identify the discrepancy between the
>original and the complement bit... it doubles the transmission data size
>and not ensure a good check system.

Useful whene you have lots of bandwidth and not much computing power though.


Nic

1999\08\24@005508 by Dennis Plunkett

flavicon
face
At 02:32 24/08/99 +0000, you wrote:
{Quote hidden}

The effectiveness will depend on the target requirments. Forward error
correction of say 16bits with a simple polynomial will correct 2 bits in 48
(Including the CRC). But in a radio system, errors are nominaly determined
by fading, hence the chance of one bit in error is slim, whereas fade or a
noise hit will corrupt 2 or more bits in a row (Note that the nominal
checksum is weighted on bits in a row being hit not just one here and there
(Generally speaking only, so don't flame me on that)), you may also find
that a simple 2s complement checksum of 8 to 16 bits is quite OK for up to
256 bytes of data. If you need to correct the data, then a hamming code
will be required (Interleaving) to ensure that you don't get caught with
unfixable errors (Take a look at the GSM format for the "protected" data
for some ideas on how it was done) .

In large you will find that CRCs like x7+x5+x2+1 will be quite OK at
detecting the error in a small packet, however if the data is IMPORTANT,
then this simple CRC WILL NOT SURRFICE, and another signature check may
also be required etc.


I know that this has not answered your question, but do hope that it makes
you think about how important the data transmitted is etc. This may then
help you answer the questions you have raised.

Dennis

1999\08\24@012158 by Brent Crosby

flavicon
face
>Assuming I'm going to be generating between two to eight words of twelve
>bits each in a data stream over a remote control UHF link, what sort of
>checksum or CRC is appropriate?

We had a 10 byte packet, and added a 16 bit CRC. It made
for a rock solid system.

Here is a great reference on CRC's:

ftp://ftp.rocksoft.com/clients/rocksoft/papers/crc_v3.txt

If you are going to throw data away when the CRC does not match,
remember that it is important to only throw away one byte, and then
re-apply the CRC criteria. This will guarantee that your algorithm
re-synchronizes without the need for timeouts or any other complex
code.


| Brent A. Crosby
| Crystalfontz America, Incorporated
| 15611 East Washington Road
| Valleyford, WA 99036
| toll free (888) 206-9720
| voice (509) 291-3514 facsimile (509) 291-3345
| http://www.crystalfontz.com brentspamKILLspamcrystalfontz.com
| We manufacture and sell economical, feature packed, serial interface LCD
modules.

1999\08\24@095915 by Wagner Lipnharski

picon face
Brent Crosby wrote:
[snip]
> If you are going to throw data away when the CRC does not match,
> remember that it is important to only throw away one byte, and then
> re-apply the CRC criteria. This will guarantee that your algorithm
> re-synchronizes without the need for timeouts or any other complex
> code.

Brent, I did not slept well last night, and probably this is the reason
why I can't understand your text above. Can you explain it better,
please?  I understand you are talking about the received data block in
error, but what you mean with "throw away one byte"? strip it out from
the data block?
Wagner.

1999\08\24@100326 by Andy Kunz

flavicon
face
With a 12-bit data stream, you are much better using an ECC (Look up
Hamming) than anything else.


At 02:32 AM 8/24/99 +0000, you wrote:
>Assuming I'm going to be generating between two to eight words of twelve
>bits each in a data stream over a remote control UHF link, what sort of
>checksum or CRC is appropriate?


==================================================================
Andy Kunz               Life is what we do to prepare for Eternity
------------------------------------------------------------------
.....andyKILLspamspam.....rc-hydros.com      http://www.rc-hydros.com     - Race Boats
EraseMEandyspam_OUTspamTakeThisOuTmontanadesign.com  http://www.montanadesign.com - Electronics
==================================================================

1999\08\24@181710 by Brent Crosby

flavicon
face
Wagner:

 Say you have a 10-byte fixed length packet. Your receiving
routine would typically wait until 10 bytes are in its buffer, then
apply the CRC routine. If the CRC does not match, you might
empty the buffer, saying that there is garbage coming in, not
packets. Well, the routine may not ever synchronize if you do
this.

 As an example, say the transmitter is always sending out
valid 10-byte packets. What if the receiver wakes up in the
middle of a packet? It receives 5 bytes from the end of the
first packet, then 5 bytes from the start of the next packet,
applies the CRC, discards the data and then repeats the
whole process, staying out of sync, even though there are
good packets coming in.

 The trick is to only discard one byte instead of the whole
buffer or a whole packet's worth of bytes. Then the receiver
essentially has a  sliding 10-byte window, whose CRC will
only match up if there is a valid packet in the 10 bytes. Of
course, once you do get  valid packet, you take the whole
packet out at once.

 Maybe this is obvious to everyone, but it had me stumped
for a bit--once I got out of sync it would reject all packets.

At 06:57 AM 8/24/99 , you wrote:
{Quote hidden}

                               Sincerely,
                               Brent A. Crosby

| Brent A. Crosby
| Crystalfontz America, Incorporated
| 15611 East Washington Road
| Valleyford, WA 99036
| voice (509) 291-3514 facsimile (509) 291-3345
| http://www.crystalfontz.com brentspamspam_OUTcrystalfontz.com

1999\08\24@184043 by Andy Kunz

flavicon
face
>  The trick is to only discard one byte instead of the whole
>buffer or a whole packet's worth of bytes. Then the receiver

A good way to synch yourself is to use a mechanism such as this:

void sendc (char c)
       {
       if (c >= 0xe0)
               {
               putc (0x1b);
               putc (c);
               }
       else
               putc (c + 0x20);
       }

void sendmsg (char *s, int count)
       {
       int i;
       char c;

       putc (0x02);
       for (i = 0; i < count; i++)
               {
               c = *s++;
               sendc (c);
               CRC = crcfunc (CRC, c);
               }
       s = (char*)&CRC;
       for (i = 0, i < sizeof (CRC); i++)
               sendc (*s++);
       putc (0x0d);
       }

While this is not perfect (because the CRC should be handled as a
network-level thing) is does work quite well.  The code above is also
generic enough that it should compile pretty easily on your machine - just
define a few variables (CRC and the message you are sending) and the crcfunc().

The receiving end simply looks until it reads a 0x02, then reads and
buffers all chars until
       a) it detects the 0x0d, which causes it to validate and forward the
message, or
       b) it detects a buffer overrun, which causes it to look for the 0x02 aga
in.

The receiver code is almost as simple, and is "left as an exercise for the
student."

Hope this helps.

We use this ALL the time.

Andy

==================================================================
Andy Kunz               Life is what we do to prepare for Eternity
------------------------------------------------------------------
@spam@andyKILLspamspamrc-hydros.com      http://www.rc-hydros.com     - Race Boats
KILLspamandyKILLspamspammontanadesign.com  http://www.montanadesign.com - Electronics
==================================================================

1999\08\24@191105 by Kevin J. Maciunas

flavicon
picon face
Brent Crosby wrote:

{Quote hidden}

Guys,
        If you want to do either forwared error control (ie receiver can
detect AND correct) or just a simple receiver detects errors (and then
either discards or requests re-transmission) you need to be able to locate
the packet!  This is called framing.  Check out any computer networks text -
the issue cited above (jumping into the middle of a packet)  is trivially
solved by framing - look for start-of-frame and discard everything till you
get one.  This is how all networking protocols work.  As in all life, don't
re-invent wheels where this ain't required.
       I thought the original poster was asking about CRC's for really
small frames - you might be better off with forward error control - if you
use hamming codes (for example) and have 12 bits of data you need an
additional 5 bits to be able to correct single bit errors.  Again, get thee
to a text book.  Hamming codes and CRCs are trivially implemented (even my
students could do this...) CRCs require little more than XOR's (and you do
this byte by byte as you receive) and Hamming codes are just parity
computations.  Andy Tanenbaum's book on Computer Networks has a pretty
readable description of both.

Anyway my $0.02
Cheers
/Kevin
-----------
Kevin J. Maciunas           Net: RemoveMEkevinTakeThisOuTspamcs.adelaide.edu.au
Dept. of Computer Science   Ph : +61 8 8303 5845
University of Adelaide      Fax: +61 8 8303 4366
Adelaide 5005
SOUTH AUSTRALIA

1999\08\24@191528 by quozl

flavicon
face
On Tue, Aug 24, 1999 at 03:11:51PM -0700, Brent Crosby wrote:
>   The trick is to only discard one byte instead of the whole
> buffer or a whole packet's worth of bytes. Then the receiver
> essentially has a  sliding 10-byte window, whose CRC will
> only match up if there is a valid packet in the 10 bytes.

If you are dealing with an unaligned bit stream you would drop a bit at
a time instead, I guess.

--
James Cameron                                      (spamBeGonequozlspamBeGonespamus.netrek.org)

1999\08\24@194104 by Dennis Plunkett

flavicon
face
At 18:36 24/08/99 -0400, you wrote:
{Quote hidden}

crcfunc().
>
>The receiving end simply looks until it reads a 0x02, then reads and
>buffers all chars until
>        a) it detects the 0x0d, which causes it to validate and forward the
>message, or
>        b) it detects a buffer overrun, which causes it to look for the
0x02 again.
{Quote hidden}

Hey Andy,
Why not include the rest of it? You know the header bit so that others can
understand the 0x02 (STX) bits nad that so they can see what is going on.
Also some may think that the first part is a bit strainge where you include
the EXCAPE detection/insertion bits. But then again maybe tell them that it
is an X25 implementation.

Also, the sizeof bit may get some people, but does meand that the size of
the CRC can be altered with little trouble.

Ahhug! Type casting! s = (char*) &CRC (But I do this too!)
Ahhug! Global varibale CRC! Naughty!

I also see that this is targeted at an 8bit device, as others out there may
think that the code if

       c= *s++;

Is a waste of a variable (And they would be right!), however you could
force this as a near variable, but this does limit the code very much
indeed. So one could say that this code segment does meet the best of all
worlds.

And just for the end bit, the second for next loop is in error!

Oh Andy you have come down a setp or two :)

But it could be simpler!


#include CRC.h

void
sendmsg (char *s,
               int count)
{
CRCVAULE CRC;          /*(Assume that this is an int and not globle as above)*/
char c;

       putc (0x02);
        while (count--)
       {
               c = *s++;
               sendc (c);
               CRC = crcfunc (CRC, c);
       }

      s = (char*)&CRC;
      for (c = 0; c < sizeof (CRC); c++)
               sendc (*s++);

      putc (0x0d);

}/*end sendmsg*/


And on top of that the method does have the ability to loose sync if the
CRC contains 0x0d in the data stream. This can lead to a packet that will
never get though if sych is lost at the wrong time, as I see you add 0x20
to the character, assuming that only ASCII is sent then this does cause
some concern for me, but then again I am always concerened but if it is an
X25 implementation, then there is a lenght in the header that will prevent
this from occuring.

Dennis

Waiting to be flamed

1999\08\24@195550 by Brent Crosby

flavicon
face
>         If you want to do either forwared error control (ie receiver can
>detect AND correct) or just a simple receiver detects errors (and then
>either discards or requests re-transmission) you need to be able to locate
>the packet!  This is called framing.  Check out any computer networks text -
>the issue cited above (jumping into the middle of a packet)  is trivially
>solved by framing - look for start-of-frame and discard everything till you
>get one.

Fair enough. However, if you are using a relatively huge (16 bit) CRC on a
relatively small (10 byte) fixed length packet, you can dispense with the
start of frame and end of frame characters and the required "escaping" of
them in the case that your data contains them. Lots of different ways to
skin a cat. All of them fun.



                               Sincerely,
                               Brent A. Crosby

| Brent A. Crosby
| Crystalfontz America, Incorporated
| 15611 East Washington Road
| Valleyford, WA 99036
| voice (509) 291-3514 facsimile (509) 291-3345
| http://www.crystalfontz.com brentEraseMEspam.....crystalfontz.com

1999\08\25@004942 by Wagner Lipnharski

picon face
Brent Crosby wrote:
{Quote hidden}

Oh, thanks Brent, I see your point of view, but this is why we use sync
or start of packet characters, so the receiver will not start to fill
the buffer until it "sees" this sync or SOH (Start of Header)
character.  Several protocols use the SOH and EOB (End of Block), and
many other symbologies for those "start" and "end" of data block
characters.  Of course, as you said before, a receiver "waking up" in
the middle of the block will not get the sync and will not answer,
generating time-out.  Some more inteligent protocols can recognize the
end-of-block character and send a negative acknoledgement (even without
received the start of block), so it avoid the time-out and starts a fast
retransmition.

I use to develop several *special protocols* for different applications,
for several reasons as security or application customized and so on. In
every one I use those SOH and EOB (plus the CRC-16 of course), so the
receiver would ever understand when a block starts and ends.

I also use to do the software run the CRC for every char received, in
real time, so at the end of the block after receiving the 2 CRC bytes,
the resulting CRC should be zero (for CRC-16). Of course it implies a
processing window available in between of each char received.

Wagner

1999\08\25@042548 by root

flavicon
face
Hi,

Dallas uses 8-bit CRC for such packets. It seems to be reliable enough.
The procedure is disclosed in their book Automatic Identification Data
Book.

Regards,
Imre


On Tue, 24 Aug 1999, James Cameron wrote:

{Quote hidden}

1999\08\25@101054 by Andy Kunz

flavicon
face
>And just for the end bit, the second for next loop is in error!

The compiler catches typos like that very well, thank you!

CRC was supposed to be local - sorry about that.

>And on top of that the method does have the ability to loose sync if the
>CRC contains 0x0d in the data stream. This can lead to a packet that will

Not mine, because the CRC is passed through the sendc() function, which
will add the 0x20 to a 0x0d.

No length is necessary in the header using my description.  I use it with
variable-length messages all the time.  In my implementation, the caller
also passes a length parameter for those who need it.

Andy


==================================================================
Andy Kunz               Life is what we do to prepare for Eternity
------------------------------------------------------------------
RemoveMEandyEraseMEspamEraseMErc-hydros.com      http://www.rc-hydros.com     - Race Boats
RemoveMEandyspam_OUTspamKILLspammontanadesign.com  http://www.montanadesign.com - Electronics
==================================================================

1999\08\25@113126 by Kolesnikoff, Paul

flavicon
face
Date:    Tue, 24 Aug 1999 15:11:51 -0700
From:    Brent Crosby <RemoveMEbrentTakeThisOuTspamspamCRYSTALFONTZ.COM>
Subject: Re: [OT] CRCs on short packets

 Say you have a 10-byte fixed length packet. Your receiving
routine would typically wait until 10 bytes are in its buffer, then
apply the CRC routine. If the CRC does not match, you might
empty the buffer, saying that there is garbage coming in, not
packets. Well, the routine may not ever synchronize if you do
this.

 As an example, say the transmitter is always sending out
valid 10-byte packets. What if the receiver wakes up in the
middle of a packet? It receives 5 bytes from the end of the
first packet, then 5 bytes from the start of the next packet,
applies the CRC, discards the data and then repeats the
whole process, staying out of sync, even though there are
good packets coming in.

 The trick is to only discard one byte instead of the whole
buffer or a whole packet's worth of bytes. Then the receiver
essentially has a  sliding 10-byte window, whose CRC will
only match up if there is a valid packet in the 10 bytes. Of
course, once you do get  valid packet, you take the whole
packet out at once.

 Maybe this is obvious to everyone, but it had me stumped
for a bit--once I got out of sync it would reject all packets.

Brent and Wagner,
In my dealings with data packets, I have always included a synchronizing
byte. My receiving routine would wake up and then check every byte it
received until a synchronizing byte came in. Then it would start reading the
number of bytes required to make a packet.

In this case, my interpretation of the suggestion was to save the packet
that you received with an error and then call for another transmission.
Assuming the CRC failed on the second packet also, you would then compare
the two packets to determine which bytes were different. Assuming that the
bytes that matched were correct, you could mix and match the the
non-matching bytes until you got a complete packet.

My 2cents,
Paul Kolesnikoff

More... (looser matching)
- Last day of these posts
- In 1999 , 2000 only
- Today
- New search...