Searching \ for '[PIC] Error correction by majority rule' 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=error+cor
Search entire site for: 'Error correction by majority rule'.

Exact match. Not showing close matches.
PICList Thread
'[PIC] Error correction by majority rule'
2008\10\29@122433 by Bob Blick

face
flavicon
face
I'm currently using hamming error correction in an RF link but I want to
get even more distance, and hamming only fixes single bit errors. I'm
going to try a best two out of three scheme that assembles a byte out of
the best bits of three bytes. The three bytes are the same when
transmitted but multiple bits are expected to arrive damaged. This is
what I've come up with, if anyone has anything simpler or more clever
please chime in. I know I could cram a lot of it in one line but I left
it big so the code would be obvious.

Basically c is the tiebreaker for any bits that a and b disagree on.

Thanks, Bob

unsigned char Majority(unsigned char a, b, c){
 unsigned char d;
 d = a ^ b;      // find conflicting bits
 c &= d;         // tiebreaker byte keeps only those bits
 d ^= 0xFF;      // invert the choices
 a &= d;         // mask off the disputed bits
 a |= c;         // merge with tiebreaker byte
 return a;
}


--
http://www.fastmail.fm - IMAP accessible web-mail

2008\10\29@130431 by Alan B. Pearce

face picon face
>I'm currently using hamming error correction in an RF link but
>I want to get even more distance, and hamming only fixes single
>bit errors.

Well, that depends on how many parity bits you use. If you use more parity
bits, and assign them to the data bits in a proper way, a Hamming code can
detect and correct more bits.

2008\10\29@131548 by Bob Blick

face
flavicon
face

On Wed, 29 Oct 2008 17:04:09 -0000, "Alan B. Pearce"
<spam_OUTAlan.B.PearceTakeThisOuTspamstfc.ac.uk> said:

> Well, that depends on how many parity bits you use. If you use more
> parity
> bits, and assign them to the data bits in a proper way, a Hamming code
> can
> detect and correct more bits.

I've never heard that or seen any examples with more than a single bit
correction. Got a link?

Thanks,

Bob

--
http://www.fastmail.fm - I mean, what is it about a decent email service?

2008\10\29@132600 by Bob Ammerman

picon face
> Basically c is the tiebreaker for any bits that a and b disagree on.
>
> Thanks, Bob
>
> unsigned char Majority(unsigned char a, b, c){
>  unsigned char d;
>  d = a ^ b;      // find conflicting bits
>  c &= d;         // tiebreaker byte keeps only those bits
>  d ^= 0xFF;      // invert the choices
>  a &= d;         // mask off the disputed bits
>  a |= c;         // merge with tiebreaker byte
>  return a;
> }
>

how about:

   unsigned char d;
   d = a & b;
   d |= b & c;
   d |= a & c;
   return c;

-- Bob Ammerman
RAm Systems


2008\10\29@134156 by Bob Ammerman

picon face

----- Original Message -----
From: "Bob Ammerman" <.....rammermanKILLspamspam@spam@verizon.net>
To: "Microcontroller discussion list - Public." <piclistspamKILLspammit.edu>
Sent: Wednesday, October 29, 2008 1:25 PM
Subject: Re: [PIC]Error correction by majority rule


{Quote hidden}

oops - that should be

   return d;

-- Bob Ammerman
RAm Systems

2008\10\29@134252 by Alan B. Pearce

face picon face
>I've never heard that or seen any examples with more
>than a single bit correction. Got a link?

Umm, only the course unit I was doing this year, but that is not on the web
...

Will have to go back and work out what would be required.

2008\10\29@134823 by Bob Ammerman

picon face
Look up "Forward Error Correction" (FEC)

Wiki has a pretty good article on it at:

http://en.wikipedia.org/wiki/Forward_error_correction

-- Bob Ammerman
RAm Systems

2008\10\29@140957 by Dr Skip

picon face
I don't know if source is available, but the author probably is. Here's an
implementation for PC data which works very well up to 100% redundancy:

http://www.ice-graphics.com/ICEECC/IndexE.html

-Skip

2008\10\29@142416 by Bob Ammerman

picon face
See also:

http://www.eccpage.com

-- Bob Ammerman
RAm Systems

2008\10\29@161448 by Bob Blick

face
flavicon
face
Thanks Bob!

Looking at those web pages about ECC methods reminds me how much I am
not a computer scientist.

Cheerful regards,

Bob

On Wed, 29 Oct 2008 13:41:21 -0400, "Bob Ammerman"
<.....rammermanKILLspamspam.....verizon.net> said:

{Quote hidden}

--
http://www.fastmail.fm - A fast, anti-spam email service.

2008\10\29@175006 by Bob Ammerman

picon face
Simpler expression yet...

unsigned char Majority(unsigned char a, unsigned char b, unsigned char c)
{
   unsigned char d;
   d = a & (b|c);
   d |= b&c;
   return d;
}

2008\10\29@181638 by Dave Tweed

face
flavicon
face
Bob Blick wrote:
{Quote hidden}

Here's a shorter sequence:

unsigned char Majority (unsigned char a, b, c)
{
 b ^= a;       // find the conflicting bits between A and B
 c ^= a;       // find the conflicting bits between A and C
 b &= c;       // which bits disagree in both?
 a ^= b;       // flip them
 return a;
}

The usual implementation is more like this, which is the same number of
operations as your original (5):

unsigned char Majority (unsigned char a, b, c)
{
 // return (a&b) | (b&c) | (a&c);
 unsigned char d;
 d = a & c;
 a &= b;
 b &= c;
 a |= b;
 a |= d;
 return a;
}

However, like the others, I question the wisdom of jumping to 200% overhead
in your radio channel -- the other choices for FEC would be better starting
points.

-- Dave Tweed

2008\10\29@183415 by Bob Blick

face
flavicon
face
On Wed, 29 Oct 2008 18:16:35 -0400 (EDT), "Dave Tweed" <EraseMEpicspam_OUTspamTakeThisOuTdtweed.com>
said:

> However, like the others, I question the wisdom of jumping to 200%
> overhead
> in your radio channel -- the other choices for FEC would be better
> starting
> points.

Hi Dave,

Basically I don't have much data to move, and I want correction for
multiple bits.

The hamming method I was using has almost 100% overhead, only corrects
single bit errors and uses two tables.

All the examples I've seen on the web that do what I want are for long
groups of bytes and use things like Reed-Solomon coding. Those methods
are way too clever for me to recreate for just a couple of bytes. As I
said, I'm not a computer scientist.

Thanks,

Bob

--
http://www.fastmail.fm - Does exactly what it says on the tin

2008\10\29@191025 by Dr Skip

picon face
Some combination of data, followed by logically inverted data (as an 'opposite'
data stream), parity bits (or your code) on each, and repeating will probably
get the data through, and if you don't get 2 good answers out of n (preferably
1 real and one inverted agree with good parity, at least), then light the "I
give up" LED. ;)

If this needs to happen only once every n seconds, constantly repeat the data
and sample at the receiver every n seconds instead, but be continually checking
as above. You'll have LOTs of redundancy to work with by the time you need the
sample.

-Skip


Bob Blick wrote:
{Quote hidden}

2008\10\29@194755 by Bob Blick

face
flavicon
face
On Wed, 29 Oct 2008 19:10:19 -0400, "Dr Skip" <drskipspamspam_OUTgmail.com> said:
> Some combination of data, followed by logically inverted data (as an
> 'opposite'
> data stream), parity bits (or your code) on each, and repeating will
> probably
> get the data through, and if you don't get 2 good answers out of n
> (preferably
> 1 real and one inverted agree with good parity, at least), then light the
> "I
> give up" LED. ;)
>
> If this needs to happen only once every n seconds, constantly repeat the
> data
> and sample at the receiver every n seconds instead, but be continually
> checking
> as above. You'll have LOTs of redundancy to work with by the time you
> need the
> sample.

Error checking and redundancy works fine up to a certain distance, but I
am able to get three to four times the distance by correcting the
errors.

I just checked with multiple bit correction, and it gets me a little
further than with single bit correction. I think I've gotten all the low
hanging fruit, so I'm happy.

Thanks for everyones help on this!

Cheerful regards,

Bob

--
http://www.fastmail.fm - A no graphics, no pop-ups email service

2008\10\29@232109 by Sean Breheny

face picon face
Hi Bob,

In one class I had, the prof told us that the data coming back from
deep space probes had almost 50% of bits in error (50% is worst case
since bits have only two states and if 100% were in error, you could
just invert them and get 0% error). I think he said that the error
control coding on the data from those probes was so good that they
could get near 100% correct data out from a stream with something like
45% errors. I think they use Reed-Solomon, which is also what I
believe they use on CDs.

Reed Solomon is pretty standard and there are open-source libraries
for it. It is used in 2D barcodes in which case it is often being done
on only 8 bytes of data.

Sean


On Wed, Oct 29, 2008 at 7:47 PM, Bob Blick <@spam@bobblickKILLspamspamftml.net> wrote:
{Quote hidden}

> -

2008\10\30@013406 by Bob Blick

face
flavicon
face
Sean Breheny wrote:

> Reed Solomon is pretty standard and there are open-source libraries
> for it. It is used in 2D barcodes in which case it is often being done
> on only 8 bytes of data.

Hi Sean,

Thanks, that is good to know. I have a couple of months before the code
is set in stone, so if I can find it and it works well I'll use it.

Cheerful regards,

Bob

2008\10\31@074416 by Peter

picon face
Bob Blick <bobblick <at> ftml.net> writes:

Please try this Google key: "forward error correction fec table"

Peter


2008\10\31@074500 by Peter

picon face
Bob Blick <bobblick <at> ftml.net> writes:

likely exactly what you are looking for:

http://en.wikipedia.org/wiki/Turbo_code

Peter


'[PIC] Error correction by majority rule'
2008\11\03@073547 by Michael Rigby-Jones
picon face


> -----Original Message-----
> From: RemoveMEpiclist-bouncesTakeThisOuTspammit.edu [spamBeGonepiclist-bouncesspamBeGonespammit.edu] On
Behalf
{Quote hidden}

Implementing turbo codes on a PIC is going to be challenge; they use
very complex algorithms.

Mike

=======================================================================
This e-mail is intended for the person it is addressed to only. The
information contained in it may be confidential and/or protected by
law. If you are not the intended recipient of this message, you must
not make any use of this information, or copy or show it to any
person. Please contact us immediately to tell us that you have
received this e-mail, and return the original to us. Any use,
forwarding, printing or copying of this message is strictly prohibited.
No part of this message can be considered a request for goods or
services.
=======================================================================

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