I'm looking for a kind of error correction code or solution that can correct my codeword in this case:

My message holds $k$ bits, and $2k$ bits codeword (rate is $1/2$) is produced by the generator matrix, e.g. $k=5$, so it yields $10$ bits codeword $\rm 1001100111$. If the codeword is erased for some reason and it becomes $\rm 1xx1x00xx1$ (similar to the codeword transmitted through Binary Erasure Channel, and $\rm x$ is unknown, either '$0$' or '$1$'), can I still correct all the "$\rm x$ bits" in such situation as bit error rate is $1/2$?

I have read about some error correction code, such as block code, convolutional code and LDPC and got the following questions:

  1. All these ECC have pratical application in communication, so do they still work when BER is close to $1/2$ (I think BER is impossible so high)?

  2. Are there any feasible solution to my case? In fact, my message is $30$ bits and I can introduce another $30$ bits redundancy as parity bits. Can I still correct my codeword even if its half bits are erased where the recipient knows which bits he didn't receive properly?

  3. What's the limit of ECC? If it can't correct half bits of codeword that are erased, how many bits can it correct at most?

Any guides or suggestions are appreciated!

  • $\begingroup$ Are all of your $2k$-bit blocks expected to have such a high level of erasures? You might be able to achieve improvements by interleaving over multiple $2k$-bit blocks so that the erasures are spread across multiple codewords. $\endgroup$ – Jason R Mar 27 '13 at 17:13

I'm afraid that this will be an incomplete answer, but I'm giving it in the hopes that it is better than nothing.

It is impossible to recover any information with a BER of 50% because, as information theory tells us, no information is getting through such a channel. You can see this intuitively if you realize that no matter what bit you send, 0 or 1, it has equal chance of arriving at the receiver as a 0 or 1, so what you receive tells you nothing about what was actually sent. In such a case it is theoretically impossible to create an ECC that will help at all.

Erasures are, in some situations, better than errors though. Reed-Solomon decoders often use erasures to increase their error correction capability. The reason why it works is because with RS codes you have two sets of unknowns: the error locations and the error magnitudes (the number of errors is also an implicit unknown). Erasures give the decoder the error location so it only needs to figure out the magnitude.

Talking about "erasures" in the context of bits, though, makes little sense because with bit-based codes there is only one set of unknowns: the error locations. The error magnitudes are always 1. So if you have a bit "erasure" you are trading one unknown (error location) for another (error magnitude).

With bit-based codes like Viterbi codes the analog to erasures is using soft-decisions. Soft-decisions contain "confidence" information- i.e. how sure the receiver is that the bit is really a 1 or really a 0. That information can be used to greatly improve decoder performance.

All that being said, though, if your error/erasure rate is really that high you will probably not get good performance out of any ECC.

  • $\begingroup$ Thanks Jim. Could you ask my Question 3? I want to know if ECC is just helpful when correcting minority errors of a codeword, maybe 1 out of 10, 1 out of 100? $\endgroup$ – WangYudong Mar 27 '13 at 23:56
  • 1
    $\begingroup$ The amount of errors that a code can fix varies by type of code and the amount of parity, but yes, there are lots of codes that can correct 1/10 or 1/100 BER. If you're not worried about computational load Turbo codes and LDPC codes are the best known codes. $\endgroup$ – Jim Clay Mar 28 '13 at 1:28

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.