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

Exact match. Not showing close matches.
PICList Thread
'[PIC]: two bit checksum'
2001\03\26@112051 by Roman Black

flavicon
face
Hi guys, I have data in 32 byte chunks, that's
256 bits total, and the transmission method I am
using must transmit 258 bits per chunk.

So I have 2 "spare" bits on each transmisison.

Does anyone have ideas for using a simple
checksum type system on the 32 bytes and using
the 2 spare bits for error checking?

I don't want mega security, just a simple
quick efficient use of the two spare bits to
check the 32 bytes was transmitted ok.
:o)
-Roman

--
http://www.piclist.com#nomail Going offline? Don't AutoReply us!
email spam_OUTlistservTakeThisOuTspammitvma.mit.edu with SET PICList DIGEST in the body


2001\03\26@121321 by Thomas McGahee

flavicon
face
Two bits isn't going to get you much of a checksum, since
there are only 4 possible combinations. So 25% chance
that even if the checksum is OK, the data isn't.

Just ignore the two extra bits.

If you want some robust error checking, try sending
the transmission packet twice. Let the receiver then
compare the self-generated checksums. If both match,
then the data is OK. Note that in the first reception
you can throw away the data and just keep the checksum.
The second reception you keep the data and compare
checksums.

Fr. Tom McGahee

{Original Message removed}

2001\03\27@031937 by Clive Frederickson

flavicon
face
Hi Roman

Hmm two bits of checksum, Not a lot.
Keeping it simple (?)
Use 1 bit for a parity check on the first 16 bits, the other for the second
16 bits
       Place the bits somewhere in the middle of the 32bits (fixed
position) to ensure you only send a limited number of 0's or 1's at a time?
               e.g. aaaa aaaa  bbbXb bbbb cccc cXccc dddd dddd
       Do an XOR of all the data as a 2bit checksum (hmm)
       Sum the four bytes together and count how many overflows you get.
       Use them as an identifier, and send the message a multiple of times.
The receiver could check the identifier to ensure all the repeats have
       been sent.
       e.g.    1st send        aaaa aaaa bbbb bbbb cccc cccc dddd dddd 01
               2nd             aaaa aaaa bbbb bbbb cccc cccc dddd dddd 02
               the receiver then checks it got '01' first, followed by '02'
if correct, then compares the two 32bits to check they are the same. If the
receiver sees '02' before '01' then it knows '01' was missed etc.

Well that's about all I can think off right now. Hope it triggers off an
idea, Bit hard to do something with only two bits.

Regards

Clive Frederickson
R&D Technician (CECF Group)

       ----------
       From:  Roman Black [SMTP:.....fastvidKILLspamspam@spam@EZY.NET.AU]
       Sent:  26 March 2001 17:19
       Subject:  Re: [PIC]: two bit checksum

       Hi guys, I have data in 32 byte chunks, that's
       256 bits total, and the transmission method I am
       using must transmit 258 bits per chunk.

       So I have 2 "spare" bits on each transmisison.

       Does anyone have ideas for using a simple
       checksum type system on the 32 bytes and using
       the 2 spare bits for error checking?

       I don't want mega security, just a simple
       quick efficient use of the two spare bits to
       check the 32 bytes was transmitted ok.
       :o)
       -Roman


*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*
Dyson's Contrarotator(TM) is the first washing machine with 2
drums rotating in opposite directions at once. This means it
gives the cleanest wash results in the fastest time and takes
the largest loads. The Contrarotator(TM) is now on sale at
selected retailers, and will be available nationwide in spring 2001.

For more information,
please visit our website at http://www.dyson.com.
*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*

--
http://www.piclist.com hint: To leave the PICList
piclist-unsubscribe-requestspamKILLspammitvma.mit.edu


2001\03\27@040436 by Roman Black

flavicon
face
Thank you everyone for the ideas on the two bit
checksum.

I will read them all tonight and have a good think
about it, then do the replys. Thanks! :o)
-Roman

--
http://www.piclist.com hint: To leave the PICList
.....piclist-unsubscribe-requestKILLspamspam.....mitvma.mit.edu


2001\03\27@112645 by Roman Black

flavicon
face
Bob Ammerman wrote:

> use those two bits as your message security.
>
> This is basically just two parity bits extended over half the bits in the
> message each.


Hi Bob, my parity knowlege is pretty weak, but
doesn't it add an extra bit based on the total
number of 1s or 0s?? This means that it will
provide absolute protection when a single bit
is changed. (common in serial transmission
faults)

Or when any ODD number of bits is changed.
Isn't that correct?

01101
10010 (example 5 errors, detected by parity)

So maybe I could do a parity check on the whole
256 bits, this will give protection if any one bit
or odd number of bits has changed.

So would it be possible to do a complimentary
system with the other spare bit, that detects
likely error situations? Is my best case error
detection limited to 75% proof? Probably...
-Roman

--
http://www.piclist.com hint: To leave the PICList
EraseMEpiclist-unsubscribe-requestspam_OUTspamTakeThisOuTmitvma.mit.edu


2001\03\27@125129 by Alan B. Pearce

face picon face
Roman
I cannot remember if you said there was more than one packet, but what you could
do is use the two bits in each packet combined together to make a hamming code
across a number of packets. If you had 10 packets in the message this would give
you 20 bits across the message.

The number of bits required does not grow as fast as the number of bits you are
protecting, as in by adding one bit of protection you can protect twice as many
bits.

Doing this you may be able to get to the point where you can detect (and maybe
correct) 1 bit errors across the message.

--
http://www.piclist.com hint: To leave the PICList
piclist-unsubscribe-requestspamspam_OUTmitvma.mit.edu


2001\03\27@135703 by Bob Ammerman

picon face
----- Original Message -----
From: Roman Black <@spam@fastvidKILLspamspamEZY.NET.AU>
To: <KILLspamPICLISTKILLspamspamMITVMA.MIT.EDU>
Sent: Tuesday, March 27, 2001 11:24 AM
Subject: Re: [PIC]: two bit checksum


> Bob Ammerman wrote:
>
> > use those two bits as your message security.
> >
> > This is basically just two parity bits extended over half the bits in
the
> > message each.
>
>
> Hi Bob, my parity knowlege is pretty weak, but
> doesn't it add an extra bit based on the total
> number of 1s or 0s?? This means that it will
> provide absolute protection when a single bit
> is changed. (common in serial transmission
> faults)

Yep, that is what this code is doing, but each of the bits is protecting
half the message bits, so you could detect an odd number of errors in either
of the halves.

> So would it be possible to do a complimentary
> system with the other spare bit, that detects
> likely error situations? Is my best case error
> detection limited to 75% proof? Probably...

Well over the set of all possible errors, you could only detect 75% of them
with two message security bits.

CRC's do _much_ better because errors tend to come in bursts rather than
randomly distributed.

You can't do much of a CRC with only two bits, though.

Bob Ammerman
RAm Systems
(contract development of high performance, high function, low-level
software)

--
http://www.piclist.com hint: To leave the PICList
RemoveMEpiclist-unsubscribe-requestTakeThisOuTspammitvma.mit.edu


2001\03\27@143021 by Andrew Warren

face
flavicon
face
Roman Black <spamBeGonePICLISTspamBeGonespamMITVMA.MIT.EDU> wrote:

> my parity knowlege is pretty weak, but doesn't it add an extra bit
> based on the total number of 1s or 0s?? This means that it will
> provide absolute protection when a single bit is changed. (common
> in serial transmission faults)
>
> Or when any ODD number of bits is changed. Isn't that correct?

   Hope you don't mind my jumping in here...

   You're correct on both counts.  You do, however, need to keep in
   mind that the parity bit itself can have an error, and that that
   case is indistinguishable from an error in the data packet.

> So maybe I could do a parity check on the whole 256 bits, this will
> give protection if any one bit or odd number of bits has changed.

   Yes.

> Is my best case error detection limited to 75% proof? Probably...

   You sorta have to think about what the probability of each type
   of error is.  Otherwise, saying that your error-detection scheme
   detects 75% of all error cases isn't really meaningful.  I
   mean... What if you could detect every error that involved more
   than 8 bits of your 256-bit message, but couldn't detect any
   8-bit or smaller errors?

   It would be accurate to say that you detected 97% of all error
   cases, but the 3% you didn't detect would be orders of magnitude
   more common than the ones you did.

   So you have to analyze the actual error rates.

   The simple analysis works like this:  Assume that you're dealing
   with a binary symmetric channel (that is, 1s and 0s are equally
   likely to be received in error, and the ONLY result of an error
   is that a 0 is received as a 1 or vice-versa).  Choose (or
   calculate, or discover through experimentation) the probability
   of a single bit error and call that "p".

   The probability of your 256-bit message getting through with no
   errors is (1-p)**256 ["**" means "raised to the power of"].  If
   p=0.1% (i.e., if one in a thousand bits has an error), the
   probability of your message getting through with no errors is
   .999**256 = .774.  In other words, one out of eight messages
   will have at least one error.

   If you add a single parity bit, your message length will
   increase to 257 bits and you'll be able to detect odd numbers of
   errors, but you'll fail to detect even numbers of errors.  To
   determine the chance of undetected errors, calculate the
   probability of receiving exactly 2 errors [note: P(x,y) is the
   number of ways y items can be chosen from a group of x; P(x,y) =
   x!/(y! * (x-y)!)]:

       P(257,2) * (.001)**2 * 0.999**255 = 2.5%

   and 4 errors:

       P(257,4) * (.001)**4 * 0.999**253 = 0.01%

   You can assume that the probability of receiving exactly 6, 8,
   or more errors is vanishingly small.

   So... Parity protects against all odd errors, and the chance of
   receiving 2 or 4 errors is around 2.51%.  Therefore, adding a
   single parity bit improves your error rate from one in eight
   messages to one in 40 messages.

   Even if your error probability is as bad as the 0.1% example I
   used (most wired links are MUCH more reliable), you'll still get
   97.5% reliability (or, in other words, five times greater
   resistance to errors) with a single parity bit.

   -Andy


=== Andrew Warren - TakeThisOuTfastfwdEraseMEspamspam_OUTix.netcom.com
=== Fast Forward Engineering - San Diego, California
=== http://www.geocities.com/SiliconValley/2499

--
http://www.piclist.com hint: To leave the PICList
RemoveMEpiclist-unsubscribe-requestspamTakeThisOuTmitvma.mit.edu


2001\03\27@185223 by Kevin Maciunas

flavicon
picon face
On Wed, 28 Mar 2001 02:24:52 +1000 Roman Black <Roman Black <fastvidEraseMEspam.....EZY.NET.AU>> wrote:

> Bob Ammerman wrote:
>
> > use those two bits as your message security.
> >
> > This is basically just two parity bits extended over half the bits in the
> > message each.
>
>
> Hi Bob, my parity knowlege is pretty weak, but
> doesn't it add an extra bit based on the total
> number of 1s or 0s?? This means that it will
> provide absolute protection when a single bit
> is changed. (common in serial transmission
> faults)
> Yes, that's what parity does, but this mode of error is *not* common.  The
most common form of error is an error burst (a bunch of consecutive [well,
not necessarily consecutive..] bits).  The faster you go the bigger the
burst length.  Just think of an EM zap of your transmission line - the
faster you send, the more data the noise might nuke.

{Quote hidden}

Grab a book on Computer Networks to see how/what you can do.  To *detect* r
error bits, you need to encode the data such that the hamming distance is
>= r+1.  Put simply, you need to ensure that each codeword (data+redundant
stuff) differs from every other valid codeword in at least r+1 bits. Putting it the other way around, you have 2 extra bits, so the error
detection you can do is pretty minimal.  Of course, using parity you can
get lucky and detect more errors *provided they are odd in number*.  To do
a good job you need many more bits.  Information theory is a wonderful
thing, it's a pity my Computer Networks class find it difficult!

Cheers
/Kevin
--
Kevin J. Maciunas              Net: EraseMEkevinspamcs.adelaide.edu.au
Dept. of Computer Science      Ph : +61 8 8303 5845
University of Adelaide         Fax: +61 8 8303 4366
Adelaide 5005 SOUTH AUSTRALIA  Web: http://www.cs.adelaide.edu.au/~kevin

--
http://www.piclist.com hint: To leave the PICList
RemoveMEpiclist-unsubscribe-requestEraseMEspamEraseMEmitvma.mit.edu


2001\03\28@110628 by Olin Lathrop

face picon face
> Grab a book on Computer Networks to see how/what you can do.  To *detect*
r
> error bits, you need to encode the data such that the hamming distance is
> >= r+1.  Put simply, you need to ensure that each codeword (data+redundant
> stuff) differs from every other valid codeword in at least r+1 bits.
> Putting it the other way around, you have 2 extra bits, so the error
> detection you can do is pretty minimal.  Of course, using parity you can
> get lucky and detect more errors *provided they are odd in number*.  To do
> a good job you need many more bits.  Information theory is a wonderful
> thing, it's a pity my Computer Networks class find it difficult!

I guess they prefer beafing over hamming.



********************************************************************
Olin Lathrop, embedded systems consultant in Littleton Massachusetts
(978) 742-9014, RemoveMEolinspam_OUTspamKILLspamembedinc.com, http://www.embedinc.com

--
http://www.piclist.com hint: PICList Posts must start with ONE topic:
[PIC]:,[SX]:,[AVR]: ->uP ONLY! [EE]:,[OT]: ->Other [BUY]:,[AD]: ->Ads


2001\03\28@110722 by Roman Black

flavicon
face
Hi Kevin, thanks! Everyone has helped a lot
with this. I have a couple of ideas in the
works thanks to what i've learned from
everyones input. :o)
-Roman




Kevin Maciunas wrote:
{Quote hidden}

--
http://www.piclist.com hint: PICList Posts must start with ONE topic:
[PIC]:,[SX]:,[AVR]: ->uP ONLY! [EE]:,[OT]: ->Other [BUY]:,[AD]: ->Ads


2001\03\28@110746 by Roman Black

flavicon
face
Wow, thanks Andy, that's a great post.
It's going to take me a couple of reads to
really make the most of it. :o)

Some of the math there is above my head,
but if you are right about the probability
of missing an error is 2.5% I can live with
that.:o)

So if I can get a decent result with just
one parity bit and minimum calc time to
determine parity then I need to look at
some use for the other bit...

Am I right in thinking that if parity is
the single bit lsb result of adding all the
bytes togther, since I am forced to use
2 bits anyway I could just keep the lsb
2 bits after adding all the bytes together?
One would still be parity and the other
would give some small additional protection?

Thanks again!
-Roman





Andrew Warren wrote:
{Quote hidden}

--
http://www.piclist.com hint: PICList Posts must start with ONE topic:
[PIC]:,[SX]:,[AVR]: ->uP ONLY! [EE]:,[OT]: ->Other [BUY]:,[AD]: ->Ads


2001\03\28@110752 by Roman Black

flavicon
face
Alan B. Pearce wrote:
>
> Roman
> I cannot remember if you said there was more than one packet, but what you could
> do is use the two bits in each packet combined together to make a hamming code
> across a number of packets. If you had 10 packets in the message this would give
> you 20 bits across the message.
>
> The number of bits required does not grow as fast as the number of bits you are
> protecting, as in by adding one bit of protection you can protect twice as many
> bits.
>
> Doing this you may be able to get to the point where you can detect (and maybe
> correct) 1 bit errors across the message.


That's very clever! I like that.
It's going to take a bit of thinking, my
data is stored in external eeprom and can only
load it to ram in 64byte chunks max, but I may be
able to do some pre-processing.
Thanks!:o)
-Roman

--
http://www.piclist.com hint: PICList Posts must start with ONE topic:
[PIC]:,[SX]:,[AVR]: ->uP ONLY! [EE]:,[OT]: ->Other [BUY]:,[AD]: ->Ads


2001\03\28@185319 by Bob Ammerman

picon face
> Am I right in thinking that if parity is
> the single bit lsb result of adding all the
> bytes togther, since I am forced to use
> 2 bits anyway I could just keep the lsb
> 2 bits after adding all the bytes together?
> One would still be parity and the other
> would give some small additional protection?
>
> Thanks again!
> -Roman


Actually, the parity is the single bit result of exclusive-oring all the
bits together.

You have to first xor all the bytes together, then compute parity across the
resulting value.

Or you do like the snippet I sent earlier and compute parity across half the
bits in the message for each of your two bits. This will give you a little
better error detection than simple parity because it can detect an even
number of errors if that even number is composed of an odd number of errors
in each half of the message.

Bob Ammerman
RAm Systems
(contract development of high performance, high function, low-level
software)

--
http://www.piclist.com hint: PICList Posts must start with ONE topic:
[PIC]:,[SX]:,[AVR]: ->uP ONLY! [EE]:,[OT]: ->Other [BUY]:,[AD]: ->Ads



'[PIC]: two bit checksum'
2001\04\07@120026 by Alan B. Pearce
face picon face
Roman
You may want to download these two articles from EDN magazine if you haven't
already come across them.

Both available in PDF if you want.

http://www.ednmag.com/ednmag/reg/2001/02152001/04ms700.htm

http://www.ednmag.com/ednmag/reg/2001/03152001/06ms700.htm

--
http://www.piclist.com hint: PICList Posts must start with ONE topic:
[PIC]:,[SX]:,[AVR]: ->uP ONLY! [EE]:,[OT]: ->Other [BUY]:,[AD]: ->Ads


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