Forward error correction on 8 bit (8051/PIC/etc) CPU?

Do you have a question? Post it now! No Registration Necessary

Translate This Thread From English to

Threaded View
I have an app that occasionally needs to send data on a rather noisy
link. Packets are typically 16 or 32 bytes long. If it matters, noise
may cause bits to be flipped, but never erased. Right now I'm using
CRC to detect errors and request retransmission.

The question is: Is an 8-bit CPU powerful enough to handle error
correction? I'm having a lot of trouble finding a decent starting
point explaining algorithms. Specifically: Which algorithms can be
used? And how many extra bytes are required to correct E errors in an
N-byte packet?

Source code would be great, in any language, as long as it does not
assume previous knowledge of error-correction or is augmented by
sufficient information. The ideal implementation, I think, would
receive an array(data+length) of bytes and number of errors to correct
and return an array of error correcting data; another function would
receive all of these (+ any errors) and return the error-corrected
data.

Another question: How can I tell if the errors were corrected
successfully? It looks like I'd still need to calculate a CRC before
adding the error correction data.

Of course feel free to point out anything I might have missed.


Re: Forward error correction on 8 bit (8051/PIC/etc) CPU?
.lightspawn.removecolorname.org> writes
Quoted text here. Click to load it


use a more  resilient protocol. RS485, CAN etc,

Quoted text here. Click to load it

Yes.


IS this homework?

/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\
\/\/\/\/\ Chris Hills  Staffs  England    /\/\/\/\/\
/\/\/ snipped-for-privacy@phaedsys.org       www.phaedsys.org \/\/
\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/

Re: Forward error correction on 8 bit (8051/PIC/etc) CPU?
Quoted text here. Click to load it
CAN? Can't. The transmission is wireless.

Quoted text here. Click to load it
No, it's not. If you'd like to wait a week or two (presumably if it
had been a homework assignment it would have had to be handed in
earlier) or even until the end of the semester (whenever that is) I'd
still value any input then.


Re: Forward error correction on 8 bit (8051/PIC/etc) CPU?
On Tue, 18 May 2004 17:24:02 -0700, Chad

Quoted text here. Click to load it

Why didn't you state this in the first posting that the transmission
path is wireless ?

Since these errors usually occur in bursts, the data is usually
interleaved before transmission, the multipath fade takes out a burst
of bits. In the receiver, the deinterleaver converts the burst errors
to random errors that are then easily corrected by FEC.

The (de)interleaving process require that you have two full size
message buffers, so this may be an issue, if a processor with a very
small RAM is used.

Paul


Re: Forward error correction on 8 bit (8051/PIC/etc) CPU?
Quoted text here. Click to load it
I apologize. I did not realize the nature of the medium changes the
error distribution. You're right, interleaving makes perfect sense.



Re: Forward error correction on 8 bit (8051/PIC/etc) CPU?
Quoted text here. Click to load it

Of course it can.. We use wireless CAN networks. There are several
about.

Quoted text here. Click to load it

Since it is wireless and there are errors I would suggest that the
transmission system be looked at before you worry about error
correction.

/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\
\/\/\/\/\ Chris Hills  Staffs  England    /\/\/\/\/\
/\/\/ snipped-for-privacy@phaedsys.org       www.phaedsys.org \/\/
\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/

Re: Forward error correction on 8 bit (8051/PIC/etc) CPU?

Quoted text here. Click to load it

I suggest that you move the two systems that want to communicate with
each other somewhere halfway between the Earth and the Moon :-). There
are not going to be any multipath reflections and there are going to
be a nice line of sight path between the stations and the received
signal power is very predictable and stable.

However, if you are on the ground, either accept some errors or be
prepared to use 100 to 10000 times (20-40 dB) more transmitter power
than would be required to communicate in the average situation.

Paul
 

Re: Forward error correction on 8 bit (8051/PIC/etc) CPU?
Quoted text here. Click to load it
Have you identified the frequency of errors that you are seeing on the
"rather noisy" link? This will define what strength error correction you
need for reliable coummunication.

You might start by trying Hamming codes (Google is your friend) which for a
(7, 3) code allow you to correct a 1 bit error, detect a 2 bit error. This
doubles the amount of data that you have to send. Hamming codes are fairly
lightweight in terms of implementation (a lot of XORing) and so would be
straightforward on a PIC/8051. Other FEC schemes demand rather more work!

You should continue to calculate CRCs on the unencoded data.

A good book is Morelos-Zaragoza's "The Art of Error Correcting Coding":
nearly all the books require som mathematics I'm afraid - that is the nature
of the codes.

    Andrew



Re: Forward error correction on 8 bit (8051/PIC/etc) CPU?
Quoted text here. Click to load it
Sometimes I seem to be losing as much as 1 in 100 256-bit packets, so
a ballpark figure for the BER would be 1/25600.

Quoted text here. Click to load it
If I were to implement a byte-level solution, I'd probably use a table
instead of calculate the values through XORing. But this approach
seems to use more bandwidth than necessary, and two consecutive bit
errors still couldn't be corrected even though the rest of the packet
is correct (well, they could if they ended up in different nybbles).
Ideally I'd like to error-correct the packet as a whole. Can Hamming
codes be used to correct more than a single error?

Quoted text here. Click to load it
Which is why I asked about them... Do you mean programming work or CPU
work? The latter is far less flexible (work-wise) than the former.

Quoted text here. Click to load it
Thank you. I'll swing by the library tomorrow and see if I can pick it
up (or another book on the subject).


Re: Forward error correction on 8 bit (8051/PIC/etc) CPU?
Quoted text here. Click to load it
a
This
fairly
A straightforward Hamming implementation would correct 1 bit errors in each
nibble of the data packet. Hamming codes have been used in Teletext (Closed
Captioning). You could use (8/4) Hamming or (24/18) Hamming for a reduce
overhead and easy calculation.

Quoted text here. Click to load it
More programming and CPU. You might consider Reed-Solomon codes which have a
lower overhead than Hamming. A good web site (related to the book I
mentioned) is http://the-art-of-ecc.com .

    Andrew



Re: Forward error correction on 8 bit (8051/PIC/etc) CPU?
Quoted text here. Click to load it

  What about shifted left/right errors ?
You should analyse your error profiles, then choose a correction scheme
that works well on that.
  A very simple FEC system, is to send 8 bits, and index into a 4 bit
result table. One nibble is the recovered data, and the other nibble
can contain corrected / too corrupted / errorfree result flags.
-jg


Re: Forward error correction on 8 bit (8051/PIC/etc) CPU?
Quoted text here. Click to load it
Since the data packets are short and are preceded by a long sequence
of alternating bits, timing (erasures / repeats / shifts) is never an
issue.

Quoted text here. Click to load it

Agreed, but the cost (50% of the bandwidth) seems a little to
prohibitive. I'm hoping to "pay" no more than perhaps 10-20%.


Re: Forward error correction on 8 bit (8051/PIC/etc) CPU?

Quoted text here. Click to load it

The standard used for Teletext data broadcast is based on the Reed Solomon
FEC. If you do a Google for "Reed Solomon FEC" it will give you some
pointers as to how it works. In this particular scheme there is an array of
14 rows of 35 bytes and there are horizontal and vertical checksums. If a
burst of noise wipes out a whole row then it still can be corrected. The
additional checksums mean that the efficiency works out at 76% compared to
non error corrected data.

For the Teletext standard see EN 300 708 from www.etsi.org but only
mathematicians will understand it.

Hamming is much simpler and protects against bit errors in each byte but
works out at 50% efficiency and can't cure noise bursts that wipe out
complete bytes.
See http://www.ee.unb.ca/tervo/ee4253/hamming.htm for a simple explanation.

Peter




---
Outgoing mail is certified Virus Free.
Checked by AVG anti-virus system (http://www.grisoft.com ).
We've slightly trimmed the long signature. Click to see the full one.
Re: Forward error correction on 8 bit (8051/PIC/etc) CPU?
Quoted text here. Click to load it

You have to pick the algorithm depending on how much noise there is.

Quoted text here. Click to load it

Do you have enough RAM to buffer the packet including redundancy?  This
influences your choice of algorithm as well.

Quoted text here. Click to load it

Yes. If you exceed the error correction capability of the algorithm,
usually the is a margin where the algorithm can tell, but exceeding
that as well, you'll end up with erroneous packets.  For example, an
algorithm can detect 5 bit errors, and correct 3. If you have 6 or
more, the packet may or may not slip through.


The most simple block algorithm is to arrange the databits in a square
matrix.  Then calculate the parity for each line and each column.
Transmit data and parity bits.  The receiver arranges the data in the
same way, and re-calculates the parity bits.  Then it compares the
received parity bits against the calculated parity bits.  If none or
only one parity bit is different, there was no error.  If one "line"
and one "column" parity bit is different, there was a data error.
The erroneous parity bits show you which data bit (X, Y coordinate).
If there is more than one "line" or more than one "column" parity bit
different, there were errors but you cannot correct them.  Discard
the block.

More powerful yet simple is convolutional coding.  It works by
interleaving the data with parity bits (doubling the bandwidth).  It's
a channel coder with sliding window, and does not require you to store
a whole packet in memory.  By adjusting the window size, you can tune
it to be robust against your channels typical error profile.

If you have a lot of CPU time you can use Reed-Solomon coding, which
is very effective but requires more RAM.

Marc

Re: Forward error correction on 8 bit (8051/PIC/etc) CPU?
Quoted text here. Click to load it
Yes, I do (and if I'm wrong I can always find a CPU with more external
RAM).

Quoted text here. Click to load it
I actually managed to think this one up myself (especially since I'm
transmitting no more than 256 bits - 16 x 16) but discarded the idea
since only a single error could be detected.

Quoted text here. Click to load it

I hope I do - that's why I originally asked if an 8-bit system can
handle it. According to all this feedback (thanks, everybody)  it
seems it is possible.

Re: Forward error correction on 8 bit (8051/PIC/etc) CPU?
Quoted text here. Click to load it

Leave a blank line between your comments and the quoted material,
please.  It makes it much easier to tell them apart.  You should
also include attribution lines for whatever you quote.

Why don't you simply extend the idea.  Add an ECC syndrome to each
row and to each column.  With a burst error you can expect to get
multiple errors signalled in one or two rows (more is
uncorrectible).  Each column ECC check should show only one bit in
error (else uncorrectible), so repair those bits.  Now a repeat of
the horizontal calculation should show all errors corrected (else
uncorrectible).

If you break it up 16 x 16 you should be able to correct up to a
16 bit burst error.  However the matrix including ECC bits will be
21 x 21.  To handle longer bursts change the breakup, 32 bit burst
errors should be handled by 32 x 8, requiring a 38 x 12 matrix.

--
Chuck F ( snipped-for-privacy@yahoo.com) ( snipped-for-privacy@worldnet.att.net)
   Available for consulting/temporary embedded and systems.
We've slightly trimmed the long signature. Click to see the full one.
Re: Forward error correction on 8 bit (8051/PIC/etc) CPU?
On Tue, 18 May 2004 09:24:27 -0700, Chad

Quoted text here. Click to load it

I have used Hamming (and BCH) codes with good results even
with F8 processors (ummm, several years ago) and I don't think
there exists an 8-bit processor that has less computer power than
that.  I did gas pump totals in a (63,24) BCH code that corrected
up to 7 bit errors in each 24 data bits.  So almost 1/8 of the
transmitted bits could be bad (this did require your never-erased
feature, which I did have).  The expansion was more than 2:1,
but we needed the security.  I don't think we ever had an EEPROM
data failure (even when we were writing 10x the expected number
of write cycles in burn-in!).

I think they work well for small 8-bit systems since the computation
load is acceptable and the memory required is reasonable (I think
the BCH encoder and decoder shared only a dozen or two bytes
of RAM).

A primitive BCH code of length 255 correcting any 3 bit error would
be able to encode 231 data bits (<15% expansion).  If your error rate
were low enough, that should work well.

The books I am familiar with are pretty heavy on the math:

Peterson & Weldon: "Error-correcting Codes" (I have 2nd Ed from 1972)
Adamek: "Foundations of Coding" (mine is the 1991 edition)

But I have seen "Error Coding Cookbook" by C. Britton Rorabaugh
(1995 or later, I think).  It is a bit more of a cookbook (suprise!)
but it still has some serious math in it....

Quoted text here. Click to load it

I believe Rorabaugh's book comes with a diskette containing
some code libraries for at least some of the code systems.

Quoted text here. Click to load it

The standard Hamming code used in ECC memory detects two
bit errors and corrects one bit errors, so if you assume the chances
of a 3-bit error in a 72-bit word is inconsequential, it does not
require any further checks.  If not, then a CRC or something
equivalent would be needed.

Quoted text here. Click to load it

[I've never been good at that....]

--Charles

Re: Forward error correction on 8 bit (8051/PIC/etc) CPU?


Quoted text here. Click to load it

(Guy runs out of the building screaming in hooror over the
mention of The Processor That Shall Never Be Mentioned...)


Site Timeline