[PIC]: two bit checksum
Roman Black
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 list...@mitvma.mit.edu with SET PICList DIGEST in the body
Thomas McGahee
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
Clive Frederickson
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:fas...@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
mailto:piclist-unsub...@mitvma.mit.edu
Roman Black
checksum.
I will read them all tonight and have a good think
about it, then do the replys. Thanks! :o)
-Roman
Bob Ammerman
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)
Andrew Warren
> 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 - fas...@ix.netcom.com
=== Fast Forward Engineering - San Diego, California
=== http://www.geocities.com/SiliconValley/2499
Kevin Maciunas
> 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.
> 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
>
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: ke...@cs.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
Bob Ammerman
> 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