1
$\begingroup$

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.

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

I am processing my signal using MATLAB right now...

$\endgroup$
5
  • $\begingroup$ As a semantic issue, and to calibrate expectations, coding theory will only predicts 100% transmission success (as Shannon put it, "reliable communication") in the limit where the coding block size $\to \infty$ (and as long as you have SNR above the Shannon limit). There will still be a nonzero probability of error for any real decoder. For hard-decision decoders, you typically speak of a certain number of correctable bits/symbols per block. Soft-decision decoders are better characterized via their coding gain; the improvement in error rate performance when measured in $\frac{E_b}{N_0}$. $\endgroup$ – Jason R Aug 21 '12 at 15:43
  • $\begingroup$ @JasonR I was thinking that I could never get to 100% but thank you for clarifying the conditions around why I can't. I am pretty sure RS is hard-decision (but please correct me if you think I am wrong). Do you know given a msg length of k bits and a block size of N bits how to determine the correctable symbols/block? This may be a Reed-Solomon question now but I am open to any method of FEC. RS is just what I have read the most about. $\endgroup$ – Matthew Kemnetz Aug 21 '12 at 15:50
  • $\begingroup$ @JasonR I specifically know that 1/3 symbols will be wrong leading to the ~30% error above...I don't know if that helps. $\endgroup$ – Matthew Kemnetz Aug 21 '12 at 15:53
  • 1
    $\begingroup$ Exactly what is meant by "100% transmission from a transmission channel"? Perfectly reliable transmission (that is, with error probability $0$)? If so, no coding technique will work: perfect reliability is impossible. A Reed-Solomon code with $2t$ parity symbols and $k$ data symbols (of $m$ bits each) can correct $t$ symbol errors (that is, as many as $mt$ bit errors if all the bits in the $t$ incorrect symbols got flipped), but will fail to correct as few as $t+1$ bit errors if the errors are in different symbols. $\endgroup$ – Dilip Sarwate Aug 21 '12 at 19:10
  • $\begingroup$ I see that you've added some details of your system below, indicating that it is an 8-level ASK scheme. You might be better served by asking some higher-level system design questions. What is your expected SNR (more specifically, $\frac{E_b}{N_0}$ at the receiver? The best way to objectively compare different system designs is by comparing their bit error rate versus $\frac{E_b}{N_0}$. You must be careful to actually calculate the correct value for $E_b$ when doing so. It is defined as the "energy per received information bit". $\endgroup$ – Jason R Aug 22 '12 at 1:06
2
$\begingroup$

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

Normally yes, if you know that you will never have more than $e$ bit errors in a block of length $N$, then you could design a RS code that would fix them all. The problem in your case is that 30% bit errors is a LOT of errors. Assuming the errors are randomly distributed, no RS code will be able to fix that many errors. The number of parity symbols you would need would exceed $N$.

The analysis goes as follows- RS codes work on symbols, not bits. All of the RS codes that I have seen have symbol widths of 6 to 9 bits, with the most common symbol width being 8 (CD's use an 8-bit wide RS code). At 30% bit errors, well over half of the symbols will have errors. You need two parity symbols for each error that you want to correct, so when over half of the symbols have errors it is impossible to correct them.

You may think "why not make the symbols narrower, reducing the chance that they will contain a bit error?" The problem is that the block length, $N$, is $2^m-1$, where $m$ is the RS symbol width. If you reduce the symbol width to 1, then your block length is 1 and you can't correct any data. Thus, no RS code can correct your errors.

I would say that your best bet is a low-rate Turbo code, though turbo codes cannot guarantee that they will fix your errors.

$\endgroup$
11
  • $\begingroup$ could you possibly explain your second paragraph a little more on how it is impossible for a RS code to correct my errors? I thought in RS I could add an arbitrary number of parity symbols. So could I have say 3 msg symbols and 6 parity symbols? I apologize for my ignorance on the subject ahead of time as I am new to this subject. $\endgroup$ – Matthew Kemnetz Aug 21 '12 at 17:27
  • $\begingroup$ do you know about LDPC as a FEC method? Would that be a better option? $\endgroup$ – Matthew Kemnetz Aug 21 '12 at 17:28
  • $\begingroup$ in the end though my time might be best spent improving the quality of the channel than working with this much noise... $\endgroup$ – Matthew Kemnetz Aug 21 '12 at 17:37
  • $\begingroup$ @MatthewKemnetz Yes, you can have 3 msg symbols and 6 parity symbols, which would be capable of correcting 3 symbol errors. The problem is that with a 30% bit error rate most of the time you will have more than three symbol errors. The chance of a symbol not having an error, in your case, is $0.7^m$, where $m$ is the symbol width. $\endgroup$ – Jim Clay Aug 21 '12 at 17:55
  • $\begingroup$ @MatthewKemnetz I know of LDPC codes, but I don't know enough about them to know if they are a better option or not. I recommended a Turbo code because it is my understanding that the state of the art is to use Turbo codes for low-rate codes, and LDPC codes for high-rate codes. With 30% bit errors, you will need a low-rate code. And yes, I absolutely agree that improving your link margins to improve the bit error rate that you start out with is crucial. $\endgroup$ – Jim Clay Aug 21 '12 at 17:58

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.