4

I have been looking into using LDPC's in some of my projects and have had some questions come up. Currently my structure looks something like this:

Message

I am then able to have hardware wake when it sees the preamble, read the length byte, and even check CRC for me before my processor has to handle the packet at all. This takes a lot of load off of processing time as well as code writing time.

What I am wondering is if there is any hardware out there that can use LDPC or any other correction code in a similar manner to what I am currently doing. Preferably it would be included with the wireless module, especially if it is able to do some soft decoding, but I am starting to think there isn't anything out there that does that currently. Because of this I am also open to "in-line" hardware that can assist with this.

So, know of anything?

Kellenjb
  • 17,509
  • 5
  • 51
  • 87

2 Answers2

1

What is the physical representation of bits being sent? In many cases, intra-packet error-correcting codes will be useless because even a transient glitch will cause many bits to be misinterpreted--quite possibly all bits until the next synchronization mark.

If forward error correction is needed, and packets are of uniform size, the simplest approach may be to send n packets worth of data using n+1 packets--each labeled with a packet number--where the (n+1)th packet contains the xor of the other ones. If the first n packets are read successfully, ignore the extra one. Otherwise, if one packet is missing or corrupted, infer its value by xor'ing the remaining n packets together.

A slight improvement of this approach would be to send 2n packets worth of data using 2n+2 packets, interleaving two sets of n+1 packets, each set being formulated as above. That would guarantee recovery from any single communications glitch which was no longer than the time required to send a single packet (a short glitch might hit the end of one packet and the start of the next, but the two packets would be in different xor-groups).

The biggest limitation with this approach is that packets must be assembled into groups (or, putting it another way, what could otherwise be larger packets must be subdivided into smaller ones). On the other hand, it is robust against glitches that would cause synchronization loss render large amounts of data unreadable.

supercat
  • 45,939
  • 2
  • 84
  • 143
  • QPSK is what I would prefer, but currently using a form of FM. It sounds like you are explaining a simplified form of Raptor/fountain codes. I am more concerned about noise causing the demodulator to flip the bit even though it still has a lock. – Kellenjb Apr 25 '11 at 18:54
  • How does the likelihood of having a single bit flip without affecting any other bits compare with the likelihood of having a noise glitch cause a synchronization problem or otherwise distort many bits? There are some data-transmission systems which can do a good job of maintaining sync in the presence of noise, but even with those a glitch which affects one bit is far more likely to affect neighboring bits as well than arbitrary other bits. Design of any good scheme will require an understanding of the relative probabilities of different types of errors. – supercat Apr 25 '11 at 21:37
  • 1
    From real life test data that I have seen a single bit flip is pretty common. – Kellenjb Apr 25 '11 at 21:59
  • If single-bit flips are common, it might be useful to do error correction in hardware, but it's apt to be resource-intensive. Unless you need to be able to identify "interesting-looking" packets in the presence of errors, and can't afford to bother the CPU with packets that shouldn't be considered "interesting", it may be better to do error-correction in software. BTW, would it be possible to have the receiver produce a "quality" indicator for each bit (e.g. characterize each bit as "definite zero", "definite one", "probable zero", or "probable one")? Such info may be tricky... – supercat Apr 25 '11 at 22:10
  • ...for a hardware ECC to use most effectively, but could be very useful for a software ECC (e.g. the latter could decide that a triple-bit error on three bits that were marked as "probable zero" was more likely than a single-bit error on a bit marked as "definite one", but such logic would be difficult to implement in hardware. – supercat Apr 25 '11 at 22:12
  • 1
    That is what my question is about, is if there is hardware out there that handles all of that for me. Even if it is really software on the device, I just would like it to be off of my processor. – Kellenjb Apr 25 '11 at 23:07
  • 1
    I am not aware of any hardware to do such things as a general solution. It may exist in certain specialized communications IC's, and hardware ECC certainly exists within things like memory chips and memory controllers, but in general the type of ECC that's suitable for a particular application will be highly application-specific, and except for things like high-bandwidth memories I think that letting the processor handle the ECC is often the best approach. – supercat Apr 25 '11 at 23:10
0

All the early error detection and error correction codes, both encoders and decoders/detectors, were originally designed to be implemented in hardware, rather than software -- CRC, error-correcting convolutional code and their trellis decoder (Viterbi decoder), BCH code, Reed–Solomon error correction code, etc.

In particular, hardware implementations of a CRC are much simpler and often faster than table-driven software CRC implementations of the same CRC -- it takes only a handful of 74xxx-series chips to implement, rather than a few pages of code (well, a few lines of executable code, plus a few pages of pre-calculated constants).

All the ECC implementations I've seen are in one of these categories; it sounds like the first category is closest to what you want:

  • ECC decoding in software in an external co-processor that talks to the main processor: this approach seems to have the quickest development time. Many radio transceivers include such a co-processor that can be programmed to handle the ECC decoding -- radio transceivers; " Low power radio + microcontroller recommendation? "; such as Jennic wireless modules; etc.

  • a handful of 74xxx-series chips: historically accurate, and very educational, but CPU and memory costs have plummeted such that other approaches are lower-cost or faster or both. a b c

  • FPGA: at high data rates, such as when handling uncompressed video, you are pretty much forced into using a FPGA. Often a small part of the FPGA handles the FEC stuff; most of the FGPA deals with video encoding/decoding. a b c

  • ECC decoding in the main processor.

  • I hear rumors of Viterbi/trellis decoder chips. Are there any that not obsolete? a b c d e

Community
  • 1
davidcary
  • 17,426
  • 11
  • 66
  • 115