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

In article , Chad writes

use a more resilient protocol. RS485, CAN etc,

Yes.

IS this homework?

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

\/\/ \/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/

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

CAN? Can't. The transmission is wireless.

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.

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

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.

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?

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.

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

Since the data packets are short and are preceded by a long sequence of alternating bits, timing (erasures / repeats / shifts) is never an issue.

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

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

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.

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

Andrew

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

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

for a simple explanation.

Peter

--
Outgoing mail is certified Virus Free.
Checked by AVG anti-virus system (http://www.grisoft.com).
Version: 6.0.659 / Virus Database: 423 - Release Date: 15/04/04

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

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

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

I apologize. I did not realize the nature of the medium changes the error distribution. You're right, interleaving makes perfect sense.

Yes, I do (and if I'm wrong I can always find a CPU with more external RAM).

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.

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.

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 (cbfalconer@yahoo.com) (cbfalconer@worldnet.att.net)
   Available for consulting/temporary embedded and systems.
     USE worldnet address!

In article , Paul Keinanen writes

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

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

\/\/ \/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/

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

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 (Source code would be great, in any language, as long as it does not

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

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.

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

--Charles

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