FEC - Forward Error Correction on a PIC?

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

Translate This Thread From English to

Threaded View
Would a PIC be a suitable device for converting Asynchronous RS232 in to a
FEC encoded bitstream, and at the other end, take the dodgy bitstream, error
correct it and convert it back to rs232?

Thanks in advance

Marky C



Re: FEC - Forward Error Correction on a PIC?
Quoted text here. Click to load it

That depends largely on the data rate, the maximum error burst length you
want to correct, and how much (if any) interleave you want.

It's certainly possible to code some FEC algorithms for the PIC.  At one
time I wrote a Reed-Solomon encoder, but I haven't written a decoder.
(The code belongs to a client so don't bother asking me for it.)

If you're only expecting an occasional single-bit error, you could use
a simple Hamming code, but if you do that on individual bytes it will
increase the necessary channel data rate by 50%.

It's also possible to correct single-bit errors in blocks of data using
a normal CRC.  For instance, if you have a block of less than 8 Kbytes,
you can correct a single bit error using CRC-16, but you will not
necessarily be able to detect mulit-bit errors.

Re: FEC - Forward Error Correction on a PIC?

Quoted text here. Click to load it
a
error


Thanks for the reply.

My data rate is low at  1200bps, and the majority of the errors are single
bit.  I come from the software side of life and therefore the PIC
capabilities are the mystery.  My data originates as rs232 8n1, which is
hugely suseptable to cataclysmic failure when a single bit error hits one of
the start or stop bits.  Synchronisation at the rx UART is lost for 1, 2 or
3 chars depending on how it feels.

So thats my problem, a single bit error is causing me to loose 16 or more.
I wondered if a PIC could be used to takes the rs232, convert it to a
bitstream, tx it and correct the errors before presenting it to the UART.

I feel that correcting the odd bit is a lot easier that chuncks of my data
going missing.

Does this still sound like a problem for a PIC.  Is it possible for rxing
PIC to synchronise its clock in line with the incoming bitstream so that
individual bits can be gleaned from the stream?

Thanks again
Marky C



Re: FEC - Forward Error Correction on a PIC?
Quoted text here. Click to load it
... snip ...
Quoted text here. Click to load it

If you are having problems with start/stop bits, I would think
that sending with two stop bits, and receiving with one, would
ensure good syncs and immunize against most data rate mismatches.
If problems still show up I would examine the UART start bit
detection routines.  After that you might be able to use 8 bits +
parity, together with a block parity byte, for a simple one bit
error correction method.

At 1200 bps you must have an incredibly noisy link to have serious
difficulties.

--
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: FEC - Forward Error Correction on a PIC?
Snip
Quoted text here. Click to load it
of
or
Snip
The other possibility is to look for a FEC that can hande a burst error of
24 bits.

Wim




Re: FEC - Forward Error Correction on a PIC?
Quoted text here. Click to load it

The problem is not with FEC, it's the UART synchronization.  Say the
2nd byte of a 100 byte packet is 0xFF, and the start bit is missed due
to a single bit error.  You will miss the whole byte, and thus all
remaining 98 bytes will be mis-aligned by 1 byte.  These are 784 error
bits, caused by one single bit error.  You might even take the next
packet's first byte for the last one of the earlier packet, and carry
the error over to the next packet as well.

The only reliable way around this problem is to not use an UART.  Use
a synchronization frame instead (eg a pseudorandom "magic" token,
possibly with a 01010101 preamble for the analog->digital treshold
comparator).    Compare the incoming data with the token, using XOR
and accept the same number of biterrors per incoming bits, as the
FEC.  Then there remains no weak point, every bit is equally
vulnerable (both in "start" and "data" section of the telegram).
Either the complete packet goes through, or nothing.


Marc

Re: FEC - Forward Error Correction on a PIC?
Hi

First have a look at the hardware setup. Perhaps a simple switch to
RS422 with twisted pair wiring and balanced signalling will solve the
signal integrity if you're not already using that. Otherwise I suggest
you take a look at short haul modems(google for it). Even if your
product cost or other reasons may not allow you to buy modems off the
shelf, the signalling techiques used are probably valuable. Use a
simple FSK or PSK encoding together with a short trellis
encoder/decoder such as Viterbi. This is definitely possible to
implement on a small PIC or AVR for both Tx and Rx.

/Pr

Re: FEC - Forward Error Correction on a PIC?
Quoted text here. Click to load it

In the past I did precisely that with an AT90S2313 AVR.

Re: FEC - Forward Error Correction on a PIC?
Quoted text here. Click to load it


I don't suppose you would share?

Marky C



Re: FEC - Forward Error Correction on a PIC?
Quoted text here. Click to load it

It's difficult to talk to you, given the email " snipped-for-privacy@a.a"

Re: FEC - Forward Error Correction on a PIC?
On Wed, 22 Oct 2003 08:16:38 +0000 (UTC), "MarkyC"


Quoted text here. Click to load it

I think that you are trying to solve the wrong sort of problem.

The first thing is to make a good physical connection between the end
points and my guess is that after that there is no need for any
elaborate FEC systems. Some CRC may be needed to detect some random
errors perhaps once a day or once a week.

The RS-232 standard was originally designed for low speed connections
between a computer and a modem in the same room. Using it for long
distance or high speed connections is just asking for troubles.

One of the worst things about RS-232 is that it is unbalanced (i.e.
the signal is referenced to signal ground) but if there is a galvanic
connection between the ends and due to quite large ground potential
differences between the ends, a large ground loop current may flow in
the signal ground, causing all kinds of troubles, especially, if the
link ends are in different buildings.

One way around this is using optoisolators at least at one end. This
will break the ground loop current.

However, if optoisolation is required and the speeds are quite low, as
in this case, it would be even simpler to use the traditional 20 mA
current loop system. I have used such systems at 9600 bit/s in a
system with slip rings and with 220 V 10 A mains in adjacent rings.
This required some hacking in the protocol retransmission system to
avoid backlogs when one data transmission direction was temporarily
off due to dirty rings and some arching in the mains rings. Normally
20 mA systems work very well in less demanding applications.

A more modern system is to use the differential RS-422
connection,which works reliably even on high speeds, but again,
galvanic isolation is preferred and thus, you have to be careful about
cable shield grounding (usually only at one end).

With speeds as low as 1200 bit/s you should be able to communicate for
a kilometer or more.  

It is quite hard for me to think about a situation in a wired slow
speed connection in which FEC is needed.

The situation is radically different if a radio link is involved, in
which case some interleaving and FEC is justified in most cases, but I
haven't seen any references to radio links in this thread.

Paul
  

Re: FEC - Forward Error Correction on a PIC?


<snip>

Quoted text here. Click to load it


I am so sorry to have not mentioned this earlier.  It is indeed for use over
a radio.

I have made a modem which takes rs232, converts it to analogue tones and
squirts it in to a transmitter.  "jetmarc" has hit the nail on the head.  I
loose only the bit here or there but the use of start & stop bits leaves me
open to difficulty.  That is why I would like to convert the framed
asynchronous data  with its vulnerabilities to a synchronous one without the
start & stop bits.  Once I have my hands on a continuous bitstream I can add
fec easily (I guess).  It also has the added benefit of removing the 20% of
my air time that is taken up with start & stop bits.




Re: FEC - Forward Error Correction on a PIC?
On Thu, 30 Oct 2003 09:59:37 +0000 (UTC), "MarkyC"


Quoted text here. Click to load it

Yes indeed, since quite a few people would have been able to pinpoint
the problems with asynchronous characters immediately.  

Quoted text here. Click to load it

In radio systems, the bandwidth is always limited and thus the rise
and fall times are quite long. With some noise added to the signal and
a level sensitive triggering will make detecting the start bit timing
quite vulnerable and the sampling times for the rest of the bits can
be quite far away from the nominal point, at which point the slope to
the next state might have already started.
 
Quoted text here. Click to load it

A suitable preamble in front of a frame can be used in obtain exact
bit timing, since the random noise errors can be averaged out during
the preamble, thus the sampling times of the actual data bits hit
close to the centre of bit, reducing the risk for bit errors.
  
Quoted text here. Click to load it

Radio amateurs have used the AX.25 protocol in packet radio for two
decades. The protocol is a variant of the SDLC/HDLC protocol with
start/end flags (7E) and bit stuffing to avoid the flag sequence in
actual data.

Quite a few systems at 1200 bit/s have been implemented with bit
banging in old PC:s running MS-DOS and controlling an external FSK
modem chip. The Baycom implementation used the PC serial port control
signal pins (e.g. RTS/CTS) and the PMP (Poor Man's Packet) the
parallel port pins for reception and transmission. The source was
available at least for the PMP implementation. The PIC should be able
to handle the bit banging as well.

The AX.25 is just using the CRC and relies on retransmissions if
errors occur. This might be sufficient in your case, especially if the
errors are truly single bit errors, with at most a single bit error in
each frame, this might even be correctable as described in this
thread.

However, in radio communication, burst errors are more likely in
ground based systems, taking out multiple adjacent bits. Simply adding
FEC bits into the frame does not help, since too much related
information is missing. The message needs to be interleaved all over
the frame at transmission and if a burst error takes out some bits,
after deinterleaving, the bit errors are converted to random bit
errors all over the frame,which is then easily correctable using FEC.
  
Quoted text here. Click to load it

The frame header, bit stuffing, preamble, CRC and possible FEC can
easily consume any gain that you might get, so you would still be able
to transfer only 120 net data bytes each second in the best case.

Paul


Re: FEC - Forward Error Correction on a PIC?
Quoted text here. Click to load it


A CRC doesn't correct bit errors, it merely detects them.
A CRC error then causes a retransmit of the packet.

Rene
--
Ing.Buero R.Tschaggelar - http://www.ibrtses.com
& commercial newsgroups - http://www.talkto.net


Re: FEC - Forward Error Correction on a PIC?

Quoted text here. Click to load it


With sufficient computational power (or low transmission speeds), if
the CRC does not match, you could always try and invert a single bit
in the message and recalculate the CRC. If the CRC does not match, try
to invert some other bit and repeat the CRC calculation and so on.  If
the message size is 1kB, the CRC has to be calculated 8000 times.

If the CRC match with only one permutation, you have the most likely
have the correct combination. If no combination match, there are more
than a single bit error. However, if more than one combination match,
you have the problem of selecting the most likely.

This approach is realistic, if you have a quite low bit error rate
(BER) and the cost of retransmission is huge (especially in space
communication, in which the delay can be hours).

Paul
  

Re: FEC - Forward Error Correction on a PIC?

Quoted text here. Click to load it

I don't doubt it is possible.

How many bit faults would a larger hash, like SHA-1 or MD5 be able to
'correct'?

Anyway, why would you want to, when there are much better error
correcting codes that need no brute force approach.

Wumpus


Re: FEC - Forward Error Correction on a PIC?
Quoted text here. Click to load it



There are *much* more efficient ways for this to be done.  Assuming that
there is only a single-bit error, if you XOR the received CRC with the
locally computed one to produce a syndrome value.  The syndrome uniquely
identifies the bit position in error.  One approach is to have a table
mapping the XOR result to the offset and bit number of the error, but
this burns a lot of memory in the case of CRC-16.

There are slightly more complex approaches that do involve iteratively
searching for the correction, but do not require recalculating the CRC
over the entire block for each iteration.  The basic idea is that you
can trivially compute the CRC of a block with the first bit of the first
byte set, and all other bits clear.  If that doesn't match the syndrome,
you can run one iteration of the CRC algorithm to get the CRC of a block
that would have only the second bit of the first byte set.  And so on.
At most, this requires as much computation as doing a bit-serial
CRC calculation of the data block.

Note that these approaches are also sometimes used with other cyclic
error correction codes; there's nothing too special about CRC in this
regard.  But by exploiting the mathematical properties of a particular
error correction code, it is often possible to come up with more
efficient correction algorithms.

Eric

Re: FEC - Forward Error Correction on a PIC?
On Wed, 22 Oct 2003 16:25:43 GMT, in msg

Quoted text here. Click to load it

I know Eric well enough to know it would be unlikely for him to make this kind
of error in his post, a quick google search on "CRC error correction" turned
this up as the second hit:

http://www.cuj.com/documents/s82%35/cuj0306mcdaniel /

-Zonn
--------------------------------------------------------
Zonn Moore
Zektor, LLC
www.zektor.com

Remove the ".AOL" from the email address to reply.

Re: FEC - Forward Error Correction on a PIC?
Quoted text here. Click to load it


A CRC *can* be used to correct errors.  It just normally isn't done that
way.

Quoted text here. Click to load it

That's typical, but it's certainly not required by anything in the
fundamental nature of the CRC.

Re: FEC - Forward Error Correction on a PIC?
Hi Rene!
You should read textbooks before posting nonsense! Sorry, it's almost
completely false what you said.
- Henry

Rene Tschaggelar schrieb in Nachricht
Quoted text here. Click to load it
a
error



Site Timeline