# Determining parity or FEC (Forward Error Correction) requirements from percent error

I am very new to signal processing and my background is in physics. I would like to know if it is possible to determine the number of parity bits needs to theoretically get 100% transmission from a transmission channel with known percent error. Over a given transmission 25-30% of the transmission is incorrect. This 25-30% represent the symbol error rate. I am using a 8 level amplitude modulation scheme.

Is it possible to know with say a Reed-Solomon technique how many parity bits I would need to add to each block to move in the neighborhood of 100%?

I am processing my signal using MATLAB right now. I am not sure if the EE stack exchange is the proper location for this. If it is off topic I will close the question but I thought you all might have some knowledge in this area.

EDIT

I have been asking around and reading more and it looks like I could over come a great deal of error by using a RS code with a msg of 3 symbols and 6 parity symbols. Is this correct?

• FYI, There is also a DSP StackExchange. But they do like their MathJax over there. – The Photon Aug 21 '12 at 19:31

A BER of 25-30% implies that you have only about a 5-10% chance of receiving an error-free byte. This is way beyond the capability of any practical Reed-Solomon based FEC system. You need to look at convolutional coding -- FEC at the bit level -- using something like Viterbi decoding on the receive side.

To answer your original question, the probability of finding exactly k errors in a block of n symbols, given a symbol error rate of p, is:

C(n,k)×pk×(1-p)n-k

where C(n,k) is the binomial coefficient: C(n,k) = n!/(k!×(n-k)!)

To find the probability of having m or fewer errors, you need to add up the individual values for k = 0...m. Then, the probability of having an uncorrectable block (more than m errors) is 1 minus this sum.

• I should make this change that it is a SYMBOL error rate of 25-30% not BER. I am using an 8 level Amplitude modulation scheme. I need to edit my original question – Matthew Kemnetz Aug 21 '12 at 19:34
• Nonetheless, that's still a very high error rate for a Reed-Solomon system. Keep in mind that R-S requires two check symbols for each erroneous symbol in any given block of data. I did a fairly extensive writeup of this topic for Circuit Cellar's "Engineering Quotient" quiz back in 2001, but unfortunately, it's no longer available online. The answer strongly depends on the residual uncorrectable block error rate you can tolerate. – Dave Tweed Aug 21 '12 at 19:57
• For your specific example of 3 data symbols and 6 check symbols per block, with a symbol error rate of 30%, you'd still have a 37% chance of having 4 or more errors in any given 9-symbol block, making the entire block uncorrectable. – Dave Tweed Aug 21 '12 at 20:17
• With a symbol error rate of 25%, this improves to having just a 7% chance of an uncorrectable block, which shows that you just barely have a workable system at these error rates. – Dave Tweed Aug 21 '12 at 20:24

Error percentages are typically expressed as independent probabilities, meaning that if there are e.g. four bits which have a 1/3 error rate, there would be a 16/81 probability of no errors, a 32/81 probability of exactly one, a 24/81 probability of exactly two, an 8/81 probability of exactly three, and a 1/81 probability of all four bits being wrong. If the independent bit-error rate is non-zero, there is no way to have guarantee that incorrect data won't be delivered. The best one can do is achieve a certain probability of correct delivery, and given a 25% random error rate on a significant-sized payload one would need to have a really massive amount of overhead to achieve even a 90% probability of successful delivery.

In many real-world situations, however, errors will be strongly correlated. For example, the probability that a group of 64 consecutive bits in a packet might get replaced with random data could be much higher than the probability of having even four erroneous bits spread throughout the packet. It may be possible to deal much more effectively with strongly-correlated errors than with non-correlated errors. For example, if one wants to deliver 8192 bytes, one might divide them into groups of 16 bytes, each with a 16-bit CRC. Groups would be sent in pairs, with one being called 'even' and one being 'odd'. Attached to each meta-group of 16 pairs of groups would be an extra pair of groups, which represented the XOR of the data in the first 16 pairs (storing separately an 'even-group-XOR-group' and an 'odd-group-XOR-group'), and a 32-bit CRC. Attached to the payload would be an extra 'meta-group', whose data was the XOR of the previous 16 meta-groups, plus some larger validation check value (e.g. an MD5 hash)

If a single burst error occurs which is less than 16 bytes in length, it would at most splatter at most one even group and one odd group within a meta-group. Such corruption would likely be detected and could be corrected by taking the xor of the non-corrupted groups and the appropriate group-xor group. There would be a slight probability that the corruption might not be detected at that level, but the CRC32 of the meta group would fail. In that scenario, the receiver could check whether rejecting each group in sequence (reconstructing its data using the xor group) would yield a valid meta-group. If not, or if more than one even group or more than one odd group within a meta-group is corrupted, the code could discard the meta-group and reconstruct it using the xor-of-metagroups data. The correctness of the reconstruction could be assured using the overall-data validity check.

Note that this approach can work very well in protecting against isolated burst errors, and one may easily adjust the number of levels of hierarchy or the size of the various nested groups as needed for the application. The approach is not optimal for dealing with isolated random errors, but as noted a 25% random error rate is going to be very hard to deal with in any case.